Brainfuck — один из самых популярных эзотерических языков программирования . Написание интерпретатора Brainfuck — это весело, в отличие от реального использования этого «языка». Синтаксис очень прост и семантика довольно ясна. Таким образом, написание такого интерпретатора является хорошим кандидатом для сеанса ката , практики TDD и т. Д. Использование Clojure для этой задачи несколько сложнее из-за несоответствия внутреннего сопротивления императивному Brainfuck и функциональному Clojure. Однако вы найдете множество существующих реализаций ( [1] , [2] , [3] , [4] ), многие из них менее идиоматичны, поскольку используют атомы для изменения состояния на месте ( [5] , [6] ,[7] , [8] , [9] ).
Давайте напишем простой, идиоматический интерпретатор мозгового штурма, шаг за шагом. Оказывается, что переход от изменчивости к неизменности довольно прост — вместо того, чтобы мутировать состояние на месте, мы просто обмениваем предыдущее состояние с новым. В Brainfuck состояние представлено cells
(память), cell
(указатель на один из cells
, индекс внутри cells
) и ip
( указатель инструкции , инструкция выполняется в настоящее время):
(loop [cells [0N], cell 0, ip 0] ; interpretation (recur cells cell (inc ip)))
Я не изменяю ни одну из переменных состояния (фактически, я не могу по определению), но в каждой итерации я создаю новый набор переменных состояния, отбрасывая старые. Как правило, мы по крайней мере увеличиваем указатель инструкции (чтобы оценить следующую инструкцию в программе), но возможно больше. Вот и все, в каждой итерации мы читаем один символ
program
(последовательность кодов операции brainfuck) и переходим к соответственно обновленному состоянию:
(loop [cells [0N], cell 0, ip 0] (condp = (get program ip) \> (recur cells (inc cell) (inc ip)) \< (recur cells (dec cell) (inc ip)) \+ (recur (update-in cells [cell] inc) cell (inc ip)) \- (recur (update-in cells [cell] dec) cell (inc ip)) ; more to come (recur cells cell (inc ip))))
Это должно быть самоочевидным —
>
и
<
перемещать
cell
указатель while
+
и
-
увеличивать / уменьшать текущую ячейку соответственно. Во всех случаях указатель инструкции увеличивается, чтобы выполнить следующую инструкцию во время следующей итерации. Все идет нормально. Код для
>
на самом деле немного сложнее для достижения бесконечного роста
cells
вектора, но это не имеет значения. Обработка петель в мозговом потоке более интересна. Каждый раз, когда мы сталкиваемся с открывающей квадратной скобкой, мы условно перескакиваем на
соответствующую (
не встречаемую) закрывающую скобку. Немного логики требуется, чтобы справиться с этим:
(defn brainfuck-interpreter [& lines] (let goto-bracket (fn [same-bracket other-bracket ip dir] (loop [i (dir ip) opened 0] (condp = (nth program i) same-bracket (recur (dir i) (inc opened)) other-bracket (if (zero? opened) i (recur (dir i) (dec opened))) (recur (dir i) opened))))] (loop [cells [0N], cell 0, ip 0] (condp = (get program ip) \[ (recur cells cell (inc (if (zero? (nth cells cell)) (goto-bracket \[ \] ip inc) ip))) \] (recur cells cell (goto-bracket \] \[ ip dec)) ;... nil cells (recur cells cell (inc ip))))))
Открывающая скобка переходит на соответствующую закрывающую скобку, если текущая ячейка равна нулю, и в противном случае переходит к следующей инструкции. Закрывающая скобка безусловно переходит на соответствующую открывающую скобку. Думайте о них как о вложенных
while
циклах. Угадайте что, мы только что внедрили интерпретатор brainfuck на функциональном языке, вообще не изменяя состояния! Ниже приведен полный исходный код, включая нечистые операции ввода-вывода и весь поддерживающий код:
(ns com.blogspot.nurkiewicz.brainfuck.interpreter) (defn brainfuck-interpreter [& lines] (let [program (apply str lines) goto-bracket (fn [same-bracket other-bracket ip dir] (loop [i (dir ip) opened 0] (condp = (nth program i) same-bracket (recur (dir i) (inc opened)) other-bracket (if (zero? opened) i (recur (dir i) (dec opened))) (recur (dir i) opened))))] (loop [cells [0N], cell 0, ip 0] (condp = (get program ip) \> (let [next-ptr (inc cell) next-cells (if (= next-ptr (count cells)) (conj cells 0N) cells)] (recur next-cells next-ptr (inc ip))) \< (recur cells (dec cell) (inc ip)) \+ (recur (update-in cells [cell] inc) cell (inc ip)) \- (recur (update-in cells [cell] dec) cell (inc ip)) \. (do (print (char (nth cells cell))) (recur cells cell (inc ip))) \, (let [ch (.read System/in)] (recur (assoc cells cell ch) cell (inc ip))) \[ (recur cells cell (inc (if (zero? (nth cells cell)) (goto-bracket \[ \] ip inc) ip))) \] (recur cells cell (goto-bracket \] \[ ip dec)) nil cells (recur cells cell (inc ip))))))
Использовать этот интерпретатор довольно просто. Завершается, когда встречается с концом программы.
brainfuck-interpreter
возвращает состояние в том виде, в каком оно было по окончании, чтобы упростить модульное тестирование. Этот проект
доступен на GitHub , но это была просто разминка. В следующей статье мы напишем компилятор брейкфук
в Clojure. В 100 строк кода. Будьте на связи!