[PRL] [plt-internal] Video of Clojure talk

[Joe Marshall]

Shriram pointed out:
Maybe we should have written "Continuations from Generalized Stack
Inspection" as "Tail-Calls from Generalized Stack Inspection".

To which SamTH replied:
I don't think that he'd be willing to take the performance hit from
that either.

I've been playing with my own version of Scheme on the CLR (not Larceny).
I've used a variant of the Continuations from Generalized Stack Inspection.
(The CLR supports tail calls, but the C# compiler does not emit them.)

The original paper used the exception handler as the mechanism to activate
the alternative flow of control needed to read the stack.  In my
version of Scheme,
I have used `exception conversion' to deal with the problem.  The idea is this:
all Scheme functions return values via a call-by-reference parameter.  The
usual return value is a boolean that is used for tail recursion.  So a standard
call to Eval looks like this:

            object evarg;
            Control unev = this.operand;
            Environment env = environment;
            while (unev.EvalStep (out evarg, ref unev, ref env)) { };

The tail recursion is achieved by the while loop.  When a function wishes
to tail-call to another one, it smashes the Control and Environment variables
in the caller and then return true.  If it returns a value, it smashes the
out parameter in the caller and returns false.  In effect, we've hoisted the
allocation of the Control and Environment parameters into the caller's frame
even though they are logically part of the callee.

This gives us our tail recursion, but what about continuations?  We have a
special distinguished value `Interpreter.UnwindStack' that we test for after
each call:

            object evarg;
            Control unev = this.rand;
            Environment env = environment;
            while (unev.EvalStep (out evarg, ref unev, ref env)) { };
            if (evarg == Interpreter.UnwindStack) {
                ((UnwinderState) env).AddFrame (new Combination1Frame0
(this, environment));
                answer = Interpreter.UnwindStack;
                environment = env;
                return false;
            }

If the return value is this magic token, then we evacuate our stack frame to
a data structure and continue by returning the same magic token to our caller.
The rest is simply following the paper.

(A side note.  In order pass back the unwinder state that used to be in the
exception, I pass it back in the `Environment'.  It isn't an
environment, though.
How do I get this pass the type checker?  It's a bald-faced lie.  I derive the
unwinder from the Environment class, override every method to throw an error,
and add the methods to support unwinding.  So much for type safety and static
type checking.)

As you recall (at least SamTH recalls), throwing an exception is 50,000 times
slower than returning a value and this makes the mechanism useless in
practice.  By converting the code as above I bypass the performance hit.

My Scheme interpreter uses the CLR stack in a reasonably `normal' way,
supports full and proper tail recursion, and supports full first-class
continuations.
Because it uses the CLR stack for continuation management rather than
the heap, it takes advantage of the stack hardware.

I have compared it to the MIT Scheme interpreter running identical code.
MIT Scheme uses a single large C function to implement the interpreter and
manages an external stack for continuations.  My interpreter, despite being
written in C#, outperforms MIT Scheme on identical Scheme code.  I think
this demonstrates that this method is a practical one for achieving proper
tail recursion and first-class continuations without an undue performance hit.


Maybe we need a followup paper.

-- 
~jrm