尾部优化函数计算列表长度的最佳方法是什么？
这是论坛发帖者给出的一个例子，我不知道这个尾巴是否优化过。 另外，有人可以外行描述一下尾部优化版本如何胜过正常版本吗？
(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))
Here is an example that a forum poster gave, I can't tell if this tail optimized. Also, could someone give a laymans description of how a tail optimized version would trump the normal version.
(defun mylength (s)
(labels ((mylength-inner (s x)
(if (car s) (mylength-inner (cdr s) (+ x 1)) x)))
(mylength-inner s 0)))
A non tail optimized version?
(defun l (s) (if (car s) (+ 1 (l (rest s))) 0))
如果你对这篇内容有疑问，欢迎到本站社区发帖提问 参与讨论，获取更多帮助，或者扫码二维码加入 Web 技术交流群。
绑定邮箱获取回复消息
由于您还没有绑定你的真实邮箱，如果其他用户或者作者回复了您的评论，将不能在第一时间通知您！
发布评论
评论（4）
如果函数返回直接调用自身或不调用自身，则该函数可以进行尾调用优化。 函数 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 + ...)放在哪里呢？A function can be tail-call optimized if it returns a straight call to itself or no call to itself. The function mylength-inner will return either
xor(mylength-inner (cdr s) (+ x 1)), and so it can be tail-optimized.This means the compiler can turn it into a loop instead of calling the function recursively. Either return x, or assign (cdr s) to s, increment x, and start again at the top. (The Scheme standard requires that implementations be able to do this optimization, while the Common Lisp standard leaves it up to the implementation. Of course, this optimization is a very useful thing, so most implementations will do it.)
In the non-optimized version, l doesn't just return a call to l, but rather the result of a call to l with one added. This means it can't be directly turned into a loop, so all the function calls will have to be made.
Suppose the compiler wanted to turn l into a loop. There's no problem with the assignment of (rest s) to s, but where does it put the
(1 + ...)?尾部调用可以优化为不需要调用堆栈上的额外空间，并且它要求函数中的最后一个操作是递归调用，这在您的论坛来源示例中似乎是这种情况。 非尾版本中的最后一个操作是加法，因此递归调用需要自己的堆栈帧。
这遵循一个简单的模式，定义一个内部函数，除了外部函数参数之外，它还接受累加器参数，并随时累积你的答案。 当你到达终点时，产生累计值。
这里可能有更好的解释：
http://mitpress.mit.edu/sicp/full-text/book/book-ZH-11.html#%_sec_1.2.1
Tail calls can be optimized to not need extra space on the call stack, and it requires that the last operation in the function be the recursive call, which appears to be the case in your forum-sourced example. The last operation in the non-tail version is an addition, so the recursive call requires its own stack frame.
This follows a simple pattern, define an inner function that takes an accumulator argument in addition to the outer functions arguments, and accumulate your answer as you go. When you get to the end, yield the accumulated value.
There's probably a better explanation here:
http://mitpress.mit.edu/sicp/full-text/book/book-Z-H-11.html#%_sec_1.2.1
FWIW，CL 不保证它会优化尾部调用； 这取决于实施。 SBCL 支持它。 这与Scheme不同，Scheme的规范要求编译器消除尾部调用。 如果你不这样做，你就不是Scheme。
而且，尾递归在 CL 中相当不惯用。 我们有一个
loop宏，所以使用它:)FWIW, CL doesn't guarantee that it will optimize away tail calls; it depends on the implementation. SBCL supports it. This is different from Scheme, where the spec requires that the compiler eliminate tail calls. If you don't do it, you're not Scheme.
Also, tail recursion is rather non-idiomatic in CL. We have a
loopmacro, so use it :)列表长度的方案“教科书”示例如下： http:// www.scheme.com/tspl3/start.html#./start:h8 搜索“长度”。
Scheme's "textbook" example of list length would be here: http://www.scheme.com/tspl3/start.html#./start:h8 search for "length."