为什么 Scala 编译器无法识别这种尾调用优化方法？

Question

这个简单的正则表达式实现 (scastie here) 没有像我预期的那样编译。错误在第 14 行，其中中间递归调用被解释为违反 @tailrec 要求。虽然这个中间递归调用确实不在尾调用位置，但表达式 的实际最后调用是 ，使完整的表达式尾调用优化。

这条推理线可以通过给中间递归调用起别名来说明，将其变成 'arbitrary' 调用。当 this 调用的别名是 aliasMatches 时，代码会按预期编译和执行。

为什么编译器不接受非别名实现？这是一个实际限制，还是上面的推理有问题？有没有办法让编译器接受我缺少的第一个版本（除了完整的累加器重写）？

（使用 Scala 2.13.5）

import scala.annotation.tailrec

def matches(input: String, pattern: String): Boolean = {

    @tailrec
    def matchesRemainder(remainder: Seq[Char], remainingPattern: Seq[Char]): Boolean =
        (remainder, remainingPattern) match {
            case (Seq(), Seq()) => true
            case (Seq(_@_*), Seq()) => false

            case (Seq(), Seq(_, '*', _@_*)) => true
            case (Seq(), Seq(_@_*)) => false
                                                        \ vvvv error vvvv
            case (Seq(_, rs@_*), Seq('.', '*', xs@_*)) => matchesRemainder(rs, remainingPattern) ||
                matchesRemainder(remainder, xs)
            case (Seq(r, rs@_*), Seq(p, '*', xs@_*)) => (r == p && aliasMatches(rs, remainingPattern)) ||
                matchesRemainder(remainder, xs)

            case (Seq(_, rs@_*), Seq('.', ps@_*)) => matchesRemainder(rs, ps)
            case (Seq(r, rs@_*), Seq(p, ps@_*)) => r == p && matchesRemainder(rs, ps)
        }

    def aliasMatches(remainder: Seq[Char], p: Seq[Char]): Boolean =
        matchesRemainder(remainder, p)

    matchesRemainder(input, pattern)
}

Answer 1

我们稍微简化一下，看问题更清楚。

    @tailrec
    def foo(x: Int): Boolean = x == 0 || foo(x-1) || foo(x-2)

这不会编译，因为它不能完全消除递归：foo(x-1) 必须 return 将控制权交还给调用者，因此可以评估结果并且 return 它，或致电 foo(x-2)。尾递归只有在递归调用的结果直接 return 直接 returned 而没有控制 returning 给调用者时才会发生。

现在为什么要编译？

   def bar(x: Int) = foo(x) 
   @tailrec
   def foo(x: Int): Boolean = x == 0 || bar(x-1) || foo(x-2)

好吧，那只是作弊 :) 编译器并不期望你那么狡猾，它无法知道 bar 只是要调用 foo，所以它有相信你。

基本上@tailrec如果你试图掩盖它只能检测到立即递归......好吧，你会成功:)

从上面删除 || foo(x-2) - 它会停止编译，并告诉你没有递归。即使它现在是一个完美的尾递归函数，它也无法优化它。

这不是一颗金弹。这是另一个怪癖：

    @tailrec
    def foo(x: => Future[Int]): Future[Int] = {
       x.recoverWith { case _ => foo(x) }
       foo(Future(1))
    }

这个是尾递归的，但它会拒绝编译，因为它没有意识到对foo的第一次调用实际上并没有发生在外部 foo.

为什么 Scala 编译器无法识别这种尾调用优化方法？

Why is this tail-call optimized method not recognized as such by the Scala compiler?

scala

tail-call-optimization