In
functional programming
In computer science, functional programming is a programming paradigm where programs are constructed by Function application, applying and Function composition (computer science), composing Function (computer science), functions. It is a declarat ...
, continuation-passing style (CPS) is a style of programming in which
control is passed explicitly in the form of a
continuation
In computer science, a continuation is an abstract representation of the control state of a computer program. A continuation implements ( reifies) the program control state, i.e. the continuation is a data structure that represents the computat ...
. This is contrasted with direct style, which is the usual style of programming.
Gerald Jay Sussman and
Guy L. Steele, Jr. coined the phrase in
AI Memo 349 (1975), which sets out the first version of the programming language
Scheme.
John C. Reynolds
John Charles Reynolds (June 1, 1935 – April 28, 2013) was an American computer scientist.
Education and affiliations
John Reynolds studied at Purdue University and then earned a Doctor of Philosophy (Ph.D.) in theoretical physics from Harvard U ...
gives a detailed account of the many discoveries of continuations.
A function written in continuation-passing style takes 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
In computer science, a tail call is a subroutine call performed as the final action of a procedure. If the target of a tail is the same subroutine, the subroutine is said to be tail recursive, which is a special case of direct recursion. Tail recur ...
s, which simply call 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 is the study of correct reasoning. It includes both formal and informal logic. Formal logic is the study of deductively valid inferences or logical truths. It examines how conclusions follow from premises based on the structure o ...
compilers often use CPS as an
intermediate representation
An intermediate representation (IR) is the data structure or code used internally by a compiler or virtual machine to represent source code. An IR is designed to be conducive to further processing, such as optimization and translation. A "good" ...
where a compiler for an
imperative or
procedural programming language
A programming language is a system of notation for writing computer programs.
Programming languages are described in terms of their Syntax (programming languages), syntax (form) and semantics (computer science), semantics (meaning), usually def ...
would use
static single assignment form
In compiler design, static single assignment form (often abbreviated as SSA form or simply SSA) is a type of intermediate representation (IR) where each variable is assigned exactly once. SSA is used in most high-quality optimizing compilers for ...
(SSA).
SSA is formally equivalent to a subset of CPS (excluding non-local control flow, which does not occur when CPS is used as intermediate representation).
Functional compilers can also use
A-normal form (ANF) (but only for languages requiring eager evaluation), rather than with ''
thunk
In computer programming
Computer programming or coding is the composition of sequences of instructions, called computer program, programs, that computers can follow to perform tasks. It involves designing and implementing algorithms, step-by- ...
s'' (described in the examples below) in CPS. CPS is used more frequently by
compiler
In computing, a compiler is a computer program that Translator (computing), translates computer code written in one programming language (the ''source'' language) into another language (the ''target'' language). The name "compiler" is primaril ...
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 known as 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, thus CPS makes explicit the order of evaluation as well as the control flow. Some examples of code in direct style and the corresponding CPS appear below. These examples are written in the programming language
Scheme; by convention the continuation function is represented as a parameter named "
k
":
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 requires writing 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 +))
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 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 is used the simplest convention, however sometimes Boolean primitives are provided that take two
thunk
In computer programming
Computer programming or coding is the composition of sequences of instructions, called computer program, programs, that computers can follow to perform tasks. It involves designing and implementing algorithms, step-by- ...
s 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 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.
CPS in Haskell
A function
pyth
to calculate a hypotenuse using the
Pythagorean theorem
In mathematics, the Pythagorean theorem or Pythagoras' theorem is a fundamental relation in Euclidean geometry between the three sides of a right triangle. It states that the area of the square whose side is the hypotenuse (the side opposite t ...
can be written in
Haskell
Haskell () is a general-purpose, statically typed, purely functional programming language with type inference and lazy evaluation. Designed for teaching, research, and industrial applications, Haskell pioneered several programming language ...
. A traditional implementation of the
pyth
function looks like this:
pow2 :: Float -> Float
pow2 x = x ** 2
add :: Float -> Float -> Float
add x y = x + y
pyth :: Float -> Float -> Float
pyth x y = sqrt (add (pow2 x) (pow2 y))
To transform the traditional function to CPS, its signature must be changed. The function will get another argument of function type, and its return type depends on that function:
pow2' :: Float -> (Float -> a) -> a
pow2' x cont = cont (x ** 2)
add' :: Float -> Float -> (Float -> a) -> a
add' x y cont = cont (x + y)
-- Types a -> (b -> c) and a -> b -> c are equivalent, so CPS function
-- may be viewed as a higher order function
sqrt' :: Float -> ((Float -> a) -> a)
sqrt' x = \cont -> cont (sqrt x)
pyth' :: Float -> Float -> (Float -> a) -> a
pyth' x y cont = pow2' x (\x2 -> pow2' y (\y2 -> add' x2 y2 (\anb -> sqrt' anb cont)))
First we calculate the square of ''a'' in
pyth'
function and pass a lambda function as a continuation which will accept a square of ''a'' as a first argument. And so on until the result of the calculations are reached. To get the result of this function we can pass
id
function as a final argument which returns the value that was passed to it unchanged:
pyth' 3 4 id 5.0
.
The mtl
library
A library is a collection of Book, books, and possibly other Document, materials and Media (communication), media, that is accessible for use by its members and members of allied institutions. Libraries provide physical (hard copies) or electron ...
, which is shipped with
Glasgow Haskell Compiler
The Glasgow Haskell Compiler (GHC) is a native or machine code compiler for the functional programming language Haskell.
It provides a cross-platform software environment for writing and testing Haskell code and supports many extensions, libra ...
(GHC), has the module
Control.Monad.Cont
. This module provides the Cont type, which implements Monad and some other useful functions. The following snippet shows the
pyth'
function using Cont:
pow2_m :: Float -> Cont a Float
pow2_m a = return (a ** 2)
pyth_m :: Float -> Float -> Cont a Float
pyth_m a b = do
a2 <- pow2_m a
b2 <- pow2_m b
anb <- cont (add' a2 b2)
r <- cont (sqrt' anb)
return r
Not only has the syntax become cleaner, but this type allows us to use a function
callCC
with type
MonadCont m => ((a -> m b) -> m a) -> m a
. This function has one argument of a function type; that function argument accepts the function too, which discards all computations going after its call. For example, let's break the execution of the
pyth
function if at least one of its arguments is negative returning zero:
pyth_m :: Float -> Float -> Cont a Float
pyth_m a b = callCC $ \exitF -> do -- $ sign helps to avoid parentheses: a $ b + c a (b + c)
when (b < 0 , , a < 0) (exitF 0.0) -- when :: Applicative f => Bool -> f () -> f ()
a2 <- pow2_m a
b2 <- pow2_m b
anb <- cont (add' a2 b2)
r <- cont (sqrt' anb)
return r
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
In the industrial design field of human–computer interaction, a user interface (UI) is the space where interactions between humans and machines occur. The goal of this interaction is to allow effective operation and control of the machine fro ...
(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()
function confirmNameContinuation(fields)
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 is one of the Greater Sunda Islands in Indonesia. It is bordered by the Indian Ocean to the south and the Java Sea (a part of Pacific Ocean) to the north. With a population of 156.9 million people (including Madura) in mid 2024, proje ...
8 using the
Swing UI framework:
void buttonHandler()
Tail calls
Every call in CPS is a
tail call
In computer science, a tail call is a subroutine call performed as the final action of a procedure. If the target of a tail is the same subroutine, the subroutine is said to be tail recursive, which is a special case of direct recursion. Tail recur ...
, and the continuation is explicitly passed. Using CPS without ''tail call optimization'' (TCO) will cause both the constructed continuation to potentially grow during recursion, and the
call stack
In computer science, a call stack is a Stack (abstract data type), stack data structure that stores information about the active subroutines and block (programming), inline blocks of a computer program. This type of stack is also known as an exe ...
. 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
In computer science, functional programming is a programming paradigm where programs are constructed by Function application, applying and Function composition (computer science), composing Function (computer science), functions. It is a declarat ...
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
continuation
In computer science, a continuation is an abstract representation of the control state of a computer program. A continuation implements ( reifies) the program control state, i.e. the continuation is a data structure that represents the computat ...
s but does have
first-class function
In computer science, a programming language is said to have first-class functions if it treats function (programming), functions as first-class citizens. This means the language supports passing functions as arguments to other functions, returning ...
s and
tail-call optimization. Without tail-call optimization, techniques such as
trampolining
Trampolining or trampoline gymnastics is a competitive Olympic Games, Olympic sport in which athletes perform acrobatics while bouncing on a trampoline. In competition, these can include simple jumps in the straight, pike, tuck, or straddle posit ...
, i.e., using a loop that iteratively invokes
thunk
In computer programming
Computer programming or coding is the composition of sequences of instructions, called computer program, programs, that computers can follow to perform tasks. It involves designing and implementing algorithms, step-by- ...
-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
In mathematical logic, the lambda calculus (also written as ''λ''-calculus) is a formal system for expressing computability, computation based on function Abstraction (computer science), abstraction and function application, application using var ...
, 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.
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))))))
A CPS transform is conceptually a
Yoneda embedding
In mathematics, the Yoneda lemma is a fundamental result in category theory. It is an abstract result on functors of the type ''morphisms into a fixed object''. It is a vast generalisation of Cayley's theorem from group theory (viewing a group as a ...
. It is also similar to the embedding of
lambda calculus
In mathematical logic, the lambda calculus (also written as ''λ''-calculus) is a formal system for expressing computability, computation based on function Abstraction (computer science), abstraction and function application, application using var ...
in
Ï€-calculus
In theoretical computer science, the -calculus (or pi-calculus) is a process calculus. The -calculus allows channel names to be communicated along the channels themselves, and in this matter, it is able to describe concurrent computations whose ...
.
Use in other fields
Outside of
computer science
Computer science is the study of computation, information, and automation. Computer science spans Theoretical computer science, theoretical disciplines (such as algorithms, theory of computation, and information theory) to Applied 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
Semantics is the study of linguistic Meaning (philosophy), meaning. It examines what meaning is, how words get their meaning, and how the meaning of a complex expression depends on its parts. Part of this process involves the distinction betwee ...
,
Chris Barker and his collaborators have suggested that specifying the denotations of sentences using CPS might explain certain phenomena in
natural language
A natural language or ordinary language is a language that occurs naturally in a human community by a process of use, repetition, and change. It can take different forms, typically either a spoken language or a sign language. Natural languages ...
.
In
mathematics
Mathematics is a field of study that discovers and organizes methods, Mathematical theory, theories and theorems that are developed and Mathematical proof, proved for the needs of empirical sciences and mathematics itself. There are many ar ...
, the
Curry–Howard isomorphism between computer programs and mathematical proofs relates continuation-passing style translation to a variation of double-negation
embedding
In mathematics, an embedding (or imbedding) is one instance of some mathematical structure contained within another instance, such as a group (mathematics), group that is a subgroup.
When some object X is said to be embedded in another object Y ...
s of
classical logic
Classical logic (or standard logic) or Frege–Russell logic is the intensively studied and most widely used class of deductive logic. Classical logic has had much influence on analytic philosophy.
Characteristics
Each logical system in this c ...
into
intuitionistic (constructive) logic. 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
Graph of the identity function on the real numbers
In mathematics, an identity function, also called an identity relation, identity map or identity transformation, is a function that always returns the value that was used as its argument, unc ...
as a continuation to the CPS 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 control operator, an observation due to Tim Griffin (using the closely related C control operator).
See also
*
Tail recursion through trampolining
Notes
References
*Continuation Passing C (CPC)
programming language for writing concurrent systems designed and developed by Juliusz Chroboczek and Gabriel Kerneis
github repository*The construction of a CPS-based compiler for
ML is described in:
*
*
Chicken Scheme compiler
Chicken (stylized as CHICKEN) is a programming language, specifically a compiler and Interpreter (computing), interpreter which implement a Dialect (computing), dialect of the programming language Scheme (programming language), Scheme, and which ...
, a
Scheme to
C 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"
{{DEFAULTSORT:Continuation-Passing Style
Continuations
Functional programming
Implementation of functional programming languages
Articles with example Java code
Articles with example Scheme (programming language) code