10

在这次演讲中，在前 8 分钟，Runar 解释了 Scala 在尾调用消除方面存在问题，这让我想知道 F# 是否也有类似的问题？如果不是，为什么不呢？

4

3 回答 3

23

Scala 中正确尾调用的问题是工程权衡之一。将 PTC 添加到 Scala 很容易：只需在 SLS 中添加一个句子。瞧：Scala 中的 PTC。从语言设计的角度来看，我们已经完成了。

现在可怜的编译器编写者需要实现该规范。嗯，用 PTC 编译成一种语言很容易……但不幸的是，JVM 字节码不是这样的语言。好吧，那怎么GOTO办？没有。续集？没有。异常（已知等同于延续）？啊，现在我们到了某个地方！因此，我们可以使用异常来实现 PTC。或者，或者，我们可以根本不使用 JVM 调用堆栈并实现我们自己的堆栈。

毕竟JVM上有多个Scheme实现，都支持PTC就好了。您不能在 JVM 上安装 PTC，只是因为 JVM 不支持它们，这是一个神话。毕竟，x86 也没有它们，但是，在 x86 上运行的语言有它们。

那么，如果在 JVM 上实现 PTC 是可能的，那么为什么 Scala 没有它们呢？就像我上面说的，您可以使用异常或您自己的堆栈来实现它们。但是对控制流使用异常或实现自己的堆栈意味着期望 JVM 调用堆栈以某种方式显示的所有内容都将不再起作用。

特别是，您将失去与 Java 工具生态系统（调试器、可视化器、静态分析器）的几乎所有互操作性。您还必须建立与 Java 库互操作的桥梁，这会很慢，因此您也失去了与 Java 库生态系统的互操作性。

但这是 Scala 的主要设计目标！这就是 Scala 没有 PTC 的原因。

我将此称为“Hickey 定理”，以 Clojure 的设计师 Rich Hickey 命名，他曾在一次演讲中说过“尾调用、互操作、性能 – 选择两个”。

您还将向 JIT 编译器展示一些非常不寻常的字节码模式，它可能不知道如何优化。

如果你要将 F# 移植到 JVM，你基本上必须做出这样的选择：你放弃尾调用（你不能，因为语言规范要求它们），你放弃互操作还是放弃放弃性能？在 .NET 上，您可以同时拥有这三个，因为 F# 中的尾调用可以简单地编译为 MSIL 中的尾调用。（虽然实际的翻译比这更复杂，而且在 MSIL 中尾调用的实现在某些极端情况下是错误的。）

这就提出了一个问题：为什么不向 JVM 添加尾调用？好吧，由于 JVM 字节码中的设计缺陷，这非常困难。设计者希望 JVM 字节码具有一定的安全属性。但是，不要以这样一种方式设计 JVM 字节码语言，即您一开始就不能编写不安全的程序（例如，在 Java 中，您不能编写违反指针安全的程序，因为该语言只是首先不让你访问指针），JVM 字节码本身是不安全的，需要一个单独的字节码验证器来保证它的安全。

该字节码验证器基于堆栈检查，尾调用更改堆栈。因此，这两者很难协调，但 JVM 根本无法在没有字节码验证器的情况下工作。花了很长时间和一些非常聪明的人最终弄清楚如何在不丢失字节码验证器的情况下在 JVM 上实现尾调用（参见Clements 和 Felleisen 的带有堆栈检查的尾递归机器和John的 VM 中的尾调用） Rose（JVM 首席设计师）），所以我们现在已经从它是一个开放的研究问题的阶段转移到它“只是”一个开放的工程问题的阶段。

请注意，Scala 和其他一些语言确实具有方法内直接尾递归。然而，这在实现方面非常无聊：它只是一个while循环。大多数目标都有while循环或类似的东西，例如 JVM 有 intra-method GOTO。Scala 也有scala.util.control.TailCallsobject，它是一种重新定义的蹦床。（请参阅Rúnar Óli Bjarnason的Stackless Scala With Free Monads了解这个想法的更通用版本，它可以消除对堆栈的所有使用，而不仅仅是在尾调用中。）这可用于在 Scala 中实现尾调用算法，但这与 JVM 堆栈不兼容，即它看起来不像是对其他语言或调试器的递归方法调用：

import scala.util.control.TailCalls._

def isEven(xs: List[Int]): TailRec[Boolean] =
  if (xs.isEmpty) done(true) else tailcall(isOdd(xs.tail))

def isOdd(xs: List[Int]): TailRec[Boolean] =
 if (xs.isEmpty) done(false) else tailcall(isEven(xs.tail))

isEven((1 to 100000).toList).result

def fib(n: Int): TailRec[Int] =
  if (n < 2) done(n) else for {
    x <- tailcall(fib(n - 1))
    y <- tailcall(fib(n - 2))
  } yield (x + y)

fib(40).result

Clojure 具有recur特殊的形式，它也是一个明确的蹦床。

于 2014-03-31T16:32:54.063 回答
17

F# 没有尾调用的问题。这是它的作用：

  • 如果您有一个尾递归函数，编译器会生成一个带有突变的循环，因为这比生成.tail指令要快

  • 在其他尾调用位置（例如，当使用延续或两个相互递归函数时），它生成.tail指令，因此尾调用由 CLR 处理

  • 默认情况下，尾调用优化在 Visual Studio 的调试模式下关闭，因为这使调试更容易（您可以检查堆栈），但如果需要，您可以在项目属性中将其打开。

在过去，.tail某些运行时（CLR x64 和 Mono）上的指令曾经存在问题，但现在所有这些都已修复并且一切正常。

于 2014-03-31T12:24:43.640 回答
4

事实证明，对于正确的尾调用，您必须在“发布模式”而不是默认的“调试模式”中编译，或者打开项目属性，然后在“构建”菜单中，向下滚动并选中“生成尾调用” ”。感谢 IRC.freenode.net 上的 Arnavion #fsharp 的提示。

于 2016-01-24T05:52:14.580 回答