Malbolge

Malbolge (назван в честь восьмого круга ада “Божественной комедии” Данте, предназначенного для обманщиков) — эзотерический язык программирования.

Язык был придуман Беном Олмстедом (Ben Olmstead) в 1998 году. Автор задался целью максимально усложнить процесс написания программ на этом языке. Это ему вполне удалось: программа “Hello, World!” была написана только через два года после публикации спецификации языка, в 2000 году, и до сих пор не существует принципиально более сложных программ. Более того, она была написана не вручную; для ее поиска потребовалось написать эвристическую программу на Lisp. В 2004 был написан универсальный генератор программ, выводящих нужную строку.

Значительный вклад в развитие языка был сделан Лу Шеффером (Lou Scheffer), который сохранил оригинальные интерпретатор и документацию языка, а также провел фундаментальную работу по криптоанализу языка, написал программу, копирующую свой ввод в вывод, и привел рекомендации по написанию программ на Malbolge и примерное доказательство Тьюринг-полноты языка. Стандартом языка считается его оригинальный интерпретатор; в случае расхождений спецификации и интерпретатора (например, в том, какие команды выполняют ввод/вывод данных) правильным считается последний.

Виртуальная машина Malbolge работает в троичной системе счисления. Машинное слово имеет размер 10 тритов (троичных цифр), т.е. может хранить беззнаковые целые числа от 0 до 59048, включительно. Код и данные хранятся в одном и том же одномерном сегменте памяти, состоящем из 59049 ячеек памяти. Кроме того, в машине есть три регистра размером одно слово каждый: A (аккумулятор, используется для манипуляций с данными, а также для ввода-вывода), C (указатель инструкций, указывает на текущую выполняемую команду) и D (указатель данных). Изначально все регистры содержат значение 0.

Перед выполнением программы интерпретатор загружает ее в память целиком, по одной команде на ячейку памяти. Если в программе есть символ, который невозможно интерпретировать как команду (см. далее) или как пустой символ, интерпретатор отвергает программу в целом. Ячейки памяти, оставшиеся неинициализированными, заполняются результатом выполнения операции crazy над двумя предыдущими ячейками.

Процесс интерпретации одной команды выглядит следущим образом. Обозначим ASCII-код текущей команды как [C] (т.е. значение, хранящееся в ячейке памяти, на которую указывает регистр C). Если [C] не входит в диапазон от 33 до 126, включительно, команда считается некорректной. В противном случае вычисляется значение (C + [C]) mod 94, которое затем используется в качестве индекса в таблице перекодировки. Если результатом перекодировки не является одна из следующих команд, команда считается некорректной.

• j D = [D] Сдвигает указатель данных в ячейку, на которую указывало его прошлое значение
• i C = [C] Сдвигает указатель инструкций в ячейку, на которую указывало его прошлое значение
• * A = [D] = ROTATE([D]) Циклически сдвигает значение в ячейке, на которую указывает D, на один трит вправо. Попутно это значение записывается в A.
• p A = [D] = CRAZY(A, [D]) Применяет операцию crazy к значению регистра A и ячейки, на которую указывает D.
• / A = INPUT Читает один символ из потока ввода и сохраняет его в A.
• < PRINT A Выводит на печать символ с ASCII-кодом A mod 256.
• v STOP Завершить выполнение программы.
• o NOP Команда, которая не делает ничего (единственная допустимая).

Операция crazy выполняется над соответствующими тритами аргументов по следующему правилу:

        | A trit:  
________|_0__1__2_  
      0 | 1  0  0  
  *D  1 | 1  0  2  
 trit 2 | 2  2  1