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:

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?)
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

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.

Answer 2

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.)

友情链接