Malbolge

Malbolge - уникальный язык программирования. Благодаря сериалу "Элементарно" ему досталась немалая слава. Слава языка, писать что-то на котором могут лишь тру-хакеры, и те под кайфом. Что самое интересное, это почти истинная правда. Не про кайф, про хакеров. С момента создания в 1998 году на нем написаны хорошо, если пара десятков программ, и те в большинстве своем написаны не вручную, а сгенерированы.

Причина? Прочитайте спецификацию, ознакомьтесь с интерпретатором и выберите любую по вкусу:

• результат выполнения инструкции зависит не только от ее назначения, но и от положения в исходном коде
• в языке полностью отсутствуют операции условного перехода, что делает невозможным произвольное перемещение по тексту программы
• после выполнения инструкции она шифруется, что невероятно затрудняет повторное ее использование
• и прочие мелкие радости.

Надеюсь, вы ознакомились со ссылками выше, так что я не буду объяснять основы языка. Замечу лишь, что там, где спецификация и ее реализация в интерпретаторе (от самого автора, Бена Ольмстеда) различаются, верным считается интерпретатор. Например, за вывод символа на печать отвечает инструкция <, а не /.

Посмотрите на исходник Hello world в Вики. Смотрится жутко, не правда ли? С виду совершенно хаотическое нагромождение символов, формируемое непонятно по каким правилам. На деле выглядит он так потому, что обфусцирован. Необфусцированная версия (называемая также "нормализованным исходным кодом") состоит лишь из набора инструкций языка (j,i,*,p,<,/,v,o) да еще, быть может, пробельных символов, которые будут проигнорированы интерпертатором.

Итак, наша цель - вывести на печать строку Malbolge program.

Виртуальная машина языка использует 3 регистра: A (аккумулятор), C (указатель на код) и D (указатель на данные). Изначально все регистры установлены в 0. То, что C и D указывают на одну и ту же инструкцию (а это значит, что исходный код одноврменно является и данными), крайне затрудняет формирование кода ASCII-символа для его вывода. Возможное решение заключается в разделении исходного кода на 2 части: собственно секция кода и секция данных. Единственный доступный метод разделения - jump в другое место исходного кода.

Чтобы понять, как это сделать, достаточно приглядеться к инструкциям языка. Например, заглянуть в Википедию. Как видно, есть 2 инструкции, которые позволяют выполнить jump: i (меняет значение C, указателя на код) и j (меняет значение D, указателя на данные).

В первом случае исходный код будет выглядеть примерно так:

...i[данные]...[код]

Во втором случае наоборот:

...j[код]...[данные]

Второй вариант нам не подходит, поскольку совершить jump можно максимум в инструкцию, располагающуюся на 40 месте, и нам не хватит места для кода, который должен формировать на вывод все символы фразы Malbolge source. Остается второй вариант.

Далее, нам нужен код, который будет формировать вывод. Для вывода символа предназначена инструкция <, которая читает значение из регистра A. Значит, до вызова этой инструкции мы должны записать в регистр A нужное нам значение. В спецификации указаны 2 инструкции, с помощью которых можно это сделать: * и p. Первая производит циклический сдвиг значения, лежащего по адресу D и сохраняет это значение в A, вторая вычисляет значение операции Crazy между значением по адресу D и значением в регистре A и перезаписывает последнее результатом. Выходит, наш исходный код будет выглядеть следующим образом:

...i[{набор из инструкций}o...o{набор из инструкций}oo]...[{набор из *,p,o}<...<{набор из *,p,o}<v]

где o - nop-инструкция, не производящая никаких полезных действий, v - инструкция окончания выполнения кода.

Осталась одна задача - подобрать соответветствующие наборы инструкций. Как раз этим и занимается написанный на Mathematica генератор. Конкретный алгоритм поиска я описывать не буду (возможно, сделаю это позже), нам важен итоговый результат. Вот он в нормализованном виде:

ooooooi/iojpo*pivojji/oovvoipooooo/oo*o<o/oo/iojo/oo/o/joijoo/ooooooooooooooooooooooooooooooo*p<*p<*ppp<*ppp<opp<*p<pp<pp<o*<*op<o*p<*op<*p<*p<pp<*p<v

Впоследствии некоторые инструкции были заменены, поскольку они делали некорректным исходный код программы на другом языке. Плюс были добавлены 2 пустые инструкции практически в самом конце - точной причины я не помню, возможно, это была попытка добавить Befunge (не взлетело :). Итоговый вид:

ooooooi/iojpo*pivojji/ijvvoipooooo/ji*p<o/oo/iojo/oo/o/joijpo/oopop<p<*p*o*<*ppo**p<pp*<oppoo*p<*p<*ppp<*ppp<opp<*p<pp<pp<o*<*op<**p<*op<*p<*p<pp<*poo<v

ooooooi     jump
,_____/
|   /io         data for 'M'
|   jpo         data for 'a'
|   *pivo       data for 'l'
|   jji/i       data for 'b'
|   jvvo        data for 'o'
|   ipo         data for 'l'
|   ooo         data for 'g'
|   o/j         data for 'e'
|   i*p         data for ' '
|   <o/o        data for 'p'
|   o/io        data for 'r'
|   jo/o        data for 'o'
|   o/o         data for 'g'
|   /jo         data for 'r'
|   ijp         data for 'a'
|   o/oop       data for 'm'
|   op<p<*p     do nothing (some instructions between data & code)
|   *o*<*pp     --//--
|   o**p<pp     --//--
v   *<oppoo     --//--
*p<             print 'M'
*p<             print 'a'
*ppp<           print 'l'
*ppp<           print 'b'
opp<            print 'o'
*p<             print 'l'
pp<             print 'g'
pp<             print 'e'
o*<             print ' '
*op<            print 'p'
**p<            print 'r'
*op<            print 'o'
*p<             print 'g'
*p<             print 'r'
pp<             print 'a'
*poo<           print 'm'
v               stop

Или то же самое в виде, пригодном для исполнения интерпретатором языка:

DCBA@?\nZ;|38x0SA3tsN`Lo98*G"'&%$#Sc>`v<zLxwI5tWrDpoAm?Oj)Laf8dc\aZ~X|?U=Y;v9ONS54JnHG/jJCBGF(>b%;_"876Z{321U5.-Qr*N('K%$H(hEf${Abaw=^zs9Zp6Wm3kj0Qglk+v

DCBA@?\     jump
nZ;         data for 'M'
|38         data for 'a'
x0SA3       data for 'l'
tsN`L       data for 'b'
o98*        data for 'o'
G"'         data for 'l'
&%$         data for 'g'
#Sc         data for 'e'
>`v         data for ' '
<zLx        data for 'p'
wI5t        data for 'r'
WrDp        data for 'o'
oAm         data for 'g'
?Oj         data for 'r'
)La         data for 'a'
f8dc\       data for 'm'
aZ~X|?U     do nothing (some instructions between data & code)
=Y;v9ON     --//--
S54JnHG     --//--
/jJCBGF     --//--
(>b         print 'M'
%;_         print 'a'
"876Z       print 'l'
{321U       print 'b'
5.-Q        print 'o'
r*N         print 'l'
('K         print 'g'
%$H         print 'e'
(hE         print ' '
f${A        print 'p'
baw=        print 'r'
^zs9        print 'o'
Zp6         print 'g'
Wm3         print 'r'
kj0         print 'a'
Qglk+       print 'm'
v           stop

Можете проверить этот исходный код, запустив его, например, в дебаггере Маттиаса Эрнста.

Итак, первая - и, пожалуй, самая сложная часть - завершена. Идем дальше.