在JVM中运行时在Scala中使用递归

Question

通过搜索此站点和Web上的其他位置,JVM不支持尾调用优化.因此,这是否意味着如果要在JVM上运行,则不应写入可能在非常大的输入列表上运行的尾递归Scala代码(如下所示)？

// Get the nth element in a list    
def nth[T](n : Int, list : List[T]) : T = list match {
            case Nil => throw new IllegalArgumentException
            case _ if n == 0 => throw new IllegalArgumentException
            case _ :: tail if n == 1 => list.head
            case _ :: tail  => nth(n - 1, tail)
}

Martin Odersky的Scala示例包含以下段落,似乎表明存在适合递归的情况或其他环境:

原则上,尾调用总是可以重用调用函数的堆栈帧.但是,某些运行时环境(例如Java VM)缺少基本条件,以使堆栈帧重用用于尾调用.因此,生产质量Scala实现只需要重新使用直接尾递归函数的堆栈帧,其最后一个操作是对自身的调用.其他尾调用也可以进行优化,但不应该在实现中依赖于此.

任何人都能解释一下这段中间两句话是什么意思吗？

谢谢!

Answer 1

由于直接尾递归等同于while循环,因此您的示例将在JVM上高效运行,因为Scala编译器可以将其编译为循环内的循环,只需使用跳转即可.但是,JVM不支持常规TCO,尽管有可用的tailcall()方法支持使用编译器生成的trampolines进行尾调用.

为了确保编译器可以正确地优化尾递归函数的循环,你可以使用scala.annotation.tailrec注释,这将导致一个编译错误,如果编译器不能进行所需的优化:

import scala.annotation.tailrec

@tailrec def nth[T](n : Int, list : List[T]) : Option[T] = list match {
            case Nil => None
            case _ if n == 0 => None
            case _ :: tail if n == 1 => list.headOption
            case _ :: tail  => nth(n - 1, tail)
}

(螺钉IllegalArgmentException!)

Answer 2

原则上,尾调用总是可以重用调用函数的堆栈帧.但是,某些运行时环境(例如Java VM)缺少基本条件,以使堆栈帧重用用于尾调用.因此,生产质量Scala实现仅需要重新使用直接尾递归函数的堆栈帧,其最后一个操作是对自身的调用.其他尾调用也可以进行优化,但不应该在实现中依赖于此.

任何人都能解释一下这段中间两句话是什么意思吗？

尾递归是尾调用的特例.直接尾递归是尾递归的一种特殊情况.只保证优化直接尾递归.其他人也可以进行优化,但这基本上只是编译器优化.作为语言功能,Scala仅保证直接尾递归消除.

那么,有什么区别？

好吧,尾调用只是子程序中的最后一次调用:

def a = {
  b
  c
}

在这种情况下,调用c是一个尾调用,调用b不是.

尾递归是指尾调用之前调用的子例程:

def a = {
  b
}

def b = {
  a
}

这是尾递归:a调用b(尾调用),然后再调用a.(与下面描述的直接尾递归相反,这有时称为间接尾递归.)

但是,Scala不会优化这两个示例.或者,更准确地说:允许 Scala实现对它们进行优化,但不需要这样做.这与例如Scheme形成对比,其中语言规范保证所有上述情况都将占用O(1)堆栈空间.

Scala语言规范仅保证直接尾递归被优化,即当子例程直接调用自身而两者之间没有其他调用时:

def a = {
  b
  a
}

在这种情况下,调用a是一个尾调用(因为它是子例程中的最后一个调用),它是尾递归(因为它再次调用自身),最重要的是它是直接尾递归,因为a直接调用自身而不通过先打个电话.

请注意,有许多微妙的事情可能导致方法不直接尾递归.例如,如果a过载,则递归实际上可能经历不同的重载,因此不再是直接的.

在实践中,这意味着两件事:

1. 你不能对尾递归方法执行提取方法重构,至少不包括尾调用,因为这会将直接尾递归方法(将被优化)变成间接尾递归方法(不会得到)优化).
2. 您只能使用直接尾递归.尾递归下降解析器或状态机,可以使用间接尾递归非常优雅地表达.

这样做的主要原因是当你的底层执行引擎缺乏强大的控制流操作功能,如GOTOcontinuation,一流的可变堆栈或正确的尾调用时,你需要在它上面实现自己的堆栈,使用trampolines,进行全局CPS变换或同样令人讨厌的东西,以便提供广义的正确尾调用.所有这些都会对性能产生严重影响,或者与同一平台上的其他代码实现互操作性.

或者,正如Clojure的创建者Rich Hickey在面对同样的问题时所说:"性能,Java互操作,尾部调用.选择两个." Clojure和Scala都选择在尾调用上做出妥协,只提供尾递归而不是尾调用.

简而言之:是的,您发布的具体示例将进行优化,因为它是直接尾递归.您可以通过@tailrec在方法上添加注释来测试它.注释不会更改方法是否得到优化,但它确实保证如果无法优化方法,您将收到编译错误.

由于上述细微之处,通常最好@tailrec在需要优化的方法上添加注释,既可以获得编译错误,也可以作为维护代码的其他开发人员的提示.