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
themod
function is munged tomod-non-recursive
during compilation soFoo
doesn't actually have amod
method to override.
Best Answer
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:
Now, when Foo's
mod
calls itself, because my object is aBar
, not aFoo
, you are supposed (and do) go to Bar'smod
, 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.