Are we dead or alive? (was Re: a good volunteer)

[Lars Thomas Hansen]

>I think there's something you should know if you're considering
>this option.  That is, it is not possible to build a conforming
>scheme using the Java Virtual machine.  It is flatly impossible
>as far as I know to build a properly tail-recursive language
>with first-class continuations when you have to fight the Java
>Virtual Machine's security-inspired stack discipline.  Per
>Bothner (author of kawa) has talked about this on
>comp.lang.scheme, and Kawa is not a conforming implementation. 

I don't know what Bothner has told you, but I suspect that he must have
qualified that statement somehow.  There should be nothing in Java that
hinders use of the dispatch loop technique (aka "UUO handler", due to
Guy Steele and used in his Rabbit system; an article in LOPLAS a few
years ago describes it in some detail) used by some Scheme-to-C and
ML-to-C compilers, nor should there be anything problematic about using
the "Cheney on the MTA" technique (due to Henry Baker and (I think)
Andrew Appel; I'm not sure where this is written up).

In both cases, the translation is required to keep a continuation and
other system state separate from the continuation (stack) and system
state of the Java system, and the performance penalty for this may be
nontrivial.  However, I very much doubt it's impossible.

The dispatch loop technique consists of a simple dispatch loop:

	f = <some object with a run method>
	while (true)
		f = f.run();

Each Scheme procedure is compiled into a CPS-like form where each
continuation is an instance with a run() method; when compiled code
needs to perform a call, it returns the instance that represents the
address to call to the dispatch loop, which then calls it.  Return
addresses are also represented as instances and saved on a control
stack.

The Cheney on the MTA technique is similar, but instead of returning the
continuation to the dispatch loop it calls it directly.  A limit is kept
on the number of these (non-tail) calls.  When the limit is reached, a
longjmp (exception) is performed to prune the useless stack, and
execution continues.  (Gross, huh? :-)

Since the Scheme continuation is maintained separately from the Java
continuation, it can be captured and resumed without much trouble.

(All of this modulo problems with the type system: I've implemented the
dispatch loop technique in C but that required a typecast because C
can't express the necessary recursive procedure type; I don't think this
would be an issue in Java.)

--lars