JVM是否会阻止尾调用优化？

Question

JVM是否会阻止尾调用优化？

Jas*_*git 98 java jvm scala tail-recursion

我在这个问题上看到了这个引用:什么是构建Web服务的好函数语言？

特别是Scala不支持尾调用消除,除了自递归函数,这限制了你可以做的组合种类(这是JVM的一个基本限制).

这是真的？如果是这样,那么创建这个基本限制的JVM是什么呢？

Answer 1

Mic*_*ers 74

这篇文章:递归或迭代？可能有帮助.

简而言之,由于安全模型以及始终需要堆栈跟踪的需要,在JVM中很难进行尾调用优化.理论上可以支持这些要求,但可能需要一个新的字节码(参见John Rose的非正式提案).

在Sun bug#4726340中也有更多的讨论,评估(从2002年)结束:

我相信这可以做到,但这不是一项小任务.

目前,Da Vinci Machine项目正在进行一些工作.尾调用子项目的状态列为"proto 80%"; 它不太可能进入Java 7,但我认为它在Java 8上有很好的机会.

@JustinSheehy:什么是不正确的？问题是,"JVM是否会阻止尾调优化？" 答案是,"不,但这很难." (5认同)
你知道如果在java8中包含这个吗？ (5认同)
@Gautham:关于调试的声明是关于使用trampolines作为解决方案,因为缺少JVM上的尾调用.可以并且已经在JVM上实现了尾部调用消除(Arnold Schaighofer在OpenJDK和LLVM中都实现了),因此毫无疑问是否可以完成.当然,微软的CLR支持尾部呼叫消除10年,而F#的发布表明它是一款改变游戏规则的游戏.我认为答案是JVM早已停滞不前. (4认同)
这是一种常见的误解和经常重复的借口,但是不正确.多年来,通过堆栈检查(以及提供有用的堆栈跟踪)的安全性与正确的尾调用不相容已经很成熟.例如,请参阅2004年的这篇论文.http://citeseerx.ist.psu.edu/viewdoc/download?doi=10.1.1.69.3133&rep=rep1&type=pdf Downvoting,因为答案是不正确的. (3认同)

Answer 2

Jon*_*rop 27

基本限制只是JVM不在其字节代码中提供尾调用,因此,构建在JVM上的语言本身没有直接提供尾调用的方法.有一些解决方法可以达到类似的效果(例如蹦床),但它们会带来糟糕的性能和混淆生成的中间代码,这使得调试器无用.

因此,在Sun实现JVM本身的尾调用之前,JVM不能支持任何生产质量的函数式编程语言.他们多年来一直在讨论它,但我怀疑它们是否会实现尾调用:它将非常困难,因为它们在实现这些基本功能之前过早地优化了它们,而Sun的工作主要集中在动态语言而不是函数语言上.

因此,有一个非常强烈的论点,即Scala不是一种真正的函数式编程语言:自从Scheme于30多年前首次引入以来,这些语言已将尾调用视为一项基本特性.

@Ingo:只有在程序运行时不认为程序中的堆栈溢出是一个重大问题.根据它的bug跟踪器,即使是Scala编译器本身也一直受到堆栈溢出的困扰.因此即使是经验最丰富的Scala开发人员仍然会弄错... (8认同)
F#可以成为一名倡导者.但是我已经注意到你很长一段时间(甚至在使用网络之前的几年)因为对F#的所有事情都持敌视态度,但你的阐述表明你不知道你在谈论什么.就像这里:你的论点似乎是一种语言,我可以写一个程序,中止堆栈溢出不是一个功能的？但是,对于我可能引发堆溢出的语言,我不能说同样的论点吗？因此,神圣的F#本身不会算作功能. (7认同)
@Ingo:函数式编程中的几个习语,如相互递归和连续传递样式,可能需要尾部调用消除才能工作.没有它,你的程序将堆栈溢出.如果一种语言不能可靠地运行惯用的功能代码,它是否有用？正如你所说,答案是判断,但在实践中是一个重要的区别.Martin Trojer刚刚发布了一篇有趣的博客文章:http://martinsprogrammingblog.blogspot.com/2011/11/tail-calls-in-f-clojure-and-scala.html (7认同)
因此,有一个非常强烈的论点,即Scala不是一种真正的函数式编程语言 - 这个论点实际上相当薄弱.当然是`尾部调用[as]一个必不可少的功能`,如果底层硬件(或虚拟机)直接支持它,那就很好.但它的实施细节. (5认同)
仍然,只是因为JVM(遗憾的是,毫无疑问)不能进行尾调用,这并不意味着尾部调用消除是不可能的.这就好像有人说浮点计算只能在具有FPU的计算机上进行. (2认同)

Answer 3

Dan*_*ral 21

Scala 2.7.x支持对最终方法和本地函数的自递归(一个函数调用自身)进行尾调用优化.

Scala 2.8也可能带有对trampoline的库支持,这是一种优化相互递归函数的技术.

有关Scala递归状态的大量信息可以在Rich Dougherty的博客中找到.

Answer 4

far*_*ran 8

除了在Lambda The Ultimate中链接的论文(来自上面发布的链接mmyers)之外,来自Sun的John Rose还有更多关于尾部呼叫优化的说法.

http://blogs.oracle.com/jrose/entry/tail_calls_in_the_vm

我听说有一天它可能会在JVM上实现.Da Vinci机器正在研究尾部呼叫支持等.

http://openjdk.java.net/projects/mlvm/

归档时间：	17 年，2 月前
查看次数：	24193 次
最近记录：	12 年，9 月前