Compiling Scheme continuations onto JavaVM

In connection with the diploma thesis of Tor H. Ringstad and myself
(deadline coming up), I've been thinking about the implementation of
continuations on the Java Virtual Machine. What I'm looking for is
other people's viewpoints on my thoughts. I'll explain how I imagine
it can be done.


Let's start off with how we implement them closures. A closure in our
system is a class with an integer that points to a corresponding
method (eg. the value 1 would indicate that, say, method 'l1' is to be
called if and when this closure is applied to any arguments), and a
reference to the environment class. We will not go into data
representation here. A continuation is a subclass of the closure
class, with references to a stack class and a local variable array
class thrown in.


(About actual lambda applications: A dispatch method receives a
closure object and selects the function to be called based on the
state of the 'lambda pointer' integer.)


During execution, each lambda executes within a JVM frame. The JVM
maintains a frame stack for each thread in execution. The only entry
point to a method is through a method invocation.


When a call/cc is encountered in a lambda, the compilation splits the
lambda in two methods, one with the expressions before the call/cc
application, and one with the expressions following it. In the method
that calls call/cc, code is generated to create a continuation object,
dump the entire environment (operand stack, local variable array and a
reference to the environment) in this object, and calling the argument
to the call/cc application with it as an argument. The lambda pointer
integer in the continuation object is set to the other half of the
call/cc'ing lambda, which must be compiled with code that rebuilds the
runtime environment before doing its stuff.


The problem with this approach is that we're mapping our closures onto
call frames, which are JVM-internal structures and not fit for
efficiently placing on the heap. So for the more general case of
continuations, this is quite ugly and has a substantial overload if
you implement, say, a counter with continuations, as in the recent
<5c7ap1$78c@tokyo.engr.sgi.com> by Rob Warnock, ie. if you use inward
continuations. However, outward continuations may of course still be
compiled to a simple return statement in most cases, so that the
continuation needs not be constructed, and later applications of the
continuation (if any) will simply be a return statement.


Other approaches would presumably yield a more general implementation
that is more CPS-like, but it would probably be slower. The JVM, in my
opinion, delimits the level of abstraction both downwards and upwards
- not immediately given to C++ semantics (lower level) or, say,
Smalltalk (higher level), but concentrating on Java semantics. I think
any language that doesn't coincidentally map onto the JVM (Ada seemed
to map very well) reasonably one-to-one is going to suffer in
efficiency in some departments, and that especially goes for Scheme,
which is on a higher level than Java, yet requires control features in
the target code which are supported below the abstraction level of the
JVM (which handles continuations behind the scenes). Maybe all
languages aimed at the JVM will be influenced by it. Maybe I'm
rambling. What do you think?


(Followups to the non-moderated groups. I think functional isn't.)


--
  .. Kjetil Valstadsve <eddie@pvv.org>
  .. http://www.pvv.org/~eddie/
                                                min er så ny at han fremdeles gjør det av seg selv


--

Return to the comp.compilers page.
Search the comp.compilers archives again.