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

Question

我必须为 Common Lisp 中的列表添加编写一个递归宏（作业）。到目前为止我所拥有的是：

(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

你的逻辑有两个问题。首先，您在每次迭代而不是在迭代结束时调用 reverse 。然后，您将通过 cons 在 cons 单元格的 cdr 中累积新值，而不是 car.

我也不明白为什么这必须是一个宏，所以使用一个函数。

(defun matrix-add-row (r1 r2 sum-row)
  (if (or (endp r1) (endp r2))
      (reverse sum-row)
      (matrix-add-row (cdr r1)
                      (cdr r2)
                      (cons (+ (car r1) (car r2))
                            sum-row))))

(matrix-add-row '(1 2) '(3 4) ())
;; => (4 6)

Answer 2

首先，对我来说，用宏做这件事似乎很奇怪。我认为重点是您使用宏将 (matrix-add-row '(1 2) '(3 4)) 转换为明确的总和列表，例如 (list (+ 1 3) (+ 2 4)).

此外，您所写的内容有几个问题，您似乎不太了解反引号的工作原理。所以我觉得最简单的帮助方法就是给你解决一个例子。

由于这是作业，我将解决一个不同（但相似）的问题。您应该能够得到答案并将其用于您的示例。假设我要解决以下问题：

Write a macro, diffs, which computes all differences of pairs of successive elements in a list. For example,

(diffs '(1 2 3)) should expand to (list (- 2 1) (- 3 2)), which will then evaluate to (1 1).

请注意，我的宏不会执行实际的减法，因此即使我在运行时之前不知道某些数字，我也可以使用它。（我觉得这种问题有点奇怪的原因是它确实需要在编译时知道列表的长度）。

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

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

现在我可以用 lst 做什么？如果 lst 是 nil，我想触底并仅 return 累加器，并在前面调用 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

但是有两个问题：

列表倒过来
实际构造递归展开的时候代码有点恐怖

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

(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

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

Common lisp recursive macro in matrix addition

macros

recursion

common-lisp