Continuation-passing style (CPS) is a style of programming in which a function receives an additional argument specifying what should happen to its result. This argument, called a continuation, represents the remaining computation. Instead of returning a result directly to its caller, a CPS function passes that result to its continuation. CPS makes otherwise implicit control flow explicit and is used in functional programming, programming-language semantics, and compiler construction.
Basic principle
In ordinary, or direct-style, programming, a function computes a value and returns it. The surrounding expression determines how that value is subsequently used. For example:
square(x):
return x * x
result = square(5) + 1
When square(5) finishes, the remaining computation is to add one to its result and assign the sum to result. A continuation represents this pending work explicitly.
A corresponding CPS function can be written as:
square_cps(x, k):
return k(x * x)
square_cps(5, lambda value: value + 1)
Here, k is the continuation. The function does not return the square as its ordinary result; it transfers the square to k. The return notation merely expresses a tail transfer in this pseudocode. In a fully CPS-transformed program, the continuation itself continues the computation rather than returning to perform additional work in square_cps.
The continuation lambda value: value + 1 captures the local “what happens next” associated with the original call. At a complete program’s boundary, a final continuation might display the result, terminate execution, or return control to a direct-style environment.
A continuation is therefore more specific than an arbitrary function argument: its role is to represent the computation that follows a particular point in execution.
Evaluation order and transformation
CPS can be introduced manually or produced by a mechanical transformation of source code. Such a transformation replaces implicit sequencing and returns with explicit continuation arguments.
Consider the direct-style expression:
add(square(a), square(b))
For left-to-right evaluation, its CPS form is:
square_cps(a, lambda x:
square_cps(b, lambda y:
add_cps(x, y, k)))
The nesting specifies the order:
- Compute the square of
a. - Compute the square of
b. - Add the two values.
- Pass the sum to
k.
This ordering matters when computations have observable effects, such as modifying state or performing input and output. CPS does not inherently require one evaluation order, but a particular transformation encodes one.
A formal call-by-value transformation
For a small lambda calculus, let denote the CPS translation of expression . Assume left-to-right call-by-value evaluation, and use fresh variable names to avoid capture. A standard schematic translation is:
In this curried notation, a translated function first receives its ordinary argument and then its continuation. The application rule evaluates the function expression, evaluates the argument expression, and invokes the translated function with the argument and the current continuation.
These rules concern a minimal language. Practical transformations also handle constants, primitive operations, conditionals, recursion, mutable state, and other language constructs.
A simple transformation often introduces extra function applications that perform only bookkeeping. These administrative reductions can be simplified during or after translation.
Tail calls and memory use
A distinguishing property of conventional CPS is that transfers of control occur in tail position: after invoking another function or continuation, the current computation has no further work to perform.
Consider factorial in direct style:
factorial(n):
if n == 0:
return 1
return n * factorial(n - 1)
The multiplication must wait for the recursive call to return. CPS moves that pending multiplication into a continuation:
factorial_cps(n, k):
if n == 0:
return k(1)
return factorial_cps(
n - 1,
lambda value: k(n * value)
)
The recursive call is now a tail call, but the pending multiplications have not disappeared. They are represented by a chain of closures capturing values of n and earlier continuations.
Consequently, CPS does not automatically make a computation constant-space:
- With proper tail-call support, ordinary call-stack growth can be avoided.
- Continuations may still require memory proportional to the amount of pending work.
- In a language without proper tail calls, a straightforward CPS implementation may still grow the runtime stack.
For factorial, an accumulator-based algorithm can use bounded auxiliary state under suitable arithmetic assumptions. Converting the original algorithm to CPS alone does not produce that algorithmic improvement.
A trampoline provides another execution technique: each step returns a description of the next step, and a loop repeatedly executes those descriptions. This can avoid unbounded native-stack growth without relying on the host language’s tail-call implementation.
Continuations as control mechanisms
Explicit continuations allow programs to represent more control structures than ordinary nested function calls.
Exceptions and early exit
A computation can receive separate success and failure continuations:
divide_cps(x, y, success, failure):
if y == 0:
return failure("division by zero")
return success(x / y)
This makes alternative control paths explicit. More elaborate encodings can represent exception handling, early returns, or exits from nested computations.
Such encodings require care around cleanup actions and resource lifetimes. Passing a continuation does not, by itself, reproduce every guarantee of a language’s native exception mechanism.
Backtracking
A search procedure can pass both a success continuation and a failure continuation. The failure continuation describes how to resume the search when a candidate is rejected or exhausted.
This is useful in parsers, nondeterministic computations, and implementations of logic programming. A successful result can be accompanied by a continuation that searches for another result.
Suspension and resumption
A continuation may be stored rather than invoked immediately. A scheduler or external event can later invoke it to resume computation. This principle is useful for implementing coroutines and asynchronous programming.
Ordinary CPS does not automatically provide an operation that captures the current continuation. Languages with first-class continuation operators expose additional mechanisms for capturing and invoking control state. Whether a continuation may be invoked once or repeatedly also depends on its representation and the surrounding execution model.
Relationship to callbacks and asynchronous code
Callback-based interfaces often resemble CPS because they receive functions to invoke with eventual results. For example, an asynchronous file-reading operation may receive a callback describing what to do with the file contents.
However, the concepts are not identical:
- A callback may represent an event handler, comparison function, notification, or other behavior rather than the remainder of a computation.
- An interface may invoke a callback and then continue doing substantial work.
- CPS can be entirely synchronous; passing a continuation does not imply scheduling, parallel execution, or delayed execution.
- An asynchronous system may use promises or generated state machines rather than a uniform CPS representation.
In an event loop, a continuation-like callback may run only after an earlier operation yields control. Scheduling determines when it runs; CPS describes how subsequent computation is represented.
Use in compilers and interpreters
CPS is useful as an intermediate representation because it exposes evaluation order, function calls, and control transfers in a relatively uniform form. Operations such as branches and exception transfers can be represented through continuation invocations.
A compiler may use this structure to support:
- Inlining and simplification of continuation calls.
- Analysis of where control can flow.
- Specialized representations for continuations that do not escape.
- Transformations involving exceptions and nonlocal control.
- Conversion of function-based control structures into explicit blocks or jumps.
CPS does not require every continuation to become a heap-allocated object. A compiler can represent a locally used continuation as a label or basic block when its use permits this. More general continuations may need explicit environments and allocation.
Defunctionalization is a related transformation that replaces a family of function values with tagged data describing the possible functions, together with a dispatcher that interprets those descriptions. Applied to continuations, it can turn a CPS interpreter into an explicit abstract machine whose data structures represent pending work.
CPS is one of several approaches to representing control during compilation. Other intermediate forms retain more direct-style structure or use explicit control-flow graphs. The choice affects optimization techniques, implementation complexity, and debugging information.
Types and logical interpretation
For a direct-style function with input type and output type , a simplified CPS interface has the form:
Here, is the answer type: the type of the eventual result produced by the continuation and the surrounding computation.
The corresponding computation-level transformation is:
A complete translation in a typed language must also translate function types and other compound types consistently. The simplified interface therefore should not be treated as a full type translation for every higher-order program.
CPS translations connect programming-language semantics with logic. Under the Curry–Howard correspondence, some continuation translations correspond to double-negation translations. This relationship helps explain how continuation-based control operators can express forms of classical reasoning in typed calculi.
Historical development
Continuations developed through work on the mathematical semantics of programming languages and the implementation of control structures in the 1960s and early 1970s. Christopher Strachey and Christopher Wadsworth used continuations in denotational accounts of computation, while John C. Reynolds’s work on definitional interpreters helped establish continuation-based transformations as a systematic programming technique.
During the 1970s, work on Scheme by Gerald Jay Sussman and Guy L. Steele Jr. demonstrated the importance of procedure calls, continuations, and tail calls in language implementation. CPS subsequently became an influential technique in functional-language compilation and the study of control operators.
Practical limitations
Explicit CPS often makes source programs harder to read because straightforward expressions become nested functions. Error messages and stack traces may reflect transformed control structures rather than the original program.
Closure allocation, captured environments, and indirect calls can introduce runtime costs, although compiler analysis can eliminate or specialize many of them. Conversely, exposing control can enable optimizations that are harder to express in a less explicit representation.
Continuation lifetime is also significant. A stored continuation may keep captured values reachable, increasing memory retention and affecting garbage collection. Reinvoking a continuation that repeats side effects can produce behavior different from ordinary single-return execution. These issues require a distinction between continuations intended for one invocation and those designed to support repeated use.