[Sablevm-developer] RE: [Sablevm-user] About closures...

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

> > Is there room for three new bytecodes (UseSameFrame, 
> > BeginContinuation, UseContinuation)?  I'm a bit worried :-)
> 
> Yes.  No need to worry about this.  We can build compound bytecodes
> (similar to the "WIDE" bytecode).
> 

Good.

> > In fact, I wonder if the JVM could identify tail-recursion on its
> > own and handle it behind-the-scenes.  
> 
> In fact, it doesn't have to be recursive...
> 
> ...
> invokevirtual <some method>
> areturn
> ...
> 
> This last invoke virtual can obviously reuse the current stack frame
> (under the condition that this code IS NOT enclosed in an exception
> handler).
> 
> In fact, SableVM could automatically detect the general pattern:
> 
> invokexxx  (be it invokespecial, invokestatic, invokevirtual,
> invokeinterface)
> xreturn (areturn, ireturn, ...)
> 
> And implement this reusing the current stack frame.
> 
> What we gain: tail recursion (and non-recursion:^)
> What we lose: exact stack trace for debugging.
>
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:

* Imagine a tail-recursive call set like this:

> (define (cat count total)
    (if (= 0 count) 
        total 
        (cat (- count 1) (+ count total))))

This obviously is a long way of adding the numbers from 1 to 'count', but it
creates a tail-recursive situation:

> (cat 10 0)
55
> (cat 100 0)
5050
>

* This might end up in java like so:

public class RecursiveTest
{
    public static int cat(int count, int total)
    {
        if (count == 0)
            return total;
	
	total += count;
	count--;
	return cat(count,total);
    }
    
    public static void main (String argp[])
    {
        System.out.println("Test result:");
	int output = cat(100,0);

	System.out.println(output);
        System.out.println("Done.");
    }
}

* 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

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

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 

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

e.g.:

main[1] stop in RecursiveTest.cat
Breakpoint set in RecursiveTest.cat
main[1] run
No class name specified.
main[1] cont
Test result:main[1]

Breakpoint hit: RecursiveTest.cat (RecursiveTest:5)
main[1] cont

Breakpoint hit: RecursiveTest.cat (RecursiveTest:5)
main[1] main[1] cont

Breakpoint hit: RecursiveTest.cat (RecursiveTest:5)
main[1] main[1] cont

Breakpoint hit: RecursiveTest.cat (RecursiveTest:5)
main[1] main[1] where
  [1] RecursiveTest.cat (RecursiveTest:5)
  [2] RecursiveTest.cat (RecursiveTest:10)
  [3] RecursiveTest.cat (RecursiveTest:10)
  [4] RecursiveTest.cat (RecursiveTest:10)
  [5] RecursiveTest.main (RecursiveTest:16)
main[1]

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?

> I am pretty sure that there are no security side effects, even for the
> new APIs, as the code is not enclosed in exception handlers, so there
> aren't much other things that can happen to the stack other 
> than popping the method parameters, pushing the method result, 
> and returning it.
> 
Great!

> In fact, this requires no modification to the verifier.
> 

Really Great!

> This seems like a perfect solution.  And it will be easy to implement
> (and nice to put in my thesis).  Free tail recusrion (or should we call
> it tail-method-invocation?)
> 

"Tail-Method-Invocation" has a nice ring to it. :-)

> One problem solved. :-))
> 
Wonderful!  :-)

-Brent