Scala：蹦床函数的扩展语法破坏了尾递归

Question

这是 "Functional Programming in Scala," 第 13 章中的练习，用于实现用于解释尾递归函数的蹦床。

runTrampoline2 不是尾递归的，并且我的测试输入溢出了堆栈。此外，tailrec 注释给出了 runTrampoline2 的编译器错误。 runTrampoline 是尾递归的并且通过了注解的编译时检查。

我认为这两个蹦床的区别在于 val 捕获或不捕获单位的方式，如下所示：

scala> val foo = println("abc")
val foo = println("abc")
abc
foo: Unit = ()

scala> foo
foo

scala> val bar: Int = {println("xyz"); 5}
val bar: Int = {println("xyz"); 5}
xyz
bar: Int = 5

scala> bar
bar
res8: Int = 5

否则这两个蹦床在我看来是一样的。我将包含 Free monad 和 Suspend、Return 和 FlatMap 构造函数的代码，如果有人评论说它们对这个问题很重要，但我认为它们不是。 runTrampoline2 的尾递归是否被从 val 中泄漏出来的副作用破坏了？谢谢！

@annotation.tailrec
def runTrampoline[A](tra: Free[Function0,A]): A =
  tra match {
    // case Return(A)
    case Return(a1) => a1
    // case Suspend(Function0[A])
    case Suspend(function0A1) => function0A1()
    // case FlatMap(Free[Function0[_],A], A=>Free[Function0,B]]
    case FlatMap(free1, aFree2) => free1 match {
      // case Return(A)
      case Return(a2) => runTrampoline(aFree2(a2))
      // case Suspend(Function0[A])
      case Suspend(function0A) => runTrampoline(aFree2(function0A()))
      // case FlatMap(Free[Function0[_],A], A=>Free[Function0,B]]
      case FlatMap(a0,g) =>
        runTrampoline {
          a0 flatMap { a0 => g(a0) flatMap aFree2 }
        }
    }
  }


//@annotation.tailrec
def runTrampoline2[A](tra: Free[Function0,A]): A =
  tra match {
    // case Return(A)
    case Return(a1) => a1
    // case Suspend(Function0[A])
    case Suspend(function0A1) => {
      val a1: A = function0A1()
      a1
    }
    // case FlatMap(Free[Function0[_],A], A=>Free[Function0,A]]
    case FlatMap(free1, aFree2) => free1 match {
      // case Return(A)
      case Return(a2) => {
        val free2: Free[Function0,A] = aFree2(a2)
        val a3: A = runTrampoline2(free2)
        a3
      }
      // case Suspend(Function0[A])
      case Suspend(function0A) => {
        val a2: A = function0A()
        val free2: Free[Function0,A] = aFree2(a2)
        val a3: A = runTrampoline2(free2)
        a3
      }
      // case FlatMap(Free[Function0[_],A], A=>Free[Function0,B]]
      case FlatMap(a0,g) =>
        runTrampoline2 {
          a0 flatMap { a0 => g(a0) flatMap aFree2 }
        }
      }
      }

一个月前我问过一个类似的问题，关于类型注释破坏尾递归：Scala: type annotations make tail recursion check fail

由 Aivean 解决。这是蹦床的更正版本。每个递归调用都在包含它的案例的最后。

@annotation.tailrec
def runTrampoline3[A](tra: Free[Function0,A]): A =
  tra match {
    case Return(a1) => a1
    case Suspend(function0A1) => {
      val a1 = function0A1()
      a1
    }
    case FlatMap(free1, aFree2) => free1 match {
      case Return(a2) => {
        val free2 = aFree2(a2)
        runTrampoline3(free2)
      }
      case Suspend(function0A) => {
        val a2 = function0A()
        val free2 = aFree2(a2)
        runTrampoline3(free2)
      }
      case FlatMap(a0,g) =>
        runTrampoline3 {
          a0 flatMap { a0 => g(a0) flatMap aFree2 }
        }
     }
  }

Answer 1

似乎 Scala 编译器仅在对自身的调用是实际上函数中的最后一个操作时才识别尾递归。

我反编译了两个不同的例子来检查这一点。

尾递归：

斯卡拉：

def rec:Int = rec

java:

public final class _$$anon {
  private int rec() {
    while (true) {}
  }
}

无尾递归：

斯卡拉：

def rec:Int = {
  val i = rec
  i
}

java:

public final class _$$anon {
  private int rec() {
    final int i = this.rec();
    return i;
  }
}

Scala：蹦床函数的扩展语法破坏了尾递归

Scala: expanded syntax of trampolining function breaks tail recursion

scala

tail-recursion

trampolines

尾递归：

无尾递归：