Continuation-passing style

From Wikipedia, the free encyclopedia

Continuation-passing style (CPS) is a term used within functional programming to describe a style of programming in which control is passed explicitly in the form of a continuation.

[edit] Introduction

Instead of "returning" values as in the more familiar direct style, a function written in CPS takes an explicit continuation argument which is meant to receive the result of the computation performed within the function. When a subroutine is invoked within 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 recursion, which is simply calling a procedure with the continuation that was passed to the caller.

Programs can be automatically transformed from direct style to CPS. Although CPS and SSA are formally equivalent, functional and logic compilers often use CPS as an intermediate representation where a compiler for an imperative or procedural programming language would use static single assignment form (SSA). Functional compilers can also use Administrative Normal Form (ANF) instead of or in conjunction with CPS. CPS is used more frequently by compilers than by programmers as a local or global style.

[edit] Examples

In the Scheme programming language, the simplest of direct-style functions is the identity function:

(lambda (x) x)

which in CPS becomes:

(lambda (x return) (return x))

where return is the continuation argument (often also called k). 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. This has the effect of turning expressions "inside-out" because the innermost parts of the expression must be evaluated first! Some examples of code in direct style and the corresponding CPS style appear below.

(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
     (* n (factorial (- n 1)))))

(define (factorial n k)
  (= n 0 (lambda (b)
          (if b
             (k 1)
             (- n 1 (lambda (nm1)
                     (factorial
                      nm1
                      (lambda (fnm1)
                       (* n fnm1 k))))))))

(define (factorial n) (f-aux n 1))
(define (f-aux n a)
 (if (= n 0)
     a
     (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
             (k a)
             (- n 1 (lambda (nm1)
                     (* n a (lambda (nta)
                             (f-aux nm1 nta k)))))))))

Note that 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 take two continuations, so (if (= a b) c d) in direct style would be translated to (= a b (lambda () (k c)) (lambda () (k d))). Similarly, sometimes if itself is not included in CPS, and instead a primitive function %if is provided which takes three arguments: a boolean condition and two continuations 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.

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 Confirm_name()
{
    fields.name = name;
    framework.Show_dialog_box(fields, Confirm_name_continuation);
}

function Confirm_name_continuation(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 using the Swing 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() {
            // Now we're 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() {
                    // Now we're back in the UI thread and can use
                    // the fetched data to fill in UI widgets.
                    setField(result);
                }
            });
        }
    }).start();
}

[edit] CPS and tail calls

Note that in CPS, there is no implicit continuation — every call is a tail call. There is no "magic" here, as the continuation is simply explicitly passed. Using CPS without tail call optimization (TCO) will cause not only the explicit continuation to grow during recursion, but also the function stack itself.

As CPS and TCO eliminate the concept of an implicit function return, their combined use can eliminate the need for a runtime stack. Several compilers and interpreters for functional programming languages use this ability in novel ways.

[edit] Use and implementation

Continuation passing style can be used to implement continuations in a functional language that does not feature first-class continuations but does have first-class functions. Without first-class functions, techniques such as trampolining of thunk closures can be used; in this case, it is possible to convert tail calls into gotos in a loop, eliminating even the need for TCO.

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, 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.

[edit] Use in other fields

Outside of computer science, 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, Chris Barker and his collaborators have suggested that specifying the denotations of sentences using CPS might explain certain phenomena in natural language [1].

[edit] See also

• Andrew Appel describes the construction of a CPS-based compiler for ML in: Appel, Andrew W. (1992). Compiling with Continuations. Cambridge University Press. ISBN 0-521-41695-7..
• Olivier Danvy and Andrzej Filinski. Representing Control, A Study of the CPS Transformation Mathematical Structures in Computer Science 2(4):361-391, 1992.
• Chicken Scheme compiler, an example of a Scheme compiler that exploits continuation-passing style to translate Scheme procedures into C functions that run using the Scheme heap as their stack.
• Richard A. Kelsey (March 1995). "A Correspondence between Continuation Passing Style and Static Single Assignment Form". ACM SIGPLAN Notices 30 (3): 13-22.
• Andrew W. Appel (April 1998). "SSA is Functional Programming". ACM SIGPLAN Notices 33 (4): 17-20.