F#有尾调用消除功能吗？

Question

在这次演讲中,在前8分钟,Runar解释说Scala在消除尾部呼叫方面存在问题,这让我想知道F#是否有类似的问题？如果没有,为什么不呢？

Answer 1

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

现在,糟糕的编译器编写者需要实现该规范.好吧,使用PTC 编译成一种语言很容易......但不幸的是,JVM字节代码不是这样的语言.好的,那又怎么样GOTO？不.延续？不.例外(已知等同于Continuations)？啊,现在我们到了某个地方!因此,我们可以使用异常来实现PTC.或者,或者,我们根本不能使用JVM调用堆栈并实现我们自己的堆栈.

毕竟,JVM上有多个Scheme实现,所有这些实现都支持PTC.这是一个神话,你不能在JVM上安装PTC,只是因为JVM不支持它们.毕竟,x86也没有它们,但是,有些语言在x86上运行.

因此,如果可以在JVM上实现PTC,那么为什么Scala不具备它们呢？就像我上面说的那样,你可以使用异常或你自己的堆栈来实现它们.但是使用控件流的异常或实现自己的堆栈意味着期望JVM调用堆栈以某种方式显示的所有内容将不再起作用.

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

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

在Clojure的设计师Rich Hickey之后,我称之为"Hickey's Theorem",他曾在一次谈话中说道:"Tail Calls,Interop,Performance - Pick Two".

您还会向JIT编译器提供一些非常不寻常的字节代码模式,它们可能不知道如何优化.

如果您要将F#移植到JVM,您基本上必须做出这样的选择:您是否放弃了Tail Calls(您不能,因为它们是语言规范所要求的),您是放弃Interop还是放弃放弃表现？在.NET上,你可以拥有这三个,因为F#中的Tail Calls可以简单地编译成MSIL中的Tail Calls.(虽然实际的翻译比这更复杂,但在某些极端情况下,MSIL中的Tail Calls的实现是错误的.)

这提出了一个问题:为什么不将尾调用添加到JVM？嗯,由于JVM字节代码中的设计缺陷,这非常困难.设计人员希望JVM字节代码具有某些安全属性.但是,而不是以这样的方式设计JVM字节代码语言,使得您无法首先编写不安全的程序(例如,在Java中,例如,您无法编写违反指针安全的程序,因为语言只是它不会让你首先访问指针),JVM字节代码本身是不安全的,需要一个单独的字节码验证器才能使其安全.

该字节码验证器基于堆栈检查,Tail Calls更改堆栈.所以,这两个是非常难以调和,但是JVM根本不没有字节码验证工作.花了很长的时间和一些非常聪明的人,终于弄明白如何实现在JVM上尾调用不失字节码验证(见与堆栈检查将尾递归机由克莱门茨和Felleisen和尾调用的VM由约翰· Rose(JVM首席设计师)),所以我们现在已经从一个开放式研究问题的阶段转移到"只是"一个开放式工程问题的阶段.

请注意,Scala和其他一些语言确实具有方法内直接尾递归.然而,这是非常无聊的,实现方式:它只是一个while循环.大多数目标都有while循环或类似的东西,例如JVM具有intra-method GOTO.Scala也有一个scala.util.control.TailCalls对象,这是一种重新设计的蹦床.(参见RúnarÓliBjarnason的Stackless Scala和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特殊的形式,也是一种明显的蹦床.

Answer 2

F#没有尾调用的问题.这是它的作用:

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

• 在其他尾部调用位置(例如,当使用continuation或两个相互递归函数时),它生成.tail指令,因此尾部调用由CLR处理

• 默认情况下,在Visual Studio的调试模式下关闭尾调用优化,因为这使调试更容易(您可以检查堆栈),但是如果需要,您可以在项目属性中打开它.

在过去,曾经有.tail一些运行时(CLR x64和Mono)的指令存在问题,但所有这些都已经修复,一切正常.

Answer 3

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