bf

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

Программа на языке «Браинфак», выводящая число 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 на AppleScript.

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

AppleScript медленный язык, следовательно и получившийся интерпретатор медленный (никаких оптимизаций я не делал), лучше всего на нём запускать небольшие программы. Например, «Hello, world»:

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

Не уверен, что нигде не ошибся (всё-таки время четвёртый час ночи), но даже вложенные циклы на программах, которые я прогонял, работают нормально.

#!/usr/bin/osascript
-- AppleScript Brainfuck interpreter
-- Evgeny Stepanischev 1 Jul 2011 //bolknote.ru

set Cells to {}
repeat 30000 times
    set end of Cells to 0
end repeat

display dialog "Enter your BF program" default answer ""
set Bf to text items of text returned of result

set Pointer to 1
set CmdPointer to 1
set Output to ""
set Input to {}
set Stack to {}

repeat while CmdPointer ≤ (count of Bf)
    set Cmd to item (CmdPointer) of Bf
    
    if Cmd is equal to ">" then
        set Pointer to Pointer + 1
        if Pointer > 30000 then set Pointer to 1
        
    else if Cmd is equal to "<" then
        set Pointer to Pointer - 1
        if Pointer < 1 then set Pointer to 30000
        
    else if Cmd is equal to "+" then
        set Val to (item (Pointer) of Cells) + 1
        if Val is greater than 255 then set Val to 0
        copy Val to item (Pointer) of Cells
        
    else if Cmd is equal to "-" then
        set Val to (item (Pointer) of Cells) - 1
        if Val is less than 0 then set Val to 255
        copy Val to item (Pointer) of Cells
        
    else if Cmd is equal to "." then
        set Output to Output & (ASCII character item (Pointer) of Cells)
        
    else if Cmd is equal to "," then
        if Output ≠ "" then
            display alert Output
            set Output to ""
        end if
        
        if Input is {} then
            display dialog "Enter one or more characters" default answer ""
            set Res to text returned of result
            
            set item (Pointer) of Cells to ASCII number of character 1 of Res
            
            try
                set Input to rest of text items of Res
            end try
            
        else
            set item (Pointer) of Cells to ASCII number of item 1 of Input
            set Input to rest of Input
        end if
        
    else if Cmd is equal to "[" then
        if item (Pointer) of Cells = 0 then
            set CmdPointer to CmdPointer + 1
            set Deep to 1
            
            repeat while CmdPointer ≤ (count of Bf)
                set Cmd to item (CmdPointer) of Bf
                
                if Cmd is equal to "[" then
                    set Deep to Deep + 1
                else if Cmd is equal to "]" then
                    set Deep to Deep - 1
                    
                    if Deep is 0 then exit repeat
                end if
                
                set CmdPointer to CmdPointer + 1
                
            end repeat
        else
            set Stack to (CmdPointer - 1) & Stack
        end if
    else if Cmd is equal to "]" then
        if item (Pointer) of Cells ≠ 0 then
            copy item (1) of Stack to CmdPointer
        end if
        set Stack to rest of Stack
    end if
    
    set CmdPointer to CmdPointer + 1
end repeat

if Output ≠ "" then
    display alert Output
end if

Как-то очень давно я наткнулся в сети на язык с названием 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 подвергаются процедуре голосования, прежде чем попадут в репозиторий).