|
 ABSTRACT
The last few years have seen a renewed interest in continuations for expressing advanced control structures in programming languages, and new models such as Abstract Continuations have been proposed to capture these dimensions. This article investigates an alternative formulation, exploiting the latent expressive power of the standard continuation-passing style (CPS) instead of introducing yet other new concepts. We build on a single foundation: abstracting control as a hierarchy of continuations, each one modeling a specific language feature as acting on nested evaluation contexts.
We show how iterating the continuation-passing conversion allows us to specify a wide range of control behavior. For example, two conversions yield an abstraction of Prolog-style backtracking. A number of other constructs can likewise be expressed in this framework; each is defined independently of the others, but all are arranged in a hierarchy making any interactions between them explicit.
This approach preserves all the traditional results about CPS, e.g., its evaluation order independence. Accordingly, our semantics is directly implementable in a call-by-value language such as Scheme or ML. Furthermore, because the control operators denote simple, typable lambda-terms in CPS, they themselves can be statically typed. Contrary to intuition, the iterated CPS transformation does not yield huge results: except where explicitly needed, all continuations beyond the first one disappear due to the extensionality principle (&eegr;-reduction).
Besides presenting a new motivation for control operators, this paper also describes an improved conversion into applicative-order CPS. The conversion operates in one pass by performing all administrative reductions at translation time; interestingly, it can be expressed very concisely using the new control operators. The paper also presents some examples of nondeterministic programming in direct style.
REFERENCES
Note: OCR errors may be found in this Reference List extracted from the full text article. ACM has opted to expose the complete List rather than only correct and linked references.
| |
Aho, Hopcroft, & Ullman 74
|
|
 |
Appel & Jim 89
|
A. W. Appel , T. Jim, Continuation-passing, closure-passing style, Proceedings of the 16th ACM SIGPLAN-SIGACT symposium on Principles of programming languages, p.293-302, January 11-13, 1989, Austin, Texas, United States
[doi> 10.1145/75277.75303]
|
| |
Barendregt 85
|
Hendrick P. Barendregt: The Lambda Calculus, Rs Syntax and Semantics, revised edition, Studies in Logic and the Foundations of Mathematics, Vol. 103, North-Holland (1985)
|
| |
Danvy & Malmkjær 88
|
|
| |
Danvy & Filinski 89
|
Olivier Danvy, Andrzej Fillnski: A Functional Abstraction of Typed Contexts, DIKU Rapport 89/12, DIKU, University of Copenhagen, Copenhagen, Denmark (August 1989)
|
| |
Danvy 89
|
Olivier Danvy: Programming with Tighter Control, pp 10-29 of the BIGRE journal, No 65 on Putting Scheme to Work, Andr~ Pic, Michel Briand, and Jean B~zivin (eds.), Brest, France (July 1989)
|
| |
Felleisen et al. 87
|
Matthiaz Felleisen, Daniel P. Friedman, Bruce Dubs, John Merrill: Beyond Continuations, Technical Report No 216, Computer Science Department, Indiana University, Bloomington, Indiana (February 1987)
|
| |
Felleisen 88
|
|
| |
Felleisen et al. 88
|
Matthias Felleisen , Mitch Wand , Daniel Friedman , Bruce Duba, Abstract continuations: a mathematical semantics for handling full jumps, Proceedings of the 1988 ACM conference on LISP and functional programming, p.52-62, July 25-27, 1988, Snowbird, Utah, United States
[doi> 10.1145/62678.62684]
|
| |
Filinski 89
|
|
| |
Fischer 72
|
|
| |
Friedman, Haynes, & Kohlbecker 84
|
Daniel P. Friedman, Christopher T. Haynes, Eugene Kohlbecker: Programruing with Continuations, NATO ASI Series, Vol. F8, Program Transformation and Programming Environments pp 263-274, P. Pepper (ed.), Springer-Verlag Berlin Heidelberg (1984)
|
| |
Haynes & Friedman 87
|
|
| |
Johnson 87
|
|
| |
Johnson & Duggan 88
|
|
| |
Malmkjær 89
|
|
| |
Mazurkiewicz 71
|
Antoni W. Mazurkiewicz: Proving Algorithms by Tail Functions, Information and Control Vol. 18 pp 220-226 (1971)
|
| |
Mellish & Hardy 84
|
Chris Mellish, Steve Hardy: Integrating Prolog in the POPLOG Environment, in Implementations of PROLOG, John A. Campbell (ed.) pp 147- 162, Ellis Horwood (1984)
|
| |
Miller 87
|
James S. Miller: MultiScheme: A Parallel Pro. cessing System Based on MIT Scheme, PhD thesis, MIT/LGS/TR-402 (September 1987)
|
| |
Milne & Strachey 76
|
|
| |
Moggi 89
|
|
| |
Morris 72
|
|
| |
Plotkin 75
|
Gordon Plotkin: Call-by-Name, Gall-b~t-Value, and the A.calculus, Theoretical Computer Science, Vol. I pp 125-159 (1975)
|
| |
Rees & Clinger 86
|
|
| |
Reynolds 72
|
|
| |
Reynolds 74
|
|
| |
Sethi & Tang 80
|
|
| |
Sitaram & Felleisen 90
|
|
| |
Smith 82
|
Brian C. Smith: Reflection and Semantics in a Procedural Language, PhD thesis, MIT/LCS/TR-272, MIT, Cambridge, Massachusetts (January 1982)
|
| |
Steele & Sussman 76
|
|
| |
Steele 78
|
|
| |
Stoy 81
|
Joseph E. Stoy: The Congruence of Two Program. ruing Language Definitions, Theoretical Computer Science, Vol. 13 pp 151-174 (1981)
|
| |
Strachey & Wadsworth 74
|
Christopher Strachey, Christopher P. Wadsworth: Continuations: A Mathematical Semantics for Handling Full Jumps, Technical Monograph PRG-11, Oxford University Computing Laboratory, Programming Research Group, Oxford, England (1974)
|
| |
van Wijngaarden 66
|
Adriaan van Wijngaarden: Recursive Definition of Syntax and Semantics, in Formal Lan. guage Description Languages for Computer Programruing pp 13-24, T. B. Steel Jr. (ed.), North-Holland (1966)
|
| |
Wand & Friedman 88
|
Mitchell Wand, Daniel P. Friedman: The MIlsterll of the Tower Revealed: A Non. Reflective Description of the Reflective Tower, Volume 1, Issue 1 of/Lisp and Symbolic Computation (May 1988)
|
|
Adobe Acrobat
QuickTime
Windows Media Player
Real Player
Pdf
D.3