Irrefragable

When I was a graduate student at CSU, Chico I wrote my master’s thesis on how to implement Scheme-style continuations within the context of the .NET CLR – Implementing Continuations for a Virtual Machine Environment.

Traditional continuation implementation techniques depend on the ability to modify the area of memory holding the runtime call stack, but the CLR and similar VMs such as the JVM prevent this for security reasons. Nonetheless, it is still possible to implement continuations through a variety of means.

To explore these alternative implementations I built a model Scheme interpreter in C#. I then presented four separate methods of implementing continuations, each with their own set of tradeoffs.

The four methods are:

1. Exceptions. The exceptions that currently exist in the CLR and JVM can be viewed as one-shot escaping continuations. As such they can provide the basis for first-class continuations that also have the same behavior. Last I checked the JScheme Java Scheme interpreter used this method for its continuations.
2. Heap. Instead of using the CLR stack an interpreter can maintain its own stack in heap memory. This allows the interpreter to implement reusable first-class continuations. However it also effectively requires the interpreter to act as a separate VM running within the context of the parent instance of the CLR or JVM. SISC is an example of an interpreter that uses this method.
3. Stack reconstruction. With the right kind of artful manipulation an interpreter can use the exception mechanism in the CLR to inspect the current runtime stack in order to build a logical model of its contents and, when necessary, clear the current stack and replace it with a new stack built from one of the models. The method comes from papers by Sekiguchi, Sakamoto, and Yonezawa and Pettyjohn, Clements, Marshall, Krishnamurthi, and Felleisen. At the time I wrote my thesis there were no publicly-available interpreters I could find that used it.
4. Threads. The thread method for implementing continuations also revolves around viewing an existing runtime facility in a novel context. In this method threads are treated as stack segment containers. When a continuation is captured the current thread is suspended and a new thread is created and started to continue execution. Invoking a continuation discards the current thread and restarts the thread that was suspended when the continuation was captured. The method comes from Feeley. The architectural limitations this implies for the continuations that result are similar to the exception method.

Ultimately I argued that the stack reconstruction method was superior, since it was the only method that could provide unlimited continuations while still using the CLR runtime call stack to maintain execution context.

The PDF for the document is now available here at lorelli.info. The appendices contain the complete C# code for the four variations of the Scheme interpreter described above.