Abstract Heresies

For this complex topic I needed some help. I explained the process to an AI and had it help me write this blog post. Questions and comments are welcome.

Managed runtimes like the Java Virtual Machine (JVM) and the Common Language Runtime (CLR) provide robust, high-performance environments for software execution. A key feature of these platforms is a rigidly structured call stack, which manages function calls and returns in a strict last-in, first-out (LIFO) order. While this model is efficient and simplifies memory management, it precludes certain powerful control flow constructs, most notably first-class continuations.

A first-class continuation is the reification of the current point of execution—essentially, "the rest of the program"—as an object that can be stored, passed around, and invoked. Invoking a continuation effectively discards the current execution stack and replaces it with the captured one. This document details a methodology for implementing such a mechanism within an interpreter running on a managed runtime, circumventing the limitations of the native call stack.

This document provides a comprehensive technical overview of a method for implementing first-class continuations within an interpreter executing on a managed runtime, such as the JVM or CLR. These platforms enforce a strict, stack-based execution model that is incompatible with the control-flow manipulations required for first-class continuations. The technique described herein circumvents this limitation by creating a custom, manually-managed execution model based on a trampoline and a universal "step" contract, enabling the capture, storage, and invocation of the program's execution state.

1. The Core Execution Architecture

The foundation of this system is an interpreter where every evaluatable entity—from primitive operations to user-defined functions—adheres to a single, uniform execution contract. This approach abstracts execution away from the host's native call stack.

1.1. The `Step` Method

All computable objects implement a `Step` method. This method performs one atomic unit of computation. Its precise signature is critical to the entire mechanism:

bool Step(out object ans, ref IControl ctl, ref IEnvironment env)

1.2. The Interpreter Registers

The parameters of the Step method function as the registers of our virtual machine. Their specific modifiers are essential:

• out object ans: The Answer Register. This is an output parameter used to return the final value of a computation.
• ref IControl ctl: The Control Register. This reference parameter holds a pointer to the next computational object (`IControl`) to be executed.
• ref IEnvironment env: The Environment Register. This reference parameter holds the context necessary for the execution of the control object, such as lexical variable bindings.

The use of reference (ref) and output (out) parameters is the key that allows a callee function to directly modify the state of its caller's execution loop, which is fundamental to achieving tail calls and other advanced control transfers.

1.3. The Four Modes of Control Transfer

A Step method executes its atomic portion of work and then relinquishes control in one of four distinct ways:

1. Deeper Call: To obtain a required value, it can directly invoke the Step method of a callee function, initiating a deeper, nested computation.
2. Value Return: It can conclude its computation by setting the ans parameter to its result value and returning false. The false return value signals to the caller that a value has been produced and normal execution can proceed.
3. Tail Call: It can perform a tail call by setting the ctl parameter to the callee and the env parameter to the callee's required environment, and then returning true. The true return value signals to the caller's execution loop that it should not proceed, but instead immediately re-execute with the new ctl and env values.
4. Unwind Participation: It can participate in a stack unwind event, a special protocol for capturing the continuation, which will be discussed in detail below.

2. The Trampoline: Enabling Tail Recursion

To avoid consuming the native call stack and prevent stack overflow exceptions during deep recursion, we employ a trampoline. This is a controlling loop that manages the execution of Step methods.

// Variables to hold the current state
IControl control = ...;
IEnvironment environment = ...;
object answer;
// The trampoline loop
while (control.Step(out answer, ref control, ref environment)) {}
// Execution continues here after a normal return (false)

The operation is as follows: When a callee wishes to tail call, it mutates the control and environment variables through the ref parameters and returns true. The while loop's condition evaluates to true, its (empty) body executes, and the loop condition is evaluated again, this time invoking the Step method on the newly specified control object. When a callee returns a value, it mutates the answer variable via the out parameter and returns false. This terminates the loop, and the ultimate value of the call is available in the answer variable.

3. The Unwind Protocol: Capturing the Continuation

The continuation is captured by hijacking the established return mechanism. This is a cooperative process that propagates upward from the point of capture.

3.1. Unwind Initiation

