Архитектура интерпретатора: read, eval, print

Старт первого большого проекта раздела: за одиннадцать уроков мы напишем интерпретатор учебного Lisp под названием lishp, целиком на Haskell, с парсером, вычислителем, окружениями, замыканиями, макросами, стандартной библиотекой на самом языке и REPL. Этот урок про форму целого: петля read, eval, print, единый тип значения LishpVal как вселенная всех данных и всего кода сразу, тезис “формы это значения”, инстанс Show для печати, скелет REPL и карта проекта.

Идея

Любой интерпретатор это одна петля из трёх шагов. read берёт текст и превращает его в значение. eval берёт значение и превращает его в другое значение. print берёт значение и превращает его обратно в текст. Замкни это в цикл, и получится REPL, read-eval-print loop, та самая консоль, в которой ты пробуешь язык по одному выражению за раз.

текст ──read──▶ значение ──eval──▶ значение ──print──▶ текст
                    ▲                                      │
                    └──────────────── loop ◀───────────────┘

У Lisp эта схема обнажена сильнее, чем у любого другого языка, и причина в одном слове: гомоиконность. В большинстве языков read строит дерево синтаксиса (AST), отдельный тип данных, который живёт только до начала исполнения, а дальше по нему работает совсем другой код. В Lisp такого отдельного типа нет. read сразу выдаёт значение того же типа, которым язык оперирует во время работы. (+ 1 2) после read это просто список из трёх элементов: символа + и двух чисел. Тот же список, который ты можешь построить руками, отдать в eval, разобрать на части.

Из этой одинаковости растёт всё остальное в проекте. quote (получить код как данные) сводится к “не вычисляй это”. Макрос (программа, которая пишет программу) сводится к “построй список и вычисли его”. Метациркулярность из четвёртой главы SICP, когда вычислитель Lisp пишут почти дословно на самом Lisp, возможна ровно потому, что код для такого вычислителя это обычные данные.

Прокрути конвейер по шагам и посмотри, во что превращается выражение на каждой стадии. На стадии READ задержись: справа появится дерево cons-ячеек, та самая структура, на которой потом стоит всё остальное.

Немного про сам Lisp

Lisp придумал Джон Маккарти в 1958 году, это второй по возрасту язык из тех, что дожили до наших дней, старше него только Fortran. Имя расшифровывается как LISt Processing: язык изначально про обработку списков, и именно списки оказались тем кирпичиком, из которого собрано всё.

Любое выражение в Lisp это либо атом (число, символ), либо список в круглых скобках, где первый элемент это операция, а остальные её аргументы. Запись (+ 1 2) читается как “применить + к 1 и 2”, а (def x 10) как “применить def к x и 10”. Такая форма называется S-выражением, и она же префиксная: операция всегда впереди. Отсюда и море скобок: у Lisp почти нет другого синтаксиса, вся структура программы это вложенность списков. Сначала это пугает, а потом оказывается, что правил-то и нет, кроме скобок.

Из этой простоты родилась вторая центральная идея, петля read-eval-print. Маккарти описал крошечную функцию eval, способную вычислить любое S-выражение, и обнаружилось, что вокруг неё легко закрутить интерактивный цикл: прочитать выражение, вычислить, напечатать результат, повторить. Так появился REPL, та самая консоль, в которой язык пробуют по одному выражению за раз. Сегодня REPL есть почти везде, но придумали его именно здесь.

И главная награда за то, что код это списки: списки можно строить программой. Раз (+ 1 2) это всего лишь данные, то другая функция может собрать такой список сама и отдать его на вычисление. Так работают макросы: они получают код как обычные списки, перекраивают его и возвращают новый код, который потом вычисляется. К макросам мы дойдём в уроке 23, но фундамент под них закладывается прямо здесь, в решении хранить код и данные одним типом.

Поэтому весь проект держится на одном решении: завести единый тип LishpVal, в котором живут и данные, и код. Не два типа, не дерево плюс значения, а один sum-type на всё сразу.

Тип LishpVal: одно значение на всё

Вот сердце проекта, тип, к которому мы будем возвращаться каждый урок:

data LishpVal
  = Integer Integer                              -- 42
  | Double Double                                -- 1.5
  | Str String                                   -- "hi"
  | Sym String                                   -- x, foo, +
  | Bool Bool                                    -- true, false
  | Nil                                           -- nil, она же ()
  | Pair LishpVal LishpVal                        -- (a . b), ячейка cons
  | Lambda [String] (Maybe String) LishpVal Env   -- замыкание (урок 22)
  | Dambda [String] (Maybe String) LishpVal       -- динамическая функция
  | Macro  [String] (Maybe String) LishpVal       -- макрос (урок 23)
  | Special SpecialForm                           -- def, if, quote, ...
  | BinOp BinaryOp                                -- _+_, _-_, _*_, ...
  | BinPred BinaryPred                            -- _=_, _<_, _>_

