为什么JVM仍不支持尾调用优化？

Question

在JVM中是否有防止尾调用优化两年后，似乎已经有原型 实现，而且MLVM已经将该特性列为“proto 80％”一段时间了。

难道Sun / Oracle方面没有支持尾调用的积极兴趣，还是仅仅因为尾调用被“[...]注定在每个特性优先级列表上都排名第二 [...]”，如JVM Language Summit所提到的那样？

如果有人测试了MLVM版本并能分享一些印象（如果有的话），我会非常感兴趣。

更新：请注意，像Avian这样的某些虚拟机支持适当的尾调用而不会出现任何问题。

- soc

---

据报道，Sun公司的员工正在从Oracle公司大规模离职，除非Oracle明确表示会继续进行当前的项目，否则我不认为任何一个项目会继续。 :( - Thorbjørn Ravn Andersen

请注意，您接受的答案完全是错误的。尾调用优化和面向对象编程之间不存在根本性冲突，当然，像OCaml和F#这样的几种语言同时具有OOP和TCO。 - J D

将OCaml和F#称为面向对象编程语言本身就是个笑话。但是没错，除了运行时必须检查正在优化的方法是否被其他地方覆盖/子类化之外，面向对象编程和尾递归优化没有太多共同点。 - soc

作为一个有C语言背景的人，我一直认为在任何现代JVM中都会自然支持TCO（尾调用优化）。我从未想过要实际检查它，但当我真正进行检查时，结果令人惊讶...... - thkala

你的“事实”完全是无稽之谈，@soc 的意思是除了运行时需要检查被优化的方法是否被其他地方重写/子类化。请注意，我没有进行解释或添加额外内容。 - J D

Answer 1

过去在Java中未实现尾递归优化(TCO)的原因之一（并且被视为困难）是JVM中的许可模型是栈敏感的，因此尾调用必须处理安全方面。

我相信Clements和Felleisen [1] [2]已经证明了这不是障碍，而且我很确定问题中提到的MLVM补丁也解决了这个问题。

我意识到这并没有回答你的问题；只是添加了有趣的信息。

1. http://www.ccs.neu.edu/scheme/pubs/esop2003-cf.pdf
2. http://www.ccs.neu.edu/scheme/pubs/cf-toplas04.pdf

- Alex Miller

---

+1. 在 Brian Goetz 的演示结束时，请听问题/回答。https://www.youtube.com/watch?v=2y5Pv4yN0b0&t=3739 - mcoolive

Answer 2

诊断Java代码：提高Java代码的性能（备用链接）解释了JVM为什么不支持尾调用优化。

虽然已经很清楚如何将尾递归函数自动转换为简单循环，但Java规范并不要求进行此转换。可能，其原因之一是在面向对象语言中通常无法静态地进行这种转换。相反，必须由JIT编译器动态地将尾递归函数转换为简单循环。

它还举了一个Java代码无法转换的例子。

正如清单3中的示例所示，我们不能指望静态编译器在保留语言语义的同时对Java代码进行尾递归转换。相反，我们必须依赖于JIT的动态编译。取决于JVM，JIT可以或者不可以执行。

然后它给出了一个测试，可以用来确定您的JIT是否支持此功能。

当然，由于这是IBM的论文，它包括一个插头：

我使用了几个Java SDK运行这个程序，结果令人惊讶。在Sun的Hotspot JVM版本1.3上运行，结果显示Hotspot不执行此转换。在默认设置下，堆栈空间在我的机器上不到一秒钟就耗尽了。另一方面，IBM的JVM版本1.3却毫无问题地运行，表明它确实以这种方式转换代码。

- emory

---

就译文而言，我尽量保持忠实于原文的意思并使其更易于理解。需要翻译的内容如下：FWIW，尾调用并不仅限于他所说的自递归函数。尾调用是出现在尾部位置的任何函数调用。它们不一定是对自身的调用，也不必是对静态已知位置的调用（例如，它们可以是虚方法调用）。如果针对常规情况正确地执行了尾调用优化，则他所描述的问题就不存在了，因此，他的示例在支持尾调用的面向对象语言（例如OCaml和F＃）中完美运行。 - J D

“must be done dynamically by a JIT compiler” 的意思是这必须由JVM本身而非Java编译器完成。但是OP在询问JVM相关的内容。 - Raedwald

通常，在面向对象的编程语言中，无法静态地进行转换。这是一句引用话，但每次我看到这种借口，我都想问一下数字——因为在实践中，我不会感到惊讶如果在大多数情况下，它可以在编译时确定。 - greenoldman

所引用文章的链接现已失效，但谷歌有其缓存。更重要的是，作者的推理有误。给出的示例可以使用静态编译而非动态编译进行尾调用优化，只需编译器插入一个“instanceof”检查，以查看“this”是否为“Example”对象（而不是“Example”的子类）。 - Alex D

链接到网档 http://web.archive.org/web/20120506085636/http://www.ibm.com/developerworks/java/library/j-diag8/index.html - Suvitruf - Andrei Apanasik

Answer 3

也许你已经知道了，但实际上该功能并不像听起来那么简单，因为Java语言实际上将堆栈跟踪暴露给程序员。

考虑以下程序：

public class Test {

    public static String f() {
        String s = Math.random() > .5 ? f() : g();
        return s;
    }

    public static String g() {
        if (Math.random() > .9) {
            StackTraceElement[] ste = new Throwable().getStackTrace();
            return ste[ste.length / 2].getMethodName();
        }
        return f();
    }

    public static void main(String[] args) {
        System.out.println(f());
    }
}

尽管这个函数有一个"tail-call"（尾递归），但它可能不会被优化。（即使它被优化，由于程序语义依赖于整个调用堆栈的跟踪，它仍然需要对整个调用堆栈进行簿记。）

基本上，这意味着支持这个功能而仍然保持向后兼容性是很困难的。

- aioobe

---

发现你思考上的错误：“需要记录整个调用栈，因为程序语义依赖于它。” :-) 这就像新的“抑制异常”。 依赖这种事情的程序注定会出错。 在我看来，程序的行为绝对正确：丢弃堆栈帧是尾调用的全部意义所在。 - soc

