Why is this throwing stack overflow exception?

Question

... despite it being tail-call-optimizable?

def areStreamsEqual(stream1: InputStream, stream2: InputStream): Boolean =
{
    val one = stream1.read()
    val two = stream2.read()
    if(one != two)
        false
    else if(one == -1 && two == -1)
        true
    else
        areStreamsEqual(stream1, stream2)
}

Is there anyway to force the Scala compiler to do a tail call optimization here?

You can tell scalac to throw an error if the method is not TCO'ed with the [@tailrec](http://www.scala-lang.org/api/current/scala/annotation/tailrec.html) annotation. (That annotation won't force/make it TCO'd though.) — , Jun 09 '11 at 19:18

luntain · Accepted Answer · 2011-06-09T20:00:18.277

6

Thanks to pst for the comment about @tailrec. Given that annotation scala compiler error message explains the reason for not optimizing the method.

<filename>.scala:64: error: could not optimize @tailrec annotated method: it is neither private nor final so can be overridden
def areStreamsEqual(stream1: InputStream, stream2: InputStream): Boolean =

making the method private sorts it out

I suspect that on the byte code level, there are two instructions for calling methods: virtual_call and tail_call.

edited Jun 09 '11 at 20:00

answered Jun 09 '11 at 19:53

luntain

4,560
6
37
48

3

Regarding your last comment, no, tail calls are not supported on the byte code level. scalac actually rewrites your recursive method as an iterative one. – Aaron Novstrup Jun 09 '11 at 21:47
3

There are four call instructions at the bytecode level: `invokestatic`, `invokespecial`, `invokevirtual`, `invokeinterface`. A fifth, `invokedynamic`, is coming in Java 7. Scala uses none of these for tail-recursive methods. Instead, it converts the call into a simple `goto` which jumps to the top of the method. This is exactly the same bytecode that would be produced if you had written the method as a `while` loop rather than as a recursive function. – Daniel Spiewak Jun 10 '11 at 01:22
True, no tail_call instruction. I have found this stackoverflow answer useful in explaining why compiler refuses to optimize the method http://stackoverflow.com/questions/4785502/why-wont-the-scala-compiler-apply-tail-call-optimization-unless-a-method-is-fina – luntain Jun 10 '11 at 13:35

score 1 · Answer 2 · answered Jun 09 '11 at 20:15

For anyone trying to recreate the compiler error in the REPL, you have to wrap the method in a class like this:

class Test {
@annotation.tailrec def areStreamsEqual(stream1: InputStream, stream2: InputStream): Boolean =
{
    val one = stream1.read()
    val two = stream2.read()
    if(one != two)
        false
    else if(one == -1 && two == -1)
        true
    else
        areStreamsEqual(stream1, stream2)
}
}

If you just plug the method into the REPL, it will be TCO'd just fine, since the method outside of a class can't be overridden.

Why is this throwing stack overflow exception?

2 Answers2