F#有尾调用消除吗？

Question

F#有尾调用消除吗？

scalaf#tail-recursiontail-call-optimization

10

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

- jhegedus

5

CLR通过tail操作码支持尾调用优化（.NET 4进行了一些改进），就我所知，JVM目前还不支持尾调用。 - Patryk Ćwiek

@PatrykĆwiek，我无法确定，这只是尾递归调用吗？还是所有类型的尾调用，例如互递归函数中的尾调用，如odd/even。 - Ionuț G. Stan

从这篇博客文章中可以看出，相互递归的函数也使用了tail操作码。 - Patryk Ćwiek

2

@PatrykĆwiek 谢谢。那么它比JVM有更好的支持。 - Ionuț G. Stan

3个回答

17

F#没有尾调用问题。它的处理方式如下:

如果你有一个单一的尾递归函数，编译器会生成一个循环并进行突变，因为这比生成.tail指令更快。
在其他尾调用位置（例如使用continuations或两个相互递归的函数），编译器生成.tail指令，所以尾调用由CLR处理。
默认情况下，在Visual Studio的Debug模式中，尾调用优化被关闭，因为这样可以更容易地进行调试（可以检查堆栈），但如果需要，可以在项目属性中打开它。

在旧版本中，.tail指令在某些运行时（CLR x64和Mono）上存在问题，但现在已经修复了所有问题，一切正常。

- Tomas Petricek

4

所有这些问题现在都已经得到解决，一切正常运作。虽然被宣传为这样的情况，但不幸地，这并不是真的。链接 - Robin Green

这是一个很好的总结，但需要注意一些例外情况。请参阅http://blogs.msdn.com/b/fsharpteam/archive/2011/07/08/tail-calls-in-fsharp.aspx了解详细信息。 - kvb

5

原来对于 proper tail calls，你需要将编译模式从默认的“Debug Mode”转换为“Release Mode”，或者在项目属性中打开“生成尾递归调用”选项。感谢 IRC.freenode.net #fsharp 的 Arnavion 提供的提示。

- Faré

网页内容由stack overflow 提供, 点击上面的

可以查看英文原文，
原文链接

- Jörg W Mittag · Accepted Answer

Scala中Proper Tail Calls的问题是工程上的权衡。要在Scala中添加PTCs非常容易：只需在SLS中添加一句话即可。那么，Scala就有了PTCs。从语言设计的角度来看，我们已经完成了。

现在，可怜的编译器编写者们需要实现这个规范。将代码编译成具有PTCs的语言很容易...但不幸的是，JVM字节码并不是这样的语言。好吧，那么GOTO呢？不行。Continuations呢？也不行。异常（已知等价于Continuations）？啊，现在我们正在取得进展！因此，我们可以使用异常来实现PTCs。或者，我们可以完全不使用JVM调用堆栈，而是实现自己的堆栈。

毕竟，在JVM上有多个Scheme实现，它们都很好地支持PTCs。不能在JVM上有PTCs只是一个谬论，只是因为JVM不支持它们。毕竟，x86也没有它们，但仍然有语言在x86上运行它们。

因此，如果在JVM上实现PTC是可能的，那么为什么Scala没有它们呢？就像我上面说的，你可以使用异常或自己的堆栈来实现它们。但是，使用异常控制流程或实现自己的堆栈意味着一切都期望JVM调用堆栈看起来某种方式的东西将不再起作用。

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

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

我把这叫做“Hickey定理”，以Rich Hickey的名字命名，他是Clojure的设计师，曾经在一次演讲中说过“尾调用、互操作性、性能-选两个。”

你还会向JIT编译器呈现一些非常不寻常的字节码模式，它可能不知道如何优化。

如果你要将F#移植到JVM上，你基本上必须做出这样的选择：你放弃尾调用（你不能这样做，因为它们是语言规范所必需的），你放弃Interop还是放弃性能？在.NET上，你可以拥有三者，因为F#中的尾调用可以简单地编译成MSIL中的尾调用。（虽然实际的转换比这更复杂，并且在某些角落情况下，MSIL中的尾调用实现存在缺陷。）

这引出了一个问题：为什么不将尾调用添加到JVM中呢？嗯，这很难，因为JVM字节码存在设计缺陷。设计师想要JVM字节码具有某些安全属性。但是，他们没有以这样一种方式设计JVM字节码语言，使得你根本无法编写不安全的程序（例如，在Java中，你无法编写违反指针安全性的程序，因为该语言首先不会给你访问指针的权限），JVM字节码本身就是不安全的，需要一个单独的字节码验证器来使其安全。

那个字节码验证器基于堆栈检查，而尾调用会改变堆栈。因此，两者非常难以协调，但是JVM没有字节码验证器就无法工作。花费了很长时间和一些非常聪明的人才终于找到了如何在不失去字节码验证器的情况下在JVM上实现尾调用（请参见具有堆栈检查的尾递归机，由Clements和Felleisen编写和{{link2：JVM引导设计师John Rose的VM中的尾调用}}），因此我们现在已经从它是一个开放性研究问题的阶段转变为"只是"一个开放性工程问题的阶段。

请注意，Scala和其他一些语言确实具有方法内直接尾递归。但是，就实现而言，这相当无聊：它只是一个while循环。大多数目标都有while循环或等效的东西，例如JVM具有方法内GOTO。Scala还有一个scala.util.control.TailCalls object对象，它是一种重新定义的trampoline。 (参见Stackless Scala With Free Monads by Rúnar Óli Bjarnason，了解此想法的更普遍版本，该版本可以消除对堆栈的所有使用，而不仅仅是在尾调用中。) 这可用于在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特殊形式，也是一个显式的trampoline。