如何评估递归宏定义

Question

这个宏的递归定义做了它应该做的事情(从1到n的总和):

(defmacro sum-int-seq (n)
  `(cond
     ((equal 0 ,n) 0)
     (t (+ ,n (sum-int-seq (- ,n 1))))))

例如(sum-int-seq 5)给出15.

但为什么它有效呢？当宏扩展时,我得到这个:

(macroexpand '(sum-int-seq 5))
(IF (EQUAL 0 5) 0 (+ 5 (SUM-INT-SEQ (- 5 1))))

但是因为sum-int-seq是一个宏,所以宏评估应该变成一个无限循环.编译器是否创建了递归函数？如果这个定义创建了一个递归函数,有没有办法以递归方式定义宏？

(为简洁起见,这是一个愚蠢的例子,一个函数当然会更好地工作)

Answer 1

你的例子不起作用.

它可能在翻译中起作用.但是使用编译器,您将在编译期间看到无限循环.

CL-USER 23 > (defun test (foo)
                (sum-int-seq 5))
TEST

让我们使用LispWorks解释器:

CL-USER 24 > (test :foo)
15

让我们尝试编译函数:

CL-USER 25 > (compile 'test)

Stack overflow (stack size 15997).
  1 (continue) Extend stack by 50%.
  2 Extend stack by 300%.
  3 (abort) Return to level 0.
  4 Return to top loop level 0.

Type :b for backtrace or :c <option number> to proceed.
Type :bug-form "<subject>" for a bug report template or :? for other options.

那么,现在接下来的问题是:为什么它在解释器中起作用,但是编译器无法编译它？

好的,我会解释一下.

我们先来看看口译员.

• 它看到了(sum-int-seq 5).
• 它宏观扩展到(COND ((EQUAL 0 5) 0) (T (+ 5 (SUM-INT-SEQ (- 5 1))))).
• 然后评估上面的表格.它确定它需要计算(+ 5 (SUM-INT-SEQ (- 5 1))).为此,它需要宏扩展(SUM-INT-SEQ (- 5 1)).
• 最终它会扩展成类似的东西(cond ((EQUAL 0 (- (- (- (- (- 5 1) 1) 1) 1) 1)) 0) ....然后返回0并且计算可以使用此结果并将其他术语添加到其中.

解释器获取代码,评估它的内容,并在必要时进行宏​​扩展.然后评估生成的代码或宏扩展.等等.

现在让我们看一下编译器.

• 它看到(sum-int-seq 5)并将宏扩展到(COND ((EQUAL 0 5) 0) (T (+ 5 (SUM-INT-SEQ (- 5 1))))).
• 现在宏扩展将最终在子表单上完成.
• 编译器将宏扩展(SUM-INT-SEQ (- 5 1)).请注意,代码永远不会被评估,只会扩展.
• 编译器将宏扩展(SUM-INT-SEQ (- (- 5 1) 1))等等.最后你会看到堆栈溢出.

编译器遍历(递归编译/扩展)代码.它可能不会执行代码(除非它进行优化或宏实际上明确地评估它).

对于递归宏,您需要实际倒计时.如果你在宏内部进行评估,那么类似的东西(sum-int-seq 5)可以起作用.但(defun foo (n) (sum-int-seq n))由于编译器不知道n的值是什么,因此这是没有希望的.