Стандартная библиотека на самом языке

Ядро готово, и теперь язык достраивает себя сам. Пишем std.lsp на самом lishp: бутстрап defmacro и defn из macro и lambda, макросы cond, when, and, or, вариадик-обёртки над бинарным ядром (+, *, -, <, =), список-библиотека (map, filter, foldl, foldr, range, take, drop, append, concat, length, zip-with, flatten, distinct), и match (сопоставление с образцом через codegen макросом), += и -=. Полный std.lsp это проектное домашнее задание урока.

Идея

Останься на этой мысли, она итог всего проекта. В Haskell-ядре у нас только бинарные операторы (_+_, _<_, _++_) и горстка спец-форм. Ни + на любое число аргументов, ни cond, ни map, ни сопоставления с образцом. Всё это, всё привычное API языка, мы сейчас напишем на самом lishp, в файле std.lsp, без единой строки Haskell.

Это разделение механизм против политики во всю силу. Ядро знает, как сложить два числа и как не вычислить аргумент, но не знает, что такое + на пяти числах или cond с пятью ветками. Это политика, и ей место в библиотеке на самом языке. Когда язык дорастает до того, чтобы определять сам себя, это называют движением к self-hosting. Файл std.lsp грузится в окружение сессии при старте (механику загрузки разберём в уроке 25), и дальше всё в нём доступно как родное.

Бутстрап: defmacro и defn

Писать каждое определение как (def name (macro (args) body)) неудобно. Первым делом язык даёт себе сахар. Начинается с двух мелочей: переноса строки как значения и fn как синонима lambda (помнишь, lambda это значение, его можно просто переименовать):

(def \n "\n")
(def fn lambda)

(def list (lambda (. args) args))    ; (list 1 2 3) -> (1 2 3)
(def nil? (lambda (x) (_=_ x nil)))

Теперь главный приём бутстрапа. defmacro это макрос, который определяет макросы, а defn определяет функции. Оба собраны через вспомогательную функцию-кодогенератор, которая строит форму (def name (lambda args body)):

(def defmacro-codegen (lambda (name args body-list)
  (list def name (list 'macro args
    (if (nil? body-list) nil
      (if (nil? (cdr body-list))
        (car body-list)
        (cons do body-list)))))))      ; несколько форм тела заворачиваем в (do ...)
(def defmacro (macro (name args . body)
  (eval (defmacro-codegen name args body))))

(defmacro defn (name args . body)       ; уже на удобном синтаксисе!
  (eval (defn-codegen name args body)))

Замечаешь скачок: defmacro определён через сырой macro, но defn уже записан через defmacro. Язык подтянул себя за шнурки, и дальше весь std.lsp пишется по-человечески: (defn name (args) body).

Управляющие макросы

Условные конструкции это макросы, и иначе нельзя: будь cond функцией, все её ветки вычислились бы заранее. cond рекурсивно разворачивается в цепочку if:

;; (cond c1 e1 c2 e2 ... default)
(defmacro cond (. clauses)
  (if (nil? clauses)
    nil
    (if (nil? (cdr clauses))
      (car clauses)                                    ; одинокий хвост это default
      (list 'if (car clauses) (cadr clauses)
            (cons 'cond (cddr clauses))))))            ; иначе вложенный cond

(defmacro when (c . body) (list if c (cons do body) nil))

(defmacro and (. args)
  (if (nil? args) true
    (if (nil? (cdr args)) (car args)
      (list 'if (car args) (cons 'and (cdr args)) false))))   ; короткое замыкание

(defmacro or (. args)
  (if (nil? args) false
    (if (nil? (cdr args)) (car args)
      (list 'if (car args) true (cons 'or (cdr args))))))

and и or дают короткое замыкание именно потому, что разворачиваются в if: (and a b) это (if a b false), и b не считается, если a ложно. Функция так не смогла бы.

Вариадик поверх бинарного ядра

Вот где окупается решение держать ядро бинарным. Привычный + на любое число аргументов это foldl бинарного _+_. Сначала сами свёртки (на самом языке!), потом вариадики:

(defn foldl (f init lst)
  (if (nil? lst) init
      (reduce f (f init (car lst)) (cdr lst))))
(def reduce foldl)

(defn + (. xs) (reduce (fn (a b) (_+_ a b)) 0 xs))   ; начальный аккумулятор 0
(defn * (. xs) (reduce (fn (a b) (_*_ a b)) 1 xs))   ; для умножения 1
(defn str (. xs) (reduce (fn (a b) (_++_ a b)) "" xs))

Начальный аккумулятор это нейтральный элемент операции, моноидная единица: 0 для сложения, 1 для умножения, "" для конкатенации. Цепочечные сравнения (< 1 2 3) собраны похоже, через проход по парам:

(defn bp-core (bp a xs)
  (if (nil? xs) true
    (if (bp a (car xs)) (bp-core bp (car xs) (cdr xs)) false)))
(defn < (. xs) (if (nil? xs) true (bp-core _<_ (car xs) (cdr xs))))

Механизм (как сравнить два) был в ядре, политика (сколько и что значит цепочка) здесь.

Список-библиотека и match

Вся работа со списками это обычные рекурсивные функции на lishp. Сравни с теми же map и filter, что ты писал на Haskell в начале раздела, идея одна:

(defn map (func xs)
  (if (nil? xs) nil
    (cons (func (car xs)) (map func (cdr xs)))))

(defn filter (pred xs)
  (cond (nil? xs) nil
        (pred (car xs)) (cons (car xs) (filter pred (cdr xs)))
        (filter pred (cdr xs))))

(defn range (a b) (if (< a b) (cons a (range (+ 1 a) b)) nil))
(defn length (xs) (reduce (fn (a b) (+ a 1)) 0 xs))

К ним добавляются take, drop, append, concat, reverse, zip-with, flatten, distinct, всё на тех же cons, car, cdr и рекурсии. А вершина библиотеки это match, целый маленький язык сопоставления с образцом, собранный макросом. Он сравнивает образец со значением, вычисляет список связок и разворачивается в (do (def ...) ...):

(defmacro match (pattern value)
  (def evaled-value (eval value))
  (def bindings (match-bindings pattern evaled-value))   ; список (имя значение)
  (cons 'do (map binding->def bindings)))                ; -> (do (def a ...) (def b ...))

(match (a b) (list 10 20))    ; связывает a=10, b=20
(+ a b)                        ; 30

match это и есть мораль урока: целая конструкция языка, которой нет и не должно быть в ядре, написана на самом языке макросом, генерирующим код. И +=, -= тоже макросы:

(defmacro += (x v) (list 'set! x (list '+ x v)))