Как реализовать макросистему Lisp?

Я реализовал свой собственный Lisp поверх node.js, я могу запустить s-выражения следующим образом:

(assert (= 3 (+ 1 2)))

(def even? (fn [n] (= 0 (bit-and n 1))))

(assert (even? 4))
(assert (= false (even? 5)))

Теперь я хотел бы добавить макросы - функцию defmacro, но это то, где я застрял. Мне интересно, как макросистемы реализованы в других Lisps, но я не мог найти много указателей (кроме this и this).

Я посмотрел на макросистему Clojure - Lisp, с которой я больше всего знаком - но это казалось слишком сложным, и я не мог найти дополнительные подсказки, которые я могу легко применить (макрос Clojure в конечном счете компилировать в байтовый код, который не применяется к javascript, также я не мог понять функцию macroexpand1.)

Итак, мой вопрос: при реализации Lisp без макросов, но с AST, как добавить макросную систему, например макросистему Clojure? Может ли эта макросистема быть реализована в Lisp или требуется ли дополнительные возможности в реализации на языке хоста?

Еще одно замечание: я еще не реализовал quote ('), потому что не мог понять, какие значения должны быть в возвращаемом списке. Должны ли они содержать элементы или объекты AST, такие как Symbol и Keyword (последнее относится к Clojure)?

Ответы

Ответ 1

Все макросы принимают необработанные формы в качестве параметров и выполняют замену на своем теле. Трюк реализации макросистемы заключается в том, чтобы сообщить вашему компилятору lazy.

Поставить другим способом, когда компилятор встречает функцию, он сначала оценивает свой список формальных параметров, дает результаты и передает их функции. Когда компилятор находит макрос, он передает аргументы, не имеющие аналогов в теле, затем выполняет любые вычисления, которые запрашивает тело, и, наконец, заменяет собой результат.

Например, скажем, у вас есть функция:

(defun print-3-f (x) (progn (princ x) (princ x) (princ x)))

и макрос:

(defmacro print-3-m (x) `(progn (princ ,x) (princ ,x) (princ ,x)))

Затем вы можете сразу увидеть разницу:

CL-USER> (print-3-f (rand))
* 234
* 234
* 234

CL-USER> (print-3-m (rand))
* 24
* 642
* 85

Чтобы понять, почему это так, вам нужно, как бы говоря, запустить компилятор в своей голове.

Когда функция Lisp встречает функцию, она строит дерево, в котором (rand) сначала оценивается, и результат передается функции, которая трижды печатает указанный результат.

С другой стороны, когда Lisp попадает в макрос, он передает форму (rand) нетронутой в тело, которая возвращает список с кавычками, где x заменяется на (rand), давая:

(progn (princ (rand)) (princ (rand)) (princ (rand)))

и замените вызов макроса для этой новой формы.

Здесь вы найдете огромное количество документации относительно макросов на разных языках, включая Lisp.

Ответ 2

Это от Питера Норвига Парадигмы программирования искусственного интеллекта - важный вопрос для любой книжной полки программистов LISP.

Он предполагает, что вы реализуете интерпретируемый язык и предоставляет пример интерпретатора схем, работающего в LISP.

Следующие два примера здесь показывают, как он добавляет макросы к основной функции eval (interp)

Вот функция для интерпретации S-выражения до работы с макросами:

(defun interp (x &optional env)
  "Interpret (evaluate) the expression x in the environment env."
  (cond
    ((symbolp x) (get-var x env))
    ((atom x) x)
    ((case (first x)
       (QUOTE  (second x))
       (BEGIN  (last1 (mapcar #'(lambda (y) (interp y env))
                              (rest x))))
       (SET!   (set-var! (second x) (interp (third x) env) env))
       (IF     (if (interp (second x) env)
                   (interp (third x) env)
                   (interp (fourth x) env)))
       (LAMBDA (let ((parms (second x))
                     (code (maybe-add 'begin (rest2 x))))
                 #'(lambda (&rest args)
                     (interp code (extend-env parms args env)))))
       (t      ;; a procedure application
               (apply (interp (first x) env)
                      (mapcar #'(lambda (v) (interp v env))
                              (rest x))))))))

И вот после того, как была добавлена макро-оценка (дочерние методы были в ссылке для ясности

(defun interp (x &optional env)
  "Interpret (evaluate) the expression x in the environment env.
  This version handles macros."
  (cond
    ((symbolp x) (get-var x env))
    ((atom x) x)

    ((scheme-macro (first x))              
     (interp (scheme-macro-expand x) env)) 

    ((case (first x)
       (QUOTE  (second x))
       (BEGIN  (last1 (mapcar #'(lambda (y) (interp y env))
                              (rest x))))
       (SET!   (set-var! (second x) (interp (third x) env) env))
       (IF     (if (interp (second x) env)
                   (interp (third x) env)
                   (interp (fourth x) env)))
       (LAMBDA (let ((parms (second x))
                     (code (maybe-add 'begin (rest2 x))))
                 #'(lambda (&rest args)
                     (interp code (extend-env parms args env)))))
       (t      ;; a procedure application
               (apply (interp (first x) env)
                      (mapcar #'(lambda (v) (interp v env))
                              (rest x))))))))

Интересно отметить, что открывающая глава Christian Queinnec Lisp В Small Pieces имеет очень схожую функцию, он называет ее eval.

Ответ 3

В вашей оценочной цепочке должна быть фаза макрорасширения:

text-input -> read -> macroexpand -> compile -> load

Обратите внимание, что расширение макроса должно быть рекурсивным (macroexpand до тех пор, пока не останется ничего макрообмена).

В вашей среде требуется возможность "удерживать" функции макрорасширения, которые можно посмотреть по имени на этом этапе. Обратите внимание, что defmacro является макросом в Common Lisp, который устанавливает правильные вызовы для связывания имени с функцией расширения макроса в этой среде.

Ответ 4

Взгляните на этот пример. Это игрушечная реализация Arc-подобного компилятора с достойной поддержкой макросов.