In computer science, functional programming is a programming paradigm that treats computation as the evaluation of mathematical functions and avoids state and mutable data. It emphasizes the application of functions, in contrast to the imperative programming style, which emphasizes changes in state...
, continuation-passing style (CPS) is a style of programming in which control
Control flow
In computer science, control flow refers to the order in which the individual statements, instructions, or function calls of an imperative or a declarative program are executed or evaluated....
is passed explicitly in the form of a continuation
Continuation
In computer science and programming, a continuation is an abstract representation of the control state of a computer program. A continuation reifies the program control state, i.e...
Gerald Jay Sussman is the Panasonic Professor of Electrical Engineering at the Massachusetts Institute of Technology . He received his S.B. and Ph.D. degrees in mathematics from MIT in 1968 and 1973 respectively. He has been involved in artificial intelligence research at MIT since 1964...
Guy Lewis Steele Jr. , also known as "The Great Quux", and GLS , is an American computer scientist who has played an important role in designing and documenting several computer programming languages.-Biography:...
The AI Memos are a series of influential memorandums and technical reports published by the MIT AI Lab, Massachusetts Institute of Technology, USA...
349 (1975), which sets out the first version of the Scheme programming language.
A function written in continuation-passing style takes as an extra argument an explicit "continuation" i.e. a function of one argument. When the CPS function has computed its result value, it "returns" it by calling the continuation function with this value as the argument. That means that when invoking a CPS function, the calling function is required to supply a procedure to be invoked with the subroutine's "return" value. Expressing code in this form makes a number of things explicit which are implicit in direct style. These include: procedure returns, which become apparent as calls to a continuation; intermediate values, which are all given names; order of argument evaluation, which is made explicit; and tail call
Tail call
In computer science, a tail call is a subroutine call that happens inside another procedure and that produces a return value, which is then immediately returned by the calling procedure. The call site is then said to be in tail position, i.e. at the end of the calling procedure. If a subroutine...
s, which simply is calling a procedure with the same continuation, unmodified, that was passed to the caller.
Programs can be automatically transformed from direct style to CPS. Functional and logic
Logic programming
Logic programming is, in its broadest sense, the use of mathematical logic for computer programming. In this view of logic programming, which can be traced at least as far back as John McCarthy's [1958] advice-taker proposal, logic is used as a purely declarative representation language, and a...
compilers often use CPS as an intermediate representation where a compiler for an imperative
Imperative programming
In computer science, imperative programming is a programming paradigm that describes computation in terms of statements that change a program state...
Procedural programming can sometimes be used as a synonym for imperative programming , but can also refer to a programming paradigm, derived from structured programming, based upon the concept of the procedure call...
A programming language is an artificial language designed to communicate instructions to a machine, particularly a computer. Programming languages can be used to create programs that control the behavior of a machine and/or to express algorithms precisely....
In compiler design, static single assignment form is a property of an intermediate representation , which says that each variable is assigned exactly once...
(SSA); however, SSA and CPS are equivalent. SSA is formally equivalent to a well-behaved subset of CPS (excluding non-local control flow, which does not occur when CPS is used as intermediate representation). Functional compilers can also use Administrative Normal Form
Administrative normal form
In computer science, administrative normal form is a canonical form of programs, which was introduced by Flanagan et al. 1993 to serve as an intermediate representation in functional compilers to make subsequent transformations to machine code more direct.In ANF, all arguments to a function must...
(ANF) instead of or in conjunction with CPS. CPS is used more frequently by compiler
Compiler
A compiler is a computer program that transforms source code written in a programming language into another computer language...
s than by programmers as a local or global style.
Examples
In CPS, each procedure takes an extra argument representing what should be done with the result the function is calculating. This, along with a restrictive style prohibiting a variety of constructs usually available, is used to expose the semantics of programs, making them easier to analyze. This style also makes it easy to express unusual control structures, like catch/throw or other non-local transfers of control.
The key to CPS is to remember that (a) every function takes an extra argument, its continuation, and (b) every argument in a function call must be either a variable or a lambda expression (not a more complex expression). This has the effect of turning expressions "inside-out" because the innermost parts of the expression must be evaluated first, so CPS explicates the order of evaluation as well as the control flow. Some examples of code in direct style and the corresponding CPS style appear below. These examples are written in the Scheme programming language.
Direct style
Continuation passing style
(define (pyth x y)
(sqrt (+ (* x x) (* y y))))
(define (pyth& x y k)
(*& x x (lambda (x2)
(*& y y (lambda (y2)
(+& x2 y2 (lambda (x2py2)
(sqrt& x2py2 k))))))))
(define (factorial n)
(if (= n 0)
1 ; NOT tail-recursive
(* n (factorial (- n 1)))))
(define (factorial& n k)
(=& n 0 (lambda (b)
(if b ; growing continuation
(k 1) ; in the recursive call
(-& n 1 (lambda (nm1)
(factorial& nm1 (lambda (f)
(*& n f k)))))))))
(define (factorial n)
(f-aux n 1))
(define (f-aux n a)
(if (= n 0)
a ; tail-recursive
(f-aux (- n 1) (* n a))))
(define (factorial& n k) (f-aux& n 1 k))
(define (f-aux& n a k)
(=& n 0 (lambda (b)
(if b ; unmodified continuation
(k a) ; in the recursive call
(-& n 1 (lambda (nm1)
(*& n a (lambda (nta)
(f-aux& nm1 nta k)))))))))
Note that in the CPS versions, the primitives used, like +& and *& are themselves CPS, not direct style, so to make the above examples work in a Scheme system we would need to write these CPS versions of primitives, with for instance *& defined by:
(define (*& x y k)
(k (* x y))) To do this in general, we might write a conversion routine:
(define (cps-prim f)
(lambda args
(let ((r (reverse args)))
((car r) (apply f
(reverse (cdr r)))))))
(define *& (cps-prim *))
(define +& (cps-prim +))
In order to call a procedure written in CPS from a procedure written in direct style, it is necessary to provide a continuation that will receive the result computed by the CPS procedure. In the example above (assuming that CPS-style primitives have been provided), we might call (factorial& 10 (lambda (x) (display x) (newline))).
There is some variety between compilers in the way primitive functions are provided in CPS. Above we have used the simplest convention, however sometimes boolean primitives are provided that take two thunks to be called in the two possible cases, so the (=& n 0 (lambda (b) (if b ...))) call inside f-aux& definition above would be written instead as (=& n 0 (lambda (k a)) (lambda (-& n 1 ...))). Similarly, sometimes the if primitive itself is not included in CPS, and instead a function if& is provided which takes three arguments: a boolean condition and the two thunks corresponding to the two arms of the conditional.
The translations shown above show that CPS is a global transformation. The direct-style factorial takes, as might be expected, a single argument; the CPS factorial& takes two: the argument and a continuation. Any function calling a CPS-ed function must either provide a new continuation or pass its own; any calls from a CPS-ed function to a non-CPS function will use implicit continuations. Thus, to ensure the total absence of a function stack, the entire program must be in CPS.
Continuations as objects
Programming with continuations can also be useful when a caller does not want to wait until the callee completes. For example, in user-interface (UI) programming, a routine can set up dialog box fields and pass these, along with a continuation function, to the UI framework. This call returns right away, allowing the application code to continue while the user interacts with the dialog box. Once the user presses the "OK" button, the framework calls the continuation function with the updated fields. Although this style of coding uses continuations, it is not full CPS.
function confirmName {
fields.name = name;
framework.Show_dialog_box(fields, confirmNameContinuation);
}
function confirmNameContinuation(fields) {
name = fields.name;
}
A similar idea can be used when the function must run in a different thread or on a different processor. The framework can execute the called function in a worker thread, then call the continuation function in the original thread with the worker's results. This is in Java
Java (programming language)
Java is a programming language originally developed by James Gosling at Sun Microsystems and released in 1995 as a core component of Sun Microsystems' Java platform. The language derives much of its syntax from C and C++ but has a simpler object model and fewer low-level facilities...
Swing is the primary Java GUI widget toolkit. It is part of Oracle's Java Foundation Classes — an API for providing a graphical user interface for Java programs....
UI framework:
void buttonHandler {
// This is executing in the Swing UI thread.
// We can access UI widgets here to get query parameters.
final int parameter = getField;
new Thread(new Runnable {
public void run {
// This code runs in a separate thread.
// We can do things like hit a database or access
// a blocking resource like the network to get data.
final int result = lookup(parameter);
javax.swing.SwingUtilities.invokeLater(new Runnable {
public void run {
// This code runs in the UI thread and can use
// the fetched data to fill in UI widgets.
setField(result);
}
});
}
}).start;
}
CPS and tail calls
Note that in CPS, there is no implicit continuation — every call is a tail call
Tail call
In computer science, a tail call is a subroutine call that happens inside another procedure and that produces a return value, which is then immediately returned by the calling procedure. The call site is then said to be in tail position, i.e. at the end of the calling procedure. If a subroutine...
. There is no "magic" here, as the continuation is simply explicitly passed. Using CPS without tail call optimization (TCO) will cause not only the constructed continuation to potentially grow during recursion, but also the call stack
Call stack
In computer science, a call stack is a stack data structure that stores information about the active subroutines of a computer program. This kind of stack is also known as an execution stack, control stack, run-time stack, or machine stack, and is often shortened to just "the stack"...
. This is usually undesirable, but has been used in interesting ways - see the Chicken Scheme compiler. As CPS and TCO eliminate the concept of an implicit function return, their combined use can eliminate the need for a run-time stack. Several compilers and interpreters for functional programming languages use this ability in novel ways .
Use and implementation
Continuation passing style can be used to implement continuations and control flow operators in a functional language that does not feature first-class continuations but does have first-class function
First-class function
In computer science, a programming language is said to have first-class functions if it treats functions as first-class objects. Specifically, this means that the language supports passing functions as arguments to other functions, returning them as the values from other functions, and assigning...
s and tail-call optimization. Without tail-call optimization, techniques such as trampolining
Trampoline (computers)
In computer programming, the word trampoline has a number of meanings, and is generally associated with jumps .- Low Level Programming :...
, i.e. using a loop that iteratively invokes thunk-returning functions, can be used; without first-class functions, it is even possible to convert tail calls into just gotos in such a loop.
Writing code in CPS, while not impossible, is often error-prone. There are various translations, usually defined as one- or two-pass conversions of pure lambda calculus
Lambda calculus
In mathematical logic and computer science, lambda calculus, also written as λ-calculus, is a formal system for function definition, function application and recursion. The portion of lambda calculus relevant to computation is now called the untyped lambda calculus...
, which convert direct style expressions into CPS expressions. Writing in trampolined style, however, is extremely difficult; when used, it is usually the target of some sort of transformation, such as compilation
Compiler
A compiler is a computer program that transforms source code written in a programming language into another computer language...
.
Functions using more than one continuation can be defined to capture various control flow paradigms, for example (in Scheme):
(define (/& x y ok err)
(=& y 0.0 (lambda (b)
(if b
(err (list "div by zero!" x y))
(ok (/ x y))))))
It is of note that CPS transform is conceptually a Yoneda embedding. It is also similar to the embedding of π-calculus in lambda calculus
Lambda calculus
In mathematical logic and computer science, lambda calculus, also written as λ-calculus, is a formal system for function definition, function application and recursion. The portion of lambda calculus relevant to computation is now called the untyped lambda calculus...
Computer science or computing science is the study of the theoretical foundations of information and computation and of practical techniques for their implementation and application in computer systems...
, CPS is of more general interest as an alternative to the conventional method of composing simple expressions into complex expressions. For example, within linguistic semantics
Semantics
Semantics is the study of meaning. It focuses on the relation between signifiers, such as words, phrases, signs and symbols, and what they stand for, their denotata....
, Chris Barker and his collaborators have suggested that specifying the denotations of sentences using CPS might explain certain phenomena in natural language
Natural language
In the philosophy of language, a natural language is any language which arises in an unpremeditated fashion as the result of the innate facility for language possessed by the human intellect. A natural language is typically used for communication, and may be spoken, signed, or written...
Mathematics is the study of quantity, space, structure, and change. Mathematicians seek out patterns and formulate new conjectures. Mathematicians resolve the truth or falsity of conjectures by mathematical proofs, which are arguments sufficient to convince other mathematicians of their validity...
, the Curry–Howard isomorphism between computer programs and mathematical proofs relates continuation-passing style translation to a variation of double-negation embedding
Embedding
In mathematics, an embedding is one instance of some mathematical structure contained within another instance, such as a group that is a subgroup....
Classical logic identifies a class of formal logics that have been most intensively studied and most widely used. The class is sometimes called standard logic as well...
Intuitionistic logic, or constructive logic, is a symbolic logic system differing from classical logic in its definition of the meaning of a statement being true. In classical logic, all well-formed statements are assumed to be either true or false, even if we do not have a proof of either...
. Unlike the regular double-negation translation, which maps atomic propositions p to ((p → ⊥) → ⊥), the continuation passing style replaces ⊥ by the type of the final expression. Accordingly, the result is obtained by passing the identity function
Identity function
In mathematics, an identity function, also called identity map or identity transformation, is a function that always returns the same value that was used as its argument...
as a continuation to the CPS-style expression, as in the above example.
Classical logic itself relates to manipulating the continuation of programs directly, as in Scheme's call-with-current-continuation
Call-with-current-continuation
In functional programming, the function call-with-current-continuation, commonly abbreviated call/cc, is a control operator that originated in its current form in the Scheme programming language and now exists in several other programming languages....
control operator, an observation due to Tim Griffin (using the closely related C control operator)
ML is a general-purpose functional programming language developed by Robin Milner and others in the early 1970s at the University of Edinburgh, whose syntax is inspired by ISWIM...
Chicken is a compiler and interpreter for the Scheme programming language that compiles Scheme code to standard C. It is mostly R5RS compliant and offers many extensions to the standard...
C is a general-purpose computer programming language developed between 1969 and 1973 by Dennis Ritchie at the Bell Telephone Laboratories for use with the Unix operating system....
compiler that uses continuation-passing style for translating Scheme procedures into C functions while using the C-stack as the nursery for the generational garbage collector Direct link: "Section 3.4. Continuation Passing Style".
Tail recursion through trampolining
The source of this article is wikipedia, the free encyclopedia. The text of this article is licensed under the GFDL.
