[Sablevm-developer] tail-recursion

[Etienne M. G. <eg...@j-...>]

Hi Brent.

> I wonder if the stack trace information could somehow be generated?
> I'm not totally sure if the trace data lost would be of the following
> form:...

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.  The JNI does not export any stack inspection
routines, so a Debugger should talk with the vm through another
dedicated interface.  It would be OK to simply provide a switch to
enable/disable tail-method-invocation.  A debugger could be given access
to the real (actual) stack trace [which doesn't include eliminated stack
frames], and thus users wouldn't attack us for introducing hidden bugs,
exposed only in presence of tail-method-invocation.

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

> * Imagine a tail-recursive call set like this: 
>... 
> 
> * This might end up in java like so:
>... 
> * and in bytecode as something like the following:
> 
> Compiled from RecursiveTest.java
> public class RecursiveTest extends java.lang.Object {
>     public RecursiveTest();
>     public static int cat(int, int);
>     public static void main(java.lang.String[]);
> }
> 
> 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:-))

> 
> Method int cat(int, int)
>    0 iload_0
>    1 ifne 6
>    4 iload_1
>    5 ireturn
>    6 iload_1
>    7 iload_0
>    8 iadd
>    9 istore_1
>   10 iinc 0 -1
>   13 iload_0
>   14 iload_1
>   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)!

> So it seems that we would be able to allow the "invokestatic #8"
> at line 15 (above) as an obvious recursive candidate.  But I
> wonder if we could provide some kind of back-trace information
> to signify that it was a recursion (or hold that state for use
> in a backtrace)?
>... 
> This doesn't seem all that informative -- it might be
> enough to just keep a counter for the recursive calls,
> so the debug output could reflect that we entered the
> function 'x' number of times.
> 
> What do you think?  Am I totally off-base?

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

> "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!

Etienne
-- 
----------------------------------------------------------------------
Etienne M. Gagnon, M.Sc.                     e-mail: eg...@j-...
Author of SableVM:                             http://www.sablevm.org/
----------------------------------------------------------------------