Статьи

Brainfuck в Clojure. Часть I: переводчик

Март 30, 2018

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 строк кода. Будьте на связи!

45
Share: