我在这个问题上看到了以下引用：什么是适合构建Web服务的好的函数式语言？
特别是在Scala中，尾递归消除只在自递归函数中支持，这限制了你可以做哪些组合（这是JVM的根本局限）。
这是真的吗？如果是的话，是什么让JVM产生了这种根本性的限制？
JVM是否防止尾调用优化？
100
- Jason Dagit
5个回答
77
这篇文章：递归还是迭代？可能会有所帮助。
简而言之，在JVM中很难进行尾调用优化，因为存在安全模型和始终需要有堆栈跟踪的需求。理论上可以支持这些要求，但可能需要一个新的字节码（参见John Rose的非正式提案）。
在Sun bug #4726340中还有更多讨论，其中的评估（来自2002年）如下：
简而言之，在JVM中很难进行尾调用优化，因为存在安全模型和始终需要有堆栈跟踪的需求。理论上可以支持这些要求，但可能需要一个新的字节码（参见John Rose的非正式提案）。
在Sun bug #4726340中还有更多讨论，其中的评估（来自2002年）如下：
目前，在Da Vinci Machine项目中正在进行一些工作。尾调用子项目的状态被列为“proto 80%”；它不太可能进入Java 7，但我认为它在Java 8中有很大的机会。我相信这仍然是可行的，但这不是一个小任务。
- mmyers
6
我没有完全理解这个解释。我认为尾调用优化是由编译器实现的。假设您有一个函数，可以通过编译器进行尾调用优化，那么您也可以有一个等效的非递归函数，使用循环实现相同的功能，对吗？如果是这样，那么编译器不能完成这项工作吗？我无法理解对JVM的依赖关系。与生成本地i386代码的Scheme编译器相比如何？ - Gautham Ganapathy
好的，刚刚看到Jon在下面的回答。所以，并不是说它不能被实现，而是不能得到适当的调试器支持。 - Gautham Ganapathy
4我的关于调试的陈述是针对在JVM上缺乏尾调用消除的情况下使用跳板来解决的。尾调用消除可以且已经在JVM上实现过（Arnold Schaighofer在OpenJDK和LLVM中都实现了），因此无论是否可以进行尾调用消除都没有问题。当然，微软的CLR在10年前就支持尾调用消除，而发布F #证明它是一个改变游戏规则的东西。我认为答案是JVM自长以来一直停滞不前。 - J D
3这是一个常见的误解和经常重复的借口，但是是不正确的。多年来已经非常明确地确定，通过堆栈检查进行安全性（并提供有用的堆栈跟踪）与正确的尾调用是不矛盾的。例如，可以参考这篇2004年的论文。http://citeseerx.ist.psu.edu/viewdoc/download?doi=10.1.1.69.3133&rep=rep1&type=pdf，对于答案不正确进行负评。 - Justin Sheehy
5有什么不正确吗？问题是，“JVM是否防止尾调用优化？”答案是，“不是，但很难。” - Michael Myers
5你知道在Java8中是否包含这个吗？ - nachokk
28
根本限制在于JVM在它的字节码中没有提供尾调用，因此，基于JVM构建的语言无法直接提供尾调用。虽然有一些变通方法可以实现类似的效果（如trampolining），但它们的代价是性能极差，并且会混淆生成的中间代码，使调试器无法使用。
因此，在Sun公司实现JVM中的尾调用之前，JVM无法支持任何生产级别的函数式编程语言。他们已经讨论了多年，但我怀疑他们是否会实现尾调用：这将非常困难，因为他们在实现这种基本功能之前过早地优化了他们的虚拟机，而Sun公司的努力主要集中在动态语言而不是函数式语言上。
因此，有一个很强的论点认为Scala不是一个真正的函数式编程语言：自从Scheme在30多年前首次推出以来，这些语言一直把尾调用视为一个基本特征。
- Jon Harrop
10
5因此，有一个非常有力的论点认为Scala不是真正的函数式编程语言 - 实际上这个论点相当薄弱。当然，尾调用是一项重要功能，并且如果底层硬件（或虚拟机）直接支持它会很好，但这只是实现细节。 - Ingo
8只有当您不认为程序在运行时出现堆栈溢出并被用户看到是一个重大问题时，才能这样做。根据其错误跟踪器，甚至Scala编译器本身也受到堆栈溢出的困扰。因此，即使是最经验丰富的Scala开发人员仍然会犯错... - J D
7支持某种语言，比如F#，是可以的。但我注意到你长期以来（甚至在usenet上几年前）对除F#以外的一切都很敌对，然而你的阐述表明你并不知道你在说什么。就像这里：你的论点似乎是，在我能写一个会因堆栈溢出而中止的程序的语言中，它不能算作函数式语言？但同样的论点难道不也适用于那些可以引发堆溢出的语言吗？因此，即使是神圣的F#本身也不能算作函数式语言。 - Ingo
7@Ingo: 函数式编程中有几个习语，如相互递归和续延传递风格，可能需要尾调用消除才能正常运行。如果没有它，你的程序将出现堆栈溢出。如果一种语言不能可靠地运行习惯性的函数式代码，那么它是否是函数式的？这个问题涉及判断，正如你所说，但在实践中是一个重要的区别。Martin Trojer刚刚发布了一篇有趣的博客文章：http://martinsprogrammingblog.blogspot.com/2011/11/tail-calls-in-f-clojure-and-scala.html - J D
2尽管 JVM（遗憾的是，毫无疑问）不能执行尾调用，但这并不意味着尾调用消除是不可能的。这就像有人声称浮点计算只能在带有 FPU 的计算机上进行一样。 - Ingo
显示剩余5条评论
22
Scala 2.7.x支持尾递归优化自递归（函数调用自身）的最终方法和局部函数。
Scala 2.8可能会提供库支持来优化相互递归函数的trampoline技术。
关于Scala递归状态的大量信息可以在Rich Dougherty's博客中找到。
- Daniel C. Sobral
2
请问您能否更新一下Scala的当前状态问题？ - om-nom-nom
据我所知，Scala方面和JVM方面都没有发生任何变化。 - Daniel C. Sobral
8
除了Lambda The Ultimate上的文章（来自mmyers上面的链接），来自Sun的John Rose还谈到了尾递归优化。
http://blogs.oracle.com/jrose/entry/tail_calls_in_the_vm
我听说JVM可能会在某一天实现这个功能。Da Vinci Machine正在研究尾调用支持和其他一些东西。
- Jay
0
所有来源都指向JVM在尾递归的情况下无法进行优化，但是在阅读了《Java性能调优》（2003年，O'Reilly）后，我发现作者声称通过实现尾递归可以获得更好的递归性能。
您可以在第212页找到他的说法（搜索“tail recursion”，它应该是第二个结果）。这是怎么回事？
您可以在第212页找到他的说法（搜索“tail recursion”，它应该是第二个结果）。这是怎么回事？
- fthinker
1
IBM在其JVM实现中支持某种形式的TCO（作为一种优化，因此不保证）。也许Java性能调优的作者认为这个特性最终会被所有的JVM实现所采纳。
http://www.ibm.com/developerworks/java/library/j-diag8.html - llemieng
网页内容由stack overflow 提供, 点击上面的可以查看英文原文，
原文链接
原文链接