除非方法是最终的，否则为什么Scala编译器不会应用尾调用优化？

Question

除非方法是最终的，否则为什么Scala编译器不会应用尾调用优化？

例如，这个：

class C {
    @tailrec def fact(n: Int, result: Int): Int =
        if(n == 0)
            result
        else
            fact(n - 1, n * result)
}

结果是

错误：无法优化@tailrec带注释的方法：它既不是私有的也不是最终的，因此可以被覆盖

如果编译器在这种情况下应用TCO，究竟会出现什么问题呢？

Answer 1

考虑以下与REPL的交互。首先，我们使用析因方法定义一个类：

scala> class C {
         def fact(n: Int, result: Int): Int =
           if(n == 0) result
           else fact(n - 1, n * result)
       }
defined class C

scala> (new C).fact(5, 1)
res11: Int = 120

现在让我们在子类中覆盖它以使超类的答案加倍：

scala> class C2 extends C {
         override def fact(n: Int, result: Int): Int = 2 * super.fact(n, result)
       }
defined class C2

scala> (new C).fact(5, 1)
res12: Int = 120

scala> (new C2).fact(5, 1)

你对这最后一次通话有什么期望？你可能期待240.但不是：

scala> (new C2).fact(5, 1)
res13: Int = 7680

那是因为当超类的方法进行递归调用时，递归调用将通过子类。

如果覆盖工作使得240是正确的答案，那么在这里的超类中执行尾调优化是安全的。但这不是Scala（或Java）的工作方式。

除非方法标记为final，否则在进行递归调用时可能不会调用自身。

这就是为什么除非方法是最终的（或私有的），否则@tailrec不起作用。

更新：我建议阅读其他两个答案（约翰和雷克斯）。

Answer 2

递归调用可能是子类而不是超类; final将阻止这一点。但为什么你想要这种行为呢？ Fibonacci系列没有提供任何线索。但这样做：

class Pretty {
  def recursivePrinter(a: Any): String = { a match {
    case xs: List[_] => xs.map(recursivePrinter).mkString("L[",",","]")
    case xs: Array[_] => xs.map(recursivePrinter).mkString("A[",",","]")
    case _ => a.toString
  }}
}
class Prettier extends Pretty {
  override def recursivePrinter(a: Any): String = { a match {
    case s: Set[_] => s.map(recursivePrinter).mkString("{",",","}")
    case _ => super.recursivePrinter(a)
  }}
}

scala> (new Prettier).recursivePrinter(Set(Set(0,1),1))
res8: String = {{0,1},1}

如果Pretty调用是尾递归的，我们会打印出{Set(0, 1),1}，因为扩展名不适用。

由于这种递归似乎很有用，并且如果允许对非final方法进行尾调用将被销毁，编译器会插入一个真正的调用。

Answer 3

让foo::fact(n, res)表示你的日常生活。让baz::fact(n, res)表示别人超越你的日常生活。

编译器告诉你语义允许baz::fact()成为一个包装器，如果愿意，可以上调（？）foo::fact()。在这种情况下，规则是foo::fact()，当它重复时，必须激活baz::fact()而不是foo::fact()，并且，虽然foo::fact()是尾递归，baz::fact()可能不是。此时，foo::fact()必须返回baz::fact()，而不是循环尾递归调用，因此它可以自行展开。

Answer 4

如果编译器在这种情况下应用TCO，究竟会出现什么问题呢？

什么都不会出错。任何具有正确尾调用消除的语言都会这样做（SML，OCaml，F＃，Haskell等）。 Scala没有的唯一原因是JVM不支持尾递归，而Scala通常用goto替换尾部位置的自递归调用的hack在这种情况下不起作用。 CLR上的Scala可以像F＃那样执行此操作。

Answer 5

对这个问题的流行和接受的答案实际上是误导，因为这个问题本身就令人困惑。 OP没有区分tailrec和TCO，答案没有解决这个问题。

关键点是tailrec的要求比TCO的要求更严格。

tailrec注释要求对同一函数进行尾调用，而TCO可用于对任何函数的尾调用。

编译器可以在TCO上使用fact，因为尾部位置有一个调用。具体来说，它可以通过适当调整堆栈将fact的调用转换为跳转到fact。这个版本的fact与拨打电话的功能不同并不重要。

所以接受的答案正确地解释了为什么非最终函数不能是tailrec，因为你不能保证尾调用是相同的函数而不是函数的重载版本。但它错误地暗示在这种方法上使用TCO是不安全的，而事实上这将是非常安全和良好的优化。

[注意，正如Jon Harrop所解释的那样，你不能在JVM上实现TCO，但这是对编译器的限制，而不是语言，并且与tailrec无关]

---

作为参考，以下是如何在不制作方法final的情况下避免此问题：

class C {
  def fact(n: Int): Int = {
    @tailrec
    def loop(n: Int, result: Int): Int =
      if (n == 0) {
        result
      } else {
        loop(n - 1, n * result)
      }

    loop(n, 1)
  }
}

这是有效的，因为loop是一个具体的函数而不是一个方法，不能被覆盖。此版本还具有将虚假result参数移除到fact的优势。

这是我用于所有递归算法的模式。