F#有尾部呼叫消除吗？

Question

在这个谈话中，在头8分钟，Runar解释了Scala在尾部调用消除方面的问题，这让我怀疑F#是否有类似的问题？若否，原因为何？

Answer 1

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

现在，糟糕的编译器编写人员需要实现该规范。嗯，用PTCs编译成一种语言是很容易的…。但不幸的是，JVM字节码不是这样一种语言。好吧，那GOTO呢？不是的。延续？不是的。例外(已知等同于延续)？啊，现在我们有进展了！因此，我们可以使用异常来实现PTCs。或者，我们也可以完全不使用JVM调用堆栈并实现自己的堆栈。

毕竟，JVM上有多个Scheme实现，它们都很好地支持PTC。这是一个神话，您不能在JVM上使用PTCs，仅仅因为JVM不支持它们。毕竟，x86也没有它们，但是有一些语言运行在x86上。

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

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

但这是Scala的主要设计目标！这就是为什么Scala没有PTCs。

我把这叫做“Hickey定理”，这是Rich的名字，他曾在一次谈话中说过“尾部呼叫，互操作，性能选择二”。

您还将向JIT编译器提供一些非常不寻常的字节代码模式，这些模式可能不知道如何进行优化。

如果要将F#移植到JVM，基本上必须做出这样的选择:您是放弃尾调用(因为语言规范要求它们)，还是放弃性能？在.NET上，您可以拥有所有这三个，因为F#中的尾调用可以简单地编译成MSIL中的尾调用。(尽管实际的转换要复杂得多，而且在某些角落的情况下，some中的尾调用的实现是错误的。)

这就提出了一个问题:为什么不向JVM添加尾调用呢？由于JVM字节代码中存在设计缺陷，这是非常困难的。设计人员希望JVM字节代码具有某些安全属性。但是，JVM字节代码语言的设计方法不是一开始就不能编写不安全的程序(例如，在Java中，您不能编写违反指针安全的程序，因为JVM字节代码本身并不允许您访问指针)，它本身是不安全的，需要一个单独的字节代码验证器来确保其安全性。

字节码验证器基于堆栈检查，尾调用更改堆栈。因此，两者很难调和，但是JVM没有字节代码验证器就无法工作。我们花了很长时间和一些非常聪明的人，终于找到了如何在JVM上实现尾调用，而不会丢失字节代码验证器(参见克莱门茨和费莱森和作者: John Rose (JVM首席设计人员))，因此，我们现在已经从一个开放的研究问题阶段转移到了一个“只是”一个开放的工程问题的阶段。

请注意，Scala和其他一些语言确实有方法内直接尾递归。然而，就实现而言，这是相当无聊的:它只是一个while循环。大多数目标都有while循环或类似的东西，例如JVM有方法内的GOTO。斯卡拉也有对象，这是一种重新化的蹦床。(有关这个想法的更通用版本，请参见Rúnar，它可以消除堆栈的所有使用，而不仅仅是尾调用。)这可以用于在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有特殊形式，这也是一个显式蹦床。

Answer 2

F#在尾调用方面没有问题。它所做的事情如下：

• 如果您有一个尾递归函数，编译器会生成一个带有变异的循环，因为这比生成.tail指令更快。
• 在其他尾部调用位置(例如，使用连续或两个相互递归的函数)，它生成.tail指令，因此尾调用由CLR处理。
• 默认情况下，在Visual中，尾部优化在调试模式下被关闭，因为这使得调试更容易(您可以检查堆栈)，但是如果需要，可以在项目属性中打开它。

在过去，.tail指令在某些运行时(CLR、x64和Mono)会出现问题，但现在所有这些都已经修复，一切正常。

Answer 3

事实证明，对于正确的尾调用，您必须在“释放模式”中编译，而不是默认的"Debug模式“，或者打开您的项目属性，然后在Build菜单中向下滚动并检查”生成尾调用“。感谢IRC.freenode.net #fsharp上的阿纳芬的提示。