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))

Answer 1

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

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

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

假设编译器想要将 l 变成一个循环。将(rest s) 赋值给s 没有问题，但是它把(1 + ...) 放在哪里了？ ？