Higher-Order and Symbolic Computation, 11(2)115-116

Introduction

Olivier Danvy and Carolyn L. Talcott

This issue is dedicated to the general topic of continuations. It grew out of the second ACM Workshop on Continuations (CW'97), which took place in Paris, France on January 14th, 1997 [1].

The notion of continuation is ubiquitous in many different areas of computer science,including logic, constructive mathematics, programming languages, and programming.

CW'97 aimed at providing a forum for discussion of new results and work in progress; workaimed 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. We start off with a seminal paper of Peter Landin, "A generalization of jumps and labels," which only existed in the form of a 1965 technical note, and for which Hayo Thielecke kindly agreed to write an introduction. This paper describes a real conceptual discovery, namely the idea to make control facilities first-class entities in a programming language, through the "J operator." Its exposition is typical of the simplicity, directness, clarity and honesty of Landin's writing that makes his articles such a pleasure to read.

Modelling continuations in the lambda-calculus yields what is commonly known as "Continuation-Passing Style" (CPS). In CPS, all calls are tail calls, and each function is equipped with an extra functional argument representing the rest of the computation--its continuation. To return a result to its caller, a function sends it to its continuation, i.e., it applies its continuation to this result. CPS, like continuations, has been variously discovered in many areas of computer science. John Reynolds reviewed these discoveries of continuations in our first special issue on continuations [4]. This first special issue also included Michael Fischer's discovery of CPS [2]. Traditionally, the CPS transformation operates on terms. Its type counterpart was first described by Albert Meyer and Mitchell Wand, who used it to prove the existence of a retraction between direct style and CPS [3]. Jakov Kucan generalizes their approach to the computational lambda-calculus in his article "Retraction approach to CPS transform."

To a man with a hammer, the world often looks like a nail. Ever since Milner introduced the pi-calculus, it has been part of the folklore in the continuation community that translations of the lambda-calculus into the pi-calculus look like CPS transformations. In his article "The pi-calculus in direct style," Gerard Boudol formalizes this folklore. He establishes a bridge between CPS and the pi-calculus, and presents the "blue calculus," a direct-style model for higher-order concurrency with the same expressive power as the pi-calculus but with a better notational convenience, similarly to the usual lambda-calculus in direct style compared to CPS.

Because they naturally represent the rest of a computation, continuations have often been used as a foundation to implement threads [5]. Scaling up such implementations, however, has revealed unexpected and rather subtle space leaks in the presence of exceptions. In their article "Safe-for-space threads in Standard ML," Edoardo Biagioni, Ken Cline, Peter Lee, Chris Okasaki, and Chris Stone investigate and solve this problem.

References

1. Olivier Danvy, editor. Proceedings of the Second ACM SIGPLAN Workshop on Continuations, Technical report BRICS-NS-96-13, University of Aarhus, Paris, France, January 1997.

2. Michael J. Fischer. Lambda-calculus schemata. LISP and Symbolic Computation, 6(3/4):259-288, December 1993. An earlier version appeared in an ACM Conference on Proving Assertions about Programs, SIGPLAN Notices, Vol. 7, No. 1, January 1972.

3. Albert R. Meyer and Mitchell Wand. Continuation semantics in typed lambda-calculi (summary). In Rohit Parikh, editor, Logics of Programs - Proceedings, number 193 in Lecture Notes in Computer Science, pages 219-224, Brooklyn, June 1985. Springer-Verlag.

4. John C. Reynolds. The discoveries of continuations. Lisp and Symbolic Computation, 6(3/4):233-247, December 1993.

5. Mitchell Wand. Continuation-based multiprocessing. In Ruth E.Davis and John R. Allen, editors, Conference Record of the 1980 LISP Conference, pages 19-28, Stanford, California, August 1980.

June 2003 - hosc@brics.dk