Scala3中如何进行尾调用优化？

Question

我正在尝试编写一个 100% 迭代的程序，也就是说，函数永远不需要返回，因为在这样的返回之后不会发生任何事情。

换句话说，程序100%处于尾部位置。考虑以下玩具程序：

  def foo(): Unit =
    bar()

  def bar(): Unit =
    foo()

  try
    foo()
  catch
    case s: StackOverflowError =>
      println(" Stack overflow!")

调用 foo 确实会导致堆栈溢出，这并不奇怪，事实上 foo 调用 bar，因为这样 bar 需要堆栈帧，bar 然后调用 foo，后者需要堆栈帧，等等。很明显为什么会发生堆栈溢出错误。

我的问题是，如何按原样定义 foo 和 bar 而不会出现堆栈溢出？像Scheme这样的语言允许这个程序，它们会永远运行，是的，但是堆栈不会增长，因为它知道调用后不需要发生任何事情，例如，来自foo的bar，所以不需要保留foo的堆栈帧呼叫酒吧。显然，scala（即 JVM？）确实使堆栈帧保持活动状态。

现在考虑下一个代码示例：

  def foo(): Unit = 
    foo()

  foo()

该程序将永远运行，但永远不会发生堆栈溢出。

我知道 @tailrec 注释，但据我了解，它仅适用于第二个示例之类的情况，但不适用于第一个示例。

有任何想法吗？（我需要第一个示例像第二个示例一样永远运行，而不会出现堆栈溢出。）

Answer 1

正如您所注意到的，JVM 禁止非本地跳转，因此如果foo和bar被编译为单独的方法（这通常是可取的），尾部调用消除是不可能的。

foo但是，您可以通过让您的和bar返回一个调用者将其解释为“调用此函数”的值来进行蹦床。

sealed trait TrampolineInstruction[A]

case class JumpOff[A](value: A) extends TrampolineInstruction[A]
case class JumpAgain[A](thunk: => TrampolineInstruction[A])
  extends TrampolineInstruction[A]

@tailrec
def runTrampolined(ti: TrampolineInstruction[A]): A =
  ti match {
    case JumpOff(value) => value
    case JumpAgain(thunk) => runTrampolined(thunk)
  }

def foo(): TrampolineInstruction[Unit] = JumpAgain(bar())
def bar(): TrampolineInstruction[Unit] = JumpAgain(foo())

runTrampolined(foo())  // will not overflow the stack, never completes

Cats 提供了一个Evalmonad，它封装了蹦床的思想。则上述foo和 的定义为bar

import cats.Eval

def foo(): Eval[Unit] = Eval.defer(bar())
def bar(): Eval[Unit] = Eval.defer(foo())

foo().value  // consumes a bounded (very small, not necessarily 1) number of stack frames, never completes

的一元性质Eval可能有助于表达更复杂的逻辑，而无需value在链中间调用的风险。

注意：JumpOff在第一个片段中，基本上是Eval.Leaf（通常使用 构造Eval.now）并且JumpAgain基本上是Eval.Defer。