macros - Lisp:宏可以递归吗？

Question

我最近开始使用 Lisp 编写代码，并且对宏印象最深 - 它们 allowed me to do complex loop-unrolling在编译时，我无法用我所知道的任何其他语言优雅地做到这一点(即在保持原始结构的同时生​​成代码)。

关于优化:我在同一代码中添加了类型注释(大量的“fixnum”)。一旦我添加了 3 或 4 个，我意识到我做错了 - 这就是宏的用途，不要重复自己...

; whenever we want to indicate that the result of an operation 
; fits in a fixnum, we macro expand (the fixnum (...))
(defmacro fast (&rest args)
  `(the fixnum ,args))
...
(cond
  (...)
  (t (let* ((forOrange (+ (aref counts 5)
                          (fast * 2 (aref counts 6))
                          (fast * 5 (aref counts 7))
                          (fast * 10 (aref counts 8))))
            (forYellow (+ (aref counts 3)
                          (fast * 2 (aref counts 2))
                          (fast * 5 (aref counts 1))
                          (fast * 10 (aref counts 0))))

...事实上，这行得通:我没有在各处写很多“(fixnum (...))”，而是快速在表达式前加上“fast”前缀 - 一切都很好。

但是……

我意识到即使这不是事情应该停止的地方:原则上，宏“fast”应该......在评估的顶部调用，在这种情况下:

            (forYellow (fast + (aref counts 3)
                          (* 2 (aref counts 2))
                          (* 5 (aref counts 1))
                          (* 10 (aref counts 0))))

...它应该在所有子表达式中递归地“植入”“(fixnum (...))”。

这能做到吗？“defmacro”可以递归吗？

更新:我在尝试执行此操作时遇到了一些非常奇怪的问题，所以我最终按照 Rord 下面的建议进行操作 - 即实现一个函数，在 repl 中对其进行测试，然后从宏中调用它:

(defun operation-p (x)
  (or (equal x '+) (equal x '-) (equal x '*) (equal x '/)))

(defun clone (sexpr)
  (cond
    ((listp sexpr)
     (if (null sexpr)
       ()
       (let ((hd (car sexpr))
             (tl (cdr sexpr)))
         (cond
           ((listp hd) (append (list (clone hd)) (clone tl)))
           ((operation-p hd) (list 'the 'fixnum (cons hd (clone tl))))
           (t (cons hd (clone tl)))))))
    (t sexpr)))

(defmacro fast (&rest sexpr)
  `(,@(clone sexpr)))

它在 SBCL 下运行良好:

$ sbcl
This is SBCL 1.0.52, an implementation of ANSI Common Lisp.
...
* (load "score4.cl")

T
* (setf a '(+ (1 2) (- 1 (+ 5 6)))
...
* (clone a)

(THE FIXNUM (+ (1 2) (THE FIXNUM (- 1 (THE FIXNUM (+ 5 6))))))

* (macroexpand '(fast + 1 2 THE FIXNUM (- 1 THE FIXNUM (+ 5 6))))

(THE FIXNUM (+ 1 2 THE FIXNUM (THE FIXNUM (- 1 THE FIXNUM (THE FIXNUM (+ 5 6))))))
T

一切都很好，除了一个副作用:CMUCL 可以工作，但不再编译代码:

; Error: (during macroexpansion)
; Error in KERNEL:%COERCE-TO-FUNCTION:  the function CLONE is undefined.

好吧:-)

更新:编译失败已在a different SO question中解决。 .

Answer 1

您绝对可以编写一个在自己的扩展中使用自身的宏。这是非常有道理的，这是编写 COND 宏的自然方式，它具有规则的扩展结构，因为任意长的 cond 对列表，可以用通常的 car/cdr 或 first/rest 递归表示。

(defmacro new-cond (&rest cond-pairs)
  (cond      ;; you need cond to compile new-cond syntax, LOL!
    ((null cond-pairs) nil)
    ((atom cond-pairs) (error "new-cond: bad syntax!"))
    (t `(if ,(first (first cond-pairs))
           (progn ,@(rest (first cond-pairs)))
           (new-cond ,@(rest cond-pairs))))))


> (macroexpand-1 '(new-cond (1 2) (3 4)))

(IF 1 (PROGN 2) (NEW-COND (3 4)))

这非常类似于惰性列表处理。 macroexpand 仅展开外部宏，留下“promise”对象继续展开。那个“ promise ”对象是尾部的宏调用 (NEW-COND (3 4))。

当然，真正的宏扩展器将遍历整个表单并“强制”所有这些 promise (未扩展的宏调用)，直到不再剩下为止。

我认为这种风格有一些优点，例如使用 macroexpand 可以轻松调试。你得到一个小的扩展。如果它的递归性质很明显，那就是胜利。如果宏需要您的大脑看到整个事物的扩展，那就是一种损失。

在这里，我可以看到 (IF 1 (PROGN 2) (NEW-COND (3 4))) 是正确的编译。如果 1 为真，则评估表单列表 (2)。否则继续使用其他 cond 对。现在我们必须验证一对案例:

> (macroexpand-1 '(new-cond (3 4)))
(IF 3 (PROGN 4) (NEW-COND))

非常好，通过明显的检查，无对情况 (NEW-COND) 减少为零。

其次，宏也可以在其自己的代码中调用自身。因此，例如，如果我们是试图定义 cond 的 Lisp 实现者，则有一种方法我们实际上可以逃脱:

(defmacro cond (&rest cond-pairs)
  (cond      ;; you need cond to compile new-cond syntax, LOL!
    ((null cond-pairs) nil)
    ((atom cond-pairs) (error "new-cond: bad syntax!"))
    (t `(if ,(first (first cond-pairs))
           (progn ,@(rest (first cond-pairs)))
           (new-cond ,@(rest cond-pairs))))))

如何在定义它的宏中使用cond？答案是自举。在宏中扩展的 cond 是我们已经拥有的现有 cond 。这个新定义很好地扩展了现有的 cond，然后替换了它。

这个过程可以重复。我们可以一次又一次地评估上面的defmacro形式；上次求值刚设置的cond用于展开新求值时出现的cond。

如果我们用现有的 Lisp 编译器自举，我们可以使用主机 Lisp 的 cond 开始这个过程，所以我们永远不需要 的第二个自举版本cond 不依赖于 cond 的宏。

请注意，要使其正常工作，我们的替换 cond 宏的主体必须在作为 cond 的新定义安装之前完全扩展。如果宏定义的主体未展开，这将无法工作；那么它就变成了递归调用。换句话说，这不是递归。递归不起作用；宏不需要自身来扩展自身。充其量它可能需要一个现有的宏，该宏不是它本身，但恰好具有相同的名称。