Abstract
Practically all programming languages have some form of control structure or jumping. The more advanced forms of control structure tend to resemble function calls, so much so that they are usually not even described as jumps. Consider for example the library function exit in C. Its use is much like a function, in that it may be called with an argument; but the whole point of exit is of course that its behaviour is utterly non-functional, in that it jumps out of arbitrarily many surrounding blocks and pending function calls. Such a "non-returning function" or "jump with arguments" is an example of a continuation in the sense which we are interested in here.On the other hand, a simple but fundamental idea in compiling is that a function call is broken down into two jumps: one from the caller to the callee for the call itself, and another jump back from the callee to the caller upon returning. (The return statement in C is in fact listed among the "jump statements" [5].) This is most obvious for void-accepting and -returning functions, but it generalizes to other functions as well, if one is willing to understand "jump" in the broader sense of jump with arguments, i.e. continuation.In this view, then, continuations are everywhere. Continuations have been used in many different settings, in which they appear in different guises, ranging from mathematical functions to machine addresses. Rather than confine ourselves to a definition of what a continuation is, we will focus on continuation-passing style (CPS), as it brings out the commonalities. The CPS transform compresses a great deal of insight into three little equations in λ-calculus. Making sense of it intuitively, however, requires some background knowledge and a certain fluency. The purpose of this article, therefore, is to help the reader uncompress the CPS transform by way of a rational reconstruction from jumps.In the sequel, we will attempt to illustrate the correspondence between continuations and jumps (even in the guise of the abhorred goto). The intent is partly historical, to retrace some of the analysis of jumps that led to the discoveries of continuations. At the same time, the language of choice for many researchers during the (pre)history of continuations, ALGOL 60, is not so different from today's mainstream languages (i.e. C); we hope that occasional snippets of C may be more easily accessible to many readers than a functional language would be. So in each of the four sections (Sections 2-5 below) that make up the body of this paper, some C code will be used to give a naive but concrete example of the issue under consideration, before generalizing to a more abstract setting.
- Andrew Appel. Compiling with Continuations. Cambridge University Press, 1992.]] Google ScholarDigital Library
- Gérard Boudol. Pi-calculus in direct style. In ACM Symposium on Principles of Programming Languages, 1997.]] Google ScholarDigital Library
- Timothy G. Griffin. A formulae-as-types notion of control. In Proc. 17th ACM Symposium on Principles of Programming Languages, pages 47-58, San Francisco, CA USA, 1990.]] Google ScholarDigital Library
- Richard Kelsey, William Clinger, and Jonathan Rees, editors. Revised5 report on the algorithmic language Scheme. Higher-Order and Symbolic Computation, 11(3):7-105, 1998.]] Google ScholarDigital Library
- Brian W. Kernighan and Dennis M. Ritchie. The C Programming Language. Prentice Hall, 2nd edition, 1988.]] Google ScholarDigital Library
- Peter J. Landin. A generalization of jumps and labels. Report, UNIVAC Systems Programming Research, August 1965.]]Google Scholar
- Peter J. Landin. A generalization of jumps and labels. Higher-Order and Symbolic Computation, 11(2), 1998. Reprint of {6}.]] Google ScholarDigital Library
- Robin Milner. The polyadic π-calculus: A tutorial. LFCS Report ECS-LFCS-91-180, LFCS, University of Edinburgh, October 1991.]]Google Scholar
- Robin Milner. Functions as processes. Journal of Mathematical Structures in Computer Science, 2(2):119-141, 1992.]]Google ScholarCross Ref
- Gordon Plotkin. Call-by-name, call-by-value, and the λ-calculus. Theoretical Computer Science, 1(2):125-159, 1975.]]Google ScholarCross Ref
- John C. Reynolds. Definitional interpreters for higher-order programming languages. In Proceedings of the 25th ACM National Conference, pages 717-740. ACM, August 1972.]] Google ScholarDigital Library
- John C. Reynolds. The discoveries of continuations. Lisp and Symbolic Computation, 6(3/4):233-247, November 1993.]] Google ScholarDigital Library
- Jon G. Riecke and Hayo Thielecke. Typed exceptions and continuations cannot macro-express each other. In Proc. ICALP '99, 1999.]] Google ScholarDigital Library
- Guy Steele. Rabbit: A compiler for Scheme. Technical Report AI TR 474, MIT, May 1978.]] Google ScholarDigital Library
- Christopher Strachey and C. P. Wadsworth. Continuations: A mathematical semantics for handling full jumps. Technical Monograph PRG-11, Oxford University Computing Laboratory, January 1974.]]Google Scholar
- Hayo Thielecke. Categorical Structure of Continuation Passing Style. PhD thesis, University of Edinburgh, 1997. Also available as technical report ECS-LFCS-97-376.]]Google Scholar
- Adriaan van Wijngaarden. Recursive definition of syntax and semantics. In T. B. Steel, Jr, editor, Formal Language Description Languages for Computer Programming, Proceedings of an IFIP Working Conference, pages 13-24, 1964.]]Google Scholar
Index Terms
- Continuations, functions and jumps
Recommendations
Compiling with continuations, continued
Proceedings of the ICFP '07 conferenceWe present a series of CPS-based intermediate languages suitable for functional language compilation, arguing that they have practical benefits over direct-style languages based on A-normal form (ANF) or monads. Inlining of functions demonstrates the ...
Compiling without continuations
PLDI 2017: Proceedings of the 38th ACM SIGPLAN Conference on Programming Language Design and ImplementationMany fields of study in compilers give rise to the concept of a join point—a place where different execution paths come together. Join points are often treated as functions or continuations, but we believe it is time to study them in their own right. ...
Comments