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:
- Deeper Call: To obtain a required value, it can directly invoke the
Step method of a callee function, initiating a deeper, nested computation.
- 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.
- 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.
- 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.
