LISP and Symbolic Computation, 10(3)223-236

Threads Yield Continuations

Sanjeev Kumar, Department of Computer Science, Princeton University, Princeton, NJ 08544 USA
Carl Bruggeman, Department of Computer Science and Engineering, University of Texas at Arlington, Arlington, TX 76019-0015 USA
R. Kent Dybvig, Computer Science Department, Indiana University, Bloomington, IN 47405 USA

Abstract: Just as a traditional continuation represents the rest of a computation from a given point in the computation, a subcontinuation represents the rest of a subcomputation from a given point in the subcomputation. Subcontinuations are more expressive than traditional continuations and have been shown to be useful for controlling tree-structured concurrency, yet they have previously been implemented only on uniprocessors. This article describes a concurrent implementation of one-shot subcontinuations. Like one-shot continuations, one-shot subcontinuations are first-class but may be invoked at most once, a restriction obeyed by nearly all programs that use continuations. The techniques used to implement one-shot subcontinuations may be applied directly to other one-shot continuation mechanisms and may be generalized to support multi-shot continuations as well. A novel feature of the implementation is that continuations are implemented in terms of threads. Because the implementation model does not rely upon any special language features or compilation techniques, the model is applicable to any language or language implementation that supports a small set of thread primitives.

Keywords: concurrency, continuations, control delimiters, control operators, threads

This article can be downloaded [here].

June 2003 - hosc@brics.dk