Lisp:宏可以递归吗？

Question

我最近开始使用Lisp进行编码,并且已经对宏印象最深刻 - 它们允许我在编译时进行复杂的循环展开,这是我不能用我所知的任何其他语言优雅地执行此操作(即代码生成,同时保持原始结构).

关于优化:我在相同的代码中添加了类型注释(很多"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(...))",我只是快速地用"快速"加上表达式 - 一切都很好.

但是之后...

我意识到,即使这不是事情应该停止的地方:原则上,宏"快"应该......在评估的最高位置调用,在这种情况下:

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

那好吧 :-)

更新:编译失败在一个不同的SO问题中得到解决和解决.

Answer 1

当然.您可以编写一个宏,以递归方式遍历参数表单并以您希望的方式转换它们,一次转换一个子表单.由于这比听起来要复杂一些,因此正确的方法是使用库来进行代码遍历.

Quicklisp包括hu.dwim.walker,显然是arnesi代码walker 的改进版本.

Answer 2

宏不仅被调用,而是在使用时进行扩展,因此在自己的定义中引用宏可能会变得混乱.但是您不必这样做:宏可以调用常规函数,因此您可以编写常规函数来执行递归列表处理,然后只使用宏中的函数.

Answer 3

你绝对可以编写一个在自己的扩展中使用自己的宏.这是完全合理的,并且它是编写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只扩展外部宏,留下一个"承诺"对象来继续扩展.那个"承诺"对象是(NEW-COND (3 4))尾部的宏调用.

当然,真正的宏扩展器将遍历整个形式并"强制"所有这些承诺(未扩展的宏调用),直到不再存在.

我认为这种风格有一些优点,比如易于调试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)通过明显的检查,无对的情况,减少到零.