Subcontinuations

Continuations have proven to be useful for implementing a variety of control structures, including exception handling facilities and breadth-first searching algorithms. However, traditional continuations are not useful in the presence of concurrency, because the notion of the rest of the computation represented by a continuation does not in general make sense. Traditional continuations can also be difficult to use in nonconcurrent settings, since their global nature is sometimes problematic. This article presents a new type of continuation, called asubcontinuation. Just as a traditional continuation represents the rest of a computation ¿from a given point in the computation, a subcontinuation represents the rest of asubcomputation ¿from a given point in the subcomputation. Subcontinuations may be used to control tree-structured concurrency by allowing nonlocal exits to arbitrary points in a process tree and allowing the capture of a subtree of a computation as a composable continuation for later use. In the absence of concurrency the localized control achievable with subcontinuations makes them more useful than traditional continuations.     

A new approach to procedures with variable arity

This article presents a convenient and efficient procedural interface that allows the definition and use of procedures with optional arguments and indefinite numbers of arguments without resorting to the use of a language-dependent data structure in which to store the arguments. This interface solves many of the problems inherent in the use of lists in Lisp and Scheme to store indefinite numbers of arguments. Simple recursion can be used to consume such arguments without the complexity problems that are caused by the use of the Lisp procedureapply on argument lists. A natural extension to the interface to support multiple return values is presented.This material is based on work supported by the National Science Foundation under grant number CCR-8803432 and by Sandia National Laboratories under contract number 06-06211. A preliminary version of this article was presented at the 1988 ACM Conference on Lisp and Functional Programming.     

Reliable interactive programming with modules

Interactive programming is a convenient programming style that supports fast prototyping and debugging but often results in a loss of modularity and security. This article addresses the problem of supporting reliable and modular interactive programming. A module system designed for interactive use is introduced. This module system supports separate compilation and automatic updating of module interfaces during program development. It also allows the programmer to obtain a fresh program state for reliable testing, eliminating the need to reload an entire program.A preliminary version of this article was presented at the 1992 ACM Conference on Lisp and Functional Programming.     

A family of phase-variable restriction enzymes with differing specificities generated by high-frequency gene rearrangements

The hsd genes of Mycoplasma pulmonis encode restriction and modification enzymes exhibiting a high degree of sequence similarity to the type I enzymes of enteric bacteria. The S subunits of type I systems dictate the DNA sequence specificity of the holoenzyme and are required for both the restriction and the modification reactions. The M. pulmonis chromosome has two hsd loci, both of which contain two hsdS genes each and are complex, site-specific DNA inversion systems. Embedded within the coding region of each hsdS gene are a minimum of three sites at which DNA inversions occur to generate extensive amino acid sequence variations in the predicted S subunits. We show that the polymorphic hsdS genes produced by gene rearrangement encode a family of functional S subunits with differing DNA sequence specificities. In addition to creating polymorphisms in hsdS sequences, DNA inversions regulate the phase-variable production of restriction activity because the other genes required for restriction activity (hsdR and hsdM) are expressed only from loci that are oriented appropriately in the chromosome relative to the hsd promoter. These data cast doubt on the prevailing paradigms that restriction systems are either selfish or function to confer protection from invasion by foreign DNA.     

Threads Yield Continuations

Just as a traditional continuation represents the rest of acomputation from a given point in the computation, a subcontinuationrepresents the rest of a subcomputation from agiven point in the subcomputation. Subcontinuationsare more expressive than traditional continuations and have been shown to beuseful for controlling tree-structured concurrency, yet they havepreviously been implemented only on uniprocessors. This article describes aconcurrent implementation of one-shot subcontinuations. Like one-shotcontinuations, one-shot subcontinuations are first-class but may be invokedat most once, a restriction obeyed by nearly all programs that usecontinuations. The techniques used to implement one-shot subcontinuationsmay be applied directly to other one-shot continuation mechanisms and may begeneralized to support multi-shot continuations as well. A novel feature ofthe implementation is that continuations are implemented in terms ofthreads. Because the implementation model does not rely upon any speciallanguage features or compilation techniques, the model is applicable toany language or language implementation that supports a small set of threadprimitives.     

Fixing Letrec: A Faithful Yet Efficient Implementation of Scheme's Recursive Binding Construct

A Scheme letrec expression is easily converted into more primitive constructs via a straightforward transformation given in the Revised⁵ Report. This transformation, unfortunately, introduces assignments that can impede the generation of efficient code. This article presents a more judicious transformation that preserves the semantics of the revised report transformation and also detects invalid references and assignments to left-hand-side variables, yet enables the compiler to generate efficient code. A variant of letrec that enforces left-to-right evaluation of bindings is also presented and shown to add virtually no overhead. A preliminary version of this article was presented at the 2002 Workshop on Scheme and Functional Programming [15].     

Threads Yield Continuations

Just as a traditional continuation represents the rest of acomputation from a given point in the computation, a subcontinuationrepresents the rest of a subcomputation from agiven point in the subcomputation. Subcontinuationsare more expressive than traditional continuations and have been shown to beuseful for controlling tree-structured concurrency, yet they havepreviously been implemented only on uniprocessors. This article describes aconcurrent implementation of one-shot subcontinuations. Like one-shotcontinuations, one-shot subcontinuations are first-class but may be invokedat most once, a restriction obeyed by nearly all programs that usecontinuations. The techniques used to implement one-shot subcontinuationsmay be applied directly to other one-shot continuation mechanisms and may begeneralized to support multi-shot continuations as well. A novel feature ofthe implementation is that continuations are implemented in terms ofthreads. Because the implementation model does not rely upon any speciallanguage features or compilation techniques, the model is applicable toany language or language implementation that supports a small set of threadprimitives.