Scala and tail recursion

Question

There are various answers on Stack Overflow which explain the conditions under which tail recursion is possible in Scala. I understand the limitations and how and where I can take advantage of tail recursion. The part I don't understand is why the limitation to private or final methods exists.

I haven't researched how the Scala compiler actually converts a recursive function to a non-recursive one at a bytecode level, but let's assume it does something like the following. I have a class Foo with a recursive function mod:

class Foo {
  def mod(value: Int, denom: Int): Int = {
    if(denom <= 0 || value <= 0) 0
    else if(0 <= value && value < denom) value
    else mod(value - denom, denom)
  }
}

That's a basic modulo function which I imagine the Scala compiler translates to some kind of pseudo-Java-Scala like:

class Foo {
  def mod(value: Int, denom: Int): Int = {
    if(denom <= 0 || value <= 0) return 0
    while(value > denom) value -= denom
    return value
  }
}

(I can believe I've messed up that translation but I don't think the details are important..)

So now suppose I subclass Foo:

class Bar extends Foo {
  def mod(value:Int, denom: Int): Int = 1
}

What it is that stops this from working? When the JVM has a Foo/Bar and mod is called on it, why is there a problem with resolving the mod function that should be used. Why is this any different from the situation where the base function is non-recursive?

A few possible reasons I can see for this being the case are:

1. for whatever reason the implementation of the Scala compiler doesn't handle this (fair enough if that is the case. If so, are there plans to change this?)

2. in Foo the mod function is munged to mod-non-recursive during compilation so Foo doesn't actually have a mod method to override.

Answer 1

IttayD just asked this question earlier today. The answer is that Foo's tail recursion will only be optimized if you can't override mod in subclasses (be that becuase the class is final, or because the method is final or private.)

Answer 2

I have just answered that, but let's take your own example. Say you defined that class Foo, and made it available as a JAR file.

Then I get that Jar file, and extend your Foo this way:

class Bar extends Foo {
  def mod(value:Int, denom: Int): Int = {
    Logger.log("Received mod with "+value+" % "+denom)
    super.mod(value, denom)
}

Now, when Foo's mod calls itself, because my object is a Bar, not a Foo, you are supposed (and do) go to Bar's mod, not to Foo's.

And because that is true, you can't optimize it the way you have shown.

It is the CONTRACT of subclassing that, when a super class calls a method on itself, if that method has been overridden it will be the subclass' method to be invoked.

Declaring the method private, making it final, or the class -- or even making a recursive function instead of a method, all insure you won't potentially have to go to a subclass implementation.