Первый eval: диспетчеризация по голове и бинарное ядро

Значения у нас уже есть, пора их вычислять. Первый eval: самовычисляющиеся значения (число вычисляется в себя), вызов как список, где голову вычисляем и по результату диспетчеризуем. Ставим бинарное ядро: _+_, _-_, _*_, _/_, _%_, _++_, _=_, _<_, _>_ как BinOp и BinPred ровно на два аргумента, со слабой типизацией Integer и Double, reprToStr для конкатенации. Разбираем truthiness (истинно всё, кроме false и nil) и проверку арности через getElements.

Идея

“Вычислить значение” значит свести его к результату по простым правилам. Их всего два рода. Самовычисляющиеся значения вычисляются в себя: число 42 это уже ответ, строка и булево тоже. Список это вызов: его надо как-то применить. И вот ключевая мысль lishp, ради которой затевались слова-значения: вычислитель смотрит не на текст в голове списка, а на вычисленное значение головы.

Сравни с обычным Lisp. Там eval видит список (_+_ 1 2), достаёт символ _+_ из головы, ищет его имя в большой таблице встроенных и решает, что это сложение. У нас иначе: голова _+_ уже прочитана ридером как значение BinOp Add, поэтому eval просто вычисляет голову (она вычисляется в себя, это же готовое значение) и смотрит, что за конструктор получился. BinOp это арифметика, BinPred это сравнение, Special это спец-форма (урок 20), Lambda это функция (урок 22). Диспетчеризация идёт по типу значения в голове, и потому всё вызываемое это полноценное first-class значение.

В этом уроке мы соберём вычислитель ровно для ядра: самовычисляющиеся значения плюс бинарные операторы. Символы (нужно окружение), спец-формы и функции добавим в уроках 20, 21, 22. И ещё одно честное упрощение: эта первая версия eval при плохом вводе падает через error. В следующем уроке мы заменим падения на аккуратные ошибки-значения, а пока так проще увидеть скелет.

Самовычисляющиеся значения и вызов

Учебная версия eval для ядра. Без окружения, без ошибок-значений, без IO, всё это придёт дальше:

-- учебная версия (урок 18): только ядро. В уроке 19 заменим падения
-- на ошибки-значения, в 21 добавим окружение и аргумент Env.
eval :: LishpVal -> LishpVal
eval val = case val of
  Pair headExpr tl ->
    case eval headExpr of                    -- вычисляем ГОЛОВУ
      BinOp op  -> let [a, b] = args2 tl in evalBinOp op (eval a) (eval b)
      BinPred p -> let [a, b] = args2 tl in evalBinPred p (eval a) (eval b)
      hv        -> error ("нельзя вызвать " ++ showVal hv)
  Sym name -> error ("символы будут в уроке 21: " ++ name)
  other    -> other                          -- число, строка, bool, nil: в себя

Читается по строкам. Список: вычислили голову, и если это BinOp, берём два аргумента, вычисляем каждый и применяем оператор; если BinPred, то же со сравнением; иначе голова не вызывается. Символ пока не умеем (это про окружение). Всё прочее самовычисляется. args2 это вытаскивание ровно двух аргументов из cons-цепочки:

args2 :: LishpVal -> [LishpVal]
args2 tl = case properElems tl of
  xs@[_, _] -> xs
  xs        -> error ("ожидал 2 аргумента, получил " ++ show (length xs))

Заметь, что аргументы вычисляются до применения оператора (eval a, eval b): мы в applicative-order языке, как почти все Lisp. Это станет важно в уроке про спец-формы: if нельзя сделать обычным вызовом именно потому, что тогда обе ветки вычислились бы заранее.

Прощёлкай степпером, как eval обходит вложенный вызов снизу вверх: сначала аргументы, потом оператор.

Бинарное ядро

Вот вся арифметика языка. Главное решение тут: операторы строго бинарные, ровно два аргумента, и со слабой типизацией чисел: два Integer дают Integer, два Double дают Double.

evalBinOp :: BinaryOp -> LishpVal -> LishpVal -> LishpVal
evalBinOp op l r = case op of
  Add -> arith (+) (+)
  Sub -> arith (-) (-)
  Mul -> arith (*) (*)
  Div -> divide
  Mod -> case (l, r) of
    (Integer _, Integer 0) -> error "деление на ноль"
    (Integer a, Integer b) -> Integer (a `mod` b)
    _                      -> invalid
  StrConcat -> Str (reprToStr l ++ reprToStr r)
  where
    invalid = error ("оператор " ++ binaryOpName op ++ " не применим к этим типам")
    arith fInt fDbl = case (l, r) of
      (Integer a, Integer b) -> Integer (fInt a b)
      (Double a, Double b)   -> Double (fDbl a b)
      _                      -> invalid
    divide = case (l, r) of
      (_, Integer 0)         -> error "деление на ноль"
      (_, Double 0.0)        -> error "деление на ноль"
      (Integer a, Integer b) ->                      -- целое деление, если ровно
        let q = fromIntegral a / fromIntegral b :: Double
        in if q == fromInteger (round q) then Integer (round q) else Double q
      (Double a, Double b)   -> Double (a / b)
      (Integer a, Double b)  -> Double (fromIntegral a / b)
      (Double a, Integer b)  -> Double (a / fromIntegral b)
      _                      -> invalid

Две тонкости. Деление _/_ даёт Integer, если результат ровный (6/2 это 3, а 7/2 это 3.5): язык не навязывает тип, а подбирает по результату. А _++_ это конкатенация через reprToStr, который у строки берёт сырое содержимое (без кавычек), у всего прочего печатную форму. Поэтому (_++_ "n=" 42) даёт "n=42":

-- что оператор видит как строку: у Str сырой текст, у прочего печать
reprToStr :: LishpVal -> String
reprToStr (Str s) = s
reprToStr v       = showVal v

Сравнения устроены так же, ровно на два аргумента. _=_ это структурное равенство lishpEq (мы завели его в уроке 17), а _<_ и _>_ сравнивают только однотипные числа:

evalBinPred :: BinaryPred -> LishpVal -> LishpVal -> LishpVal
evalBinPred p l r = case p of
  Equals      -> Bool (lishpEq l r)
  LessThan    -> compareWith LT
  GreaterThan -> compareWith GT
  where
    invalid = error ("предикат " ++ binaryPredName p ++ " не применим")
    compareWith ord = case (l, r) of
      (Integer a, Integer b) -> Bool (compare a b == ord)
      (Double a, Double b)   -> Bool (compare a b == ord)
      _                      -> invalid

Почему compare и Ordering, а не compareWith (<)? Параметр f внутри where мономорфен: одна и та же функция не может сравнить сначала Integer, а потом Double, и GHC отвергнет такой код. Значение LT или GT от типа чисел не зависит, поэтому годится для обеих веток.

Почему ядро бинарное, а привычный (+ 1 2 3 4) на любое число аргументов будет потом? Это разделение механизма и политики из развилки ниже: ядро знает, как сложить два числа, а сколько их складывать за раз решает вариадик +, написанный на самом lishp поверх _+_ в уроке 24.