[Sablevm-developer] RE: tail-recursion

[Brent F. <bre...@xp...>]

> Bookkeeping stack trace information is not critical to the vm
> operation.  The Java API specification does not dictate the output of
> Throwable.printStackTrace().  So, a vm is free not to provide exact
> stack information.  Where stack trace information becomes 
> handy, is when you use a debugger.

Perhaps it would be sufficient to incorporate a "(rec)" or similar
in the stacktrace output, to indicate that this function was
handled through the tail-method-invocation handler.  :-)

> We certainly do not want to keep track of eliminated stack frames in
> production code.  It would introduce too much overhead.
>
Agreed.

> > Method RecursiveTest()
> >    0 aload_0
> >    1 invokespecial #7 <Method java.lang.Object()>
> >    4 return
> 
> Interestignly:  This constructor's stack frame would be automatically
> recycled for the call to java.lang.Object's constructor, using our
> tail-method-invocation algorithm:-))
>
Great!
 
> >   15 invokestatic #8 <Method int cat(int, int)>
> >   18 ireturn
> 
> tail-method-invocation applies as expected!
>
:-)

> > Method void main(java.lang.String[])
> >    0 getstatic #9 <Field java.io.PrintStream out>
> >    3 ldc #2 <String "Test result:">
> >    5 invokevirtual #11 <Method void println(java.lang.String)>
> >    8 bipush 100
> >   10 iconst_0
> >   11 invokestatic #8 <Method int cat(int, int)>
> >   14 istore_1
> >   15 getstatic #9 <Field java.io.PrintStream out>
> >   18 iload_1
> >   19 invokevirtual #10 <Method void println(int)>
> >   22 getstatic #9 <Field java.io.PrintStream out>
> >   25 ldc #1 <String "Done.">
> >   27 invokevirtual #11 <Method void println(java.lang.String)>
> >   30 return
> 
> Here too!  We get tail-method-invocation stack frame recycling when
> calling println(java.lang.String) !!!
> 
> This is really great, specially that it is transparent to the Java vm
> specification (verifier included)!
> 

Yes!  I'm very excited about this.  It seemed that the major drawbacks
to the JVM previously (for FP-style systems) was in the three areas
I mentioned previously:

* High cost of memory allocation
* Lack of tail-recursion handling
* Stack reduction.

Obviously, with SableVM's architecture the first two are taken care of,
without any change to the API or adding new bytecode.  This is great!
The stack reduction issue (and I assume continuations) can be revisted
later.

So, let's get on with it :-)

> This seems like going through a lot of trouble to provide something
> optional.  Why not allow the optimization to be turned off while
> debugging (much like you must turn off JITs when debugging, with the
> difference that we could allow the option to be turned either on or
> off)?
>
Yes -- that sounds like the best approach.
 
> > "Tail-Method-Invocation" has a nice ring to it. :-)
> 
> So should it be;-)  Unless, of course, somebody already had a name for
> this.  I am not too familiar with Functional Programming idioms.  I'll
> check this (at some point).
> 
> I'm really happy with this idea.  It will make SableVM FP friendly,
> without the need for any extention to current specifications. 
> Even Java programs could benefit from this!
> 
Yes, as in the example above.  Recursion is often very costly (esp. in
Java), and this could help correct that.  The cool thing is that heavily
tail-recursive functions that would have overflowed the stack can now be
handled even more efficiently than a separate function call.

It will be interesting to see the difference in performance with this
feature turned on and off... :-)  Oh -- and now we are down to two new
prospective bytecodes, which is great as well!  Now if we can just 
figure out a good way to work around that...

-Brent