为什么除非方法是最终的，否则 Scala 编译器不会应用尾调用优化? [英] Why won't the Scala compiler apply tail call optimization unless a method is final?

问题描述

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

Why won't the Scala compiler apply tail call optimization unless a method is final?

例如:

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

结果

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

error: could not optimize @tailrec annotated method: it is neither private nor final so can be overridden

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

What exactly would go wrong if the compiler applied TCO in a case such as this?

推荐答案

考虑以下与 REPL 的交互.首先我们用阶乘方法定义一个类:

Consider the following interaction with the REPL. First we define a class with a factorial method:

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

现在让我们在子类中覆盖它，使超类的答案翻倍:

Now let's override it in a subclass to double the superclass's answer:

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.但不是:

What result do you expect for this last call? You might be expecting 240. But no:

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

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

That's because when the superclass's method makes a recursive call, the recursive call goes through the subclass.

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

If overriding worked such that 240 was the right answer, then it would be safe for tail-call optimization to be performed in the superclass here. But that isn't how Scala (or Java) works.

除非方法被标记为 final，它在进行递归调用时可能不会调用自己.

Unless a method is marked final, it might not be calling itself when it makes a recursive call.

这就是为什么除非方法是最终的(或私有的)否则 @tailrec 不起作用.

And that's why @tailrec doesn't work unless a method is final (or private).

更新:我建议您也阅读其他两个答案(John 和 Rex 的).

UPDATE: I recommend reading the other two answers (John's and Rex's) as well.

这篇关于为什么除非方法是最终的，否则 Scala 编译器不会应用尾调用优化?的文章就介绍到这了，希望我们推荐的答案对大家有所帮助，也希望大家多多支持IT屋！