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

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

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

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

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

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

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

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

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

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

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

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

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

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