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 annotation. (That annotation won't force/make it TCO'd though.) — user166390
– user166390, Commented Jun 9, 2011 at 19:18

luntain · Accepted Answer · 2011-06-09 20:00:18Z

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 9, 2011 at 20:00

answered Jun 9, 2011 at 19:53

luntain

4,7406 gold badges40 silver badges49 bronze badges

Sign up to request clarification or add additional context in comments.

3 Comments

Aaron Novstrup Over a year ago

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.

Daniel Spiewak Over a year ago

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.

luntain Over a year ago

True, no tail_call instruction. I have found this stackoverflow answer useful in explaining why compiler refuses to optimize the method stackoverflow.com/questions/4785502/…

brandon · Accepted Answer · 2011-06-09 20:15:13Z

1

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.

answered Jun 9, 2011 at 20:15

brandon

6756 silver badges10 bronze badges

Collectives™ on Stack Overflow

Why is this throwing stack overflow exception?

2 Answers 2

3 Comments

Comments

Your Answer

Linked

Hot Network Questions

Collectives™ on Stack Overflow

2 Answers 2

3 Comments

Comments

Your Answer

Sign up or log in

Post as a guest

Linked

Related