In
functional programming
In computer science, functional programming is a programming paradigm where programs are constructed by applying and composing functions. It is a declarative programming paradigm in which function definitions are trees of expressions tha ...
, continuation-passing style (CPS) is a style of programming in which
control
Control may refer to:
Basic meanings Economics and business
* Control (management), an element of management
* Control, an element of management accounting
* Comptroller (or controller), a senior financial officer in an organization
* Controlli ...
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 computati ...
. This is contrasted with direct style, which is the usual style of programming.
Gerald Jay Sussman
Gerald Jay Sussman (born February 8, 1947) is the Panasonic Professor of Electrical Engineering at the Massachusetts Institute of Technology (MIT). He received his S.B. and Ph.D. degrees in mathematics from MIT in 1968 and 1973 respectively. H ...
and
Guy L. Steele, Jr. coined the phrase in
AI Memo
AI is artificial intelligence, intellectual ability in machines and robots.
Ai, AI or A.I. may also refer to:
Animals
* Ai (chimpanzee), an individual experimental subject in Japan
* Ai (sloth) or the pale-throated sloth, northern Amazonian ma ...
349 (1975), which sets out the first version of the
Scheme A scheme is a systematic plan for the implementation of a certain idea.
Scheme or schemer may refer to:
Arts and entertainment
* ''The Scheme'' (TV series), a BBC Scotland documentary series
* The Scheme (band), an English pop band
* ''The Schem ...
programming language.
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 numerous 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 science of deductively valid inferences or of logical truths. It is a formal science investigating how conclusions follow from prem ...
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. Most programming languages are text-based formal languages, but they may also be graphical. They are a kind of computer language.
The description of a programming ...
would use
static single assignment form In compiler design, static single assignment form (often abbreviated as SSA form or simply SSA) is a property of an intermediate representation (IR) that requires each variable to be assigned exactly once and defined before it is used. Existing var ...
(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
In computer science, A-normal form (abbreviated ANF) is an intermediate representation of programs in functional compilers.
In ANF, all arguments to a function must be trivial (constants or variables). That is, evaluation of each argument must h ...
(ANF) (but only for languages requiring eager evaluation), rather than with '
thunks' (described in the examples below) in CPS. CPS is used more frequently by
compiler
In computing, a compiler is a computer program that translates computer code written in one programming language (the ''source'' language) into another language (the ''target'' language). The name "compiler" is primarily used for programs tha ...
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
Scheme programming language; by convention the continuation function is represented as a parameter named "
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 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.
CPS 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 has pioneered a number of programming lan ...
In this section we will write a function
pyth
that calculates the 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 opposit ...
. A traditional implementation of the
pyth
function looks like this:
pow2 :: Float -> Float
pow2 a = a ** 2
add :: Float -> Float -> Float
add a b = a + b
pyth :: Float -> Float -> Float
pyth a b = sqrt (add (pow2 a) (pow2 b))
To transform the traditional function to CPS, we need to change its signature. The function will get another argument of function type, and its return type depends on that function:
pow2' :: Float -> (Float -> a) -> a
pow2' a cont = cont (a ** 2)
add' :: Float -> Float -> (Float -> a) -> a
add' a b cont = cont (a + b)
-- 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' a = \cont -> cont (sqrt a)
pyth' :: Float -> Float -> (Float -> a) -> a
pyth' a b cont = pow2' a (\a2 -> pow2' b (\b2 -> add' a2 b2 (\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 we reach the result of our calculations. 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, which is shipped with
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 (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 (; id, Jawa, ; jv, ꦗꦮ; su, ) is one of the Greater Sunda Islands in Indonesia. It is bordered by the Indian Ocean to the south and the Java Sea to the north. With a population of 151.6 million people, Java is the world's mo ...
8 using the
Swing
Swing or swinging may refer to:
Apparatus
* Swing (seat), a hanging seat that swings back and forth
* Pendulum, an object that swings
* Russian swing, a swing-like circus apparatus
* Sex swing, a type of harness for sexual intercourse
* Swing ri ...
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
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 ...
(TCO) will cause not only the constructed continuation to potentially grow during recursion, but also the
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, program stack, control stack, run-time stack, or mac ...
. 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 language
In computer science, functional programming is a programming paradigm where programs are constructed by applying and composing functions. It is a declarative programming paradigm in which function definitions are trees of expressions that ...
s 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
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 ...
but does have
first-class function
In computer science, a programming language is said to have first-class functions if it treats functions as first-class citizens. This means the language supports passing functions as arguments to other functions, returning them as the values from ...
s and
tail-call optimization. Without tail-call optimization, techniques such as
trampolining
Trampolining or trampoline gymnastics is a competitive 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 position to more co ...
, i.e. using a loop that iteratively invokes
thunk
In computer programming, a thunk is a subroutine used to inject a calculation into another subroutine. Thunks are primarily used to delay a calculation until its result is needed, or to insert operations at the beginning or end of the other sub ...
-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 (also written as ''λ''-calculus) is a formal system in mathematical logic for expressing computation based on function abstraction and application using variable binding and substitution. It is a universal model of computation th ...
, 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 A scheme is a systematic plan for the implementation of a certain idea.
Scheme or schemer may refer to:
Arts and entertainment
* ''The Scheme'' (TV series), a BBC Scotland documentary series
* The Scheme (band), an English pop band
* ''The Schem ...
):
(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
In mathematics, the Yoneda lemma is arguably the most important 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 (vie ...
. It is also similar to the embedding of
lambda calculus
Lambda calculus (also written as ''λ''-calculus) is a formal system in mathematical logic for expressing computation based on function abstraction and application using variable binding and substitution. It is a universal model of computation th ...
in
π-calculus.
Use in other fields
Outside of
computer science
Computer science is the study of computation, automation, and information. Computer science spans theoretical disciplines (such as algorithms, theory of computation, information theory, and automation) to Applied science, practical discipli ...
, 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 (from grc, σημαντικός ''sēmantikós'', "significant") is the study of reference, meaning, or truth. The term can be used to refer to subfields of several distinct disciplines, including philosophy, linguistics and comput ...
,
Chris Barker
Christopher Andrew Barker (2 March 1980 – 1 January 2020) was an English professional footballer who played as a defender. He represented Alfreton Town, Barnsley, Cardiff City, Stoke City, Colchester United, Queens Park Rangers, Plymouth Arg ...
and his collaborators have suggested that specifying the denotations of sentences using CPS might explain certain phenomena in
natural language
In neuropsychology, linguistics, and philosophy of language, a natural language or ordinary language is any language that has evolved naturally in humans through use and repetition without conscious planning or premeditation. Natural languages ...
.
In
mathematics
Mathematics is an area of knowledge that includes the topics of numbers, formulas and related structures, shapes and the spaces in which they are contained, and quantities and their changes. These topics are represented in modern mathematics ...
, 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 that is a subgroup.
When some object X is said to be embedded in another object Y, the embedding is g ...
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 class ...
into
intuitionistic (constructive) logic. Unlike the regular
double-negation translation In proof theory, a discipline within mathematical logic, double-negation translation, sometimes called negative translation, is a general approach for embedding classical logic into intuitionistic logic, typically by translating formulas to formulas ...
, 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, un ...
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
In the Scheme computer programming language, the procedure call-with-current-continuation, abbreviated call/cc, is used as a control flow operator. It has been adopted by several other programming languages.
Taking a function f as its only argu ...
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, a
Scheme A scheme is a systematic plan for the implementation of a certain idea.
Scheme or schemer may refer to:
Arts and entertainment
* ''The Scheme'' (TV series), a BBC Scotland documentary series
* The Scheme (band), an English pop band
* ''The Schem ...
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 Scheme (programming language) code
Articles with example Java code