HOME

TheInfoList



OR:

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