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

Question

Я реализовал свой собственный 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 - но я застрял здесь. Мне интересно, как макросистемы реализованы в других Лиспах, но я не смог найти много указателей (кроме this и this ).

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

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

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

Answer 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

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

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

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

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

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

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

Answer 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))))))))

Интереснообратите внимание, что вводная глава Кристиана Квиннека Lisp In Small Pieces имеет очень похожую функцию, он называет ее eval.

Answer 3

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

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

Обратите внимание, что расширение макроса должно быть рекурсивным (macroexpand, пока не останется ничего макроэкспандируемого).среда должна иметь возможность «держать» функции макроразложения, которые можно искать по имени на этом этапе.Обратите внимание, что defmacro - это сам макрос в Common Lisp, который устанавливает правильные вызовы, чтобы связать имя с функцией расширения макроса в этой среде.

Answer 4

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