Why won't the Scala compiler apply tail call o

Question

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?

Answer 1

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.

Answer 2

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.

Answer 3

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.

Answer 4

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.