矩阵加法中常见的lisp递归宏

Question

我必须在Common Lisp(homework)中为列表添加编写一个递归宏.到目前为止我所拥有的是:

(defmacro matrix-add-row (r1 r2 sum_row)
    (if (not (and r1 r2)) `sum_row
        (progn
            `(matrix-add-row (cdr r1) (cdr r2) (cons sum_row (+ (car r1) (car r2))))
            (reverse sum_row)
        )
    )
)

我用这个函数调用

(matrix-add-row `(1 2) `(3 4) ())

作为输出,我得到未评估的代码而不是数字(这导致无限循环).

如何放置,"正确(或正确调用宏)？

Answer 1

首先,对我而言,这似乎是一个与宏相关的奇怪事情.我假设关键是你使用宏转换(matrix-add-row '(1 2) '(3 4))为明确的总和列表(list (+ 1 3) (+ 2 4)).

此外,你所写的有几个问题,看起来你不太明白反引用是如何工作的.所以我认为最简单的帮助方法就是为你解决一个例子.

由于这是家庭作业,我将解决一个不同的(但相似的)问题.您应该能够得到答案并将其用于您的示例.假设我想解决以下问题:

编写一个宏,diffs它计算列表中连续元素对的所有差异.例如,

(diffs '(1 2 3))应该扩展到(list (- 2 1) (- 3 2)),然后评估为(1 1).

请注意,我的宏不会执行实际的减法,所以即使我在运行时之前不知道某些数字,我也可以使用它.(我认为这类问题有点奇怪的原因是它确实需要在编译时知道列表的长度).

我的解决方案将被用作带有一个参数的宏,但如果我想使用递归,我还需要传入一个累加器,我可以从这开始nil.所以我写这样的东西:

(defmacro diffs (lst &optional accumulator)
  ...)

现在我该怎么办lst？如果lst是nil,我想要退出并只返回累加器,list在前面调用,这将是我的列表的代码.像这样的东西:

(defmacro diffs (lst &optional accumulator)
  (cond
    ((null lst)
     ;; You could write `(list ,@accumulator) instead, but that seems
     ;; unnecessarily obfuscated.
     (cons 'list accumulator))
    (t
     (error "Aargh. Unhandled"))))

我们来试试吧!

CL-USER> (diffs nil)
NIL

不是很令人兴奋,但看起来似乎有道理.现在使用macroexpand,只是在没有评估的情况下进行扩展:

CL-USER> (macroexpand '(diffs nil))
(LIST)
T

如果我们已经从递归中获得了一些东西呢？

CL-USER> (macroexpand '(diffs nil ((- a b) (- b c))))
(LIST (- A B) (- B C))
T

看起来不错!现在我们需要处理那里有实际列表的情况.你想要的测试是consp(对于我的例子)它只有在至少有两个元素时才有意义.

(defmacro diffs (lst &optional accumulator)
  (cond
    ;; A list of at least two elements
    ((and (consp lst) (consp (cdr lst)))
     (list 'diffs (cdr lst)
           (cons (list '- (cadr lst) (car lst)) accumulator)))
    ;; A list with at most one element
    ((listp lst)
     (cons 'list accumulator))
    (t
     (error "Aargh. Unhandled"))))

这看起来几乎可行:

CL-USER> (macroexpand '(diffs (3 4 5)))

(LIST (- 5 4) (- 4 3))
T

但是有两个问题:

1. 该列表向后出现
2. 当我们实际构造递归扩展时,代码有点可怕

让我们首先使用反引号运算符修复第二部分:

(defmacro diffs (lst &optional accumulator)
  (cond
    ;; A list of at least two elements
    ((and (consp lst) (consp (cdr lst)))
     `(diffs ,(cdr lst)
             ,(cons `(- ,(cadr lst) ,(car lst)) accumulator)))
    ;; A list with at most one element
    ((listp lst)
     (cons 'list accumulator))
    (t
     (error "Aargh. Unhandled"))))

嗯,它实际上并不短得多,但我认为它更清晰.

对于第二部分,我们可以继续将每个项添加到累加器的末尾而不是前面,但是在Lisp中并不是特别快,因为列表是单独链接的.更好的是向后构造累加器,然后在结束时反转它:

(defmacro diffs (lst &optional accumulator)
  (cond
    ;; A list of at least two elements
    ((and (consp lst) (consp (cdr lst)))
     `(diffs ,(cdr lst)
             ,(cons `(- ,(cadr lst) ,(car lst)) accumulator)))
    ;; A list with at most one element
    ((listp lst)
     (cons 'list (reverse accumulator)))
    (t
     (error "Aargh. Unhandled"))))

现在我们得到:

CL-USER> (macroexpand '(diffs (3 4 5)))

(LIST (- 4 3) (- 5 4))
T

好多了!

最后两件事.首先,我的宏中仍然有一个错误子句.你能看到如何触发吗？你能想到一个比输出错误更好的行为吗？(你的宏将不得不处理同样的问题)

其次,为了调试这样的递归宏,我建议使用macroexpand-1一次只展开一个级别.例如:

CL-USER> (macroexpand-1 '(diffs (3 4 5)))
(DIFFS (4 5) ((- 4 3)))
T
CL-USER> (macroexpand-1 *)
(DIFFS (5) ((- 5 4) (- 4 3)))
T
CL-USER> (macroexpand-1 *)
(LIST (- 4 3) (- 5 4))
T