A special function (e.g., the primitive for `call/cc`) initiates the capture. It sets the answer register to a magic constant (e.g., `UNWIND`) and mutates the environment register to hold a new `UnwinderState` object, which will accumulate the stack frames. It then returns false, causing its immediate caller's trampoline to exit.

3.2. Unwind Participation and Propagation

Crucially, every call site must check for the unwind signal immediately after its trampoline loop terminates.

while (control.Step(out answer, ref control, ref environment)) { };
if (answer == MagicValues.UNWIND) {
 // An unwind is in progress. We must participate.
 // 1. Create a Frame object containing all necessary local state
 // to resume this function from this point.
 Frame resumeFrame = new Frame(this.localState1, this.localState2, ...);
 // 2. Add the created frame to the list being accumulated.
 ((UnwinderState)environment).AddFrame(resumeFrame);
 // 3. Propagate the unwind to our own caller. Since this code is
 // inside our own Step method, we have access to our caller's
 // registers via our own parameters. We set *their* answer to UNWIND
 // and *their* environment to the UnwinderState, and return false
 // to drop *their* trampoline.
 return false; // Assuming 'ans' and 'env' are our own out/ref parameters.
}

This process creates a chain reaction. Each function up the conceptual call stack catches the unwind signal, preserves its own state in a Frame object, adds it to the list, and then triggers its own caller to unwind. This continues until the top-level dispatch loop is reached.

4. The Top-Level Dispatch Loop

The main entry point of the interpreter requires a master loop that can handle the three possible outcomes of an unwind event.

while (true) {
 answer = null;
 while (control.Step(out answer, ref control, ref environment)) { };
 if (answer == MagicValues.UNWIND) {
 UnwinderState unwindState = (UnwinderState)environment;
 // Outcome 3: The unwind was an instruction to exit the interpreter.
 if (unwindState.IsExit) {
 answer = unwindState.ExitValue;
 break;
 }
 else {
 // Outcome 1 & 2: A continuation was captured (cwcc) or is being invoked.
 // In either case, we must restore a control point.
 ControlPoint stateToRestore = unwindState.ToControlPoint();
 IControl receiver = unwindState.Receiver;
 // The RewindState holds the list of frames to be reloaded.
 environment = new RewindState(stateToRestore, receiver);
 control = ((RewindState)environment).PopFrame();
 }
 } else {
 // Normal termination of the entire program
 break;
 }
}
// Interpreter has exited.
return answer;

This top-level handler serves as the central arbiter. It runs the normal trampoline, but if an unwind reaches it, it inspects the UnwinderState to determine whether to exit the program entirely or to begin a rewind process to install a new (or previously captured) execution stack.

5. The Rewind Protocol: Restoring the Continuation

Invoking a continuation involves rebuilding the captured stack. This is managed by the `RewindState` environment and the `Step` methods of the captured `Frame` objects.

5.1. The `Frame` `Step` Method: A Dual Responsibility

The `Step` method for a `Frame` object being restored is complex. Its primary responsibility is to first restore the part of the stack that was deeper than itself. It does this by calling `PopFrame` on the `RewindState` to get the next frame and then running a local trampoline on it. The code that represents its own original pending computation is encapsulated in a separate `Continue` method.

// Simplified Step method for a Frame during rewind.
public override bool Step(out object answer, ref IControl control, ref IEnvironment environment)
{
 // First, set up and run a trampoline for the deeper part of the stack.
 object resultFromDeeperCall;
 IControl deeperFrame = ((RewindState)environment).PopFrame();
 IEnvironment rewindEnv = environment;
 while (deeperFrame.Step(out resultFromDeeperCall, ref deeperFrame, ref rewindEnv)) { };
 // Check if a NEW unwind occurred during the rewind of the deeper frame.
 if (resultFromDeeperCall == MagicValues.UNWIND) {
 // If so, we must participate again. Append our remaining frames to
 // the new UnwinderState and propagate the new unwind upwards.
 ((UnwinderState)rewindEnv).AppendContinuationFrames(this.myRemainingFrames);
 environment = rewindEnv;
 answer = MagicValues.UNWIND;
 return false;
 }
 // If the deeper call completed normally, now we can execute our own pending work.
 control = this.originalExpression;
 environment = this.originalEnvironment;
 return Continue(out answer, ref control, ref environment, resultFromDeeperCall);
}

