除非方法是最终的,否则为什么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(),因此它可以自行展开.