99

我在这个问题上看到了这句话:什么是构建 Web 服务的好的函数式语言?

Scala 尤其不支持尾调用消除,除非在自递归函数中,这限制了您可以执行的组合类型(这是 JVM 的基本限制)。

这是真的?如果是这样,那么造成这种基本限制的 JVM 是什么?

4

5 回答 5

75

这篇文章:递归还是迭代?可能有帮助。

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

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

我相信这仍然可以完成,但这不是一项小任务。

目前,达芬奇机器项目正在进行一些工作。尾调用子项目的状态列为“proto 80%”;它不太可能进入 Java 7,但我认为它很有可能进入 Java 8。

于 2008-09-19T21:44:48.400 回答
27

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

因此,在 Sun 在 JVM 本身中实现尾调用之前,JVM 无法支持任何生产质量的函数式编程语言。他们已经讨论了多年,但我怀疑他们是否会实现尾调用:这将非常困难,因为他们在实现这些基本功能之前已经过早地优化了他们的 VM,而且 Sun 的工作重点是动态语言而不是函数式语言。

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

于 2008-11-06T02:38:57.170 回答
22

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

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

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

于 2009-06-19T02:12:32.923 回答
8

除了 Lambda The Ultimate 中链接的论文(来自上面发布的链接 mmyers),来自 Sun 的 John Rose 对尾调用优化还有更多话要说。

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

我听说有一天它可能会在 JVM 上实现。在达芬奇机器上正在研究尾呼叫支持等。

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

于 2008-09-19T22:23:48.523 回答
0

所有消息来源都指向 JVM 在尾递归的情况下无法优化,但在阅读Java 性能调优(2003,O'reilly)后,我发现作者声称他可以通过实现尾递归来实现更高的递归性能。

您可以在第 212 页找到他的声明(搜索“尾递归”,它应该是第二个结果)。是什么赋予了?

于 2010-12-01T14:55:53.650 回答