sablevm-developer Mailing List for SableVM (Page 64)
Brought to you by:
egagnon
You can subscribe to this list here.
2000 |
Jan
|
Feb
|
Mar
|
Apr
|
May
|
Jun
|
Jul
(27) |
Aug
(22) |
Sep
(1) |
Oct
|
Nov
(1) |
Dec
(30) |
---|---|---|---|---|---|---|---|---|---|---|---|---|
2001 |
Jan
(2) |
Feb
|
Mar
|
Apr
|
May
|
Jun
|
Jul
|
Aug
(2) |
Sep
(32) |
Oct
|
Nov
|
Dec
|
2002 |
Jan
|
Feb
|
Mar
|
Apr
|
May
|
Jun
|
Jul
|
Aug
(69) |
Sep
(10) |
Oct
(31) |
Nov
(15) |
Dec
(58) |
2003 |
Jan
(33) |
Feb
(81) |
Mar
(85) |
Apr
(24) |
May
(15) |
Jun
(14) |
Jul
(6) |
Aug
(9) |
Sep
(101) |
Oct
(59) |
Nov
(142) |
Dec
(34) |
2004 |
Jan
(107) |
Feb
(164) |
Mar
(181) |
Apr
(96) |
May
(81) |
Jun
(71) |
Jul
(1) |
Aug
|
Sep
|
Oct
|
Nov
|
Dec
|
From: Brent F. <bre...@xp...> - 2000-07-20 21:15:19
|
> In fact, can you write for me a simple example that requires > continuation? > Here goes: I took this example from http://www.nightmare.com/schintro-v14/schintro_127.html which I need to read through -- it seems to have lots of useful information. ------------------------------------------- (define some-flag #t) (define (my-abortable-proc escape-proc) (display "in my-abortable-proc") (if some-flag (escape-proc "ABORTED")) (display "still in my-abortable-proc") "NOT ABORTED") (define (my-resumable-proc) (do-something) (display (call-with-current-continuation my-abortable-proc)) (do-some-more)) (define (do-something) (display "Doing something.")) (define (do-some-more) (display "Doing some more.")) (my-resumable-proc) ------------------------------------------------- The result of this is: Doing something. in my-abortable-proc still in my-abortable-proc ABORTED Doing some more. The "ABORTED" shows that the call-with-current-continuation was used to jump back to its calling point. A neat Scheme-on-java implementation (SILK) http://www.cs.brandeis.edu/silk/silkweb/doc/resources/HOWTO.html#class allows you to compile Scheme to Java. Running this test.scm through that yields this: ------------------------------------------------------------------ // no package name; /** * this file is automatically generated by the silk->javac compiler Compiler.scm. * Modify at your own risk! */ import silk.*; import java.lang.reflect.*; import java.util.*; public class test extends silk.Procedure implements silk.Function, Runnable { public int whichcode=0; // corresponds to a numbering of the toplevel procedures of the program public int whichtype=0; // 0 = user defined procedure, 1 = java literal public static final int USER_DEF=0, JAVA_LIT=1; public Pair frame; public test() { super();} public test(int t, int n, Pair f) { whichtype = t; whichcode = n; frame = f; } private Boolean addImport(String s) { silk.Import.addImport(s); return Boolean.TRUE; } public void run() { this.invoke(null); } public Object apply(Object[] args) { return invoke((Pair)args[0]); } public Object apply(Pair args) { return invoke(args); } public Object invoke(Pair args) { return LCO.eval(invoke1(args)); } static Object tmp; public static void load() { new test().init(); } public static void load(String shellArgs[]) { silk.Symbol.intern("shellArgs").setGlobalValue(shellArgs); load(); } public static void main(String shellArgs[]) { Symbol main = silk.Symbol.intern("main"); load(shellArgs); if (main.isDefined()) ((silk.Procedure) main.getGlobalValue()).apply(new Pair(shellArgs,Pair.EMPTY)); } public Object invoke1(Pair args) { if (whichtype == USER_DEF) { switch (whichcode) { case 0: return(_L0(args)); case 1: return(_L1(args)); case 2: return(_L2(args)); case 3: return(_L3(args)); default: System.exit(0); break; }} else { switch (whichcode) { default: System.exit(0); break; }} return null; } public void init() { Pair Args = null; Symbol.intern("this").setGlobalValue(this); Class _p = Primitive.class; // this loads the primitives Symbol.intern("some-flag").setGlobalValue(_C0); Symbol.intern("my-abortable-proc").setGlobalValue(new test(USER_DEF, 0, new Pair( Args, this.frame))); Symbol.intern("my-resumable-proc").setGlobalValue(new test(USER_DEF, 1, new Pair( Args, this.frame))); Symbol.intern("do-something").setGlobalValue(new test(USER_DEF, 2, new Pair( Args, this.frame))); Symbol.intern("do-some-more").setGlobalValue(new test(USER_DEF, 3, new Pair( Args, this.frame))); ((silk.Procedure) ((Symbol)my_45_resumable_45_proc).getGlobalValue()).apply(Pair.EMPTY); } // definitions of global variables public static Object some_45_flag = Symbol.intern("some-flag"); public static Object my_45_abortable_45_proc = Symbol.intern("my-abortable-proc"); public static Object my_45_resumable_45_proc = Symbol.intern("my-resumable-proc"); // definitions of Scheme variables defined externally static Object display= Symbol.intern("display"); static Object do_45_something= Symbol.intern("do-something"); static Object call_45_with_45_current_45_continuation= Symbol.intern("call-with-current-continuation"); static Object do_45_some_45_more= Symbol.intern("do-some-more"); // definitions of quoted terms static Object _C0=Boolean.FALSE; static Object _C1="in my-abortable-proc"; static Object _C2="ABORTED"; static Object _C3=Boolean.TRUE; static Object _C4="still in my-abortable-proc"; static Object _C5="NOT ABORTED"; static Object _C6="Doing something."; static Object _C7="Doing some more."; // definitions of embedded lambdas Object _L0(Pair Args){ Object tmp; tmp = ((silk.Procedure) ((Symbol)display).getGlobalValue()).apply(new Pair(_C1, Pair.EMPTY)); tmp = (Boolean.FALSE.equals(((Symbol)some_45_flag).getGlobalValue()) ? _C3 : ((silk.Procedure) (( Pair) Args).getEltNover2(1)).apply(new Pair(_C2, Pair.EMPTY)) ); tmp = ((silk.Procedure) ((Symbol)display).getGlobalValue()).apply(new Pair(_C4, Pair.EMPTY)); tmp = _C5; return tmp; } Object _L1(Pair Args){ Object tmp; tmp = ((silk.Procedure) ((Symbol)do_45_something).getGlobalValue()).apply(Pair.EMPTY); tmp = ((silk.Procedure) ((Symbol)display).getGlobalValue()).apply(new Pair(((silk.Procedure) ((Symbol)call_45_with_45_current_45_continuation).getGlobalValue()).apply(ne w Pair(((Symbol)my_45_abortable_45_proc).getGlobalValue(), Pair.EMPTY)), Pair.EMPTY)); tmp = new LCO(((Symbol)do_45_some_45_more).getGlobalValue(),Pair.EMPTY); return tmp; } Object _L2(Pair Args){ Object tmp; tmp = new LCO(((Symbol)display).getGlobalValue(),new Pair(_C6, Pair.EMPTY)); return tmp; } Object _L3(Pair Args){ Object tmp; tmp = new LCO(((Symbol)display).getGlobalValue(),new Pair(_C7, Pair.EMPTY)); return tmp; } ------------------------------- This class obviously relies on the Silk interpreter code. I tried creating a stand-alone version (in a *.class file) under Kawa, but couldn't get it to work right under Windows (damn pathnames!). Thanks, -Brent |
From: Etienne M. G. <eg...@j-...> - 2000-07-20 05:23:58
|
Hi Brent. > I was thinking that it would probably be possible to simulate > continuations at the JVM level by using the same mechanisms that > are used for the exception handling. I'm not sure if this is an > efficient way to go about this, but in theory it should work. I doubt this would work. Reasons: 1- At the bytecode level, exception handling is expressed quite differently from Java source. 2- If I remember my high level programming languages course correctly, the whole point of a continuation is to capture a snapshot of the "current" stack, so that you can later execute code in this same context, even if the current stack is unwinded. In ML (or some dialect?) that allowed implementing "static binding" instead of "dynamic binding" a la LISP. The consequence is that the method in which the "create snapshot" occurs might return before you "resume" and execute the continuation. In which case your scheme wouldn't work, unfortunately. Please let me know if I am completely off track. (Quite possible!) In fact, can you write for me a simple example that requires continuation? See below for additional questions. > 3. JVM creates an exception that holds the current state of > this routine (i.e., must make a copy of the current variables) What is in the "saved" state? - current stack frame? - stack (all frames) of current thread? - global variables (e.g. static fields)? - other stacks (stack of other threads)? - heap state (object instances? - other vm internal state (locks, ...)? Etienne -- ---------------------------------------------------------------------- Etienne M. Gagnon, M.Sc. e-mail: eg...@j-... Author of SableVM: http://www.sablevm.org/ ---------------------------------------------------------------------- |
From: Etienne M. G. <eg...@j-...> - 2000-07-20 05:05:27
|
For the record. -------- Original Message -------- Date: Wed, 19 Jul 2000 21:29:12 -0700 From: Brent Fulgham <bfu...@de...> To: "Etienne M. Gagnon" <eg...@j-...> ... On another subject: Continuations. I was thinking that it would probably be possible to simulate continuations at the JVM level by using the same mechanisms that are used for the exception handling. I'm not sure if this is an efficient way to go about this, but in theory it should work. I'm not really sure how I could even pseudo-code this in Java, but in a pseudo-code: ... 1. Execute some statements 2. Source code calls for a "call-with-current-continuation" 3. JVM creates an exception that holds the current state of this routine (i.e., must make a copy of the current variables) 4. JVM starts a "Try" block 4. Execution continues 5. Eventually, a condition is reached where we want to jump back to the continuation. So the JVM "Throws" that exception 6. We unwind until we hit the top of the "Try" block. This is also coded as the "Catch", which restores state to where we were when we hit the start of the continuation. In fact, I'm not sure how much of this might be automatic with respect to the stack unwinding features. Is it possible we might find ourselves back where we started with the 'stack' in the proper state just automatically? I suppose it's too much to hope for... The nice thing about this idea is that, again, we don't have to do anything new -- we make use of existing JVM features. The Scheme (or whatever) compiler that targets the JVM would just have to know how to generate the code that starts / ends the continuation... What do you think? Terrible idea? :-) Regards, -Brent |
From: Etienne M. G. <eg...@j-...> - 2000-07-19 02:38:52
|
Hi Again. Brent Fulgham wrote: > Also, Per Bothner (we talked to him earlier this week) has > a write-up (http://sources.redhat.com/java/papers/native++.html) > that he did. Hmmm... This document seems as an early draft for CNI. I would personally be inclined to stick to C for native code. JNI overhead is bad enough, adding to that C++ overhead might no be ideal for key Java library methods. But I know that some Classpath developer would prefer using C++/CNI (where CNI would be implemented as a JNI wrapper). Etienne -- ---------------------------------------------------------------------- Etienne M. Gagnon, M.Sc. e-mail: eg...@j-... Author of SableVM: http://www.sablevm.org/ ---------------------------------------------------------------------- |
From: Etienne M. G. <eg...@j-...> - 2000-07-19 00:29:52
|
Hi Brent. Brent Fulgham wrote: > > > Sounds good. I am somewhat familiar with JNI, but have not used > it recently. I found a good summary on the web (see > http://www.mindspring.com/~david.dagon/jni/Native.txt), but > I don't know if it is fully up-to-date. The JNI book has the most up-to-date information. The online documentation is somewhat outdated, but more importantly, the book has 3 main parts: I- Introduction and tutorial II- Programmer's guide III- Specification Part II is very well written, and worth reading. I do not remember seeing its equivalent online. The book list price is US$39.95. It's probably worth the investment, as it is the definitive reference. (The book explains Local Ref frames, and all kind of subtle JNI concepts, and how to apply them in your native code). Etienne -- ---------------------------------------------------------------------- Etienne M. Gagnon, M.Sc. e-mail: eg...@j-... Author of SableVM: http://www.sablevm.org/ ---------------------------------------------------------------------- |
From: Brent F. <bre...@xp...> - 2000-07-19 00:19:43
|
> Once you're familiar with the JNI, you can help me by first > cleaning up the SablePath native code. I might also need some > help implementing some core classes, unless I have time to > implement them first. > > How does that sounds? Is it OK for you? > Sounds good. I am somewhat familiar with JNI, but have not used it recently. I found a good summary on the web (see http://www.mindspring.com/~david.dagon/jni/Native.txt), but I don't know if it is fully up-to-date. I could only find a copy of the Jdk1.1 version of the JNI interface (in PDF/PS format) from Sun. I was going to use this (since it seems pretty well-written), but I'm not sure if it's too out of date. I see the Jdk 1.2 had some enhancements, but they aren't worked into the spec. Also, Per Bothner (we talked to him earlier this week) has a write-up (http://sources.redhat.com/java/papers/native++.html) that he did. |
From: Etienne M. G. <eg...@j-...> - 2000-07-19 00:07:35
|
Brent Fulgham wrote: > 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. :-) That's a simple and elegant solution. I would probably make that "(tail)", but this only costs one bit of information. I'll have to see if this could be stolen somewhere on the current frame design. In the worst case, it would cost on additional byte per frame. > It will be interesting to see the difference in performance with this > feature turned on and off... :-) There will be some overhead cause by the displacement of method arguments. But, the effect on the memory cache should be positive, as we are creating additional locality. Reducing cache misses could very well offest completely any overhead;-) It's really exciting! > 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... Let's wait for "Hello World" before we attack this more complex one. Thanks for brigning this FP subject up! I didn't realize it would be that exciting. Etienne -- ---------------------------------------------------------------------- Etienne M. Gagnon, M.Sc. e-mail: eg...@j-... Author of SableVM: http://www.sablevm.org/ ---------------------------------------------------------------------- |
From: Brent F. <bre...@xp...> - 2000-07-18 23:34:16
|
> 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 |
From: Etienne M. G. <eg...@j-...> - 2000-07-18 23:22:01
|
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/ ---------------------------------------------------------------------- |
From: Brent F. <bre...@xp...> - 2000-07-18 22:17:02
|
> > 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 |
From: Etienne M. G. <eg...@j-...> - 2000-07-18 21:10:25
|
Brent Fulgham wrote: > > All this functional-programming impact on JVM design is > interesting, but probably not real critical right now. > (Or at least, it's enough just to keep the ideas in mind > when working for now.) > > So how should we (rather, I) get started? What pieces > of the base classes need to be completed? Are you familiar with the JNI? I think that this would be the first thing to do. You need not as much to know about the vm's internals to play with the JNI. What is currently missing is the implementation of most JNI hooks, but these require deep knowledge of SableVM's internals, and they are pretty mechanical to implement. So' I'll take care of that. Once you're familiar with the JNI, you can help me by first cleaning up the SablePath native code. I might also need some help implementing some core classes, unless I have time to implement them first. How does that sounds? Is it OK for you? > As far as that goes, I would also like to see (someday) > a Swing library based on GTK. But that's obviously > going to have to wait for SableVM to be able to run > "HelloWorld!" at least. :-) Yep. Having "Hello World" will be nice. But you realize that this simple "Hello World" requires at least 90% of the vm to be operational... But we're pretty close. Etienne -- ---------------------------------------------------------------------- Etienne M. Gagnon, M.Sc. e-mail: eg...@j-... Author of SableVM: http://www.sablevm.org/ ---------------------------------------------------------------------- |
From: Etienne M. G. <eg...@j-...> - 2000-07-18 20:46:56
|
Hi Brent. > 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). > 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. So, this feature could be turned on/off. Potential problems: The latest APIs use some VM collaboration to implement some security scheme that depends on the stack. We would have to doublecheck that we are not introducing any security hole. 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. In fact, this requires no modification to the verifier. 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?) One problem solved. :-)) Etienne -- ---------------------------------------------------------------------- Etienne M. Gagnon, M.Sc. e-mail: eg...@j-... Author of SableVM: http://www.sablevm.org/ ---------------------------------------------------------------------- |
From: Etienne M. G. <eg...@j-...> - 2000-07-18 20:38:47
|
For the record;-) -------- Original Message -------- Subject: RE: [Sablevm-user] About closures... Date: Tue, 18 Jul 2000 13:21:46 -0700 From: Brent Fulgham <bre...@xp...> To: "Etienne M. Gagnon" <eg...@j-...> > Brent Fulgham wrote: > > These sound like excellent ideas. The only other thing > > that might be useful would be a "UseSameFrame" bytecode > > for help with tail-recursive situations. I.e., a Scheme > > compiler for SableVM would be able to provide the JVM with > > the "UseSameFrame" for a tail-recursive functions to > > save stack space and convert the 'recursive' function into > > an interation. > > You know, this "UseSameFrame" bytecode would be almost trivial to > implement. But more importantly, it would be very easy to extend the > verifier to check that it is correctly used: [ ... snip explanation ... ] I've started reading up on the Java VM (I am not familiar with its internals) last night. I notice that its instruction set is mapped over 8-bit values, so there are only 256 instructions available. I also read that most data types have their own bytecodes for operations, which must use up quite a few bytecodes. Is there room for three new bytecodes (UseSameFrame, BeginContinuation, UseContinuation)? I'm a bit worried :-) In fact, I wonder if the JVM could identify tail-recursion on its own and handle it behind-the-scenes. It seems that the bytecode-level commands might be too simple to allow for easy recognition. I don't know. It seems to me that we are always better of avoiding new bytecodes (or rather, any change in the JVM's API) if possible so that we are fully compliant with the "Java" specification. Non-standard additions mean people are not likely to use them, and they are therefore less likely to become part of the standard system. > Of course, this "UseSameFrame" wouldn't be available to > native methods. Or, to be precise: > - A bytecode method IS ALLOWED to invoke native methods through the > "UseSameFrame" bytecode. > - A native methods CANNOT is limited to the current JNI interface, > which desn't export a similar functionality. > Agreed... > This would be a good thing, as: > - The native code uses the normal "C" stack, which is (or can be) > different from the interpreter stack. The native language can already > have its own mechanisms to "reuse" the current stack frame, > so exporting the functionality from the VM is not that important. Right. We might even mess things up if we don't fully understand the underlying system's handling of this. > - The VM stack contains frame(s) of "Local" references, > which handling would become a nightmare if the "UseSameFrame" > functionality was exported. > Yes. And it adds a lot of complexity we don't want. Generally, tail-recursive cases will be occurring in the "runtime" code (i.e., non-native code) as parts of algorithms, etc. Especially under Lisp-ish systems. So I don't see that as being a big problem. If someone wants to write a Java class (e.g.) that wraps some set of native routines, then uses these classes as part of a tail-recursive procedure, I don't know that we want to give it the "UseSameFrame" special treatment. > PS: You may use these ideas as you see fit, but I would be > grateful that you gave me credit. Of course! I don't plan on doing anything with this information outside of SableVM, should we determine that this was beneficial to the overall goal of the VM. > PPS: It might be interesting, at some point, and if our projects go > along, to write some joint paper(s);-) Absolutely! There are several obvious topics that could be written up (the tail-recursion, especially if done inside the VM without need for special bytecodes; success in implementing some existing functional programming experiment on the JVM, as in the Haskell-on-JVM done by the Wakeling '98 paper; or just about any new aspect of the VM). Of course, it's been a couple of years since I last wrote a journal article (and that was in my former career as an Environmental Engineer). It would be nice to be published again for studying things I'm interested in. :-) Regards, -Brent |
From: Brent F. <bre...@xp...> - 2000-07-18 20:23:46
|
All this functional-programming impact on JVM design is interesting, but probably not real critical right now. (Or at least, it's enough just to keep the ideas in mind when working for now.) So how should we (rather, I) get started? What pieces of the base classes need to be completed? As far as that goes, I would also like to see (someday) a Swing library based on GTK. But that's obviously going to have to wait for SableVM to be able to run "HelloWorld!" at least. :-) Thanks, -Brent |
From: Brent F. <bre...@xp...> - 2000-07-17 22:55:10
|
The issue most functional programming languages have when "compiled" into JVM bytecode seem to fall into two areas (drawn from the Wakeling, J. Functional Programming January 1998): 1. Things that can be done inside the JVM without changing the API: (a) Poor memory allocation performance: Functional languages such as Haskell or Scheme tend to do a lot of memory allocation. A full order of magnitude slowdown on the JVM has been documented as a result of memory allocation issues. A more efficient memory allocator would greatly improve performance in this area. (b) ?? Tail-recursion: (Quoting from Wakeling, '98) "In functional programs, the result of one function application is often given by another with exactly the right number of arguments. ... an implementation can save stack space by ensuring that the two function calls use the same frame. But the JVM specification does not require that tail recursive method invocations use the same stack frame. As a result, a straightforward implementtion of a tail recursive functional program ... could easily overflow the stack". The benefits here are obvious, but I'm not sure how this would be implemented. 2. Things that require and API change. (a) Stack reduction: (Paraphrasing Wakeling, '98) Lazy functional languages (Haskell) are often implemented using some form of Graph Reduction in which expressions are represented by graphs, which are then simplified until the final result is obtained. Apparently, many implementations make use of a 'reduction stack', which holds pointers to the graphs representing parts of expressions, etc. Since there is no way to represent such pointer-to-object semantics in the JVM because there is no way to access the JVM stack. Representing these constructs in Java through arrays is costly because of the memory issues I mentioned above, plus bounds checking cost. This issue may be eased somewhat by a better memory allocator -- I think this option should be set aside for the time being, as I have no idea how to attack it. And that's about it. It seems we could make some good progress by trying to address 1.(a) and 1.(b). I suspect 1.(a) might not be too difficult to address. Christian Tismer (and others) implemented a so-called "stackless" variant of the Python compiler/interpreter. I wonder if any of the techniques he used could enhance the SableVM system? I'm cc'ing him so I don't inadvertently put words in his mouth, but he took a look at Kaffe at one point to see if he could generate a 'stackless' version, but felt there were serious architectural issues. Perhaps he could give us his reasons, and Etienne could comment on whether the same design trade-offs were made with SableVM. Thanks, -Brent |
From: Etienne M. G. <eg...@j-...> - 2000-07-17 21:29:27
|
Brent Fulgham wrote: > Oh, absolutely. I hope I am not offending you by sending all > this mail. Not at all! I just wanted to warn you that you will have to assume that I have little knowledge of functional programming run time environments, in your future questions... > > Note: You might also want to start thinking about the implications of > > adding closures on the verifier... > > Hmm. This is a good point with respect to providing compilers with > access to some internal JVM state to implement, e.g., continuations. > One that I haven't though about... I think that it is important to keep these practical matters at glance, if you want future inclusion of your ideas in the official vm specification. Have fun! Etienne -- ---------------------------------------------------------------------- Etienne M. Gagnon, M.Sc. e-mail: eg...@j-... Author of SableVM: http://www.sablevm.org/ ---------------------------------------------------------------------- |
From: Etienne M. G. <eg...@j-...> - 2000-07-17 21:21:00
|
Hi Brent. Brent Fulgham wrote: > 2. "SOOT" is a Java optimization framework. It may or may not > be useful as I haven't spent time to see if it's only used for > Java source code (as opposed to bytecode). > http://www.sable.mcgill.ca/soot/ I know quite a bit about Soot; I have implemented its type inference algorithm, and just presented a paper about that at SAS2000. Soot is an optimization framework for Java bytecode. So, it reads any "verifiable" bytecodes (the original source could be Java, scheme, ML, whatever) and transforms it into typed 3-address code, suitable for optimization, then it can spit out optimized bytecode back. It is one of our goal to have some integration of Soot with SableVM. Soot already can generate attributes in class files, that we should be able to handle in SableVM before the end of the summer. Etienne -- ---------------------------------------------------------------------- Etienne M. Gagnon, M.Sc. e-mail: eg...@j-... Author of SableVM: http://www.sablevm.org/ ---------------------------------------------------------------------- |
From: Brent F. <bre...@xp...> - 2000-07-17 21:16:54
|
> Brent Fulgham wrote: > > The first (i.e., most recent) paper discusses several flaws > > with existing JVM's. > > I probably won't have time to go through all these papers. > But, I will certainly be available to answer any question you > have about SableVM's internal representation, and how you can > make use of it. > Oh, absolutely. I hope I am not offending you by sending all this mail. I just want to "enter them into the record" so to speak, so we have them archived in the mailing list, since I can't always find things once I need them. > > I think it would be great if we could > > provide a work-around on top of SableVM. > > I am open to extentions, as long as they can be truned off/on easily > (compile and/or run time, if there's no efficiency penalty). > Preferably, extentions should be off by default, so that users using > SableVM as a normal Java interpreter get what they expect. > Yes. It is critical that the JVM be fully Java-compliant, otherwise it is relatively useless. > Note: You might also want to start thinking about the implications of > adding closures on the verifier... I know that many functional > languages provide static safety, but the Java interpreter > also provides compiler independent link time safety through the > verifier, a protection against devious compilers. > Hmm. This is a good point with respect to providing compilers with access to some internal JVM state to implement, e.g., continuations. One that I haven't though about... > > It might not be standard, but perhaps (if it is successful) it > > could be added to the JVM specification? > > This is not under my control (it is under Sun's), but I can certainly > allow you to test your ideas with SableVM:-) > Excellent! Some of these papers seem to indicate that certain performance benefits might be realized by Java itself through the proposed constructs. Only benchmarking will say for sure. But it might be interesting to try them (if we can do so in a safe fashion). Thanks, -Brent |
From: Brent F. <bre...@xp...> - 2000-07-17 21:12:38
|
More interesting ideas: 1. "JAVAB" Is a tool that can take a Java "*.class" file and automatically detect and exploit implicit loop parallelism in the bytecode. This would be really cool, but it has a restrictive license (i.e., free for non-commercial use). It's not that big a loss, since it probably only helps on multi-processor systems. http://www.extreme.indiana.edu/~ajcbik/JAVAB/index.html 2. "SOOT" is a Java optimization framework. It may or may not be useful as I haven't spent time to see if it's only used for Java source code (as opposed to bytecode). http://www.sable.mcgill.ca/soot/ 3. "KIEV" is a Java varient based on Pizza. It produces standard Java bytecode as output. It implements Closures with inner classes. http://forestro.com/kiev/ Regards, -Brent |
From: Etienne M. G. <eg...@j-...> - 2000-07-17 21:02:29
|
Hi Brent. Brent Fulgham wrote: > The first (i.e., most recent) paper discusses several flaws > with existing JVM's. I probably won't have time to go through all these papers. But, I will certainly be available to answer any question you have about SableVM's internal representation, and how you can make use of it. > I think it would be great if we could > provide a work-around on top of SableVM. I am open to extentions, as long as they can be truned off/on easily (compile and/or run time, if there's no efficiency penalty). Preferably, extentions should be off by default, so that users using SableVM as a normal Java interpreter get what they expect. Note: You might also want to start thinking about the implications of adding closures on the verifier... I know that many functional languages provide static safety, but the Java interpreter also provides compiler independent link time safety through the verifier, a protection against devious compilers. > It might not be > standard, but perhaps (if it is successful) it could be added > to the JVM specification? This is not under my control (it is under Sun's), but I can certainly allow you to test your ideas with SableVM:-) Etienne -- ---------------------------------------------------------------------- Etienne M. Gagnon, M.Sc. e-mail: eg...@j-... Author of SableVM: http://www.sablevm.org/ ---------------------------------------------------------------------- |
From: Brent F. <bre...@xp...> - 2000-07-17 20:57:37
|
Per's reply: -----Original Message----- From: Per Bothner [mailto:pe...@bo...] Sent: Monday, July 17, 2000 1:07 PM To: Brent Fulgham Cc: pe...@bo... Subject: Re: FW: Java Virtual Machine/Scheme Question [Feel free to forward this appropriately.] Brent Fulgham <bre...@xp...> writes: > After some thought, I eventually gave up on my ill-advised idea of > hacking the back-end of the MzScheme interpreter (VM) to support > Java. I now believe it is better to go the other way (i.e., a > Scheme implementation in Java), which is of course Kawa. > > One thing I've read in a few places (Kaffe list for one) is that > the current JVM architecture is not well-suited for implementing > continuation and closure semantics. I can't say if this is true > from personal experience, and I wanted to get your thoughts. Well, almost no architecture is directly suitable for continuation and closure semantics. You have to simulate them using more primitive constructs - "objects" containing pointers to other objects. JVM can do this, just like a raw cpu. However, there are some things you cannot do in Java: You cannot embed one object inside another (unless one class "extends" another). You cannot have arrays of objects (only arrays of object pointers). You cannot return multiple values, unless you wrap the in an object etc. However, these problems can be worked around by allocating extra objects. So the JVM may cause some extra object allocation (and hence garbage collection) than is needed. The challendge is to design the calling conventions and APIs to minimize this. There is no "pointer to function/method" in Java. You can simulate this using closure object or reflection, but the latter is quite slow. So Kawa goes through some hoops because of this. You can implement continuations by allocating explicit "frame objects", which some implementations (that do not have the JVM's restrictions) do anyway, so this need not be major hardship. The main problem is that the standard Java calling convention is very different (and quite faster) that a heap-based calling convention using frame objects. I did spend soem time recently on an "explicit frame" calling convention for Kawa for call/cc support. I made some progress. My problem is not figuring how to do it, but figuring out how to keep everything working together and efficiently will take more time. Creating a procedure-specific "frame" object is an issue: Creating a custom class for each procedure is elegant, but I'm concerned about the overhead of a large number of trivial classes. > Could you give any comments on your understanding of the JVM's > shortcomings in this area, and whether or not the availability of > such internal hooks might be helpful? Is it a non-issue, and the > complaints are really about trivial things? Well, the problems are trivial if you don't mind allocating an extra object or two per procedure call. (Some Scheme implementations allocate a list for the arguments to every call, which is of course just as bad or worse.) If you want to minimize object allocation, then things are harder. Inlining can help, for example. -- --Per Bothner pe...@bo... http://www.bothner.com/~per/ |
From: Brent F. <bre...@xp...> - 2000-07-17 20:48:52
|
I almost forgot the most important one of all: http://www.dcs.ex.ac.uk/~david/research/java.htm The first (i.e., most recent) paper discusses several flaws with existing JVM's. I think it would be great if we could provide a work-around on top of SableVM. It might not be standard, but perhaps (if it is successful) it could be added to the JVM specification? -Brent |
From: Brent F. <bre...@xp...> - 2000-07-17 19:10:30
|
Per, After some thought, I eventually gave up on my ill-advised idea of hacking the back-end of the MzScheme interpreter (VM) to support Java. I now believe it is better to go the other way (i.e., a Scheme implementation in Java), which is of course Kawa. One thing I've read in a few places (Kaffe list for one) is that the current JVM architecture is not well-suited for implementing continuation and closure semantics. I can't say if this is true from personal experience, and I wanted to get your thoughts. The reason for my curiosity is that the Sable JVM (SableVM project at http://www.sablevm.org) is an implementation of the JVM. It might be possible to include hooks for stack frames or other internal constructs to make the coding of "Functional Programming Paradigms" easier or the implementation more efficient. Could you give any comments on your understanding of the JVM's shortcomings in this area, and whether or not the availability of such internal hooks might be helpful? Is it a non-issue, and the complaints are really about trivial things? Thanks, -Brent |