Разбери конструкторы на три группы. Сверху обычные атомы: целые и дробные числа, строки, символы (имена), булевы и Nil. Дальше Pair, ячейка cons, из которой строятся списки: список (1 2 3) это Pair 1 (Pair 2 (Pair 3 Nil)). И снизу самое интересное, всё вызываемое тоже значение: спец-формы вроде def и if, бинарные операторы вроде _+_, замыкания, макросы. Здесь это просто ещё несколько конструкторов того же типа.

Числа разделены на Integer и Double намеренно: целочисленная арифметика остаётся целой, пока её не вынудят стать дробной (урок 18). Параметры функций это [String] (имена) плюс Maybe String (необязательный варьируемый хвост); к ним вернёмся в уроке про функции.

Три конструктора ссылаются на маленькие перечисления. Это закрытые списки встроенных форм и операторов; ридер (урок 17) будет превращать слово def в Special Define, а _+_ в BinOp Add:

-- Семнадцать спец-форм. Это значения: def, if, quote и прочие
data SpecialForm
  = Define | Set | If | Quote | Eval | Car | Cdr | Cons | Do
  | TypeOf | Read | Print | Symbol | SfLambda | SfDambda | SfMacro
  | Load | Raise | ExpandMacro
  deriving (Eq)

-- Бинарные арифметические и строковые операторы (урок 18)
data BinaryOp = Add | Sub | Mul | Div | Mod | StrConcat
  deriving (Eq)

-- Бинарные сравнения
data BinaryPred = Equals | LessThan | GreaterThan
  deriving (Eq)

И их печать, на которую опирается showVal: каждое перечисление знает своё имя в исходном тексте.

specialFormName :: SpecialForm -> String
specialFormName = \case
  Define -> "def"; Set -> "set!"; If -> "if"; Quote -> "quote"; Eval -> "eval"
  Car -> "car"; Cdr -> "cdr"; Cons -> "cons"; Do -> "do"; TypeOf -> "typeof"
  Read -> "read"; Print -> "print"; Symbol -> "symbol"; SfLambda -> "lambda"
  SfDambda -> "dambda"; SfMacro -> "macro"; Load -> "load"; Raise -> "raise"
  ExpandMacro -> "expand-macro"

binaryOpName :: BinaryOp -> String
binaryOpName = \case
  Add -> "_+_"; Sub -> "_-_"; Mul -> "_*_"; Div -> "_/_"; Mod -> "_%_"
  StrConcat -> "_++_"

binaryPredName :: BinaryPred -> String
binaryPredName = \case
  Equals -> "_=_"; LessThan -> "_<_"; GreaterThan -> "_>_"

Зачем держать встроенные операторы отдельным закрытым типом, а не обычными символами, мы разберём в уроке 17 (это и есть фокус lishp с “словами-значениями”). Пока важно одно: с этими тремя перечислениями модуль Lishp.Value компилируется целиком, а showVal умеет печатать любой конструктор. Env (поле Lambda) появится только в уроке 21; до тех пор закомментируй три callable-конструктора или подставь заглушку data Env = Env, если хочется собрать модуль прямо сейчас.

Такой подход, когда весь язык кодируется значениями одного типа на языке-хозяине, называют deep embedding: lishp это данные внутри Haskell, а eval (уроки 18 и дальше) их интерпретирует. Плата за единый тип в том, что Haskell больше не ловит за нас бессмысленные комбинации (сложить число со строкой), это станет работой рантайм-проверок и типа ошибок из урока 19.

Рядом с типом живёт горстка чистых помощников, они понадобятся всюду:

-- Собрать правильный список из элементов: [a, b] -> Pair a (Pair b Nil)
fromList :: [LishpVal] -> LishpVal
fromList = foldr Pair Nil

-- Вытащить ведущие элементы cons-цепочки в обычный список Haskell
properElems :: LishpVal -> [LishpVal]
properElems (Pair h t) = h : properElems t
properElems _          = []

isNil :: LishpVal -> Bool
isNil Nil = True
isNil _   = False

-- Правильный список это nil или пара, чей хвост снова правильный список
isList :: LishpVal -> Bool
isList Nil        = True
isList (Pair _ t) = isList t
isList _          = False

fromList это foldr Pair Nil: тот самый правый свёрток, только сворачивает он не в число, а в цепочку пар. properElems обратное: разворачивает цепочку обратно в список Haskell. Эта пара переводит туда-сюда между миром lishp и миром Haskell и будет встречаться в каждом следующем модуле.