brainfuck

Удивительно, как некоторые бесполезные идеи иногда накрепко захватывают наш ум. Я тут в качестве примера хотел привести игру «Жизнь» Конвея, но при всей своей кажущейся бесполезности она в своё время сильно продвинула математику.

Меня в своё время захватила идея языка программирования «Брейнфак». Оглядываясь назад, думаю, её тоже нельзя объявить полностью бесполезной: в своё время я немало поломал голову над созданием оптимизирующего интерпретатора для этого языка.

Для начала — про сам язык. Я узнал о нём примерно в 2000 году, когда была мода на так называемые «эзотерические языки» — языки, разработанные в качестве шутки или для исследования какой-нибудь абсурдной идеи. «Брейнфак» как раз из таких: в нём всего восемь инструкций, но при этом это полноценный язык. Нейросеть мне на нём даже написала «Тетрис».

«Брейнфак» оперирует ячейкой в массиве, индекс которой можно сдвигать при помощи конструкций < и >. Кроме того, ячейку можно декрементировать (-), инкрементировать (+), вывести на экран символ, код которой записан в ячейке (.), либо записать код введённого с клавиатуры символа (,).

Кроме того, в «Брейнфаке» можно организовывать циклы при помощи парных инструкций [ и ] неограниченной вложенности. [ проверяет значение текущей ячейки, если там не ноль, выполняет тело цикла. Например, [-] записывает в текущую ячейку ноль, декрементируя значение в цикле.

Так как это единственная управляющая конструкция, циклов в обычной программе на «Брейнфаке» — огромное количество. Например, вот так выглядит минимальный «квайн», программа, которая при запуске выведет саму себя:

->++>+++>+>+>++>>+>+>+++>>+>+>++>+++>+++>+>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>+>+>+
+>>>+++>>>>>+++>+>>>>>>>>>>>>>>>>>>>>>>+++>>>>>>>++>+++>+++>+>>+++>>>+++>+>+++>+
>++>+++>>>+>+>+>+>++>+++>+>+>>+++>>>>>>>+>+>>>+>+>++>+++>+++>+>>+++>+++>+>+++>+>
++>+++>++>>+>+>++>+++>+>+>>+++>>>+++>+>>>++>+++>+++>+>>+++>>>+++>+>+++>+>>+++>>+
++>>+[[>>+[>]+>+[<]<-]>>[>]<+<+++[<]<<+]>>+[>]+++[++++++++++>++[-<++++++++++++++
++>]<.<-<]

Я задумался об оптимизации программ на «Брейнфаке» ещё в начале 2000-х, запрограммировав свои идеи на ДжаваСкрипте.

Первые мысли были вполне очевидными — объединять одинаковые конструкции. Вместо того чтобы последовательно инкрементировать ячейку десять раз, на этапе предпроцессинга можно сразу подсчитать количество «плюсов» и прибавить сколько требуется.

Потом я начал транслировать идиомы Brainfuck напрямую в ДжаваСкрипт, что тоже заметно повысило производительность. Например, конструкцию [-] можно заменить простой записью нуля в текущую ячейку — без выполнения цикла.

Настоящий прорыв случился, когда я понял: так можно оптимизировать не только отдельные идиомы, а вообще все циклы без ввода-вывода, если после выполнения цикла указатель возвращается в ту же ячейку, с которой начал. Например, [->+++++<] превращается во что-то вроде d[i+1] = d[i] * 5; d[i] = 0.

В дальнейшем я сильно развил эту идею. И если простейшие оптимизации встречаются и в реализациях других авторов, то настолько глубоко, насколько мне известно, не копал никто.

В середине 2000-х я переписал свой интерпретатор на ПХП, сохранив основной принцип, и время от времени ненадолго загорался желанием что-нибудь в нём улучшить. Недавно я полностью переписал его с помощью нейросетей, перевёл на свежую версию ПХП, покрыл тестами и так далее. Но сами принципы оптимизации остались теми же — придуманные мной ещё в 2000-е.

Проект лежит у меня на «ГитХабе».

Ну разумеется я вчера не смог уснуть без того, чтобы не посмотреть что ещё мог бы написать ИИ на «Брейнфаке»! Попробовал написать «Тетрис», тем более что у меня были готовые идеи как это сделать. Правда для этого пришлось модифицировать интерпретатор. Свой собственным, разумеется, который я начал писать ещё в 2001-м году, надо бы про него рассказать тоже однажды.

Дело в том, что у «Брейнфака» нет рандомизации и ввод устроен очень просто — есть инструкцию чтения символа и всё. Правда сам язык не определяет подробности чтения символа, поэтому реализации отличаются. В основном авторы интерпретаторов делают буферизированный ввод, дожидаясь нажатия кнопки «Ввод». Правда тут тоже есть нюансы — где-то можно ввести строку, а где-то «Ввод» надо нажимать после введения каждого символа.

Чтобы приступить к «Тетрису» пришлось сделать две модификации.

Во-первых, ввести команду @, которая записывает случайное число в текущую ячейку («Брейнфак» всё сохраняет в ячейках, двигаясь по ней при помощи специальных команд). В таком расширении языка нет ничего необычного — когда он был на волне популярности, ему постоянно придумывали всякие расширения.

Во-вторых, я добавил специальный режим опроса клавиатуры — неблокирующее чтение. Мы передаём программе весь ввод пользователя сразу, а если он ничего не вводил, записываем в текущую ячейку ноль.

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

Чтобы каждый раз не вспоминать какие ключи нужны программе, я придумал способ как их указывать — если в начале программы на «Брейнфаке» стоит обычный шебанг, я беру параметры интерпретатора оттуда.

Как легко догадаться по скриншотам, нейросеть (я использовал «ГПТ-5.5») отлично справилась с задачей. Но что интересно, чтобы это сделать она реализовала ровно ту идею, про которую я писал в прошлый раз — написала генератор на ПХП, при помощи которого сгенерировала программу на «Брейнфаке». Немудрено — программа получилась монументальной — под сотню мегабайт в первой попытке.

Я даже сделал в своём интерпретаторе поддержку сжатия исходников. Наверное никому раньше не приходило в голову этим заниматься — как правило программы на «Брейнфаке» пишут люди и до таких размеров они их не доводят.

Трансляция такого огромного файла и применение оптимизаций занималось около 15—20 секунд на моём ноутбуке, так что пришлось применить ряд оптимизаций — немного переписать парсер интерпрератора, сделать кеширование и поработать над уменьшением размера кода «Тетриса».

«Тетрис» работает в консоли и, надеюсь, никому не надо объяснять, что для раскрашивания блоков и позиционирования тут широко применяются анси-коды, я их использую чуть ли не в каждой консольной программе, вряд ли кого-то это удивит.

Единственное о чём надо рассказать — как регулируется скорость игры. В «Брейнфаке» нет ничего, чтобы создавать паузы заданной длительности, но некоторые программы работают ощутимо долго. Хотя у меня и оптимизирующий интерпретатор, всё оптимизировать он не может. Поэтому мы с нейросетью просто «на глазок» подобрали код, который достаточно плохо оптимизируется и тормозит на моём ноутбуке ровно насколько, чтобы играть было комфортно.

Три года назад я в шутку предлагал программистам переходить на «Брейнфак» — эзотерический язык программирования из восьми конструкций, который плохо давался нейросеткам. Что-то похожее на программу на этом языке они писали, но получался мусор.

Я пропустил момент, когда модели научились на нём писать. Буквально вчера догадался снова попробовать, оказалось — могут! Программу на скриншоте мне «Курсор» написал в режиме «Авто», где выбираются, в основном, слабые модели. Топовые справляются даже с такими заданиями как написать несложный эмулятор командной строки с несколькими основными командами и небольшой файловой системой!

Для человека это уже какой-то запредельный уровень. Если бы я решал эту задачу, я бы написал себе сначала какой-нибудь макроязык с трансляцией в «Брейнфак» и уже на нём написал то, что требуется.

Две вещи, с которыми модели ещё не справляются — это написание «квайна» (программы, которая выводит сама себя) и оптимизация программ на «Брейнфаке» по размеру. Даже топовые модели наотрез у меня отказываются такое писать. Даже после прямого приказа.

Интересно будет помучить этой задачкой новую модель «Антропика», которая должна появиться летом — я считаю их модели лучшими, хотя их последний «Опус» несколько разочаровал.

Добавлено позднее: справедливости ради насколько простую программу, как на картинке выше, нейросети и сейчас могут написать оптимальнее:

Я писал уже про язык программирования в шрифтах. Там я, в качестве примера, написал программу, которая переводит вводимые буквы в азбуку Морзе. Внедрение всякой всячины в шрифт оказалось таким весёлым занятием, что вчера не удержался и воткнул в шрифт интерпретатор языка программирования Brainfuck. Язык внутри языка внутри шрифта.

Число «Пи», считаемое внутри шрифта программой на Брейнфаке

Поскольку никакого ввода, кроме строки, которую нужно написать шрифтом, тут не предусмотрено, но некоторые программы требуют ввод (для этого в Брейнфаке есть конструкция «запятая»), пришлось выкручиваться.

Я сделал так: программа и входные данные у меня записаны в одну строку и разделены слешем. Часть после слеша считается тем, что введено в программу с клавиатуры.

Сегодня мы пришли на работу в украшенный к Новому году офис. Было очень много всего крутого, но особенно меня порадовала небольшая программа на языке «Браинфак», появившаяся на одной из стен. Я много писал об этом языке и до сих пор горячо его люблю, как забавную головоломку.

Программа на языке «Браинфак», выводящая число 42 — ответ на главный вопрос жизни, вселенной и всего такого

Меня тут атакуют время от времени алармистки настроенные программисты, с вопросом что дальше делать, — ведь их всех скоро заменит ChatGPT. Так вас же ещё 2017-м Герман Греф предупреждал — не идите в программисты, программисты станут невостребованной профессией!

Лично я услышал Грефа, и вот уже шесть лет как переписываю все свои проекты на язык «Брейнфак». Это минималистичный язык, состоящий из шести операторов, при этом он полный по Тьюрингу.

Этот ваш ChatGPT очень плох в «Брейнфаке» — его программа на самом деле выводит «Hello World!»

Прелесть его в том, что он плохо токенизируется — у него совершенно другая структура, поэтому генеративные нейросети не умеют писать на нём программы. Даже хвалённая четвёртая версия ChatGPT, которая вышла недавно, не умеет на нём и двух знаков связать.

Коллеги, если мы успеем тайно переписать все свои проекты на «Брейнфак» в ближайшее время, то для поддержания всех переписанных на него проектов, понадобятся живые программисты! У нас будет работа! Никого не уволят! Так победим!

Резюме — в моём частном случае стало ощутимо быстрее, PHP 7.4 работал 63,9 секунд, 8.0a — 42,6.

Как многие знают, основной фишкой восьмой версии интерпретатора ПХП будет JIT. Обещают ускорение вычислительных задач, что немного не про веб, где в основном используется этот язык, но всё равно выглядит интересно.

В официальном репозитории альфа восьмой версии лежит уже давно, стало интересно сравнить её с «семёркой» — много ли даёт JIT приросту. Для подобных тестов я давно использую свой оптимизирующий транслятор «Брейнфака», с загруженной в него задачей вычисления числа Пи.

Восьмой ПХП собрался на моём «Макбуке» следующей последовательностью команд:

PATH=/usr/local/Cellar/bison/3.5.3/bin/:$PATH ./buildconf
./configure --prefix=/opt/php-bin/ --without-iconv --disable-xml \
--without-libxml --disable-simplexml --disable-xmlwriter --disable-dom --disable-xmlreader
make -j4
make install

Версию 7.4 ставил через «брю», сборочную конфигурацию оставил как есть, ничего не менял.

После небольшой коррекции php.ini в информации об интерпретаторе появились OPcache и JIT:

Скомпилированная версия PHP 8.0a со включенным JIT

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

Сравнение PHP 7.4 и 8.0a, со включённым и выключенным opcache (меньше — лучше)

Каждую версию интерпретатора я тестировал со включенным и выключенным OPcache десять раз, а результаты усреднил. Как видите, JIT существенно ускорил выполнение программы в моём случае (там огромное количество циклов и ветвлений) — 63,9 секунды против 42,6.

Что интересно — PHP 8.a без OPcache обогнал версию 7.4 со включенным opcache, это примечательный результат— значит сам «голый» интерпретатор тоже оптимизируют.

В качестве упражнения написал тривиальный интерпретатор «Брейнфака» на языке «Эр», никаких оптимизаций, кроме преподсчёта переходов. Даже на версию без поддержки вложенных циклов ушло прилично времени — некоторые вещи у меня пока со скрипом идут. Зато воспользовался разными структурами данных и сделал класс на RC (в языке «Эр» три встроенных способа работы с классами).

У меня есть старинная забава — брать свой оптимизирующий интерпретатор языка «Брейнфак» и запускать программу, вычисляющую число «Пи» под разными версиями ПХП, чтобы посмотреть их производительность. Тест довольно синтетический, но посмотреть всё равно интересно.

Сравнил в данном случае версии 5.5.14  и сегодняшнюю сборку 7.0, разница всё равно заметна, хоть и не так впечатляюща, как в случае с «Вордпрессом» — там разница в два раза.

Время у меня на скриншоте общее — то есть трансляция программы на «Брейнфаке» в ПХП и запуск получившегося через eval.

Грех было не запустить свою же программу из предыдущего поста на собственном стареньком (2005 года) оптимизирующем трансляторе Брейнфака в ПХП. Оказалось, оттранслировал его неправильно.

Нашёл баг (неверно транслировалась последовательность «[<]» в некоторых случаях), исправил, почистил, убрал наследие ПХП 4, ввёл небольшую новую оптимизацию и выхожил на ГитХаб.

История этого интерпретатора тянется ещё с 2001-го года и сайта bf.kzn.ru, который ныне не существует. На нём у меня работал jBF, транслятор Брейнфака на Джаваскрипт и это был первый в мире интерпретатор Брейнфака, который использовал оптимизирующие техники. Вышло аж тринадцать версий интерпретатора и он довольно неплохо уделывал аналоги.

В 2005 году я переделал его на ПХП и попробовал предложить на ПЕАР (к тому времени у меня там уже было несколько модулей), но там он не прошёл предворительный осмотр, сказали, что такой модуль не нужен.

Так он у меня и валялся в разделе «Храню», пока я не запустил сегодня на нём свою программу. Должен, кстати, сказать, что интерпретатор держит марку, например, вот вычисление числа «Пи» на моём трансляторе и интерпретаторе на Джаве:  

Хотя, может быть, Джава просто медленно стартует.

Заодно, кстати, на своей же программе нашёл баг в расцветке Брейфака, которую я делал для библиотеки highlight.js.

Помните моё поздравление с Новым годом, написанное на запутанном Джаваскрипте? Такой же принцип я использовал для привлекающего внимание баннера нашей компании.

Я давно уже заметил, что это сильно похоже на язык Брейнфак. Давно хотелось попробовать смешать эти два языка в одном листинге. Со стороны Брейнфака всё довольно гладко — надо только балансировать квадратные скобки (но Джаваскрипт требует того же) и избегать вечных циклов (тут уже сложнее, так как листинги на запутанном Джаваскрипте часто требуют пустых циклов), незнакомые символы этот язык пропускает. В Джаваскрипте синтаксис построже, там нужно было помучаться больше.

Получилась следующая программа (используется расцветка для Брейнфака, чтобы было видно какие части программы он пропускает):

($=!{}[/-/+/\+@+@+!+/)-!{$:/>/+/!>/+/</}+
(_=!-{}-$+/>/)-~(/</)+
(_$=-$-{}-$+/>/)[$$=-(~-~$+~-~$-!+{$:/!</})+
_[$$+=~-~{$:/]/}+
_$-~{}+
_$[$$+~{_:-$>/]/}+
$-$$]

Оба интерпретатора выполняют её с разным результатом, Брейнфак выводит «hello», а Джаваскрипт — «friends»:

bolk@Bolk ~$ ./brainfuck <<<'($=!{}+[/-/]+/\+@+@+!+/)[-!{$:/>/+/!+>/+/<</}]+(_=!-{}+[-$]+/>/)[-~(/>[->+>+<<]>>[-<+<+>>]<<</)]+(_$=[-$][-{}]+[-$]+/>>/)
[$$=-(~-~$+~-~$-!+{$:/!+>+>+>+>+>+<<<<</})]+_[$$+=~-~{$:/[->++++>+>++++++++>++++++++>+++++++++++[<]]/}]+_$[-~{}]+_$[$$+~{_:-$>/[.>]/}]+$[-+-$$]'

hello

bolk@Bolk ~$ v8 -e 'print(($=!{}+[/-/]+/+@+@+!+/)[-!{$:/>/+/!+>/+/<</}]+(_=!-{}+[-$]+/>/)[-~(/>[->+>+<<]>>[-<+<+>>]<<</)]+(_$=[-$][-{}]+[-$]+/>>/)
[$$=-(~-~$+~-~$-!+{$:/!+>+>+>+>+>+<<<<</})]+_[$$+=~-~{$:/[->++++>+>++++++++>++++++++>+++++++++++[<]]/}]+_$[-~{}]+_$[$$+~{_:-$>/[.>]/}]+$[-+-$$])'

friends

Повозиться пришлось прилично, если честно, некоторые конструкции ДжЭс делит с Брейфаком (большинство квадратных скобок), а кое-где торчат чистые инструкции Брейнфака, засунутые в те места программы, где они не могут помешать своему соседу. Пустые циклы, которые образуются квадратными скобками я старался сводить к операции зануления ячейки („[-]“), сильно мешали плюсы, используемые в Джаваскрипте для объединения букв — они увеличивали содержимое ячейки в Брейнфаке на единицу, это приходилось учитывать.

Слово «friends» я выбрал потому что его легко записать:

"false"[0]+"true"[1]+"undefined"[5]+"true"[3]+"undefined"[1]+"undefined"[2]+"false"[3]

Принцип я когда-то более-менее подробно разбирал.

Я как-то писал, что ко Дню программиста сделал подсветку синтаксиса языка Brainfuck для библиотеки highlight.js.

Оказывается, я пропустил выход версии 7.3, куда вошла моя подсветка, теперь Brainfuck входит в список поддерживаемых языков.

Как-то очень давно я наткнулся в сети на язык с названием Brainfuck. Его идея, так подходящая к его названию, так меня захватила, что я в своё время создал оптимизирующий компилятор программ Brainfuck в JavaScript, выполненный в виде минишелла и работающий прямо в браузере. Язык интересен тем, что содержит всего восемь конструкций, но позволяет писать программу любой сложности, правда скорость выполнения…

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

Модуль к PHP написан в формате PEAR, т. е. его можно либо использовать непосредственно, либо исталлировать в составе PEAR.

Нельзя сказать, что я компилятор проводит глубокую оптимизацию, но, например, код «[->+>++<<][>+>[-]<<-][>+<[-]]" будет преобразован в

<?php
$in = array(0, $id = 0);
$d = array_fill(-65535, 65535, $di = 0);

$d[$di+1]+= $d[$di];
$d[$di+2]+= $d[$di]*2;
$d[$di] = 0;

$d[$di+1]+= $d[$di];
if ($d[$di]) $d[$di+2] = 0;
$d[$di] = 0;

$d[$di+1]+= $d[$di];
$d[$di] = 0;

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