@Marco，但几乎任何方法都可能抛出异常，从而将整个调用堆栈绑定在一起，对吗？此外，在这种情况下你无法事先确定哪些方法将间接调用g...考虑到多态性和反射等因素。 - aioobe

@soc，只是因为某些新功能会破坏一些向后兼容性，并不意味着如果其他功能也破坏向后兼容性就没有任何区别... 不，我的答案没有错误。暴露API中的堆栈跟踪对于(软)尾递归构成了问题，这是为什么这种功能很麻烦添加的原因之一（许多原因之一）。 - aioobe

这个语言暴露调用栈的事实使得实现这一点变得困难。该语言是否要求由方法x()返回的堆栈跟踪（通过getStackTrace()获得），显示x()是从y()调用的？因为如果在此方面存在某些自由，那么就不存在实际问题。 - Raedwald

这只是修改一个方法规范的措辞问题，从“提供所有堆栈帧”改为“提供所有活动堆栈帧，并省略由尾调用废除的那些”。此外，可以将其作为命令行开关或系统属性来设置是否启用尾调用。 - Ingo

Answer 4

Java是你可能想象中最不具备功能的语言（嗯，好吧，也许并不是，MUMPS 除外！），但这对于像Scala这样的JVM语言来说将是一个巨大的优势。

我的观察是，使JVM成为其他语言的平台似乎从未成为Sun公司的首要任务，我猜现在对于Oracle公司也是如此。

- oxbow_lakes

---

@Thorbjørn - 我写了一个程序来预测任何给定程序是否会在有限的时间内停止运行。这花费了我 很长时间！ - oxbow_lakes

我使用的第一种BASIC语言没有函数，而是使用GOSUB和RETURN。我认为LOLCODE也不是非常实用（你可以从两个方面理解这句话）。 - David Thornley

@David，functional != 有函数。 - Thorbjørn Ravn Andersen

@Thorbjørn Ravn Andersen：不是必须的，但你不觉得这是一种前提条件吗？ - David Thornley

OP没有使用Java这个词，只用了JVM。 - Marco van de Voort

让JVM成为其他语言的平台似乎从未成为Sun公司的优先事项。他们在将JVM作为动态语言平台方面投入了相当多的精力，而对于函数式语言则没有这么多的投入。 - J D

Answer 5

这不是Java的问题，而是JVM的问题。Java只是JVM语言中最古老的。

实现TCO的方法是跳到下一个堆栈帧时删除当前帧，在运行程序和当前调用变量之间，应该有其他地方存储变量... ;)

最好的方法是为在其他帧中进行跳转-调用的新特殊调用操作码，使其完成这些事情。他们已经为虚拟调用做到了这一点。在解释上真的不是个问题，JIT可能会引发其他问题，而JVM已经足够庞大了。

在Java或其他语言中，由于没有适当的TCO，另一种方法是使用trampolining，但它会添加大量代码。或者使用特定的异常，但它会造成很多混乱。而且它存在于你的代码中，但不存在于其他人的库中...

啊！如果Rich Hickey添加了（recur...）东西（它不是一个函数），那是因为缺乏真正的TCO，他不希望人们认为有一个TCO。他可以在内部尾部调用中很容易地实现自动TCO。它还有助于检测不在尾部位置的不良尾部调用。

还有一种外部TCO的（trampoline...）东西，但它很混乱（就像蹦床），除了在糟糕的堆栈情况下几乎没有使用。

没错，很多虚拟机都管理TCO。我听说CLR会这样做。我甚至看到过一个付费的JVM也可以管理它（以前的事情，记不清了...）

JavaScript中的跳板示例：https://codeinjavascript.com/2020/06/13/tail-call-optimization-tco/

关于HotSpot VM上帧覆盖的TCO的旧论文：https://ssw.jku.at/Research/Papers/Schwaighofer09Master/schwaighofer09master.pdf

- Ivan Pierre