This structure ensures that the stack is rebuilt in the correct order and that the system can gracefully handle a new continuation capture that occurs while a previous one is still being restored.

5.2. Terminating the Rewind: The `CWCCFrame`

The rewind chain must end. The innermost frame of a captured continuation corresponds to the `call/cc` primitive itself. Its `Step` method does not reload any deeper frames. Its sole purpose is to invoke the continuation receiver—the lambda function that was passed to `call/cc`—and provide it with the fully reified continuation object.

public override bool Step(out object answer, ref IControl control, ref IEnvironment environment)
{
 // The rewind is complete. Deliver the continuation to the waiting function.
 ControlPoint continuation = ((RewindState)environment).ControlPoint;
 return this.receiver.Call(out answer, ref control, ref environment, continuation);
}

With this final call, the stack is fully restored, the RewindState is discarded, and normal execution resumes within the receiver function, which now holds a reference to "the rest of the program" as a callable object.

Back when I was taking a Software Engineering course we used a language called CLU. CLU was an early object-oriented language. A feature of CLU was that if you wrote your code correctly, the compiler could enforce completely opaque abstract data types. A good chunk of your grade depended on whether you were able to follow insructions and write your data types so that they were opaque.

CLU did not have polymorphism, but it did have discriminated type unions. You could fake simple polymorphism by using a discriminated type union as the representation of an opaque type. Methods on the opaque type would have to dispatch on the union subtype. Now to implement this correctly, you should write your methods to check the union subtype even if you “know” what it is. The course instructors looked specifically for this and would deduct from your grade if you didn't check.

One subproject in the course was a simple symbolic math system. You could put expressions in at the REPL, substitute values, and differentiate them. The core of the implementation was term data type that represented a node in an expression tree. A term was a type union of numeric constant, a symbolic variable, a unary expression, or a binary expression. Unary and binary expressions recursively contained subterms.

The term data type would therefore need four predicates to determine what kind of term it was. It would also need methods to extract the constant value if it was a constant, extract the variable name if it was symbolic, and extract the operator and subterms if it was a unary or binary expression. The way to use the data type was obvious: you'd have a four-way branch on the kind of term where each branch would immediately call the appropriate selectors. But if you wrote your selectors as you were supposed to, the first thing they should do is check that they are called on the appropriate union subtype. This is a redundant check because you just checked this in the four-way branch. So your code was constantly double checking the data. Furthermore, it has to handle the case should the check fail, even though the check obviously can never fail.

I realized that what I needed was a discrimination function that had four continuations, one for each subtype. The discrimination function would check the subtype and then call the appropriate continuation with the subcomponents of the term. This would eliminate the double checking. The code was still type safe because the discrimination function would only invoke the continuation for the correct subtype.

One way to introduce alternative continuations into the control flow is through exceptions. The discrimination function could raise one of four exceptions, each with the appropriate subcomponents as arguments. The caller would not expect a return value, but would have four catch handlers, one for each subtype. The caller would use the try/except syntax, but it would act like a switch statement.

The TA balked at this use of exceptions, but I appealed to the professor who saw what I was trying to do and approved.

There is some debate about whether exceptions should be used for control flow. Many people think that exceptions should only be used for “exceptional” situations and that it is poor form to use them for normal control flow. I think they are taking too narrow a view. Exceptions are a way to introduce alternative paths of control flow. One can use them to, for instance, handle an exceptional situation by jumping to a handler, but that's not the only way to use them.

Of course you should think hard about whether exceptions are the right way to introduce alternative control flow in your use case. Exception syntax is usually kind of klunky and you may need to rewrite the code to insert the exception handling at the right point. Readers of your code are likely to be surprised or baffled by the use of exceptions for control flow. There is often a significant performance penalty if an exception is thrown. But sometimes it is just the trick.