Brainfuck - kenrube/Esopoly GitHub Wiki
Brainfuck, пожалуй, самый известный представитель из семейства эзотерики, в первую очередь, благодаря своему минималистичному синтаксису. Имея в активе всего 8 инструкций, Brainfuck является Тьюринг-полным, что позволяет в перспективе написать на нем любую программу. Но, могу вас уверить, увязнете в яме Тьюринга вы намного быстрее, чем напишите хоть что-то полезное :)
К счастью, наша задача совсем проста: вывести на печать фразу Brainfuck program. Как и прежде, синтаксис языка я описывать не буду, - для этого достаточно заглянуть в любую статью по языку.
Алогритм чрезвычайно прост. В любой ячейке формируем требуемое нам значение (ASCII-код символа, как обычно) и выводим его на печать командой .. В принципе, всю задачу можно решить последовательностью + и -, но это слишком топорное и длинное решение. Воспользуемся возможностями языка для умножения чисел.
Схема проста (предполагаем, что мы находимся в ячейке 0 и вся память пуста):
> перейти в ячейку 1
+...+ присвоить этой ячейке (счетчику) некоторое значение {первый множитель}
[ повторять, пока значение текущей ячейки больше 0
< вернуться в ячейку 0
+...+ прирастить значение в ячейке на некоторое значение {второй множитель}
> снова перейти в первую ячейку
- уменьшить значение счетчика на 1
] вернуться к началу цикла
< вернуться в ячейку 0Или более компактно
>+...+[<+...+>-]<Разумеется, память не обязана быть пустой, да и ничто не мешает нам находиться в любой другой ячейке памяти. Если, скажем, в первоначальной ячейке было какое-то значение, оно с каждым декрементом счетчика будет увеличиваться на значение второго множителя. Точно так же работает и уменьшение.
Следуя этой схеме, составим нашу программу вывода фразы:
>>++++++[<+++++++++++>-]<. print 'B' (0 + 6 * 11 = 66)
>++++++[<++++++++>-]<. print 'r' (66 + 6 * 8 = 114)
>++++[<---->-]<-. print 'a' (114 - 4 * 4 - 1 = 97)
++++++++. print 'i'
+++++. print 'n'
--------. print 'f'
>+++[<+++++>-]<. print 'u'
>++++[<---->-]<--. print 'c'
++++++++. print 'k'
>>++++++++[<++++>-]<. print ' '
[-]<+++++. print 'p'
++. print 'r'
---. print 'o'
--------. print 'g'
+++++++++++. print 'r'
>++++[<---->-]<-. print 'a'
++++++++++++. print 'm'После добавления в общий исходный код других языков и их согласования между собой этот исходник стал выглядеть чуть-чуть иначе, обеспечивая, впрочем, тот же вывод:
><>.-+ head
>>++++++[<+++++++++++>-]<. print 'B'
>++++++[<++++++++>-]<. print 'r'
>++++[<---->-]<-. print 'a'
++++++++. print 'i'
+++++. print 'n'
--------. print 'f'
>+++[<+++++>-]<. print 'u'
>++++[<---->-]<--. print 'c'
++++++++. print 'k'
>>++++++++[<++++>-]<. print ' '
[-]<+++++. print 'p'
++. print 'r'
---. print 'o'
--------. print 'g'
+++++++++++. print 'r'
>++++[<---->-]<-. print 'a'
+++++<>+++++++. print 'm'
<><><>><<><><>><> tail
<><><<><>><><>><< --//--
><><><><<<>><>><> --//--
<>><<><<><>><><>< --//--
><><><><><>><<><< --//--
>><><>><<><><>><< --//--
><><<>><><><><><><>< --//--head я впредь буду обозначать ту часть исходного кода на конкретном языке, которая входит в состав первоначального исходника программы на Malbolge.
tail - команды, уже не выполняющие полезной работы, но присутствующие в итоговом исходном коде по той причине, что они нужны для каких-то других языков. В данном случае, например, они используются еще и программой на EXCON. Плюс Malbolge, разумеется.
Посмотреть на процесс и результат выполнения этой программы можно в Brainfuck Visualizer.
Дальше перед нами стоит задача объединить 2 исходника, которые у нас уже есть.
Как вы помните, любая программа на любом языке в составе нашего полиглота должна быть корректной с точки зрения Malbolge. Это значит, что любая команда из исходника на Brainfuck должна располагаться на таком месте, чтобы при нормализации исходного кода она превратилась в валидную команду из синтаксиса Malbolge.
У этого языка, кстати, есть интересная особенность: в состав его программ могут входить только печатные символы (33-126 в ASCII), поэтому, если после вычисления кода символа для ненормализованного представления символ оказался за пределами промежутка, код будет автоматически приведен обратно в эти границы. Например, 127 преобразуется в 33, а 32 - в 126. И так далее. А это значит, что для каждой команды Malbolge ее ненормализованное представление повторяется с шагом в 94 символа.
Выглядит это так:
('&%$#"!~}|{zyxwvutsrqponmlkjihgfedcba`_^]\[ZYXWVUTSRQPONMLKJIHGFEDCBA@?>=<;:9876543210/.-,+*) j
ba`_^]\[ZYXWVUTSRQPONMLKJIHGFEDCBA@?>=<;:9876543210/.-,+*)('&%$#"!~}|{zyxwvutsrqponmlkjihgfedc i
'&%$#"!~}|{zyxwvutsrqponmlkjihgfedcba`_^]\[ZYXWVUTSRQPONMLKJIHGFEDCBA@?>=<;:9876543210/.-,+*)( *
>=<;:9876543210/.-,+*)('&%$#"!~}|{zyxwvutsrqponmlkjihgfedcba`_^]\[ZYXWVUTSRQPONMLKJIHGFEDCBA@? p
cba`_^]\[ZYXWVUTSRQPONMLKJIHGFEDCBA@?>=<;:9876543210/.-,+*)('&%$#"!~}|{zyxwvutsrqponmlkjihgfed <
utsrqponmlkjihgfedcba`_^]\[ZYXWVUTSRQPONMLKJIHGFEDCBA@?>=<;:9876543210/.-,+*)('&%$#"!~}|{zyxwv /
QPONMLKJIHGFEDCBA@?>=<;:9876543210/.-,+*)('&%$#"!~}|{zyxwvutsrqponmlkjihgfedcba`_^]\[ZYXWVUTSR v
DCBA@?>=<;:9876543210/.-,+*)('&%$#"!~}|{zyxwvutsrqponmlkjihgfedcba`_^]\[ZYXWVUTSRQPONMLKJIHGFE o
Можете убедиться, приведя любую из этих строк в нормализованный вид в дебаггере.
Поскольку наша Malbolge-программа завершила свою работу с выводом последнего символа, команды, которые будут находиться за пределами ее исходного кода, могут быть любыми из j,i,*,p,<,/,v,o. Они никак не повлияют на работоспособность первоначальной программы. Это дает нам возможность выбирать ближайшее местоположение для очередной команды из Brainfuck-исходника из всех 8 вариантов.
Теперь у нас есть все, что нужно для объединения. Для удобства выравниваем исходник по 94 символа в ширину и заменяем все отсутствующие пока команды nop-инструкцией.
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+vooooooooooooo>>o+ooooooooooooooo++oo
ooooooooooooooooooo+ooooo+oooooooooooo+ooo[oooooooooooooo<oooooooooooooooo+ooooooooooooooo++oo
ooooooooooooooooooo+ooooo+oooooooooooo+oooooooooooooooo++ooooooooooooooooo+ooooooooooooooo++oo
>oooooooooooooooo-oooooo]ooooooooooooo<ooooooooooooo.oo>+ooooooooooooooooo+ooooooooooooooo++oo
ooooooooooooooooooo+ooooo+[ooooooooooo<oooooooooooooooo++ooooooooooooooooo+ooooooooooooooo++oo
ooooooooooooooooooo+ooooo+oooooooooooo+oooooooooooooooo>oooooooooooooooo-ooooooooo]ooooooooooo
oooooooo<ooooooo.oo>ooooo+oooooooooooo+oooooooooooooooo++oooooooo[ooooooo<oooooooooooooo--oooo
ooooooooooooooooo-ooooo-oooooooooooo>oooooooooooooooo-ooooooooo]ooooooooo<oooooooooooooo-ooooo
oooooooooooooooo.oo+ooooo+oooooooooooo+oooooooooooooooo++ooooooooooooooooo+ooooooooooooooo++oo
oooooooooooooooo.oo+ooooo+oooooooooooo+oooooooooooooooo++oooooooooooooo.-ooooooooooooooo--oooo
ooooooooooooooooo-ooooo-oooooooooooo-oooooooooooooooo--oooooooooooooooo.>o+ooooooooooooooo++oo
ooooooo[<oooooooooo+ooooo+oooooooooooo+oooooooooooooooo++oooooooooooooo>-ooooooooo]ooooooooooo
oo<ooooooooooooo.oo>ooooo+oooooooooooo+oooooooooooooooo++oooooooo[ooooooo<oooooooooooooo--oooo
ooooooooooooooooo-ooooo-oooooooooooo>oooooooooooooooo-ooooooooo]ooooooooo<oooooooooooooo--oooo
oooooooooooooooo.oo+ooooo+oooooooooooo+oooooooooooooooo++ooooooooooooooooo+ooooooooooooooo++oo
oooooooooooooooo.oo>oooooooooooooooo>o+oooooooooooooooo++ooooooooooooooooo+ooooooooooooooo++oo
ooooooooooooooooooo+ooooo+[ooooooooooo<oooooooooooooooo++ooooooooooooooooo+ooooooooooooooo+ooo
>oooooooooooooooo-oooooo]ooooooooooooo<ooooooooooooo.oooooooooooo[oooooo-ooooooooo]ooooooooooo
oo<oooooooooooooooo+ooooo+oooooooooooo+oooooooooooooooo++oooooooooooooo.oo+ooooooooooooooo+ooo
oooooooooooooooo.-ooooo-oooooooooooo-ooooooooooooooo.--ooooooooooooooooo-ooooooooooooooo--oooo
ooooooooooooooooo-ooooo-oooooooooooo-ooooooooooooooo.oo++ooooooooooooooooo+ooooooooooooooo++oo
ooooooooooooooooooo+ooooo+oooooooooooo+oooooooooooooooo++ooooooooooooooooo+oooooooooooo.oooooo
>oooooooooooooooooo+ooooo+oooooooooooo+oooooooooooooooo+ooooooooo[ooooooo<oooooooooooooo--oooo
ooooooooooooooooo-ooooo-oooooooooooo>oooooooooooooooo-ooooooooo]ooooooooo<oooooooooooooo-ooooo
oooooooooooooooo.oo+ooooo+oooooooooooo+oooooooooooooooo++ooooooooooooooooo+ooooooooooooooo++oo
ooooooooooooooooooo+ooooo+oooooooooooo+oooooooooooooooo+ooooooooooooooo.oooooooooooooooooooooo
Можете прогнать его через интерпретатор Brainfuck и убедиться, что два языка вполне себе прекрасно уживаются. Для Malbolge, впрочем, этот исходник пока невалиден - мы исправим это досадное упущение позже. А пока идем дальше.