Higher-Order and Symbolic Computation, 15(2/3)139-140

Editorial

Olivier Danvy and Amr Sabry

This issue of HOSC is dedicated to the general topic of continuations. It grew out of the third ACM SIGPLAN Workshop on Continuations (CW'01), which took place in London, UK on January 16, 2001 [3].

The notion of continuation is ubiquitous in many different areas of computer science, including logic, constructive mathematics, programming languages, and programming. CW'01 aimed at providing a forum for discussion of new results and work in progress; work aimed at a better understanding of the nature of continuations; applications of continuations; and the relation of continuations to other areas of logic and computer science.

The articles in this special issue reflect this diversity. "Comparing Control Constructs by Double-barrelled CPS" studies the fundamental typing and logical properties (intuitionistic, classical, or linear) of various control operators in a simply typed lambda-calculus. The study hinges on an extension of the conventional CPS transformation that uses two continuations, one for the normal and one for the exceptional flow of control. Different interpretations of lambda-abstractions give rise to different type systems. As a byproduct, the author also reconstructs Landin's historical J operator.

"Optimizing Nested Loops Using Local CPS Conversion" illustrates how a direct-style compiler can selectively transform part of the source program into continuation-passing style to make more functions share the same stack frame. The CPS-transformed functions are those whose continuations are known at compile time. Among other optimizations, tail calls between functions that share the same stack frame can be compiled into jumps. Nested loops (which commonly arise in scientific computation) provide a wealth of opportunities for local CPS conversion.

"Linear Continuation-Passing" investigates the expressiveness of control constructs based on the number of times they use continuations and continuation transformers. At one extreme, function calls and returns use continuations linearly; at the other extreme, call/cc allows continuations to be used arbitrarily many times. The space between these two extremes includes many control constructs like exceptions, coroutines, and both forward and backward jumps to reified continuations. The authors review a variety of situations where the type system makes it possible to crystallize linear uses.

"Secure Information Flow via Linear Continuations" shows the benefits of using continuations to reason about the security property of non-interference. Continuations make it possible to generalize previous results about non-interference from simple imperative languages to higher-order imperative languages in continuation-passing style. The generalization requires a linear type system that can accurately track the number of uses of each continuation as well as their stack discipline.

"Axioms for Recursion in Call-by-Value" proposes a natural axiomatization of fixedpoint operators in call-by-value functional languages. It shows that the proposed syntactic axioms correspond to Simpson and Plotkin's semantic characterization of uniform T-fixpoint operators. It also establishes that, in the presence of first-class continuations, the axioms induce a bijective correspondence between primitives for recursion and iteration. These results strengthen and streamline Filinski's earlier work in the previous special issue of HOSC (then LISP and Symbolic Computation) that grew out of the first ACM SIGPLAN Workshop on Continuations [1, 2]. Hasegawa and Kakutani's article is the journal version of an article presented at FOSSACS 2001 and that received the EATCS Best Theoretical Paper Award.

References

1. Danvy, O. and Talcott, C.L. (Eds.). ACM SIGPLAN Workshop on Continuations (1992). Technical Report STAN-CS-92-1426, Stanford University, San Francisco, California.

2. Filinski, A. Recursion from iteration. LISP and Symbolic Computation, 7(1) (1994) 11-37.

3. Sabry, A. (Ed.). Proceedings of the Third ACM SIGPLAN Workshop on Continuations (CW'01) (2001). Technical Report 545, Computer Science Department, Indiana University. London, England.

July 2003 - hosc@brics.dk