Why won't the Scala compiler apply tail call optimization unless a method is final?
For example, this:
class C {
@tailrec def fact(n: Int, result: Int): Int =
if(n == 0)
result
else
fact(n - 1, n * result)
}
results in
error: could not optimize @tailrec annotated method: it is neither private nor final so can be overridden
What exactly would go wrong if the compiler applied TCO in a case such as this?
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)
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.
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.
Unless a method is marked final, it might not be calling itself when it makes a recursive call.
And that's why @tailrec doesn't work unless a method is final (or private).
UPDATE: I recommend reading the other two answers (John's and Rex's) as well.
Recursive calls might be to a subclass instead of to a superclass; final
will prevent that. But why might you want that behavior? The Fibonacci series doesn't provide any clues. But this does:
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}
If the Pretty call was tail-recursive, we'd print out {Set(0, 1),1}
instead since the extension wouldn't apply.
Since this sort of recursion is plausibly useful, and would be destroyed if tail calls on non-final methods were allowed, the compiler inserts a real call instead.
Let foo::fact(n, res)
denote your routine. Let baz::fact(n, res)
denote someone else's override of your routine.
The compiler is telling you that the semantics allow baz::fact()
to be a wrapper, that MAY upcall (?) foo::fact()
if it wants to. Under such a scenario, the rule is that foo::fact()
, when it recurs, must activate baz::fact()
rather than foo::fact()
, and, while foo::fact()
is tail-recursive, baz::fact()
may not be. At that point, rather than looping on the tail-recursive call, foo::fact()
must return to baz::fact()
, so it can unwind itself.
What exactly would go wrong if the compiler applied TCO in a case such as this?
Nothing would go wrong. Any language with proper tail call elimination will do this (SML, OCaml, F#, Haskell etc.). The only reason Scala does not is that the JVM does not support tail recursion and Scala's usual hack of replacing self-recursive calls in tail position with goto
does not work in this case. Scala on the CLR could do this as F# does.