В прошлый раз мы разработали интерпретатор Brainfuck в Clojure . На этот раз мы напишем компилятор. Компиляция имеет два преимущества перед интерпретацией: результирующая программа имеет тенденцию работать быстрее, а исходная программа теряется / скрывается в двоичном виде. Оказывается, компилятор brainfuck (для любой сборки / байт-кода) на самом деле не так уж и сложен — brainfuck очень низкого уровня и похож на типичные архитектуры ЦП (кусок изменяемой памяти, изменяемый по одной ячейке за раз). Таким образом, мы пойдем на что-то немного другое. Вместо создания байт-кода JVM (что некоторые уже сделали ) мы напишем макрос Clojure, который будет генерировать код, эквивалентный любой программе brainfuck. Другими словами, мы создадим исходный код Clojure, эквивалентный исходному мозгу — во время компиляции.
Эта задача на самом деле более сложная, потому что идиоматический Clojure сильно отличается от идиоматического мозгового хуя (если когда-либо существовала такая вещь, как « идиоматический мозговый хуй »). Давайте сначала подумаем, как может выглядеть такой код Clojure, а затем напишем генератор / переводчик. В сущности, каждая программа для мозгового меха — это последовательность шагов, каждое изменяющееся состояние (или создание нового состояния на основе текущего). Например (обратитесь к обзору языка brainfuck, если у вас его еще нет, всего 8 команд) перевод из » ++>-<» в brainfuck на Clojure может выглядеть следующим образом:
(let [state {:ptr 0, :cells [0N]}]
(-> state
cell-inc
cell-inc
move-right
cell-dec
move-left)
Сначала мы определяем неизменяемость
state(массив
cellsс одним элементом и
ptrиндексом) для текущей ячейки, а затем применяем последовательность преобразований поверх нее. Каждое преобразование дает новое состояние.
->Макрос представляет собой синтаксический сахар, более читабельным , чем:
(move-left
(cell-dec
(move-right
(cell-inc
(cell-inc state))
Хорошо, давайте определим все эти преобразования:
(let [state {:ptr 0, :cells [0N]}
cell-inc (fn [state] (update-in state [:cells (:ptr state)] inc))
cell-dec (fn [state] (update-in state [:cells (:ptr state)] dec))
move-right (fn [state] (update-in state [:ptr] inc))
move-left (fn [state] (update-in state [:ptr] dec))]
(-> state
cell-inc
cell-inc
move-right
cell-dec
move-left))
move-rightна самом деле более сложный, потому что он должен расти,
cellsкогда это необходимо, но это не имеет значения здесь. С помощью этих вспомогательных функций можно легко перевести любую программу Brainfuck в Clojure — просто замена
+,
-,
>и
<операторов с соответствующими функциями. Ну, мы еще не совсем там. Для того, чтобы быть
полным мозгом, Тьюрингу нужна некоторая форма условного утверждения. Брейнфук имеет две инструкции условного перехода,
[и
]. Для наших целей мы можем рассматривать каждую пару квадратных скобок как одну инструкцию (концептуально это оператор
whileцикла). Так, например,
++[>+<-]>есть четыре инструкции:
(let [state {:ptr 0, :cells [0N]}]
(-> state
cell-inc
cell-inc
loop-nested ; [>+<-]
move-right
)
loop-nestedявляется сгенерированной функцией, которая инкапсулирует инструкции в квадратных скобках. Такой цикл завершается, когда он встречается
0в текущей ячейке:
(let
[state {:ptr 0, :cells [0N]}
(letfn [
(loop-nested [state]
(loop [state state]
(if (zero? (nth (:cells state) (:ptr state)))
state
(recur
(-> state
move-right
cell-inc
move-left
cell-dec)))))]
(-> state
cell-inc
cell-inc
loop-nested
move-right)))
Смотри внимательно! Программа начинается внизу. Когда он достигает
loop-nestedфункции (преобразование состояния), он входит во вложенный цикл, определенный выше. Цикл сначала проверяет текущую ячейку — если она равна нулю, stateвозвращается подарок
. В противном случае выполняется последовательность
stateпреобразований, определенных во вложенном цикле. Как только они все выполнены,
recurвызывается для того, чтобы начать последующую итерацию. Рано или поздно
loop-nestedвыходы и
move-right(последняя строка выше) будут выполнены.
Конечно, мы можем вкладывать циклы, как, например, в любой другой язык программирования:
>+>+++[-<[-<+++++>]<++[->+<]>>]<это, пожалуй, самая короткая из известных программ для мозгового меха, которая генерирует … 187 константу. Вы можете увидеть внешний цикл, заключающий в себе два вложенных цикла. Эквивалентный код Clojure, который мы хотели бы сгенерировать, выглядит следующим образом:
(let
[state {:ptr 0, :cells [0N]}]
(letfn [
(loop1279 [state] ; [-<[-<+++++>]<++[->+<]>>]
(loop [state state]
(if (zero? (nth (:cells state) (:ptr state)))
state
(recur
(letfn [
(loop1280 [state] ; [-<+++++>]
(loop [state state]
(if (zero? (nth (:cells state) (:ptr state)))
state
(recur
(-> state ; -<+++++>
cell-dec move-left cell-inc cell-inc cell-inc cell-inc cell-inc move-right)))))
(loop1281 [state] ; [->+<]
(loop [state state]
(if (zero? (nth (:cells state) (:ptr state)))
state
(recur
(-> state ; ->+<
cell-dec move-right cell-inc move-left)))))]
(-> state ; -<[...]<++[...]>>
cell-dec move-left loop1280 move-left cell-inc cell-inc loop1281 move-right move-right))))))]
(-> state ; >+>+++[...]<
move-right cell-inc move-right cell-inc cell-inc cell-inc loop1279 move-left)))
Я оставил комментарии, чтобы показать вам, какие части соответствуют каким кусочкам мозгов Начните читать с самого низа. Полагаю, теперь мы можем полностью оценить лаконичность мозгового срыва. ОК, просто шучу.
Правильно, мы видим, как мозговой трах может быть переведен на Clojure. Давайте реализуем такой переводчик (который я назвал
компилятором в заголовке, так как он звучит лучше). Это может показаться сложным, особенно после просмотра примера кода выше, но весь переводчик
помещается на одном экране !
Реализация состоит из двух основных частей — генерации кода для блока исходного кода и функции внедрения для вложенного цикла. Первая часть, упрощенная для наглядности:
(defn- translate-block [brainfuck-source]
(apply list
(loop [code [`letfn [] `[-> ~'state]], program brainfuck-source]
(condp = (first program)
\> (recur (append-cmd code `~'move-right) (rest program))
\< (recur (append-cmd code `~'move-left) (rest program))
\+ (recur (append-cmd code `~'cell-inc) (rest program))
\- (recur (append-cmd code `~'cell-dec) (rest program))
\[ (let [loop-name (gensym "loop")]
(recur
(insert-loop-fun loop-name program code)
source-after-loop))
nil code
(recur code (rest program))))))
Обратите внимание на то, как мы перебираем символы исходного кода brainfuck и добавляем соответствующие команды к Clojure, который
codeсоздается постепенно (изначально установлен на
(letfn [] ())). Открывающая квадратная скобка (
[) добавляет автоматически сгенерированный цикл в
insert-loop-funфункцию:
(defn- insert-loop-fun [loop-name brainfuck-source code]
(let [loop-body "..."
loop-body-code (translate-block loop-body)
loop-code
`(loop [~'state ~'state]
(if (zero? (nth (:cells ~'state) (:ptr ~'state)))
~'state
(recur ~loop-body-code)))]
`(~loop-name [~'state] ~loop-code)))
Код выше также упрощен для удобства чтения. Выполняются два важных шага: генерация кода для тела цикла с использованием рекурсивного вызова
translate-blockи завершение заключительного кода Clojure с шаблоном цикла. Весь рабочий код
доступен на GitHub . Давайте возьмем этот макрос для тест-драйва. Обратите внимание, что нам больше не нужно экранировать код brainfuck в виде строки, мы можем поместить его
прямо в Clojure!
(is (=
(brainfuck +>-<+)
{:ptr 0 :cells [2 -1]}))
(is (=
(brainfuck >>+>>-)
{:ptr 4 :cells [0 0 1 0 -1]}))
(is (=
(brainfuck
>+>+++[
-<[
-<+++++>
]
<++[
->+<
]
>>
]
<
)
{:ptr 1 :cells [0 187 0]}))
Как видите, вызывающий
brainfuckмакрос дает конечное состояние программы. Ввод / вывод не реализован, но его легко добавить.
Напомним, что нам удалось создать программу Clojure, содержащую менее 60 строк кода, которая переводит любой исходный код в действительный исходный код Clojure. Позднее компилятор Clojure превращает это в байт-код JVM. Исходный код для
интерпретатора и
компилятора (плюс
контрольные примеры )
доступен на GitHub .