Спец-формы как значения: quote, eval, car, cdr, cons

Обычный вызов сначала вычисляет все аргументы. Но quote обязан их НЕ вычислять, а if обязан вычислить только одну ветку. Такое нельзя выразить обычной функцией, поэтому существуют спец-формы. В этом уроке разбираем спец-формы lishp, которые не про переменные и функции: quote и eval, car, cdr, cons (и почему car или cdr не-списка это сам элемент и nil), typeof, do как последовательность, print и read, symbol из строки. И почему cond, case и предикаты типов живут в библиотеке, а не в ядре.

Идея

Вспомни правило вызова из урока 18: список это вызов, и аргументы вычисляются до применения головы. Для арифметики это правильно: чтобы сложить, надо знать оба числа. Но есть конструкции, которым такое правило мешает. quote обязан вернуть аргумент невычисленным. if обязан вычислить только одну ветку, а не обе. Обычной функцией это не выразить: функция в applicative-order языке всегда получает аргументы уже посчитанными, у неё нет шанса не вычислить ветку.

Поэтому существуют спец-формы. Спец-форма получает аргументы сырыми, как они пришли от ридера, и сама решает, что вычислять. У нас они уже first-class значения: ридер прочитал quote как Special Quote, и когда такое значение оказывается в голове вызова, eval отдаёт хвост не вычисленным, а самой форме. quote это самый чистый пример: вернуть аргумент как есть.

Диспетчер спец-форм это одна функция evalSpecial, которую вызывает ветка Special f из eval. У неё два помощника, with1 и with2. Они берут ровно один или два невычисленных аргумента, а на неверной арности внятно жалуются через getElements из урока 19:

evalSpecial :: Env -> SpecialForm -> LishpVal -> Eval LishpVal
evalSpecial env form tl = case form of
  -- ветки разберём ниже по группам
  where
    with1 f = getElements tl 1 >>= \case [a]    -> f a; _ -> throwError (MissingElements 1 0)
    with2 f = getElements tl 2 >>= \case [a, b] -> f a b; _ -> throwError (MissingElements 2 0)

Прогони одно и то же выражение двумя стратегиями и посмотри, где они расходятся. Слева оно идёт как обычный вызов (все аргументы вычисляются заранее), справа как спец-форма (аргументы сырые, форма выбирает сама):

quote и eval

quote и eval это две стороны моста между кодом и данными. quote берёт аргумент и возвращает его не трогая (вот зачем он спец-форма, обычная функция вычислила бы аргумент). eval наоборот: берёт значение и вычисляет его, причём дважды, ведь сам аргумент eval сперва вычисляется по общему правилу, а потом вычисляется его результат.

  Quote -> with1 (\x -> pure x)              -- вернуть аргумент как есть
  Eval  -> with1 (\ae -> eval env ae >>= eval env)  -- вычислить дважды

Сложи их вместе: (eval (quote (_+_ 1 2))) это 3. Внутренний quote отдал список (_+_ 1 2) как данные, внешний eval оживил эти данные обратно в код. Эта пара, “заморозить код в данные и потом разморозить”, и есть фундамент макросов из урока 23.

car, cdr, cons

Три операции над списками. cons строит пару (приставляет элемент в голову списка), car берёт голову, cdr берёт хвост. У lishp тут своя особенность: car и cdr от не-списка это не ошибка, а сам элемент и nil соответственно. Так удобнее в рекурсии по неоднородным данным.

  Cons -> with2 $ \ae be -> do
    a <- eval env ae
    b <- eval env be
    if isList b then pure (Pair a b) else throwError (ExpectedList (showVal b))
  Car -> with1 $ \ae -> do
    v <- eval env ae
    case v of
      _ | not (isList v) -> pure v       -- car не-списка это сам элемент
      Nil      -> throwError CarOfNil     -- car пустого списка это ошибка
      Pair h _ -> pure h
      _        -> throwError CarOfNil
  Cdr -> with1 $ \ae -> do
    v <- eval env ae
    case v of
      _ | not (isList v) -> pure Nil      -- cdr не-списка это nil
      Nil      -> throwError CdrOfNil
      Pair _ t -> pure t
      _        -> throwError CdrOfNil

Заметь: эти формы вычисляют свои аргументы (eval env ae), в отличие от quote. Спец-форма не значит “ничего не вычисляй”, она значит “решай сам”. cons вычисляет оба аргумента, car один, quote ни одного.