Под катом вы найдете самую ненормальную реализацию интерпетатора Brainfuck с помощью нормальных алгоритмов Маркова. В этой реализации все операторы Brainfuckа и сам интерпретатор являются нормальными алгоритмами Маркова. Целью этого поста было рассмотреть Brainfuck с точки зрения классической теории алгоритмов и привести его реализацию с помощью какого-либо классического уточнения понятия алгоритма. Кто не боится причинить своему мозгу вред столь ненормальным программированием добро пожаловать (под катом много текста, иногда сложного для понимания если не знаком с теорией алгоритмов, но в конце поста есть ссылка на реализацию этого интерперетатора, который можно попробовать в действии). Его быстродействие, по понятным причинам не очень высоко, но с точки зрения понимания алгоритмов работы он очень наглядный.

Как родилась такая идея

Все началось с того, что масса постов о Brainfuck на хабре подбила меня все же выучить что это такое. Кроме того на этот пост меня натолкнул мой друг, тоже программист, который сказал что-то вроде:«Раз ты мучаешь студентов в универе этой теорией алгоритмов, то опиши интерпретатор Brainfuck с помощью примитивно рекурсивной функции». Эта фраза и плохая погода и настроение и подтолкнула к тому, что получилось. Поскольку хабр ИТ а не математический ресурс, то вместо реализации с помощью рекурсивных функций мне показалось более правильным сделать реализацию с помощью нормальных алгоритмов Маркова.
Чтобы познакомиться с основными понятиями, которые будут встречаться можно почитать:
Brainfuck;
Рекурсивные функции;
Нормальный алгоритм Маркова.

Собственно полнейший Brainfuck

Как известно, Brainfuck является Тьюринг полным языком, что теоретически позволяет реализовать с его помощью любой алгоритм. Давайте посмотрим чем же является Brainfuck с точки зрения теории алгоритмов. Наиболее точно можно охарактеризовать его как некий гибрид машины Тьюринга и машины с натуральнозначными регистрами. Поскольку Brainfuck является Тьюринг полным, то значит его можно реализовать как на машине с натуральнозначными ре��истрами так и на машине Тьюринга, рекурсивных функциях, алгоритмах Маркова(чем я и занялся).
И так, что реализовано:
Команда Brainfuck
 Описание команды
 Реализовано?
>
 перейти к следующей ячейке
 Реализовано.
<
 перейти к предыдущей ячейке
 Реализовано.
+
 увеличить значение в текущей ячейке на 1
 Реализовано.
-
 уменьшить значение в текущей ячейке на 1
 Реализовано.
.
 напечатать значение из текущей ячейки
 Реализовано.
,
 ввести извне значение и сохранить в текущей ячейке
 Не реализовано, так эта операция не представляет особого интереса с точки зрения алгоритмов Маркова
[
 если значение текущей ячейки нуль, перейти вперёд по
тексту программы на ячейку, следующую за соответствующей ] (с учётом
вложенности)
 Реализовано.
]
 если значение текущей ячейки не нуль, перейти назад по
тексту программы на символ [ (с учётом вложенности)
 Реализовано.


Что нужно для реализации интерпретатора на нормальных алгоритмах Маркова: строка, в которую будем вводить код на брейнфаке(без оператора "," ), строка выполняющая роль ленту памяти, строка буффера(для вывода результата), строка для вывода результата.

При начале работе интерпретатора строка-лента должна иметь вид
._…
Количество точек — это количество доступных ячеек памяти, символ _ — указатель на текущую ячейку.
Продукции алгорима Маркова будем задавать в виде двух массивов строк одинаковой длины: первый — левые части продукций, второй — правые. Если правая часть продукции заканчивается на FIN, то это значит что эта продукция будет финальной.
Начнем с того, что проще — реализация операций брейнфака алгоритмами Маркова.

Команда Brainfuck
 Реализация алгоритмом Маркова
>
 В строке-ленте:
string[] left = new string[5] { "|_.", "@_|", "@_.", "_..", "_.|" };
string[] right = new string[5] { "|.@_", "|@_", "_.FIN", "._.FIN", ".@_" };
<
 В строке-ленте:
string[] left = new string[2] { "|_", "._" };
string[] right = new string[2] { "_|", "_.FIN" };
+
 В строке-ленте:
string[] left = new string[1] { "_"};
string[] right = new string[1] { "|_FIN"};
-
 В строке-ленте:
string[] left = new string[1] { "|_" };
string[] right = new string[1] { "_FIN" };
.
 В строке-буффере:
| > .a
a. >.a
.. >.
.aaaaaaaaaa > a,.
,a > a,
.aaaaaaaaa > 9
.aaaaaaaa > 8
.aaaaaaa > 7
.aaaaaa > 6
.aaaaa >5
.aaaa > 4
.aaa > 3
.aa > 2
.a > 1
. > 0
, >
a > .a
тут печатаем в строку OUT символ с номером из буфера
1>0
2>0
3>0
4>0
5>0
6>0
7>0
8>0
9>0
00>0
[
 В строке-исходнике(учитывает влож��нность [])
string[] left = new string[10] { "_+", "_-", "_.", "_,", "_<", "_>","_[","_]","**","]*" };
string[] right = new string[10] { "+_", "-_", "._", ",_", "<_", ">_","[__","]*","_","]_FIN" };
]
 В строке-исходнике(учитывает вложенность [])
string[] left = new string[11] { "+_", "-_", "._", ",_", "<_", ">_", "]_", "[_", "*_","[**", "[*" };
string[] right = new string[11] { "_+", "_-", "_.", "_,", "_<", "_>", "__]", "[*","**", "_[", "_[FIN" };

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

Что заменить На что заменить Вызываемый подалгоритм
_+ +_ +
_- -_ -
_[ [_ [
_> >_ >
_< <_ <
_] Если на строке-ленте можно выполнить продукцию
._. на ._.FIN, то
]_
иначе вызов подалгоритма ]
 ]
_. ._ .

У Вас есть возможность выполнить всю программу сразу или выполнять ее шаг за шагом. Реализация на С#, так что для ее работы нужен установленный .NET 2.0.
Демонстарция работа классического Hello World! на Brainfuck на этом интерпретаторе.
image

P.S. Надеюсь это было хоть кому-нибудь интересно. Старался уложится �� максимально небольшой объем текста.
Реализация интерпретатора. Можете попробовать этого монстрика в работе.