[jvm-l] CPS languages in Java
Hi, I'm looking at implementing a language that would be best represented using CPS. Now, I can't really find any references to full CPS implementations on the JVM anywhere. I'm looking at using the technique Kawa is planning for compiled code (see the last part at http://www.gnu.org/software/kawa/internals/complications.html). Has anyone else done this? It seems one of the natural side effects of something like this would be a need to have almost all primitives implemented in the language itself, since writing this kind of code by hand is a bit of a pain. Second, has anyone tried, or is it even possible to do real CPS in interpreted style on the JVM? It would seem as that would require at least TCO to work. I guess my implementation won't have any interpretation if that's the case. =) Cheers -- Ola Bini (http://ola-bini.blogspot.com) JRuby Core Developer Developer, ThoughtWorks Studios (http://studios.thoughtworks.com) Practical JRuby on Rails (http://apress.com/book/view/9781590598818) Yields falsehood when quined yields falsehood when quined. --~--~-~--~~~---~--~~ You received this message because you are subscribed to the Google Groups JVM Languages group. To post to this group, send email to jvm-languages@googlegroups.com To unsubscribe from this group, send email to [EMAIL PROTECTED] For more options, visit this group at http://groups.google.com/group/jvm-languages?hl=en -~--~~~~--~~--~--~---
[jvm-l] Re: CPS languages in Java
On Dec 29, 2007 9:05 AM, Ola Bini [EMAIL PROTECTED] wrote: I'm looking at implementing a language that would be best represented using CPS. Now, I can't really find any references to full CPS implementations on the JVM anywhere. I'm looking at using the technique Kawa is planning for compiled code (see the last part at http://www.gnu.org/software/kawa/internals/complications.html). Has anyone else done this? If you haven't already, I recommend reading Henry Baker's classic paper Cheney on the MTA http://home.pipeline.com/~hbaker1/CheneyMTA.html, which is about compiling full Scheme to the C virtual machine, which is close enough to the JVM as far as control issues are concerned. Essentially, you compile all functions into CPS, and then each function calls its successor using an ordinary C function call, never returning from it. When the C stack gets too full[*], all the data structures are evicted to the GCed heap, and all the control frames are discarded by a longjmp back to the beginning. This provides *amortized* TCO automatically; that is, although stack is pushed, it gets recycled rapidly -- in essence, the C stack doubles as the first generation of the Scheme heap. [*]The size of the C stack is measured by subtracting a pointer to a local variable from a global pointer to a variable kept in the main procedure; on the JVM, you'd presumably keep a global count of procedures invoked as a rough measure. It seems one of the natural side effects of something like this would be a need to have almost all primitives implemented in the language itself, since writing this kind of code by hand is a bit of a pain. It's no problem in such a system to call ordinary C functions, provided they don't call back into Scheme or consume too much stack. The Chicken Scheme implementation http://www.call-with-current-continuation.org is an actual implementation of this idea for Scheme-to-C (I'm involved in the community in my copious spare time). I'd look there next. The community is helpful and friendly, and may well have good ideas about how to adapt Cheney-style operations to the JVM. -- GMail doesn't have rotating .sigs, but you can see mine at http://www.ccil.org/~cowan/signatures --~--~-~--~~~---~--~~ You received this message because you are subscribed to the Google Groups JVM Languages group. To post to this group, send email to jvm-languages@googlegroups.com To unsubscribe from this group, send email to [EMAIL PROTECTED] For more options, visit this group at http://groups.google.com/group/jvm-languages?hl=en -~--~~~~--~~--~--~---
[jvm-l] Re: CPS languages in Java
John Cowan wrote: On Dec 29, 2007 9:05 AM, Ola Bini [EMAIL PROTECTED] wrote: I'm looking at implementing a language that would be best represented using CPS. Now, I can't really find any references to full CPS implementations on the JVM anywhere. I'm looking at using the technique Kawa is planning for compiled code (see the last part at http://www.gnu.org/software/kawa/internals/complications.html). Has anyone else done this? If you haven't already, I recommend reading Henry Baker's classic paper Cheney on the MTA http://home.pipeline.com/~hbaker1/CheneyMTA.html, which is about compiling full Scheme to the C virtual machine, which is close enough to the JVM as far as control issues are concerned. Essentially, you compile all functions into CPS, and then each function calls its successor using an ordinary C function call, never returning from it. When the C stack gets too full[*], all the data structures are evicted to the GCed heap, and all the control frames are discarded by a longjmp back to the beginning. This provides *amortized* TCO automatically; that is, although stack is pushed, it gets recycled rapidly -- in essence, the C stack doubles as the first generation of the Scheme heap. Hi, Yes, I've taken a look at that paper, and various other implementations, including Lisp In Small Pieces, which does all these tricks. The problem is that they're all using things that require you to manipulate the stack in some way. setjmp and longjmp can of course be duplicated in a manner by using exceptions, but the rest of the stack manipulation doesn't seem possible. Otherwise, that model would probably work fine. -- Ola Bini (http://ola-bini.blogspot.com) JRuby Core Developer Developer, ThoughtWorks Studios (http://studios.thoughtworks.com) Practical JRuby on Rails (http://apress.com/book/view/9781590598818) Yields falsehood when quined yields falsehood when quined. --~--~-~--~~~---~--~~ You received this message because you are subscribed to the Google Groups JVM Languages group. To post to this group, send email to jvm-languages@googlegroups.com To unsubscribe from this group, send email to [EMAIL PROTECTED] For more options, visit this group at http://groups.google.com/group/jvm-languages?hl=en -~--~~~~--~~--~--~---
[jvm-l] Re: CPS languages in Java
Ola, One more: http://www.ccs.neu.edu/scheme/pubs/stackhack4.html This one is a C# implementation of the ideas found in Continuations from Generalized Stack Inspection. The implementation doesn't access the stack directly and use exception handling to perform the capturing. Useful since it shows what the generated code would look like for the fibonacci and takeuchi functions. Kelly On Dec 29, 2007 4:55 PM, Ola Bini [EMAIL PROTECTED] wrote: Kelly Nawrocke wrote: Ola, I had some papers on A-Normal form and trampolining on the JVM (to allow for proper tail call optimization for scheme and ml impls though accessing the current continuation in the user code is possible) but they seem to be lost. The one paper compared using return sleds (special Class instance that would be returned to the trampoline loop capturing the frames all the way down) and exceptions (similar to the return sled except used try/catch blocks instead). They found that returning to the trampoline loop every N frames (~40 was optimal at the time) was the most efficient. The code needed to be transformed into A-Normal form to allow for proper capture of the current continuation (what would be passed to the trampoline loop to unwind the stack). I am going to keep on searching for them and will post the links on this thread. Kelly Thank you! That would be very helpful. Since the current approach needs some careful transformation too, transforming to A-Normal shouldn't be much harder. I've considering using versions of trampolining too, of course. Cheers -- Ola Bini (http://ola-bini.blogspot.com) JRuby Core Developer Developer, ThoughtWorks Studios (http://studios.thoughtworks.com) Practical JRuby on Rails (http://apress.com/book/view/9781590598818) Yields falsehood when quined yields falsehood when quined. -- Like the fella says, in Italy for 30 years under the Borgias they had warfare, terror, murder, and bloodshed, but they produced Michelangelo, Leonardo da Vinci, and the Renaissance. In Switzerland they had brotherly love - they had 500 years of democracy and peace, and what did that produce? The cuckoo clock. -- Orson Welles --~--~-~--~~~---~--~~ You received this message because you are subscribed to the Google Groups JVM Languages group. To post to this group, send email to jvm-languages@googlegroups.com To unsubscribe from this group, send email to [EMAIL PROTECTED] For more options, visit this group at http://groups.google.com/group/jvm-languages?hl=en -~--~~~~--~~--~--~---
