22

主要问题：我认为尾调用优化 (TCO) 最重要的应用是将递归调用转换为循环（在递归调用具有特定形式的情况下）。更准确地说，当翻译成机器语言时，这通常会翻译成某种系列的跳跃。一些编译为本机代码（例如 SBCL）的 Common Lisp 和 Scheme 编译器可以识别尾递归代码并执行此转换。Clojure 和 ABCL 等基于 JVM 的 Lisps 很难做到这一点。JVM 是什么机器可以防止或使这变得困难？我不明白。JVM 显然没有循环问题。必须弄清楚如何进行 TCO 的是编译器，而不是它编译到的机器。

相关问题：Clojure可以将看似递归的代码转换为循环：如果程序员用关键字替换函数的尾调用，它就好像在执行 TCO recur。但是，如果可以让编译器识别尾调用（例如 SBCL 和 CCL 所做的），那么为什么 Clojure 编译器不能确定它应该以处理尾调用的方式处理尾调用recur？

（对不起——这无疑是一个常见问题解答，我确信上面的评论表明我的无知，但我没有成功找到之前的问题。）

4

3 回答 3

9

Real TCO 适用于尾部位置的任意调用，而不仅仅是自调用，因此如下代码不会导致堆栈溢出：

(letfn [(e? [x] (or (zero? x) (o? (dec x))))
        (o? [x] (e? (dec x)))]
  (e? 10))

显然，您需要 JVM 支持，因为在 JVM 上运行的程序无法操作调用堆栈。（除非您愿意建立自己的调用约定并将相关的开销强加于函数调用；Clojure 旨在使用常规 JVM 方法调用。）

至于消除尾部位置的self调用，这是一个更简单的问题，只要将整个函数体编译为单个JVM方法即可解决。然而，这是一个有限的承诺。此外，recur它的明确性相当受欢迎。

于 2013-10-19T04:29:23.797 回答
4

JVM不支持TCO是有原因的：为什么JVM还不支持tail-call优化？

但是，有一种方法可以通过滥用堆内存和A First-Order One-Pass CPS Transformation 论文中解释的一些技巧来解决这个问题；它由 Chris Frisz 和 Daniel P. Friedman 在 Clojure 中实现（参见clojure-tco）。

现在 Rich Hickey 可以选择默认进行这样的优化，Scala 在某些时候会这样做。相反，他选择依靠最终用户来指定可以由 Clojure 使用 trampolineorloop-recur结构优化的情况。该决定已在此处解释：https ://groups.google.com/d/msg/clojure/4bSdsbperNE/tXdcmbiv4g0J

于 2013-10-22T16:00:08.820 回答
2

在 ClojureConj 2014 的最终演示中，Brian Goetz 指出 JVM 中有一个安全特性可以防止堆栈帧崩溃（因为对于希望将函数返回到其他地方的人来说，这将是一个攻击向量）。

https://www.youtube.com/watch?v=2y5Pv4yN0b0&index=21&list=PLZdCLR02grLoc322bYirANEso3mmzvCiI

于 2015-07-10T14:44:26.060 回答