Skip to content

Brainfuck

Jump to bottom
Ivan Zolotarev edited this page Apr 8, 2017 · 16 revisions

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, впрочем, этот исходник пока невалиден - мы исправим это досадное упущение позже. А пока идем дальше.

Clone this wiki locally