如何实现Lisp宏系统？

Question

我在node.js上实现了自己的Lisp,我可以像这样运行s表达式:

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

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

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

现在我想添加宏 - defmacro功能 - 但这是我被卡住的地方.我想知道的宏系统是如何在其他的Lisp实现,但我无法找到许多指针(除了这个和这个).

我看过Clojure宏系统 - 我最熟悉的Lisp - 但这看起来太复杂了,我找不到我可以轻易应用的其他线索(Clojure宏最终编译成不适用的字节码对于javascript,我也无法理解这个macroexpand1功能.)

所以我的问题是:给定一个没有宏但带有AST的Lisp实现,如何添加像Clojure宏系统这样的宏系统？这个宏系统可以在Lisp中实现,还是在宿主语言的实现中需要额外的功能？

还有一句话:我还没有实现quote(')因为我无法弄清楚返回列表中应该包含哪种值.如果它包含AST的元件或类似的对象Symbol和Keyword(后者是用于Clojure的情况下)？

Answer 1

宏所做的就是将未评估的表单作为参数并在其主体上执行替换.实现宏系统的技巧是告诉编译器是懒惰的.

换句话说,当编译器遇到函数时,它首先计算其形式参数列表,产生结果并将它们传递给函数.当编译器找到一个宏时,它会将未评估的参数传递给正文,然后执行正文请求的任何计算,最后将其自身替换为结果.

例如,假设您有一个功能:

(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.

Answer 2

这是来自 Peter Norvig 的人工智能编程范式- 任何 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 In Small Pieces的开篇章节有一个非常相似的功能，他称之为eval。