This paper is an addendum to Pettyjohn, et al. `Continuations from Generalized Stack Inspection', Proceedings of the tenth ACM SIGPLAN international conference on Functional programming. In this article, I provide more detail about the transformation than was possible in the SIGPLAN paper. Please refer to the SIGPLAN paper for a more complete set of references.
This paper describes a technique for implementing first-class continuations in languages that do not support stack inspection and manipulation. The technique involves modifying procedures (or methods) such that they are able to co-operatively participate in the creation and use of first-class continuations. The transform differs from continuation-passing-style in that the call/return stack continues to be the primary mechanism for representing continuations; a heap representation of the continuation is only constructed when necessary. This may result in better performance than CPS-conversion for those programs that make only occasional use of first-class continuations.
This technique was first described by F�nfrocken[F�nfrocken98] as a mechanism for saving and restoring the transient (stack-based) state of a computation. Sekiguchi, Sakamoto, and Yonezawa[Sekiguchi01] generalize this to a mechanism for implementing continuation operators. Tao[Tao01] uses this code transformation in the context of mobile and distributed systems.
This paper presents a refinement of Sekiguchi, et al.[Sekiguchi01]. It is assumed that the reader is familiar with other techniques for implementing first-class continuations[Baker94] [Clinger99]. The goal of this paper is to familiarize Scheme implementors with this technique.
Many popular languages provide no means for a procedure or method to access its continuation. A procedure always has access to its own dynamic state. This suggests that a procedure or method could be augmented to save its own state as part of the process of capturing a continuation. A reasonably simple transformation may be performed on the procedure body that, when combined with the appropriate external support code, allows continuations to be used in a first-class manner.
The steps used to transform the code are shown here as source-code transformations in the C# language[ECMA334], but analagous transforms could be done in Java[Java] or at a bytecode level. These transforms are similar to ones that many compilers already perform. It may be possible to adapt an existing compiler to use this technique with a fairly small amount of effort.
This transformation preserves the calling signature of a
procedure, but it augments the behavior of the procedure when a
continuation is to be captured. Interaction with code that has
not been transformed will still be somewhat problematic. On the
other hand, the transformation is applicable to intermediate level
code such as a Java .class file. If it is necessary
for transformed and untransformed code to interoperate, a
technique such as continuation barriers may be used.
Capturing and re-instating a continuation will cause variables to be unbound and rebound perhaps multiple times. Variable bindings that are part of a lexical closure must not be unshared when this occurs. Assignment conversion[Kranz86] may be used to ensure the correct behavior of the transformed code. This is not an issue in languages that do not provide lexical closures. Management of shared variable bindings is an orthogonal issue so the examples given below will omit this step.
Syntax for compound expressions is one of the defining features of a higher-level computer language. Compound expressions abstract away the details of control flow and temporary values, in other words, the continuation. To save the continuation we will require access to those temporary values and detailed knowledge of the control flow within a procedure. Converting the code into A-normal form[Flanagan93] gives names to the temporary values and linearizes the control flow by replacing compound expressions with an equivalent sequence of primitive expressions and variable bindings.
A complete definition of an A-normal form of C# or Java is beyond the scope of this paper, but once converted to A-normal form the code will exhibit the key property that all procedure calls appear either as the right-hand side of a binding form (in C# or Java, this is syntactically a statement that assigns to a fresh variable) or as the expression element in a return statement. In other words, the result of any procedure call is either immediately bound to variable or immediately returned.
Introducing explicit variables for temporaries is necessary in order to save the values, and linearizing nested expressions makes the control flow explicit, but there is another important effect of converting to A-normal form that is not so obvious. Languages like Java or C# make a strong distinction between statements — program constructs that are sequentially executed and return no value — and expressions — hierarchical program constructs that compute a value. This distinction is even present at the bytecode level: evaluation of expressions cause a change in the depth of the stack whereas evaluation of statements do not. Flow control constructs such as loops and exceptions are usually statements, but procedure and method calls are expressions.
Control must be returned to that procedure in order for it to assist in saving the continuation. Unfortunately, returning control to the procedure deallocates a portion of the very continuation we are attempting to save. We can, however, synthesize a procedure that would have the same effect as the now absent continuation if we can reason about what that effect would have been. Once the code is converted to A-normal form, the continuation of a procedure or method call will always be a binding (or assignment) to a fresh variable. We arrange for an equivalent binding to take place as the first action performed by the synthesized procedure.
// Unconverted code
int fib (int x)
{
if (x < 2)
return x;
else
return fib (x - 2) + fib (x - 1);
}
// A-normal conversion
int fib_an (int x)
{
bool temp0 = x < 2;
if (temp0)
return x;
else {
int temp1 = x - 2;
int temp2 = fib_an (temp1);
int temp3 = x - 1;
int temp4 = fib_an (temp3);
return temp2 + temp4;
}
}
It is important to convert any implicit method calls that may occur as a result of type casting.
// Original expression
long foo = (long) (1.0 + fib (6));
// After A-normal conversion
int temp0 = fib (6);
double temp1 = (double) temp0;
double temp2 = 1.0 + temp1;
long foo = (long) temp2;
Temporary variables must not be introduced for those procedure or method calls that appear as the immediate expression part of a return statement.
// Original form
return fib (fib (x));
// Incorrect A-normal conversion
int temp1 = fib (x);
int temp2 = fib (temp1);
return temp2;
// Correct A-normal conversion
int temp1 = fib (x);
return fib (temp1);
To keep the examples below concise, subexpressions that can be evaluated without a method call will be considered primitive and will not be converted.
// A-normal conversion
int fib_an (int x)
{
if (x < 2)
return x;
else {
int temp0 = fib_an (x - 2);
int temp1 = fib_an (x - 1);
return temp0 + temp1;
}
}
// Takeuchi function with A-normal conversion
int tak_an (int x, int y, int z)
{
if (! (y < x))
return z;
int temp0 = tak_an (x - 1, y, z);
int temp1 = tak_an (y - 1, z, x);
int temp2 = tak_an (z - 1, x, y);
return tak_an (temp0, temp1, temp2);
}
It will be necessary to note what variables are live at each continuation. We are only interested in those variables that are live after a procedure or method call returns. Those variables that are last used as arguments to the procedure or method call are no longer live.
When reinstated, a continuation proceeds from the point at which it was captured. Methods and procedures have a single entry point at the beginning. We create a number of procedures each of which has the effect of continuing in the middle of the original procedure. Because we converted the code to A-normal form, the fragments will always begin with the statement following the assignment associated with a method call. The arguments to each fragment will be the free variables needed by that fragment.
Each procedure fragment will make a tail-recursive call to the next fragment. Fragmenting the code may result in a performance decrease from the introduction of so many interprocedural boundaries. Inlining the fragments will reduce the number of interprocedural boundaries at the cost of increasing the code size. One possible compilation strategy is to collect the fragments in a single procedure and use a dispatch table to select the correct point.
Fragmentation also replaces iteration constructs with procedure calls. This will be of concern if there is no mechanism for tail-recursion, but this will be addressed below.
// After A-normal conversion and fragmentation
int fib_an (int x)
{
if (x < 2)
return x;
else {
int temp0 = fib_an (x - 2);
return fib_an0 (temp0, x);
}
}
int fib_an0 (int temp0, int x)
{
int temp1 = fib_an (x - 1);
return fib_an1 (temp1, temp0);
}
int fib_an1 (int temp1, int temp0)
{
return temp0 + temp1;
}
// Takeuchi function after A-normal conversion
// and fragmentation.
int tak_an (int x, int y, int z)
{
if (! (y < x))
return z;
int temp0 = tak_an (x - 1, y, z);
return tak_an0 (temp0, x, y, z);
}
int tak_an0 (int temp0, int x, int y, int z)
{
int temp1 = tak_an (y - 1, z, x);
return tak_an1 (temp1, temp0, x, y, z);
}
int tak_an1 (int temp1, int temp0, int x, int y, int z)
{
int temp2 = tak_an (z - 1, x, y);
return tak_an2 (temp2, temp1, temp0);
}
int tak_an2 (int temp2, int temp1, int temp0)
{
return tak_an (temp0, temp1, temp2);
}
A continuation will be composed of a series of frames. Each frame is closed over the values of the live variables at the point where the continuation was captured. Each frame also has a method that accepts a single value (the argument to the continuation) and invokes the appropriate procedure fragment.
These classes would be automatically generated if the underlying language were to support anonymous methods. For example, anonymous delegates in C# could have been used. The C# compiler implements anonymous delegates through a mechanism of closure conversion where the compiler generates a class to close over the free variables in the delegate.
abstract class ContinuationFrame
{
abstract object Invoke (object continue_value);
// Other members omitted ....
}
class fib_frame0 : ContinuationFrame
{
// Live variables for fib_an0 minus the one assigned
// by the continuation.
int x;
// Constructor
fib_frame0 (int _x) {this.x = _x;}
// Restart method
override object Invoke (object continue_value)
{
return fib_an0 ((int) continue_value, this.x);
}
}
class fib_frame1 : ContinuationFrame
{
// Live variables for fib_an1 minus the one assigned
// by the continuation.
int temp0;
// Constructor
fib_frame1 (int _temp0) {this.temp0 = _temp0;}
// Restart method
override object Invoke (object continue_value)
{
return fib_an1 ((int) continue_value, this.temp0);
}
}
class tak_frame0 : ContinuationFrame
{
int x;
int y;
int z;
tak_frame0 (int _x, int _y, int _z)
{
this.x = _x;
this.y = _y;
this.z = _z;
}
override
object Invoke (object continue_value)
{
return tak_an0 ((int)continue_value, x, y, z);
}
}
class tak_frame1 : ContinuationFrame
{
int temp0;
int x;
int y;
int z;
tak_frame1 (int _temp0, int _x, int _y, int _z)
{
this.temp0 = _temp0;
this.x = _x;
this.y = _y;
this.z = _z;
}
override
object Invoke (object continue_value)
{
return tak_an1 ((int)continue_value, temp0, x, y, z);
}
}
class tak_frame2 : ContinuationFrame
{
int temp1;
int temp0;
tak_frame2 (int _temp1, int _temp0)
{
this.temp1 = _temp1;
this.temp0 = _temp0;
}
override
object Invoke (object continue_value)
{
return tak_an2 ((int)continue_value, temp1, temp0);
}
}
The fragmented code is now annotated so that it can save its state in the appropriate continuation frame. When control is returned to the procedure, it must either perform its normal computation or construct its part of the continuation being saved. Wrapping each procedure call with an exception handler is probably the most perspicuous way of annotating the code. Another way would be to create a distinguished return value or to have a special global flag that indicates that a continuation is to be captured. Exception handling appears to perform best when capturing continuations is a rare occurrance compared with normal procedure calls.
Whatever method is chosen, when the procedure is required to save its state it allocates the appropriate frame structure and adds it to the state being accumulated. The procedure then returns control to its caller (by returning the special value or rethrowing the exception) indicating that a continuation capture is in progress rather than a normal return.
The following code illustrates how each call is annotated by using exceptions. Note that the calls in tail position (those that appear as the expression in a return statement) are not annotated.
// After A-normal conversion, fragmentation,
// and annotation.
int fib_an (int x)
{
if (x < 2)
return x;
else {
int temp0;
try {
temp0 = fib_an (x - 2);
}
catch (SaveContinuationException sce) {
sce.Extend (new fib_frame0 (x));
throw;
}
return fib_an0 (temp0, x);
}
}
int fib_an0 (int temp0, int x)
{
int temp1;
try {
temp1 = fib_an (x - 1);
}
catch (SaveContinuationException sce) {
sce.Extend (new fib_frame1 (temp0));
throw;
}
return fib_an1 (temp1, temp0);
}
int fib_an1 (int temp1, int temp0)
{
return temp0 + temp1;
}
// Takeuchi function after A-normal conversion
// and fragmentation.
int tak_an (int x, int y, int z)
{
if (! (y < x))
return z;
int temp0;
try {
temp0 = tak_an (x - 1, y, z);
}
catch (SaveContinuationException sce) {
sce.Extend (new tak_frame0 (x, y, z));
throw;
}
return tak_an0 (temp0, x, y, z);
}
int tak_an0 (int temp0, int x, int y, int z)
{
int temp1;
try {
temp1 = tak_an (y - 1, z, x);
}
catch (SaveContinuationException sce) {
sce.Extend (new tak_frame1 (temp0, x, y, z));
throw;
}
return tak_an1 (temp1, temp0, x, y, z);
}
int tak_an1 (int temp1, int temp0, int x, int y, int z)
{
int temp2;
try {
temp2 = tak_an (z - 1, x, y);
}
catch (SaveContinuationException sce) {
sce.Extend (new tak_frame2 (temp1, temp0));
throw;
}
return tak_an2 (temp2, temp1, temp0);
}
int tak_an2 (int temp2, int temp1, int temp0)
{
// No try/catch annotation needed here
return tak_an (temp0, temp1, temp2);
}
Once annotated, the procedures and methods will have the ability to save their own part of the continuation. The code must be run within an additional framework that can collect the pieces, construct an object that models the continuation, and turn a continuation model back into an actual continuation.
The set of frames that are collected as the
SaveContinuationException is propagated can be considered a model
of a partial continuation. A real and complete continuation must
be constructed from this model in order for it to be used. We
start by capturing a continuation that we will use as the root
continuation. When we need to restore a continuation we will
return to the root continuation before beginning the restoration
process. The root continuation acts as the join point
of all other continuations. Since all code using first-class
continuations must run in the dynamic context of the root
continuation, establishing this continuation should be among
the very first actions a program performs.
// Defines the Thunk type as a method of zero arguments.
public delegate object Thunk();
public class
Continuation
{
// Private inner class
class WithinInitialContinuationException : Exception
{
public
Thunk thunk;
public
WithinInitialContinuationException (Thunk thunk)
{
this.thunk = thunk;
}
}
public static
object EstablishInitialContinuation (Thunk thunk)
{
while (true) {
try {
return InitialContinuationAux (thunk);
}
catch (WithinInitialContinuationException wic) {
thunk = wic.thunk;
}
}
}
// Definition of class Continuation to be continued...
The WithinInitialContinuation method accepts a
thunk and invokes it in a context where the initial continuation
will receive the value. It accomplishes this by a throw to a
handler in EstablishInitialContinuation.
EstablishInitialContinuation will just keep invoking
thunks until one of them actually returns a value.
// Definition of class Continuation continues...
static
object InitialContinuationAux (Thunk thunk)
{
try {
return thunk();
}
catch (SaveContinuationException sce) {
Continuation k = sce.toContinuation();
throw new WithinInitialContinuationException (
delegate
{
return k.Reload (k);
});
}
}
// Definition of class Continuation to be continued...
The definition of InitialContinuationAux looks
intimidating at first, but it's function is fairly
straightforward. It's purpose is to catch any
SaveContinuationException that is thrown and build
the final continuation object. The continuation object needs to
be restored, but the restored continuation should be rooted at the
initial continuation. We therefore wrap the restore code in a
thunk (the anonymous delegate) and throw the
WithinInitialContinuationException.
The reason that the continuation also appears as an argument to
the Reload method will be explained shortly.
Frames are saved in order from most recent to least recent, following the last-in/first-out discipline enforced by the stack. This is a problem because captured frames will be duplicated if they are part of more than one continuation. This could lead to a change in the order of space growth of the process.
When saving a continuation, we should save the frames in the reverse order. When restoring a continuation, we should arrange for subsequent continuation capture to use the saved frames when possible. We do this by placing in each saved frame a linked list of the frames that are less recent than it. The second time a frame is saved, it will append the linked list rather than construct a new copy of the frame.
The entire list of frames is not known, however, until they
have all been collected. A Continuation will contain
the list of frames. When the continuation is constructed, the
newly captured frames, which have been collected in the reverse
order, will be appended to the list of any previously captured
frames. Each new frame will be modified to hold a pointer to the
list of prior frames.
// Definition of class Continuation continues...
FrameList frames;
public
Continuation (FrameList new_frames, FrameList old_frames)
{
// The new frames don't know what the continuation is below them.
// We take them one by one and push them onto the old_frames
// while setting their continuation to the list of frames below.
frames = old_frames;
while (new_frames != null) {
ContinuationFrame new_frame = new_frames.first;
new_frames = new_frames.rest;
if (new_frame.continuation != null)
throw new Exception ("Continuation not empty?");
new_frame.continuation = frames;
frames = new FrameList (new_frame, frames);
}
}
// Definition of class Continuation to be continued...
Restoring a continuation involves recursively restoring each frame.
The code in Continuation has little to do:
// Definition of class Continuation continues...
object Reload (object restart_value)
{
// Reverse the frames in order to reload them.
FrameList rev = FrameList.reverse (frames);
return rev.first.Reload (rev.rest, restart_value);
}
// Definition of class Continuation to be continued...
Once reloaded, the continuation expects to have a value
returned to it. The restart_value will be provided
to the final frame after it is loaded. (This value will be
the continuation itself if the reload is caused by a continuation
capture. The user visible method
CallWithCurrentContinuation is the only method that
initiates a continuation save, so the newly
created continuation is returned as the result of saving that
continuation.)
CallWithCurrentContinuation simply starts a the
entire process going. The continuation frame it creates for
itself is unusual in that it calls the receiver function that the
user passes in.
// Definition of class Continuation continues...
static
void BeginUnwind()
{
throw new SaveContinuationException();
}
class CWCC_frame0 : ContinuationFrame
{
ContinuationReceiver receiver;
public
CWCC_frame0 (ContinuationReceiver receiver)
{
this.receiver = receiver;
}
public override
object Invoke (object return_value)
{
return receiver ((Continuation) return_value);
}
}
public static
object CWCC (ContinuationReceiver receiver)
{
try {
BeginUnwind();
}
catch (SaveContinuationException sce) {
sce.Extend (new CWCC_frame0 (receiver));
throw;
}
// Should never get here.
return null;
}
} // End of definition of Continuation class.
The FrameList is a simple linked list. The
SaveContinuationException contains two frame lists
and provides methods for manipulating them. Rather than
recursively building up a nested exception structure, we mutate
the SaveContinuationException as we save the
continuation. This may avoid a large amount of recomputation in
the underlying system (it makes a measurable difference on some
CLI platforms).
public
class SaveContinuationException : Exception
{
public
FrameList new_frames;
public
FrameList old_frames;
// Push a single new frame.
public
void Extend (ContinuationFrame extension)
{
this.new_frames = new FrameList (extension, this.new_frames);
}
// Tack on a pile of old frames.
public
void Append (FrameList old_frames)
{
this.old_frames = old_frames;
}
public
Continuation toContinuation()
{
return new Continuation (new_frames, old_frames);
}
}
As mentioned earlier, continuation frames are loaded recursively. Because the code has been transformed in the above manner, we know that each frame is awaiting the return value of a procedure or method call and will assign or bind that value to a variable. Upon reloading a frame we recursively reload the more recent frames and again wait for them to return a value.
But suppose another continuation is captured before the value
arrives? Since the more recent frames have pointers to the less
recent ones, and since we can rely on them to append the shared
frame list to the SaveContinuationException, we do
not wrap the recursive call to Reload with an
exception handler. Once we begin to execute code within the
procedure fragment associated with this continuation, this frame
becomes the point at which the shared list of frames ends. Thus
the call to the procedure fragment should be protected by an
exception handler that appends the old frames to the
SaveContinuationException.
public abstract
class ContinuationFrame
{
public
FrameList continuation;
public
object Reload (FrameList frames_above, object restart_value)
{
// The continutation for the call to Reload is the expression
// continuation of this assignment followed by the subsequent
// try/catch block.
// This call does *not* have to be protected by a try/catch
// because we have not made any progress at this point. When we Invoke
// the continuation function, we need to establish a try/catch in order
// to tie this continuation in to the new frames about to be
// created.
object continue_value = (frames_above == null)
? restart_value
: frames_above.first.Reload (frames_above.rest, restart_value);
try {
return this.Invoke (continue_value);
}
catch (SaveContinuationException sce) {
sce.Append (continuation);
throw;
}
}
public abstract
object Invoke (object return_value);
}
The complete code is attached as an appendix. Note that anonymous delegates are not yet standard C#, but named delegates may be used instead. Java programmers will need to create a Thunk interface class.
In the above code we are very careful to avoid wrapping procedures calls in tail position. If we erroneously wrap the tail call within the Takeuchi function, it becomes obvious why we should not. We again start with the A-normal transformation, but we transform the call within the return statement as well as the others:
// Takeuchi function with incorrect A-normal conversion
int tak_an (int x, int y, int z)
{
if (! (y < x))
return z;
int temp0 = tak_an (x - 1, y, z);
int temp1 = tak_an (y - 1, z, x);
int temp2 = tak_an (z - 1, x, y);
// Erroneous introduction of unneeded temporary
int temp3 = tak_an (temp0, temp1, temp2);
return temp3;
}
The fragmented program is mostly the same, but we have the additional fragment shown here.
int tak_an2 (int temp2, int temp1, int temp0)
{
int temp3 = tak_an (temp0, temp1, temp2);
return tak_an3 (temp3);
}
int tak_an3 (int temp3)
{
return temp3;
}
The frame class associated with tak_an3 is this:
class tak_frame3 : ContinuationFrame
{
tak_frame3 ()
{}
override
object Invoke (object continue_value)
{
return tak_an3 ((int) continue_value);
}
}
And the final annotated code for tak_an2 is:
int tak_an2 (int temp2, int temp1, int temp0)
{
int temp3;
try {
temp3 = tak_an (temp0, temp1, temp2);
}
catch (SaveContinuationException sce) {
sce.Extend (new tak_frame3());
throw;
}
return tak_an3 (temp3);
}
Notice that the continuation frame tak_frame3 has no instance
variables. There are no free variables beyond the continuation
variable in tak_an3. tak_an3 is obviously just the identity
function.
But more importantly, the Invoke method within the
continuation frame tak_frame3 is also the identity
function. While this makes no difference in the computed value,
the code that creates continuations will carefully link in these
excess frames and the code that restores continuations will splice
identity frames back into the stack. This wastes both time and space.
Removing the identity continuations (and their associated frames) when possible is simply tail recursion. Continuations saved using this method will elide out the frames in tail position. This method is asymptotically safe-for-space. By occasionally capturing continuations, we can provide tail-recursive behavior even if the underlying machine does not. The replacement of iteration constructs with tail-recursive calls during the fragmentation phase is much less of a problem.
To make this a feasible mechanism for implementing tail recursion, enough frames need to be recovered per unload/reload cycle to justify the cost of unloading. Exception handling is typically quite a bit slower than normal function call/return, so it would be necessary to amortize the cost over hundreds or thousands of method calls. If stack space is sufficiently large, there may be no need of other tail recursion techniques.
This method provides a mechanism by which first-class continuations may be used without incurring much overhead in the more common situation where they are not used very much. Code that has been converted as above does not typically exhibit a large decrease in performance.
ANF conversion makes little impact on the performance because the compiler must perform a similar transformation anyway. The virtual machine model may keep explicit local variables segregated from compiler temporaries, but the actual implementation is likely to store them both in the stack. (And were there a significant difference, an optimizing compiler could change locals to temporaries or vice versa.)
Procedure fragmentation is likely to introduce overhead, but as noted above, the fragments are only used when continuations are reinvoked. Inlining the fragments in the main body of the code will essentially eliminate the performance overhead at the cost of a fixed factor of space overhead. (Inlining every fragment would be proportional to the square of the number of fragments, but inlining the main path would only be double.)
Closure conversion will introduce a number of extra classes and methods, but these methods will not be frequently used. The runtime overhead should be small, but there will be an increase in code size proportional to the number of code fragments.
Code annotation introduces a number of try/catch blocks. This, too, will increase code size proportional to the number of code fragments. Inlined fragments will duplicate the try/catch blocks and have additional size overhead. The runtime overhead of a try/catch block depends greatly on whether an exception is thrown. The overhead when no exception occurs is quite small, and may be zero if the virtual machine optimizes this case. On the other hand, throwing an exception may be very expensive — perhaps several decimal orders of magnitude more than a normal return. Code that infrequently captures first-class continuations should therefore be comparable to un-converted code in performance, but it may be larger by some amount. Code that frequently captures first-class continuations may perform quite poorly if the cost of exception handling cannot be amortized over a sufficient number of normal call/return cycles.
The advantage of this technique over continuation-passing-style conversion is that the continuations of the underlying language still serve as the implementation for Scheme continuations in the large majority of cases.
This technique shares a drawback with continuation-passing-style conversion in that all code that participates in continuation capture must be converted. A pending method that has not been converted will not save its frame when necessary and the resulting continuation model will be incomplete (and useless).
Baker's “Cheney on the MTA” technique, used by Winkelmann's Chicken compiler[Winklemann] and in version 1.0 of the REBOL language, is often suggested as a possible means to implement first-class continuations in Java or on the CLR. Baker's technique relies on the ability to allocate objects on the stack. By never returning from a method call, the technique guarantees that a stack-allocated object has indefinite extent.
Neither the JVM and the CLR support the necessary stack-allocation operations. While the CLR offers the ability to create references to stack-allocated objects, it prohibits stack allocated objects from containing such references: a single continuation frame could be modeled, but a chain of them cannot. It would, of course, be possible to allocate these objects in the heap, but the main benefit of Baker's technique — bypassing the heap for short-lived continuations — would be lost.
While it seems that the above method correctly implements first-class continuations, a convincing formal proof using operational semantics has not yet been produced. The method appears to be asymptotically safe-for-space, but a formal description of the space characteristics for all cases would be very useful. It's obvious that long chains of tail calls will be collapsed, but not obvious that individual calls repeatedly taken from the same continuation — a tail-recursive loop implemented via continuation operations — exhibits provably safe-for-space behavior.
The implementation described above essentially “copies the stack”. Clinger, et al., report that hybrid stack/heap implementations that involve lazy copying or using the stack as a cache perform much better than simple stack copying. Adapting the above technique to a hybrid stack/heap model would be useful.
This technique requires no support from the underlying virtual machine. Some other techniques for first-class continuations require substantial modification of the underlying virtual machine. If there are some trivial or minor changes to the virtual machine that will accelerate or enhance the performance of this technique, it is more likely that those would be adopted by the larger community that makes little or no use of first-class continuations.
Victor Luchangco asked if I could prove that Java or CLR continuations were insufficient to model Scheme continuations. In thinking about the proof, I discovered this counterexample.
I also thank the PLT Team at Northeastern University, in particular, Matthias Felleisen, William Clinger, John Clements, Ryan Culpepper, David Herman, Shriram Krishnamurthi, Felix Klock, and Greg Pettyjohn.
// -*- Mode: Csharp; coding: iso-8859-1 -*-
// This code has some additional features not shown above. In
// particular, the tak function is (needlessly) made to periodically
// capture a continuation. This introduces a new code fragment for
// tak and changes the numbering.
namespace StackHack
{
using System;
using System.Diagnostics;
public delegate object Thunk();
public delegate object ContinuationReceiver (Continuation arg);
public abstract
class ContinuationFrame
{
public
FrameList continuation;
/// <summary>
/// The magic is here. Each frame invokes the loader for the frame
/// above it thus reconstructing the stack. The topmost frame gets
/// the restart value passed into its continuation.
/// </summary>
public
object Reload (FrameList frames_above, object restart_value)
{
// The continutation for the call to Reload is the expression
// continuation of this assignment followed by the subsequent
// try/catch block.
// This call does *not* have to be protected by a try/catch
// because we have not made any progress at this point. When we Invoke
// the continuation function, we need to establish a try/catch in order
// to tie this continuation in to the new frames about to be
// created.
object continue_value = (frames_above == null)
? restart_value
: frames_above.first.Reload (frames_above.rest, restart_value);
try {
return this.Invoke (continue_value);
}
catch (SaveContinuationException sce) {
sce.Append (continuation);
throw;
}
}
public abstract
object Invoke (object return_value);
}
public
class FrameList
{
public ContinuationFrame first;
public FrameList rest;
public
FrameList (ContinuationFrame _first, FrameList _rest)
{
first = _first;
rest = _rest;
}
public static
FrameList reverse (FrameList original)
{
FrameList result = null;
while (original != null) {
result = new FrameList (original.first, result);
original = original.rest;
}
return result;
}
}
public
class SaveContinuationException : Exception
{
/// <summary>
/// A list of frames that have not yet been fully assembled
/// into the continuation. Each frame has saved its own state.
/// </summary>
public
FrameList new_frames;
/// <summary>
/// A list of frames that already have been assembled into the continuation.
/// When unloading the stack, we need not unload these frames.
/// </summary>
public
FrameList old_frames;
/// <summary>
/// Push a newly created heap frame onto the list of frames that need
/// to be assembled into the continuation. This should be done in the
/// exception handler that protects the initial subroutine call.
/// </summary>
public
void Extend (ContinuationFrame extension)
{
this.new_frames = new FrameList (extension, this.new_frames);
}
/// <summary>
/// Append the tail of the current continuation to the exception
/// object so that the handler can assemble the new frames onto it.
/// </summary>
public
void Append (FrameList old_frames)
{
this.old_frames = old_frames;
}
public
Continuation toContinuation()
{
return new Continuation (new_frames, old_frames);
}
}
public
class Continuation
{
/// <summary>
/// Holds the list of frames in order from most recent to least recent.
/// This is the direction we want for sharing, but the reverse direction
/// for loading.
/// </summary>
FrameList frames;
public
Continuation (FrameList new_frames, FrameList old_frames)
{
// The new frames don't know what the continuation is below them.
// We take them one by one and push them onto the old_frames
// while setting their continuation to the list of frames below.
frames = old_frames;
while (new_frames != null) {
ContinuationFrame new_frame = new_frames.first;
new_frames = new_frames.rest;
if (new_frame.continuation != null)
throw new Exception ("Continuation not empty?");
new_frame.continuation = frames;
frames = new FrameList (new_frame, frames);
}
}
object Reload (object restart_value)
{
// Reverse the frames in order to reload them.
FrameList rev = FrameList.reverse (frames);
return rev.first.Reload (rev.rest, restart_value);
}
static
void BeginUnwind()
{
throw new SaveContinuationException();
}
class CWCC_frame0 : ContinuationFrame
{
ContinuationReceiver receiver;
public
CWCC_frame0 (ContinuationReceiver receiver)
{
this.receiver = receiver;
}
public override
object Invoke (object return_value)
{
return receiver ((Continuation) return_value);
}
}
public static
object CWCC (ContinuationReceiver receiver)
{
try {
BeginUnwind();
}
catch (SaveContinuationException sce) {
sce.Extend (new CWCC_frame0 (receiver));
throw;
}
// Should never get here.
return null;
}
class WithinInitialContinuationException : Exception
{
public
Thunk thunk;
public
WithinInitialContinuationException (Thunk thunk)
{
this.thunk = thunk;
}
}
public static
object EstablishInitialContinuation (Thunk thunk)
{
while (true) {
try {
return InitialContinuationAux (thunk);
}
catch (WithinInitialContinuationException wic) {
thunk = wic.thunk;
}
}
}
static
object InitialContinuationAux (Thunk thunk)
{
try {
return thunk();
}
catch (SaveContinuationException sce) {
Continuation k = sce.toContinuation();
throw new WithinInitialContinuationException (
delegate
{
return k.Reload (k);
});
}
}
}
public
class tak
{
public static
int callcount = 0;
public static
int breakat = -1;
public static
int breakevery = -1;
public static
object tak_pause ()
{
Console.WriteLine ("tak_pause at {0}", callcount);
breakat = callcount + breakevery;
Console.WriteLine ("next_pause at {0}", breakat);
Console.WriteLine (new StackTrace());
return
Continuation.CWCC (delegate (Continuation cont) {
Console.WriteLine ("tak_pause cont is {0}", cont);
return null;
});
}
class tak_frame0 : ContinuationFrame
{
int x;
int y;
int z;
public
tak_frame0 (int x, int y, int z)
{
this.x = x;
this.y = y;
this.z = z;
}
public override
object Invoke (object return_value)
{
return tak_an0 (x, y, z);
}
}
public static
int tak_an (int x, int y, int z)
{
callcount += 1;
if (callcount == breakat) {
try {
tak_pause();
}
catch (SaveContinuationException sce) {
sce.Extend (new tak_frame0 (x, y, z));
throw;
}
}
return tak_an0 (x, y, z);
}
class tak_frame1 : ContinuationFrame
{
int x;
int y;
int z;
public
tak_frame1 (int x, int y, int z)
{
this.x = x;
this.y = y;
this.z = z;
}
public override
object Invoke (object return_value)
{
return tak_an1 ((int)return_value, x, y, z);
}
}
public static
int tak_an0 (int x, int y, int z)
{
if (! (y < x))
return z;
int temp0;
try {
temp0 = tak_an (x - 1, y, z);
}
catch (SaveContinuationException sce) {
sce.Extend (new tak_frame1 (x, y, z));
throw;
}
return tak_an1 (temp0, x, y, z);
}
public static
int tak_an1 (int temp0, int x, int y, int z)
{
int temp1;
try {
temp1 = tak_an (y - 1, z, x);
}
catch (SaveContinuationException sce) {
sce.Extend (new tak_frame2 (temp0, x, y, z));
throw;
}
return tak_an2 (temp1, temp0, x, y, z);
}
class tak_frame2 : ContinuationFrame
{
int temp0;
int x;
int y;
int z;
public
tak_frame2 (int temp0, int x, int y, int z)
{
this.temp0 = temp0;
this.x = x;
this.y = y;
this.z = z;
}
public override
object Invoke (object return_value)
{
return tak_an2 ((int)return_value, temp0, x, y, z);
}
}
public static
int tak_an2 (int temp1, int temp0, int x, int y, int z)
{
int temp2;
try {
temp2 = tak_an (z - 1, x, y);
}
catch (SaveContinuationException sce) {
sce.Extend (new tak_frame3 (temp1, temp0));
throw;
}
return tak_an3 (temp2, temp1, temp0);
}
class tak_frame3 : ContinuationFrame
{
int temp1;
int temp0;
public
tak_frame3 (int temp1, int temp0)
{
this.temp1 = temp1;
this.temp0 = temp0;
}
public override
object Invoke (object return_value)
{
return tak_an3 ((int)return_value, temp1, temp0);
}
}
public static
int tak_an3 (int temp2, int temp1, int temp0)
{
// NO TRY/CATCH NEEDED HERE
return tak_an (temp0, temp1, temp2);
}
public static
int takgo (int x, int y, int z)
{
return
(int) Continuation.EstablishInitialContinuation (delegate {
return tak_an (18, 12, 6);
});
}
public static
void taktest ()
{
Console.WriteLine ("tak ({0}, {1}, {2}) = {3}", 18, 12, 6, takgo (18, 12, 6));
Console.WriteLine ("callcount = {0}", callcount);
Stopwatch ticker = Stopwatch.StartNew();
for (int i = 0; i < 1000; i++)
takgo (18, 12, 6);
Console.WriteLine ("1000 iterations took {0}", ticker.ElapsedMilliseconds);
callcount = 0;
breakevery = 1000;
breakat = breakevery;
int answer = takgo (18, 12, 6);
Console.WriteLine ("tak ({0}, {1}, {2}) = {3}", 18, 12, 6, answer);
}
}
public
class main
{
public static
void Main ()
{
Console.WriteLine (".NET framework {0}", System.Environment.Version);
Console.WriteLine ("Stopwatch frequency: {0}, High resolution: {1}",
Stopwatch.Frequency,
Stopwatch.IsHighResolution);
tak.taktest();
Console.WriteLine ("done.");
}
}
}