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

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

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.

Answer 3

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 4

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 5

The popular and accepted answer to this question is actually misleading, because the question itself is confusing. The OP does not make the distinction between tailrec and TCO, and the answer does not address this.

The key point is that the requirements for tailrec are more strict than the requirements for TCO.

The tailrec annotation requires that tail calls are made to the same function, whereas TCO can be used on tail calls to any function.

The compiler could use TCO on fact because there is a call in the tail position. Specifically, it could turn the call to fact into a jump to fact by adjusting the stack appropriately. It does not matter that this version of fact is not the same as the function making the call.

So the accepted answer correctly explains why a non-final function cannot be tailrec because you cannot guarantee that the tail calls are to the same function and not to an overloaded version of the function. But it incorrectly implies that it is not safe to use TCO on this method, when in fact this would be perfectly safe and a good optimisation.

[ Note that, as explained by Jon Harrop, you cannot implement TCO on the JVM, but that is a restriction of the compiler, not the language, and is unrelated to tailrec ]

---

And for reference, here is how you can avoid the problem without making the method final:

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

    loop(n, 1)
  }
}

This works because loop is a concrete function rather than a method and cannot be overridden. This version also has the advantage of removing the spurious result parameter to fact.

This is the pattern I use for all recursive algorithms.