Когда-то давно, году в 2013-м, мне на глаза попался следующий код:
>>>+[[-]>>[-]++>+>+++++++[<++++>>++<-]++>>+>+>+++++[>++>++++
++<<-]+>>>,<++[[>[->>]<[>>]<<-]<[<]<+>>[>]>[<+>-[[<+>-]>]<[[
[-]<]++<-[<+++++++++>[<->-]>>]>>]]<<]<]<[[<]>[[>]>>[>>]+[<<]
<[<]<+>>-]>[>]+[->>]<<<<[[<<]<[<]+<<[+>+<<-[>-->+<<-[>+<[>>+
<<-]]]>[<+>-]<]++>>-->[>]>>[>>]]<<[>>+<[[<]<]>[[<<]<[<]+[-<+
>>-[<<+>++>-[<->[<<+>>-]]]<[>+<-]>]>[>]>]>[>>]>>]<<[>>+>>+>>
]<<[->>>>>>>>]<<[>.>>>>>>>]<<[>->>>>>]<<[>,>>>]<<[>+>]<<[+<<
]<]Это интерпретатор языка Brainfuck, написанный на самом Brainfuck. Ссылки на оригинал у меня не осталось, только код, так что автора я назвать не смогу.
UPDATE: авторы найдены одним из читателей, который прислал мне ссылку в личку:
http://www.hevanet.com/cristofd/08.html. Я код брал из другого источника, в котором объяснений не было.
Мне всегда было безумно интересно узнать, как он работает. И теперь я решил наконец-то это сделать!
Что ещё за Brainfuck
Несмотря на то, что для Brainfuck есть отдельный хаб на хабре, по делу даже в него пишут нечасто. Непопулярный язык. Не все могут быть с ним знакомы, поэтому начнём с описания.
Программа на Brainfuck представляет собой манипуляцию массивом байт, канонично состоящего из, как минимум, 30-ти тысяч элементов. Для ясности будем считать, что в начале исполнения у нас есть byte* p = ...; - ссылка на память, заполненную нулями. В языке есть следующие «инструкции»:
>- сдвиг каретки право, соответствует кодуp++. При выходе за переделы массива программа ломается, это нормально.<- сдвиг каретки влево, соответствует кодуp--.+- инкремент текущего элемента, соответствует коду(*p)++.-- декремент текущего элемента, соответствует коду(*p)--..- вывод текущего элемента, соответствует кодуprint(*p).,- чтение текущего элемента, соответствует коду*p = read().[ code ]- цикл.codeтут - это какой-то корректный код на Brainfuck. Парность скобок должна соблюдаться. Соответствует кодуwhile (*p) { code; }.
Вообще говоря, следуя этим описаниям, становится очень просто написать транслятор с Brainfuck на какой-нибудь там C++. С примерами простых программ мы встретимся по ходу анализа.
С чего начать понимание
Первое, что нужно сделать с непонятным кодом - это отформатировать его. Форматирование заключается в красивом оформлении особо больших циклов. Результат может выглядеть как-то так (в статье код отформатирован со знанием будущего):
1 >>>+ [
2 [-]>>[-]++>+>+++++++[<++++>>++<-]++>>+>+>+++++[>++>++++++<<-]+>>>,<++ [
3 [>[->>]<[>>]<<-]<[<]<+>>[>]> [
4 <+>-[[<+>-]>]< [
5 [[-]<]++<-[<+++++++++>[<->-]>>]>>
6 ]
7 ] <<
8 ] <
9 ] <
10 [
11 [<]>[[>]>>[>>]+[<<]<[<]<+>>-]>[>]+[->>]<<<< [
12 [<<]<[<]+<<[+>+<<-[>-->+<<-[>+<[>>+<<-]]]>[<+>-]<]++>>-->[>]>>[>>]
13 ] <<
14 [
15 >>+<[[<]<]>[[<<]<[<]+[-<+>>-[<<+>++>-[<->[<<+>>-]]]<[>+<-]>]>[>]>]>[>>]>>
16 ]
17 <<[>>+>>+>>]<<[->>>>>>>>]<<[>.>>>>>>>]<<[>->>>>>]<<[>,>>>]<<[>+>]<<
18 [+<<]<
19 ]Второе, что нужно сделать с непонятным кодом - это откомментировать его, и вот тут возникают очевидные проблемы.
Ясно одно - фактически код состоит из 2-х больших циклов. Первый цикл просто обязан быть кодом парсинга программы на Brainfuck, а второй - кодом её интерпретации. Иначе и быть не может, так что считаем это утверждение нашим базовым предположением об алгоритме.
Как читать эту статью
Объяснять код на Brainfuck в письменной форме - дело непростое, зачем я вообще это делаю? Любая более-менее сложная программа постоянно опирается на большое количество неявных инвариантов, контролируемых во время исполнения.
Это главная причина, по которой я считаю, что у данной статьи «высокая сложность» - тяжело держать всё в памяти. Ну и объём текста, естественно. Оценке времени, которую дал хабр, доверять не советую, минут потребуется немного больше.
В остальном - никаких глубоких познаний в программировании не нужно.
Со своей стороны я постараюсь облегчить процесс понимания настолько, насколько смогу. Но есть и другие объективные факторы, сильно мешающие чтению - при скроллинге статьи код пропадает из виду. Тут уж придётся либо открыть статью 2 раза в 2-х вкладках, либо скопировать код себе в редактор.
Так же поощряется самостоятельный запуск кода на Brainfuck во время чтения. В интернете легко найти кучу онлайн-интерпретаторов на любой вкус. Если не хочется онлайн, то можно написать свой, это вряд-ли займёт больше 15 минут. Да и контроля будет больше
На этом с введением покончено, начнём разбирать код!
Цикл 1. Парсинг программы
В первую очередь, несколько слов о том, в каком формате интерпретатор получает данные. Делается это в таком виде:
Сперва на ввод подаётся код на Brainfuck, который нужно интерпретировать.
После идёт символ-разделитель
!, который указывает на окончание кода на Brainfuck. Именно!выбран вероятно потому, что это первый «нормальный» ASCII символ, помимо пробела, конечно же.Всё, что идёт после, уже считается входными данными для интерпретируемого кода.
Например, ввод ,.!A будет соответствовать интерпретации программы ,., которой на вход подаётся символ A. Эта программа читает символ из ввода и тут же его распечатывает, то есть выводом интерпретатора на данном вводе должна быть просто буква A.
Строка 1
1 >>>+ [В первой строке идёт несложная подготовка массива к последующей работе. В самом начале массив заполнен нулями и каретка указывает на 0-й элемент. Я буду это обозначать следующим образом:
{[0], ...}
Выполняемый в начале код делает сдвиг вправо на 3 позиции (>>>) и увеличивает хранящийся там 0 на единицу (+):
{0, 0, 0, [1], ...}
После этого следует начало цикла, который мы заранее назовём «циклом парсинга». Так как текущий элемент не равен 0, то будет выполнена как минимум одна итерация. Вообще говоря, единственная цель выставления текущего элемента в 1 - это как раз гарантия выполнения цикла, подтверждение этого утверждения мы увидим буквально в нескольких следующих символах программы.
Строка 2
1 .... [
2 [-]>>[-]++>+>+++++++[<++++>>++<-]++>>+>+>+++++[>++>++++++<<-]+>>>,<++ [Это код инициализации для каждой итерации. Он пишет какие-то значение в какие-то ячейки массива и потом запускает другой большой внутренний цикл.
Так как этот код находится внутри цикла, мы можем не знать, в каком состоянии находится массив. Поэтому вынуждены прибегать к предположениями. Я пока буду исходить из следующей позиции здравого смысла: «если код явно не зануляет какую-то ячейку массива, значит нам заранее известно, что в ней 0».
Что делает код [-]? Если вспомнить данное ранее определение квадратных скобок, то получится следующий аналог: while (*p) { (*p)--; }. Мы уменьшаем текущую ячейку до тех пор, пока она не станет равна 0. Другими словами это код, аналогичный *p=0, т.е. зануление текущей ячейки.
Соответственно код [-]>>[-] зануляет 2 ячейки, превращая{head, 0, [?], 0, ?, ...} в{head, 0, 0, 0, [0], ...}. Тут я явно обозначаю незатронутые элементы нулями, а те, что мы зануляем - вопросиками. Зачем я в примере пишу элемент перед первым ? станет ясно позже, он тоже всегда равен 0.
Дальнейшая каша из плюсов и минусов нужна для того, чтобы записать какие-то числа в массив, начиная с текущего положения.++>+> переводит массив в состояние {head, 0, 0, 0, 2, 1, [0], ...}.
Далее код +++++++[<++++>>++<-] записывает числа побольше с помощью операции умножения.
Массив {..., 1, [0], ...} превращается сперва в {..., 1, [7], 0, ...},
а потом выполняется 7 итераций, которые эту 7 зануляют, попутно модифицируя ячейки слева и справа от неё:..., 1, [7], 0, ... -> ..., 5, [6], 2, ... -> ..., 9, [5], 4, ... ->
... -> ..., 25, [1], 12, ... -> ..., 29, [0], 14, .... Тут и происходит умножение 7 на 4 и 2 соответственно. После выполнения цикла данного цикла массив будет выглядеть так:{head, 0, 0, 0, 2, 29, [0], 14, ...}.
Далее следует код ++>>+>+>, который добавит ещё несколько небольших чисел:{head, 0, 0, 0, 2, 29, 2, 14, 1, 1, [0], ...}.
Код +++++[>++>++++++<<-] похож на умножение, которые мы делали совсем недавно, он добавляет в ячейку справа число 10 (= 5 * 2), а за ней 30 (= 5 * 6):
{head, 0, 0, 0, 2, 29, 2, 14, 1, 1, [0], 10, 30, ...}.
Осталось совсем немного. Код +>>>,<++ пишет в текущую ячейку значение 1, передвигает каретку право за 30, читает ввод, возвращается к 30 и увеличивает её на 2. Значение введённой ячейки я обозначу как c:
{head, 0, 0, 0, 2, 29, 2, 14, 1, 1, 1, 10, [32], c, ...}.
Будь моя воля, я бы последний кусок кода заменил на +>>++>,<, чтобы увеличить 30 до 32 на первом проходе, но что есть, то есть.
В дальнейшем я буду расписывать код чуть менее подробно, полагая, что читатель уже успел освоить упомянутые ранее приёмы. В противном случае и так длинная статья стала бы совершенно невыносимой.
Что ещё за магические числа
Вот мы получили загадочную последовательность чисел и одну из команд читаемой нами программы в самом конце (c). Очевидно, что числа не случайны и как-то связаны с парсингом команд. Чтобы найти связь, взглянем на числовые коды команд, которые мы парсим:
char |
|
|
|
|
|
|
|
|
|
code | 33 | 43 | 44 | 45 | 46 | 60 | 62 | 91 | 93 |
Повторю встреченные нам магические числа: 2, 29, 2, 14, 1, 1, 1, 10 и 32. Посмотрев на них очень внимательно, может даже немного прищурившись, становится ясно, что все они равны разнице между соседними кодами, но в обратном порядке.
10 = '+' - '!', 1 = ',' - '+', 29 = '[' - '>'. 32 же равно '!' - 1, т.е. тоже некая осмысленная разница.
В действительности единственное магическое число тут - это та самая 1 в '!' - 1, всё остальное укладывается в точную закономерность.
У такого расположения констант есть полезное свойство: если просуммировать хвост последовательности и добавить к сумме 1, то получится код одного из символов, которые мы хотим парсить:
'!'= 32 + 1'+'= 10 + 32 + 1','= 1 + 10 + 32 + 1...
']'= 2 + 29 + 2 + 14 + 1 + 1 + 1 + 10 + 32 + 1
Вероятно, парсинг будет происходить пользуясь именно этим свойством.
Строки 3-4
2 .... [
3 [>[->>]<[>>]<<-] <[<]<+>>[>]> [
4 <+>-[[<+>-]>]< [
5 ....
6 ]
7 ] <<
8 ] <Мы остановились на следующем состоянии массива перед заходом во внутренний цикл, тело которого мы сейчас будем анализировать. Назовём его «циклом анализа команды»:
{head, 0, 0, 0, 2, 29, 2, 14, 1, 1, 1, 10, [32], c, ...}.
В точности такое состояние будет только на первой итерации, более общий вид мы сможем получить только после анализа. Напомню, что в данном случае многоточие обозначает последовательность нулей.
Строка 3 состоит из 2-х кусочков: [>[->>]<[>>]<<-] и <[<]<+>>[>]>, рассмотрим их по очереди.>[->>]< (начало тела маленького цикла) делает из {..., [32], c, ...} следующее:{..., 32, c-1, [0], 0, ...}. Тут я подразумеваю, что ... справа состоит целиком из нулей. Последующий [>>] не должен ни на что влиять, так как текущий элемент - 0. Далее <<- понижает 32 до 31 и мы начинаем итерацию заново. К концу цикла мы должны получить следующее:{head, 0, 0, 0, 2, 29, 2, 14, 1, 1, 1, 10, [0], c-32, ...}.
Мы сделали вычитание, которое можно было достичь обычным [>-<-]. Зачем тогда так сложно? С этим разберёмся позже.
Код <[<]<+>>[>]> сперва пропускает все ненулевые элементы слева (<[<]):{head, 0, 0, [0], 2, 29, 2, 14, 1, 1, 1, 10, 0, c-32, ...}
потом увеличивает элемент слева от найденного нуля (<+>):{head, 0, 1, [0], 2, 29, 2, 14, 1, 1, 1, 10, 0, c-32, ...}
и наконец возвращается назад, добавляя ещё один сдвиг вправо (>[>]>):{head, 0, 1, 0, 2, 29, 2, 14, 1, 1, 1, 10, 0, [c-32], ...}.
Далее начинается ещё один вложенный цикл, в котором обязательно выполнится хоть одна итерация, ведь c-32 не равно 0. Назовём этот цикл «циклом переноса».
Строка 4 выглядит так: <+>- [[<+>-]>] < [, и это наша первая реальная точка ветвления. Здесь очень важно разграничить, является ли текущий элемент (c-32) единицей или нет.
Если текущий элемент равен
1, то<+>-превратит..., 0, [1], ...
в..., 1, [0], ...и дальнейший цикл не выполнит ни одной итерации. После цикла стоит смещение влево<, которое приведёт массив в состояние..., [1], 0, ....Если текущий элемент не равен
1, то после выполнения<+>-мы получим..., 1, [c-33], ...и запустим цикл. Тело цикла тут же запустит другой цикл[<+>-], который прибавит текущей элемент к элементу слева, попутно занулив текущий элемент:..., c-32, [0], .... После чего произойдёт критически важное действие:>перед выходом из цикла. Состояние станет следующим:..., c-32, 0, [0], .... После этого цикл завершится (мы стоим на0) и произойдёт финальный сдвиг влево.
Соберём всё сказанное в кучу.
Результат будет ..., [1], 0, ..., если с-32 == 1.
Результат будет ..., c-32, [0], ..., если с-32 != 1.
Получились разные позиции (что сейчас не так принципиально) и разные значения на текущих ячейках. Фактически мы сделали условное ветвление, сравнив c-32 с единицей и разрешив выполнять последующий цикл только в случае равенства.
Чтобы сразу не углубляться ещё в один вложенный цикл, положим сперва, что равенства с единицей не случилось. Конкретно сейчас это означает, что прочитанный символ c не равен '!' (33). В этом случае мы выйдем из цикла переноса (строка 7) и сделаем 2 сдвига влево (<<), встав в ячейку перед c-32, после чего начнём следующую итерацию цикла анализа команды, начиная со строки 3.
Состояние массива в начале 1-й итерации было следующим:{head, 0, 0, 0, 2, 29, 2, 14, 1, 1, 1, 10, [32], c, ...}.
В начале 2-й итерации оно будет таким:{head, 0, 1, 0, 2, 29, 2, 14, 1, 1, 1, [10], c-32, ...}.
Эти состояния очень похожи друг на друга, что неудивительно.
Что случится, если c != '+' (43)? Мы будем повторять те же самые рассуждения, дойдём до сравнения c-42 с 1, получим ответ «не равно» и в начале 3-й итерации массив станет следующим:{head, 0, 2, 0, 2, 29, 2, 14, 1, 1, [1], c-42, ...}.
Сказанное выше можно обобщить. Состояние{head, 0, i, 0, ..., n, [m], c', ...} мы превращаем в{head, 0, i+1, 0, ..., [n], c'-m, ...} если c' != m+1, т.е. найдена не «текущая» команда. i здесь - количество попыток сравнения команд, равно оно следующим величинам:
cmd |
|
|
|
|
|
|
|
|
|
i | 0 | 1 | 2 | 3 | 4 | 5 | 6 | 7 | 8 |
Строка 5
2 .... [
3 .... [
4 .... [
5 [[-]<]++<- [<+++++++++>[<->-]>>] >>
6 ]
7 ] <<
8 ] <Если нам на вход была подана корректная программа на Brainfuck, то рано или поздно мы найдём совпадающую команду, то есть выполнится условие c' == m+1. В этом случае состояние массива в начале цикла из 5-й строки будет следующим:{head, 0, i+1, 0, ..., n, [1], 0, ...}.
Код [[-]<] зануляет все ячейки слева до тех пор, пока не встретит уже нулевую ячейку:{head, 0, i+1, [0], ...}. Тем самым мы затираем все неиспользованные магические константы. Код ++<- превратит массив в следующий (зачем там именно 2 нам станет ясно значительно позже):{head, 0, [i], 2, ...}.
Дальнейший код представляет собой цикл, который выполнится только если i != 0 (эквивалентно условию c != '!'): [<+++++++++>[<->-]>>]. Сперва мы в нём запишем 9 слева от i (9 плюсов и сдвиги в начале):{head, 9, [i], 2, ...}. После этого код [<->-] произведёт вычитание:{head, 9-i, [0], 2, ...}. >> передвинет каретку:{head, 9-i, 0 , 2, [0], ...}. То есть на 5-й строке был не совсем цикл, а ещё одно условное ветвление.
После этого нужно не забыть про последний безусловный >>. Итак, мы можем находиться в 2-х разных состояниях.
{head, 0, 0, 2, [0], ...}еслиc=='!'.{head, 9-i, 0 , 2, 0, 0, [0], ...}иначе.
После этого идёт << на строке 7, после цикла переноса, который в обоих случаях поставит каретку на другой 0. Это позволит выйти из цикла парсинга и выполнить < со строки 8. Результат будет таков:
{head, [0], 0, 2, ...}еслиc=='!'.{head, 9-i, 0, [2], ...}иначе.
Если прочитанная команда была '!', то мы буквально завершаем весь парсинг. В противном случае мы находимся на значении 2, что гарантирует начало следующей итерации цикла парсинга. В новый head добавляется значение 9-i (результат назовём head') и следующую итерацию мы запускаем с массива{head', 0, [2], 0, 0, ...}, что очень похоже на{ head, 0, [?], 0, ?, ...}, с которого мы и начинали при анализе строки 2. Предположения о нулях оказались верными.
Итого, если задуматься, то финальное состояние после парсинга будет следующим:{0, 0, j0, j1, ..., jk, [0], 0, 2, ...}, где значения jm соответствуют командам кода, который мы распарсили, согласно следующей таблице:
cmd |
|
|
|
|
|
|
|
|
j | 8 | 7 | 6 | 5 | 4 | 3 | 2 | 1 |
На строке 9, после выхода из цикла, мы делаем сдвиг каретки влево и встаём на [jk], на этом парсинг полностью завершён.
Так что там с кодом на 3-й строке
Ранее в статье я писал:
Зачем тогда так сложно? Об этом будет позже.
2 .... [
3 [>[->>]<[>>]<<-] <[<]<+>>[>]> [
....
7 ] <<
8 ] <В Полагаю, что вы и так догадались - данный интерпретатор умеет игнорировать символы, не являющиеся нормальными командами языка Brainfuck. Некорректные команды могут прийти в 2-х видах:
В конце 3-й строки мы могли не зайти в цикл, если имели
c==32, например. Тогдаc-32было бы равно0.Фраза «Далее начинается ещё один вложенный цикл, в котором обязательно выполнится хоть одна итерация, ведьc-32не0.» была ложью.
Состояние массива в данном примере было бы следующим:{head, 0, 1, 0, 2, 29, 2, 14, 1, 1, 1, 10, 0, [0], ...}.
В цикл не заходим, на строке 7 выполняем<<и переходим на следующую итерацию цикла анализа команды в «таком же состоянии», в каком мы бы туда пришли, будьcнормальной:{head, 0, 1, 0, 2, 29, 2, 14, 1, 1, 1, [10], c-32, ...}(с== 32). Дальше при вычитании изcмагических констант мы будем получать отрицательные значения, которые точно снова не станут равны0, суммы магических констант банально не хватит для переполнения байта. Остальные «совпадения» (c== 42, 59, ...) будут выглядеть аналогичным образом.Если мы вычтем из
cвсе магические константы, но всё ещё не найдём нужную команду, то в последний раз цикл анализа команды мы «попытаемся исполнить» со следующими данными:{head, 0, 9, [0], c', ...}. Помним, что общий вид был{head, 0, i, 0, ..., n, [m], c', ...}.
Текущая ячейка -0, так что попытаемся исполнить мы неудачно, в цикл не зайдём. Вместо этого отработает<на строке 8 и состояние станет таким:{head, 0, [9], 0, c', ...}, что подозрительно похоже на{head, 0, [?], 0, ?, ...}, так мы в итоге обозначили состояние массива, необходимое для цикла парсинга. Помимо прочего, то ещё и единственная ситуация, где под вторым знаком вопроса скрывается не0.
Что же с тем странным циклом[>[->>]<[>>]<<-], который казалось бы можно заменить на[->-<]? Я конечно сам мог где-то накосячить в своём анализе, но при замене оригинального кода на мой, интерпретатор всё ещё продолжает отлично работать. Видимо автор просто забыл поправить финальный вариант своего кода...
Цикл 2. Интерпретация программы
Что имеем. Для программы [-] массив будет выглядеть так:{0, 0, 2, 6, [1], 0, 0, 2, ...}, а для программы >[-<+>>+<]< вот так:{0, 0, 3, 2, 6, 4, 8, 3, 3, 8, 4, 1, [4], 0, 0, 2, ...}.
Все команды представлены кодами из таблички ниже, в том же порядке, в котором парсились. Есть заголовок из 2-х нулей и загадочная 2 в хвосте.
cmd |
|
|
|
|
|
|
|
|
j | 8 | 7 | 6 | 5 | 4 | 3 | 2 | 1 |
Повторим код, который будем анализировать. Цикл со строки 10 будем называть «циклом интерпретации»:
....
10 [
11 [<]> [[>]>>[>>]+[<<]<[<]<+>>-]> [>] +[->>]<<<< [
12 [<<]<[<]+<<[+>+<<-[>-->+<<-[>+<[>>+<<-]]]>[<+>-]<]++>>-->[>]>>[>>]
13 ] <<
14 [
15 >>+<[[<]<]>[[<<]<[<]+[-<+>>-[<<+>++>-[<->[<<+>>-]]]<[>+<-]>]>[>]>]>[>>]>>
16 ]
17 <<[>>+>>+>>]<<[->>>>>>>>]<<[>.>>>>>>>]<<[>->>>>>]<<[>,>>>]<<[>+>]<<
18 [+<<]<
19 ]Строка 11
На первой итерации цикла интерпретации мы находимся в конце списка команд. Справедливо полагать, что это (нахождение где-то внутри списка команд, вероятно в конце) является условием выполнения цикла интерпретации и для всех остальных итераций. Пока неясно, каким образом в нужной ячейке образуется 0, являющийся условием выхода, но это мы обязательно выясним по ходу дела.
Для удобства полагаем, что сейчас первая итерация интерпретации, и что текущее состояние массива будет таким:{0, 0, a, b, [c], 0, 0, 2, ...}.
Первый же кусочек кода ([<]>) передвинет каретку на ячейку a:{0, 0, [a], b, c, 0, 0, 2, ...}. Может по совпадению, а может и нет, именно команду a мы должны интерпретировать, ведь она является началом программы. Можно сделать предположение, что 0 слева от a является разделительным и указывает на текущую команду. Запомним это предположение.
Далее идёт цикл [[>]>>[>>]+[<<]<[<]<+>>-]>, который (при условии, что a не 0):
[>]>>- передвигает каретку до2, стоящей сразу после списка команд:{0, 0, a, b, c, 0, 0, [2], ...}.[>>]+[<<]- пропускает пары ячеек справа до тех пор, пока не наткнётся на0, и увеличивает его до1. Потом возвращается обратно, при этом пропуская и2тоже. На первой итерации первый цикл[>>]выполнит только одну итерацию, в итоге мы получим такое состояние:{0, 0, a, b, c, [0], 0, 2, 0, 1, ...}.<[<]- это пропуск ненулевого хвоста команд. Помним, чтоa!=0, за ней и будет точка остановки:{0, [0], a, b, c, 0, 0, 2, 0, 1, ...}.<+>- увеличит ячейку слева от текущей:{1, [0], a, b, c, 0, 0, 2, 0, 1, ...}.>-уменьшитaна1. После этого цикл повторится, если результат не0:{1, 0, [a-1], b, c, 0, 0, 2, 0, 1, ...}.
После выхода из цикла стоит одинокий >, который переставит каретку на b.
Цикл выходит любопытный. Лучше всего разобрать его на конкретных значениях a:
{0, 0, [1], b, c, 0, 0, 2, ...}превратится в{1, 0, 0, [b], c, 0, 0, 2, 0, 1, ...}.{0, 0, [3], b, c, 0, 0, 2, ...}превратится в{3, 0, 0, [b], c, 0, 0, 2, 0, 1, 0, 1, 0, 1, ...}.{0, 0, [5], b, c, 0, 0, 2, ...}превратится в{5, 0, 0, [b], c, 0, 0, 2, 0, 1, 0, 1, 0, 1, 0, 1, 0, 1, ...}.
Произошло 2 вещи. Мы передвинули a влево на 2 клетки. Ранее мы делали предположение, что один из нулей наверное является разделителем команд. Что же, судя по всему разделителем является пара нулей, а не один ноль. Вторая вещь - мы поставили в хвосте количество единиц равное коду текущей команды.
В данной процедуре скрыта одна очень важная деталь - тот факт, что в области массива справа от списка команд мы всегда двигаемся по ячейкам через одну. Почему так может быть? Единственный вариант, который приходит мне на ум - мы пропускаем ячейки, представляющие собой состояние массива интерпретируемой программы. Подтвердится ли это предположение - увидим позже.
На 11-й строке осталось совсем немного кода. [>] просто пропускает код программы, это действие симметрично [<]>, встреченному вначале 11-й строки:{a, 0, 0, b, c, [0], 0, 2, 0, 1, ...} (тут многоточие - это уже необязательно только нули).
Последний же мини-цикл +[->>] делает страшное - он стирает часть только что записанных данных! Начинаем с того, что на текущий 0 ставим 1 (чтобы выполнить хоть одну итерацию), а потом отнимаем 1 от всего, что увидим, с шагом через один.
После этого:
{1, 0, 0, b, c, [1], 0, 2, 0, 1, ...}превратится в{1, 0, 0, b, c, 0 , 0, 1, 0, 0, 0, [0], ...}.{3, 0, 0, b, c, [1], 0, 2, 0, 1, 0, 1, 0, 1, ...}превратится в{3, 0, 0, b, c, 0 , 0, 1, 0, 0, 0, 0, 0, 0, 0, [0], ...}.{5, 0, 0, b, c, [1], 0, 2, 0, 1, 0, 1, 0, 1, 0, 1, 0, 1, ...}превратится в{5, 0, 0, b, c, 0 , 0, 1, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, [0], ...}.
В зависимости от того, какую команду мы выполняем, количество нулей слева от каретки (с учётом пропусков) будет разным. Последующий же <<<< частично даёт понять, зачем это нужно:
Для
a==1получим{1, 0, 0, b, c, 0, 0, [1], ...}.Для
a==3получим{3, 0, 0, b, c, 0, 0, 1 , 0, 0, 0, [0], ...}.Для
a==4получим{4, 0, 0, b, c, 0, 0, 1 , 0, 0, 0, 0 , 0, [0], ...}.
Последующий цикл (строка 12) выполнится только если a == 1, т.е. соответствует команде ]. Нули каким-то образам обеспечивают нам условное ветвление.
Что есть цикл?
Да, я серьёзно. Отвлечёмся ненадолго.
Если вспомнить, что я писал в начале статьи, то код [ code ] соответствует псевдокодуwhile (*p != 0) { code; }. Но [ и ] - 2 отдельные команды. Каким конкретно частям псевдокода они соответствуют?
В реальности скомпилированный цикл должен выглядеть следующим образом:
LOOP:
if (*p != 0) GOTO END;
code;
GOTO LOOP;
END:
...[ - это строка if (*p != 0) GOTO END;, а ] - это строка GOTO LOOP;. Ровно такой же GOTO LOOP; мы ожидаем сейчас найти в коде на Brainfuck.
Технически, всё, что этот GOTO LOOP; должен делать - это найти открывающую квадратную скобку, парную текущей ], и считать её «новой текущей командой». Всё сводится к поиску парной скобки в строке. Чтобы проще было понять код на Brainfuck, рассмотрим псевдокод высокого уровня:
int pos; // Позиция текущей ячейки.
byte* array; // Указатель на голову массива.
...
// pos сейчас - это позиция ']'.
// Переведём его в позицию, соответствующую парной '['.
int cnt = 0;
while (true) {
if (array[pos] == ']') cnt++;
if (array[pos] == '[') {
cnt--;
if (cnt == 0) break;
}
pos--;
}Здесь с помощью вспомогательной переменной cnt мы контролируем то, сколько скобок нам встретилось по пути к голове массива. Это помогает отличить нужную [ от какого-нибудь вложенного цикла. Логично ожидать, что код на Brainfuck будет делать примерно то же самое. Мне вот неизвестно более простого алгоритма поиска парной скобки. Если известно вам - обязательно сообщите в комментариях.
Строка 12
11 .... [
12 [<<]<[<] +<<[+>+<<-[>-->+<<-[>+<[>>+<<-]]]>[<+>-]<] ++>>-->[>]>>[>>]
13 ] <<Код на строке 12 выполнится только если текущая команда - ]. Состояние массива в таком случае должно быть следующим (1 в самом начале - код команды ]):{1, 0, 0, b, c, 0, 0, [1], ...}. [<<]< выполняет уже привычное нам действие, встаёт на последнюю команду в программе:{1, 0, 0, b, [c], 0, 0, 1, ...}.
[<]+<< сдвинет каретку на второй 0 в разделителе, запишет вместо него 1 и сдвинется влево дважды, до стоящей там a == 1:{[1], 0, 1, b, c, 0, 0, 1, ...}. Выставленная единица - может оказаться копией a, а может чем-то иным, пока что непонятно и с выводами я спешить не буду.
Дальнейший код расставит всё на свои места:[+>+<<- [>-->+<<-[>+<[>>+<<-]]] >[<+>-]<].
Первым делом мы увеличиваем текущую ячейку, ячейку справа от нас, и уменьшаем ячейку слева от нас.
Ячейку слева от нас...
Но слева от нас нет ячейки, мы в самом начале массива:{?-1} {2, 1, 1, b, c, 0, 0, 1, ...}.
Вообще логично, тут нет никаких противоречий. Программа, начинающаяся с ], не является нормальной программой на Brainfuck и вполне может сломаться. Парность скобок в ней не соблюдена.
Что же, положим, что перед ] есть и другие команды (x, y и z), среди которых будет происходить поиск [:{x, y, z , [1], 0, 1, b, c, 0, 0, 1, ...} превратится в{x, y, [z-1], 2 , 1, 1, b, c, 0, 0, 1, ...}, ничего нигде не сломается.
Стоящий далее [>-->+<<-[>+<[>>+<<-]]] выполнится только если z != 1 (не соответствует ещё одной ]). Давайте сперва положим, что z == 1, чтобы отложить этот сложный кусок на попозже. Тогда начнёт выполняться цикл >[<+>-]<, понять который уже несложно, это код для прибавления одной ячейки к другой, встречается не первый раз:{x, y, [2], 0, 1, 1, b, c, 0, 0, 1, ...}. Сравнив это с состоянием до:{x, y, z, [1], 0, 1, b, c, 0, 0, 1, ...} заключаем, что текущая ячейка - это количество встреченных нам ]. Назовём код >[<+>-]< «кодом переноса счётчика». Если поставить вместо единиц соответствующие буквы a и z, то станет ещё понятнее:{x, y, z, [1], 0, a, b, c, 0, 0, 1, ...} - было,{x, y, [2], 0, z, a, b, c, 0, 0, 1, ...} - стало. Мы просто пропустили скобку и инкрементировали счётчик (соответствующий переменной cnt из псевдокода).
«На попозже» настало, разберём теперь что будет делать код, если z != 1. Счётчик cnt я буду обозначать как i. Итак, в массиве записано{x, y, [z-1], i+1, 1, 1, b, c, 0, 0, 1, ...} и мы выполняем код[>-->+<<-[>+<[>>+<<-]]]. Первым делом он превращает увеличенную i+1 в i-1 (выполняя >--):{x, y, z-1, [i-1], 1, 1, b, c, 0, 0, 1, ...}. После чего трогает ещё несколько ячеек (>+<<-) и собирается выполнять (или не выполнять) цикл [>+<[>>+<<-]]:{x, y, [z-2], i-1, 2, 1, b, c, 0, 0, 1, ...}.
Цикл [>+<[>>+<<-]] выполнится только если z != 2. Поступим как в прошлый раз и сперва проверим что будет, если z == 2 (что соответствует команде [).
Тогда снова выполнится код переноса счётчика (>[<+>-]<) и мы получим такое состояние:{x, y, [i-1], 0, 2, 1, b, c, 0, 0, 1, ...}, или другими словами{x, y, [i-1], 0, z, a, b, c, 0, 0, 1, ...}.
Опять же, как и ранее это состояние соответствует декременту счётчика cnt из приведённого ранее псевдокода. И, что очень удобно, каретка как раз стоит на этом самом счётчике, т.е. i == 0 приведёт к выходу из цикла, парная скобка найдена!
Остался последний вариант: что если z вообще не является прямоугольной скобкой.
Тогда мы собираемся выполнить код [>+<[>>+<<-]] находясь в следующем состоянии:{x, y, [z-2], i-1, 2, 1, b, c, 0, 0, 1, ...}.
Первым делом этот код превратит i-1 обратно в i (>+<):{x, y, [z-2], i, 2, 1, b, c, 0, 0, 1, ...},
после чего [>>+<<-] перенесёт z за счётчик:{x, y, [0], i, 2, 1, b, c, 0, 0, 1, ...},
а затем уже код переноса счётчика (>[<+>-]<) перенесёт i в нужную позицию:{x, y, [i], 0, z, 1, b, c, 0, 0, 1, ...}.
Если z - не скобка, то она просто переносится за разделитель, а счётчик остаётся неизменным.
Конец 12-й строки
Какая же строка 12 длинная. В конце неё, когда парная [ уже найдена, будет выполнен следующий код: ++>>-->[>]>>[>>]. В наших обозначениях z - это [, а a - это ]. Между ними, в общем случае, были пропущены какие-то команды, обозначим их p, ..., q. Текущее состояние тогда будет выглядеть вот так:{x, y, [0], 0, z, p, ..., q, a, b, c, 0, 0, 1, ...}.
Первым же делом происходит перенос z в позицию до разделителя (++>>--):{x, y, z, 0, [0], p, ..., q, a, b, c, 0, 0, 1, ...}.
Тут не циклы потому, что нам и так известно, что z == 2. Достаточно ++ и --.
Уже хорошо знакомый >[>] перенесёт каретку за список команд.>>[>>] пропустит все единицы и встанет на следующий за ними 0:{x, y, z, 0, 0, p, ..., q, a, b, c, 0, 0, 1, 0, [0], ...}.
Этот шаг хитрее, чем может показаться на первый взгляд. Как бы выглядел массив из конца анализа строки 11, если бы мы сейчас на самом деле обрабатывали команду [?
Вот так, пробелы добавил для удобства сравнения:{ 2, 0, 0, b, c, 0, 0, 1, 0, [0], ...}.
Как выглядит массив сейчас (помним, что z == 2):{x, y, 2, 0, 0, p, ..., q, a, b, c, 0, 0, 1, 0, [0], ...}.
Состояния идентичны. Вот уж воистину GOTO LOOP;. Тихонько произвели поиск парной скобки ([) и делаем вид, что на самом деле её и обрабатываем.
Строка 15
13 ] <<
14 [
15 >>+<[[<]<]> [[<<]<[<]+ [-<+>>-[<<+>++>-[<->[<<+>>-]]]<[>+<-]>] >[>]>] >[>>]>>
16 ]На строке 13 мы делаем << и либо попадаем на 1 если текущая команда - [, либо попадаем на 0 если текущая команда - не команда цикла. 0 рассматривать не интересно - мы не зайдём в код 15-й строки, состояние массива в этом случае мы легко отследим позже. Положим, что текущая команда как раз равна [.
Итак, массив выглядит следующим образом:{x, y, z, 0, 0, p, ..., q, a, b, c, 0, 0, [1], ...}.
Команда [ должна выполнить if (*p != 0) GOTO END;, а значит она должна проанализировать данные в массиве интерпретируемой программы (аналог *p).>>+< встанет в нужное место, предварительно поставим ещё одну 1 справа от этого места:{x, y, z, 0, 0, p, ..., q, a, b, c, 0, 0, 1, [?], 1, ...}.
В области после интерпретируемого кода мы всегда двигались через 2 клетки и предполагали, что в пропусках лежат данные интерпретируемой программы. Теперь у этой гипотезы есть подтверждение. Ячейку, которую будем сравнивать с 0, я обозначу d:{x, y, z, 0, 0, p, ..., q, a, b, c, 0, 0, 1, [d], 1, ...}. Все остальные ячейки массива интерпретируемого кода я в дальнейшем буду обозначать ?.
Дальше должно идти условное ветвление. Код [[<]<]> просто сдвинет каретку вправо, если d == 0 (т.е. встанет на стоящую там единицу), либо же сделает кое-что интересное, если d != 0, а именно найдёт 2 подряд стоящих нуля
(> в конце ставит каретку на второй ноль):{x, y, z, 0, 0, p, ..., q, a, b, c, 0, [0], 1, d, 1, ...}.
Достигается это сложным условием выхода из цикла - двумя идущими подряд <]<]. А 2 нуля у нас ожидаются только сразу после списка команд и перед стоящей там единицей, после них все данные имеют вид ..., 1, ?, 1, ?, ....
Так как после этого идёт достаточно большой кусок кода в цикле, то сперва предположим что он не выполнится, т.е. что d != 0 и в текущей ячейке 0. Согласно нашему описанию команды [, дальнейшее действие должно быть равносильно NOOP - интерпретатор должен потом взять команду, стоящую за [, и выполнять её.
После пропущенного цикла нас ждёт код >[>>]>>, который вернёт нас в предыдущую позицию за последней единицей, и зачем-то отодвинет каретку ещё 2 раза вправо:{x, y, z, 0, 0, p, ..., q, a, b, c, 0, 0, 1, d, 1, ?, 0, ?, [0], ...}. Смысл этого действия пока не ясен, отложим разбирательство на потом.NOOP действительно произошёл, просто завершился в странном месте.
Если же d == 0, то выполняем цикл[[<<]<[<]+ [-<+>>-[<<+>++>-[<->[<<+>>-]]]<[>+<-]>]>[>]>].
Кодом [<<]<[<]+ из положения {x, y, z, 0, 0 , p, ..., q, a, b, c, 0, 0, 1, d, [1], ...}
мы сдвигаем каретку ([<<]<[<]) к разделителю команд и ставим там 1.{x, y, z, 0, [1], p, ..., q, a, b, c, 0, 0, 1, d, 1, ...}.
По логике вещей, сейчас мы должны начать поиск парной закрывающейся скобки ], чтобы выйти из цикла. Логично ожидать для этого примерно тот же алгоритм, что мы уже разбирали ранее, только слева направо, а не справа налево.
И действительно, текущий код выглядит так:[-<+>>-[<<+>++>-[<->[<<+>>-]]]<[>+<-]>],
а код поиска парной [ выглядел так:[+>+<<-[>-->+<<-[>+<[>>+<<-]]]>[<+>-]<].
Практически одно и то же, так что разбирать алгоритм повторно смысла нет.
После же идёт >[>]>, выводящий нас из ветки d == 0:{x, ..., q, a, 0, 0, b, c, 0, [0], 1, d, 1, ...}.
За ним код >[>>]>>, ставящий нас на то же место, в котором мы закончили
при условии d != 0:{x, ..., q, a, 0, 0, b, c, 0, 0, 1, d, 1, ?, 0, ?, [0], ...}.[ обработана, строка 15 завершена.
Строка 17
11 .... [
12 ....
13 ] <<
....
16 ]
17 <<[>>+>>+>>] <<[->>>>>>>>] <<[>.>>>>>>>] <<[>->>>>>] <<[>,>>>] <<[>+>] <<На 17-й строке мы видим 6 циклов. Согласно текущей тенденции, они должны отвечать за обработку оставшихся шести команд. Напомню табличку:
cmd |
|
|
|
|
|
|
|
|
j | 1 | 2 | 3 | 4 | 5 | 6 | 7 | 8 |
Так же вспомним, каким было состояние в конце исполнения строки 11:
Для
a==3получим{3, 0, 0, b, c, 0, 0, 1, ?, 0, ?, [0], ...}.Для
a==4получим{4, 0, 0, b, c, 0, 0, 1, ?, 0, ?, 0, ?, [0], ...}....
a в этом контексте - текущая интерпретируемая команда. После сдвигов со строки 13 состояния станут следующими:
Для
a==3получим{3, 0, 0, b, c, 0, 0, 1, ?, [0], ...}.Для
a==4получим{4, 0, 0, b, c, 0, 0, 1, ?, 0, ?, [0], ...}.Для
a==5получим{5, 0, 0, b, c, 0, 0, 1, ?, 0, ?, 0, ?, [0], ...}....
Память освежили. Количество нулей у нас соответствовало коду команды. Следующая на очереди как раз a == 3, то есть команда >. После сдвига << из самого начала строки 17 мы встанем на единицу только в том случае, если a == 3, дальнейший цикл обрабатывает именно эту ситуацию.
[>>+>>+>>] сделает из {3, 0, 0, b, c, 0, 0, [1], ...} следующее:{3, 0, 0, b, c, 0, 0, 1, ?, 1, ?, 1, ?, [0], ...}.
Очень странно, мы должны были сдвинуть каретку интерпретируемой программы на 1 ячейку вправо, что должно бы соответствовать добавлению одной единицы справа, а не двух. Более того, мы поставили себя в интересное положение - следующее же выполнение << (код после [>>+>>+>>]) поставит каретку снова на единицу!
А что у нас может означать 1 после следующего <<? Только обработку команды с номером 4, т.е. <. Совершена очередная хитрость - вместо адекватного выполнения > интерпретатор делает >><. Запутано, зато код короткий! Вообще говоря, случай a == 3 на этом закончен. Мы наконец добрались почти до самого конца программы и все циклы тут очень короткие.
Перед выполнением команд из кода <<[->>>>>>>>] вспомним, как бы выглядел наш массив если бы выполнилось a == 4. Вот так:{4, 0, 0, b, c, 0, 0, 1, ?, [0], ...}.
Как бы выглядел массив, если бы выполнилось a == 3? Вот так:{3, 0, 0, b, c, 0, 0, 1, ?, 1, ?, 1, ?, [0], ...}.
Как бы выглядел массив, если бы выполнилось a == 1 или a == 2? Помним:{x, ..., q, a, 0, 0, b, c, 0, 0, 1, d, 1, ?, [0], ...}.
Все эти случаи объединяет одно, после << мы встанем на 1 и выполним код обработки команды >.
Почему это нужно делать для a == 3 кажется уже разобрались.
Для a == 1 или a == 2 будет что-то очень похожее, только вместо логической операции < нас на самом деле интересует банальное зануление 1, идущей после d, и выставление каретки в нужное положение.
Что за положение кстати:{..., [1], ?, 0, ...} превратится в{..., 0 , ?, 0, ?, 0, ?, 0, ?, [0], ...}. Мы опять убежали куда-то вправо.
Чтобы понять, чем важно именно это количество нулей, распишем все остальные команды в момент времени после завершения <<[->>>>>>>>].
Для
a==1,2,3,4:{..., 1, ?, 0, ?, 0, ?, 0, ?, 0, ?, [0], ...}.Для
a==5:{..., 1, ?, [0], ...}.Для
a==6:{..., 1, ?, 0, ?, [0], ...}.Для
a==7:{..., 1, ?, 0, ?, 0, ?, [0], ...}.Для
a==8:{..., 1, ?, 0, ?, 0, ?, 0, ?, [0], ...}.
Состояние в первом и последнем случаях отличаются позицией ровно на 2 ячейки. Запомним данный инвариант, пригодится.
Что делает обработчик команды a == 5 (<<[>.>>>>>>>])? Превращает{..., 1, ?, [0], ...} в{..., 1, A, 0, ?, 0, ?, 0, ?, [0], ...}.A здесь - это символ, введённый с помощью команды ..
Если a != 5, то будет просто сдвиг, и для a == 8 (в частности) массив будет выглядеть так:{..., 1, ?, 0, ?, 0, ?, [0], ...}. Снова разница ровно в 2 позиции. Хороший инвариант, пока что пригождается. Любые обработанные команды в конечном итоге приводят к аналогичному результату.
Команда a == 6 (<<[>->>>>>]) соответствует - и превращает{..., 1, A, [0], ...} в{..., 1, A-1, 0, ?, 0, ?, [0], ...}. Снова та же история, инвариант тоже сохранится.
Команда a == 7 (<<[>,>>>]) печатает символ на консоль. Превращает{..., 1, A, [0], ...} в{..., 1, A, 0, ?, [0], ...}.
Последняя команда a == 8 (<<[>+>]) соответствует +. Она превращает{..., 1, A, [0], ...} в{..., 1, A+1, [0], ...}.
Если же вспоминать наш чудесный инвариант, то видно, что и для всех остальных a мы закончим таким же образом:{..., 1, ?, [0], ...}
<<, стоящий в самом конце 17-й строки, всегда перемещает каретку на 1, которая находится перед текущей ячейкой в массиве интерпретируемой программы. Фух.
Строка 18
18 [+<<]<
19 ]Помните цикл с 11-й строки ([->>]), который «стирал часть данных», а встречающиеся 2 заменял на 1? Данный цикл [+<<]< возвращает всё взад, заменяя встречающиеся 1 на 2.
А когда он закончит, то будет стоять на последней команде в списке команд (либо на 0-разделителе, если текущая команда была последней).
Разбор кода закончен =)
Как же в итоге выглядит состояние массива при интерпретации? Состоит он из двух частей: из интерпретируемого кода и из состояния интерпретируемого кода:
{x, y, z, ..., p, 0, 0, q, ..., a, b, [c], 0, 0, 2, ?, ..., 2, ?, 0, ?, ...}
^^^^^ Интерпретируемая программа ^^^^^^^ ^
^ |
текущая команда |
каретка интерпретируемой программыКаретка в начале цикла интерпретации находится в конце списка команд. Если разделитель списка команд (первый 0, 0) находится в конце списка команд, то каретка будет стоять на 0. После списка команд идёт дополнительный разделитель 0, 0. За ним чередуются данные интерпретируемой программы, обозначенные как ?, и последовательность из 2, которая продолжается вплоть до каретки интерпретируемой программы. Как бы всё.
Заключение
Программирование на Brainfuck - это отдельный вид искусства. В нём прежде всего ценится размер программы и число затронутых при исполнении ячеек массива. По обоим этим параметрам приведённый интерпретатор почти безупречен и может спокойно использоваться как учебное пособие по Brainfuck, ведь в нём используется большое количество весьма хитрых приёмов.
Но у короткого и эффективного кода есть цена - сложность. Так что покончим с лестью. Программирование на Brainfuck - это пытка над собственным мозгом. В нём приходится выдумывать супер-хитрые приёмы для выполнения элементарных действий. Пока код этого интерпретатора разберёшь, 10 раз голову себе сломаешь. Так что единственная практическая ценность, которую я здесь вижу - это набор весьма нетривиальных интеллектуальных упражнений, которые приходится выполнять при написании/чтении кода. Бывает полезно выйти из зоны комфорта и размять своё серое вещество, других плюсов нет.
Тем отчаянным, кто разобрал со мной весь код целиком, от меня низкий поклон. Спасибо!
