In ‘Continuations from Generalized Stack inspection’, and in the Addendum, I showed how to abuse the exception handling mechanism to implement call-with-current-continuation on a virtual machine that doesn't allow access to the stack. The problem with the method is that exception handling is astoundingly slow. Nearly any other method of handling continuations will outperform it.

The key to the method is noticing that the method associated with each stack frame has full access to its own frame even if the other methods do not. The exception mechanism was a way to transfer control back to method, but to a segment of code that unloads the stack rather than continues the computation. This is quite similar to what we just did with the calling conventions to EvalStep. The machinery necessary to handle first-class continuations is an almost trivial addition. We create special singleton object and test the return value for this object. If we see it, we unload the current frame and return. This propagates down the stack until we reach the bottom and the stack is empty. As an example, the code for interpreting a conditional expression is this:

public override bool EvalStep (out object answer, ref SCode expression, ref Environment environment)
{
    SCode unev = this.predicate;
    Environment env = environment;
    while (unev.EvalStep (out answer, ref unev, ref env)) { };
    if (answer == Interpreter.UnwindStack) {
        UnwindState xxx = <get unwind state>
        xxx.AddFrame (new ConditionalState (this, environment));
        return;
        }

    expression = (answer is bool) && (bool) answer == false
        ? this.alternative
        : this.consequent;
    return true;
}

The special code has a simple task. It should save any relevant state out of the current stack frame into a data structure, then add that data structure to the list of reified stack frames, and finally return the ‘Interpreter.UnwindStack’ object itself.

Where do we keep the reified stack frames? We'd like to pass it down from the frames above, but it seems a waste to allocate yet another local variable and ref argument for this purpose because they are used so rarely. We use the ‘Wolf in Sheep's clothing trick’ to accomplish this.

class UnwindState : Environment
{
   <whatever needed for unwinding>
 
   <a bunch of virtual methods that
    make the compiler think we handle the ‘Envionment’ 
    protocol, but just raise errors>
}

And now we can stuff the unwind state in the Environment:

     
public override bool EvalStep (out object answer, ref SCode expression, ref Environment environment)
{
    SCode unev = this.predicate;
    Environment env = environment;
    while (unev.EvalStep (out answer, ref unev, ref env)) { };
    if (answer == Interpreter.UnwindStack) {
        ((UnwindState) env).AddFrame (new ConditionalState (this, environment));
        return;
        }

    expression = (answer is bool) && (bool) answer == false
        ? this.alternative
        : this.consequent;
    return true;
}

Our calling convention is a fair amount more complicated than it was. Each caller to EvalStep must wrap the call in a while loop, then it must check for the answer being ‘Interpreter.UnwindStack’, and if so, handle the stack unwinding via the environment variable. Not pretty, but it works.

Continuations in my version of Scheme are no longer allocated in the heap, but on the stack where we can take advantage of the hardware. Tail recursion is preserved via an unusual calling convention. However, the code is able to load and unload the stack, so call-with-current-continuation works correctly.

With these changes, the C# version of the MIT-Scheme interpreter now outperforms the original C version.