lisp - 计算列表长度的尾部优化函数的最佳方法是什么？

Question

这是一个论坛发帖人给出的一个例子，我不知道这个尾巴是否优化了。另外，有人可以外行描述尾部优化版本如何胜过普通版本。

(defun mylength (s)
  (labels ((mylength-inner (s x)
            (if (car s) (mylength-inner (cdr s) (+ x 1)) x)))
          (mylength-inner s 0)))

非尾部优化版本？

(defun l (s) (if (car s) (+ 1 (l (rest s))) 0))

score 2 · Accepted Answer

如果函数返回对自身的直接调用或不返回对自身的调用，则可以对函数进行尾调用优化。函数 mylength-inner 将返回xor (mylength-inner (cdr s) (+ x 1))，因此它可以进行尾部优化。

这意味着编译器可以把它变成一个循环，而不是递归地调用函数。要么返回 x，要么将 (cdr s) 分配给 s，增加 x，然后从顶部重新开始。（Scheme 标准要求实现可以做这个优化，而 Common Lisp 标准则留给实现。当然，这个优化是非常有用的东西，所以大多数实现都会这样做。）

在非优化版本中，l 不仅返回对 l 的调用，而是返回对 l 的调用并添加一个的结果。这意味着它不能直接变成循环，因此必须进行所有函数调用。

假设编译器想把 l 变成一个循环。将 (rest s) 分配给 s 没有问题，但它把(1 + ...)?

score 1 · Accepted Answer

尾调用可以优化为不需要调用堆栈上的额外空间，并且它要求函数中的最后一个操作是递归调用，这在您的论坛来源示例中似乎就是这种情况。非尾版本的最后一个操作是加法，所以递归调用需要自己的栈帧。

这遵循一个简单的模式，定义一个内部函数，除了外部函数参数之外，它还接受一个累加器参数，并在你进行时累积你的答案。当你到达终点时，产生累计值。

这里可能有更好的解释：

score 1 · Accepted Answer

FWIW，CL 不保证它会优化尾调用；这取决于实施。SBCL 支持它。这与 Scheme 不同，后者的规范要求编译器消除尾调用。如果你不这样做，你就不是 Scheme。

此外，尾递归在 CL 中相当不习惯。我们有一个loop宏，所以使用它:)

score 0 · Accepted Answer

Scheme 的“教科书”列表长度示例如下：http ://www.scheme.com/tspl3/start.html#./start:h8搜索“长度”。

4 回答 4