Common Lisp 中的高效收集函数

Question

我正在学习 Lisp，并编写了以下函数来收集结果列表。

(defun collect (func args num)
  (if (= 0 num)
      ()
      (cons (apply func args)
        (collect func args (- num 1)))))

它产生与内置循环函数类似的输出。

CL-USER> (collect #'random '(5) 10)
(4 0 3 0 1 4 2 1 0 0)
CL-USER> (loop repeat 10 collect (random 5))
(3 3 4 0 3 2 4 0 0 0)

然而，当我尝试生成一个 100,000 个元素长的列表时，我的收集函数会破坏堆栈，

CL-USER> (length (collect #'random '(5) 100000))
Control stack guard page temporarily disabled: proceed with caution

而循环版本则不会。

CL-USER> (length (loop repeat 100000 collect (random 5)))
100000

如何使我的版本更加节省空间，除了 consing 之外还有其他选择吗？我认为这是尾递归。我正在使用 sbcl。任何帮助都会很棒。

Answer 1

不，它不是尾递归。 ANSI Common Lisp 和你的代码都没有对此做出任何说明：

(defun collect (func args num)
  (if (= 0 num)
      ()
      (cons (apply func args)
            (collect func args (- num 1)))))

如果你查看你的代码，就会发现你对 COLLECT 的调用存在一个缺点。此 CONS 接收递归调用 COLLECT 的值。所以COLLECT不能是尾递归。通过引入累加器变量将函数重写为看起来尾递归的函数相对简单。各种 Lisp 或Scheme 文献应该对此进行描述。

在 Common Lisp 中，对迭代计算进行编程的默认方法是使用以下几种迭代结构之一：DO、DOTIMES、DOLIST、LOOP、MAP、MAPCAR...

Common Lisp 标准不提供尾调用优化 (TCO)。必须指定在存在其他几种语言功能的情况下 TCO 应该做什么。例如，动态绑定和特殊变量会对 TCO 产生影响。但 Common Lisp 标准根本没有提及一般性的 TCO 以及 TCO 可能产生的影响。 TCO 不是 ANSI Common Lisp 标准的一部分。

一些 Common Lisp 实现可以通过编译器开关启用各种尾部调用优化。请注意，启用这些功能的方法和限制都是特定于实现的。

总结：在 Common Lisp 中使用迭代结构而不是递归。

(defun collect (func args num)
  (loop repeat num
        collect (apply #'func args)))

额外的好处：它更容易阅读。

Answer 2

ANSI 标准不要求 Common Lisp 实现进行尾调用优化；然而，大多数值得他们关注的人（包括 SBCL）确实进行了优化。

另一方面，你的函数不是尾递归的。可以通过使用引入额外参数来累积中间结果的常见技巧将其变成一个：（

(defun collect (func args num)
  (labels ((frob (n acc)
             (if (= 0 n)
                 acc
                 (frob (1- n) (cons (apply func args) acc)))))
    (frob num nil)))

原始参数 FUNC 和 ARGS 在局部函数中被消除，因为它们相对于局部函数而言是恒定的）。

Answer 3

那么，递归的替代方法是迭代。

您应该知道，Common Lisp 不需要其实现者进行尾递归，与Scheme 不同。

(defun mycollect (func args num)
  (let ((accumulator '()))     ; it's a null list. 
    (loop for i from 1 to num 
      do
      ;;destructively cons up the accumulator with the new result + the old accumulator
      (setf accumulator                   
        (cons (apply func args) accumulator)))
  accumulator))                ; and return the accumulator