From ContinuationsAreGotos:
Ways to implement full FirstClass continuations. UpwardContinuation?s can be straightforwardly implemented using a plain vanilla stack or stacks.
- Heap allocation of ActivationRecords
- Each activation record is a separate heap object, chained together by a pointer to its caller. Continuation capture saves the pointer to the current record, which prevents it and all stack frames under it from being garbage collected. Continuation reinstatement restores the PC, registers, and current record.
-
- Advantages: Simple to implement. Continuation capture and reinstatement are very fast. Flexible; can also inspect and operate upon individual stack frames. Portable.
-
- Disadvantages: Slow function calls. Puts a heavy load on the garbage collector. (not necessarily, see http://portal.acm.org/citation.cfm?id=345125&jmp=references&dl=portal&dl=ACM)
-
- Implementations: Smalltalk (aside from optimizations), StacklessPython, Ruby, Rebol 1.0, SISC Scheme interpreter. SML
- Copying whole stacks.
- Stack frames are allocated normally, but when a continuation is captured, the whole stack is copied and saved in the continuation. Continuation reinstatement restores the register state and sets the stack and frame pointers to the continuation's stack. The old stack can be deallocated or freed by the garbage collector.
-
- Advantages: Conceptually simple. No function-calling overhead. Continuation reinstatement is reasonably fast.
-
- Disadvantages: Very expensive continuation capture. Requires either assembly language coding, externalized stacks, or fancy C-hacks (see below) for implementation.
-
- Implementations: Guile, Gambit Scheme (?)
- Segmented stacks.
- The stack is allocated in large chunks, with an overflow handler to allocate a new chunk as necessary (the virtual memory hardware can handle this, by mapping in a non-writable page at the address past the stack). Continuation capture shortens the stack and saves a pointer to the previous portion. See KentDybvig and RobertHieb?, "Representing Control in the Presence of First-Class Continuations" (http://www.cs.indiana.edu/~dyb/papers/stack.ps) for details. Similar to a CactusStack.
-
- Advantages: Low performance penalty (estimated at 5-10% overhead for function calls in most cases). Quick continuation capture and reinstatement.
-
- Disadvantages: Conceptually complex. Requires either compilation to assembly or large assembly-language portions of the runtime to implement efficiently.
-
- Implementations: ? Probably most of the commercial Schemes. SmalltalkEcks. This is the preferred implementation technique for high-performance implementations.
- ContinuationPassingStyle
- Convert the whole program to CPS. The continuation is automatically available within every expression. Often used in conjunction with the-stack-is-the-heap (CheneyOnTheMta) or a CPS-based intermediate representation.
-
- Advantages: Requires no additional overhead beyond what is required for a normal CPS representation. Good for compilers that use that anyway.
-
- Disadvantages: Still faced with details of memory management. CPS can be inefficient when compiling to C, because of the large number of function calls made.
-
- Implementations: Rabbit, T, Orbit, Chicken
CopyOnWrite can be used as an optimization to prevent unnecessary copying of individual stack frames.
Implementation in C
This can also be done purely in CeeLanguage. KenThompson a wrote a thread package like this for an OS class he taught at CalBerkeley in 1975. It copied and restored entire stacks starting at the address of a local variable.
This is non-portable, of course, but then, so (even more so) is an assembly implementation of threading.
The code is short, pretty trivial, but understanding it requires prior understanding of the machine architecture, how the compiler lays things out in memory, etc, so it could be called ThreeStarProgramming. Or SixStarProgramming?. :-) There is nonetheless sometimes a place for such things. A programmer who doesn't understand all the issues wouldn't be able to maintain any threading package.
CheneyOnTheMta uses a similar approach to compile Scheme into C. The system checks whether the stack has outgrown its limit through taking the address of a local, and if so, garbage collects all reachable data and contracts the stack through a longjmp. The one implementation of it, Chicken, contains no assembly code. The only machine-dependent parameter is whether the stack grows upwards or downwards (along with checks for the existence of various C-library functions, like alloca).
ContinuationsAndCoroutines stated that sometimes continuations are implemented with co-routines. How is this done?
Actually, it's the opposite: co-routines can be implemented with continuations.
Contributors: DougMerritt, AnonymousDonor, JonathanTang, ScottJohnson
CategoryContinuation
Continuation Implementation