Editing Continuation-passing style

{{Short description|Programming style in which control is passed explicitly}}
In [[functional programming]], '''continuation-passing style''' ('''CPS''') is a style of programming in which [[control flow|control]] is passed explicitly in the form of a [[continuation]]. 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 (programming language)|Scheme]].<ref>{{cite journal
 |last1=Sussman |first1=Gerald Jay |author1-link=Gerald Jay Sussman |last2=Steele |first2=Guy L. Jr. |author2-link=Guy L. Steele Jr.
 |date=December 1975
 |title =Scheme: An interpreter for extended lambda calculus
 |journal=[[AI Memo]]
 |volume=349
 |page=19
 |quote=That is, in this '''continuation-passing programming style''', ''a function always "returns" its result by "sending" it to another function''. This is the key idea.
 |title-link=wikisource:Scheme: An interpreter for extended lambda calculus}}</ref><ref>{{cite journal
 |doi=10.1023/A:1010035624696
 |last1=Sussman |first1=Gerald Jay |author1-link=Gerald Jay Sussman |last2=Steele |first2=Guy L. Jr. |author2-link=Guy L. Steele Jr.
 |date=December 1998
 |title=Scheme: A Interpreter for Extended Lambda Calculus
 |url=https://www.cs.ru.nl/~freek/courses/tt-2011/papers/cps/HOSC-11-4-pp405-439.pdf
 |format=reprint
 |journal=Higher-Order and Symbolic Computation
 |volume=11
 |issue=4
 |pages=405–439
 |s2cid=18040106 |quote=We believe that this was the first occurrence of the term "'''continuation-passing style'''" in the literature. It has turned out to be an important concept in source code analysis and transformation for compilers and other metaprogramming tools. It has also inspired a set of other "styles" of program expression.
}}</ref>
[[John C. Reynolds]] gives a detailed account of the many discoveries of continuations.<ref>{{cite journal
 |last1=Reynolds |first1=John C. |author1-link=John C. Reynolds
 |year=1993
 |title=The Discoveries of Continuations
 |journal=LISP and Symbolic Computation
 |volume=6
 |issue=3–4
 |pages=233–248
 |doi=10.1007/bf01019459
 |citeseerx=10.1.1.135.4705 |s2cid=192862}}
</ref>

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]]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 programming|logic]] compilers often use CPS as an [[intermediate representation]] where a compiler for an [[imperative programming|imperative]] or [[procedural programming|procedural]] [[programming language]] would use [[static single assignment form]] (SSA).<ref name="Appel1998">{{cite journal |last1=Appel |first1=Andrew W. |author1-link=Andrew Appel |date=April 1998 |title=SSA is Functional Programming |journal=ACM SIGPLAN Notices |volume=33 |issue=4 |pages=17–20 |doi=10.1145/278283.278285 |citeseerx=10.1.1.34.3282 |s2cid=207227209}}</ref> 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).<ref name="Kelsey1995">{{cite journal |last1=Kelsey |first1=Richard A. |date=March 1995 |title=A Correspondence between Continuation Passing Style and Static Single Assignment Form |journal=ACM SIGPLAN Notices |volume=30 |issue=3 |pages=13–22 |doi=10.1145/202530.202532 |citeseerx=10.1.1.489.930}}</ref> Functional compilers can also use [[A-normal form]] (ANF) (but only for languages requiring eager evaluation), rather than with ''[[thunk]]s'' (described in the examples below) in CPS. CPS is used more frequently by [[compiler]]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 <code>catch/throw</code> 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 (programming)|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 (programming language)|Scheme]]; by convention the continuation function is represented as a parameter named "<code>k</code>":
{|
!{{center|Direct style}}!!{{center|Continuation passing style}}
|-valign="top"
|<syntaxhighlight lang=scheme>
(define (pyth x y)
 (sqrt (+ (* x x) (* y y))))</syntaxhighlight>
||
<syntaxhighlight lang=scheme>
(define (pyth& x y k)
 (*& x x (lambda (x2)
          (*& y y (lambda (y2)
                   (+& x2 y2 (lambda (x2py2)
                              (sqrt& x2py2 k))))))))
</syntaxhighlight>
|-valign="top"
|
<syntaxhighlight lang=scheme>
(define (factorial n)
 (if (= n 0)
     1     ; NOT tail-recursive
     (* n (factorial (- n 1)))))
</syntaxhighlight>
||
<syntaxhighlight lang=scheme>

(define (factorial& n k)
 (=& n 0 (lambda (b)
          (if b                    ; growing continuation
              (k 1)                ; in the recursive call
              (-& n 1 (lambda (nm1)
                       (factorial& nm1 (lambda (f)
                                        (*& n f k)))))))))
</syntaxhighlight>
|-valign="top"
|
<syntaxhighlight lang=scheme>
(define (factorial n)
 (f-aux n 1))
(define (f-aux n a)
 (if (= n 0)
     a        ; tail-recursive
     (f-aux (- n 1) (* n a))))
</syntaxhighlight>
||
<syntaxhighlight lang=scheme>
(define (factorial& n k) (f-aux& n 1 k))
(define (f-aux& n a k)
 (=& n 0 (lambda (b)
          (if b                    ; unmodified continuation
              (k a)                ; in the recursive call
              (-& n 1 (lambda (nm1) 
                       (*& n a (lambda (nta)
                                (f-aux& nm1 nta k)))))))))
</syntaxhighlight>
|}

In the CPS versions, the primitives used, like <code>+&</code> and <code>*&</code> 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 <code>*&</code> defined by:
<syntaxhighlight lang=scheme>
(define (*& x y k)
 (k (* x y)))
</syntaxhighlight>  To do this in general, we might write a conversion routine:
<syntaxhighlight lang=scheme>
(define (cps-prim f)
 (lambda args
  (let ((r (reverse args)))
   ((car r) (apply f
             (reverse (cdr r)))))))
(define *& (cps-prim *))
(define +& (cps-prim +))</syntaxhighlight>

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 <code>(factorial& 10 (lambda (x) (display x) (newline)))</code>.

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]]s to be called in the two possible cases, so the <code>(=& n 0 (lambda (b) (if b ...)))</code> call inside <code>f-aux&</code> definition above would be written instead as <code>(=& n 0 (lambda () (k a)) (lambda () (-& n 1 ...)))</code>. Similarly, sometimes the <code>if</code> primitive is not included in CPS, and instead a function <code>if&</code> 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 <code>pyth</code> to calculate a hypotenuse using the [[Pythagorean theorem]] can be written in [[Haskell]]. A traditional implementation of the <code>pyth</code> function looks like this:
<syntaxhighlight lang="haskell">
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))
</syntaxhighlight>

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:
<syntaxhighlight lang="haskell">
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)))
</syntaxhighlight>

First we calculate the square of ''a'' in <code>pyth'</code> 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 <code>id</code> function as a final argument which returns the value that was passed to it unchanged: <code>pyth' 3 4 id == 5.0</code>.

The mtl [[Library (computing)|library]], which is shipped with [[Glasgow Haskell Compiler]] (GHC), has the module <code>Control.Monad.Cont</code>. This module provides the Cont type, which implements Monad and some other useful functions. The following snippet shows the <code>pyth'</code> function using Cont:
<syntaxhighlight lang="haskell">
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
</syntaxhighlight>

Not only has the syntax become cleaner, but this type allows us to use a function <code>callCC</code> with type <code>MonadCont m => ((a -> m b) -> m a) -> m a</code>. 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 <code>pyth</code> function if at least one of its arguments is negative returning zero:
<syntaxhighlight lang="haskell">
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
</syntaxhighlight>

===Continuations as objects===
{{See also|Callback (computer programming)}}

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.{{Clarify|date=June 2019}}

<syntaxhighlight lang=javascript>
function confirmName() {
    fields.name = name;
    framework.Show_dialog_box(fields, confirmNameContinuation);
}

function confirmNameContinuation(fields) {
    name = fields.name;
}
</syntaxhighlight>
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 (programming language)|Java]] 8 using the [[Swing (Java)|Swing]] UI framework:

<syntaxhighlight lang=java>
void buttonHandler() {
    // This is executing in the Swing UI thread.
    // We can access UI widgets here to get query parameters.
    int parameter = getField();

    new Thread(() -> {
        // This code runs in a separate thread.
        // We can do things like access a database or a 
        // blocking resource like the network to get data.
        int result = lookup(parameter);

        javax.swing.SwingUtilities.invokeLater(() -> {
            // This code runs in the UI thread and can use
            // the fetched data to fill in UI widgets.
            setField(result);
        });
    }).start();
}
</syntaxhighlight>

==Tail calls==
Every call in CPS is a [[tail call]], 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]]. This is usually undesirable, but has been used in interesting ways; see the [[Chicken (Scheme implementation)#Design|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]] languages use this ability in novel ways.<ref>{{cite book |last1=Appel |first1=Andrew W. |author1-link=Andrew Appel |date=1992 |title=Compiling with Continuations |publisher=Cambridge University Press |isbn=0-521-41695-7}}</ref>

==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]]s but does have [[first-class function]]s and [[tail-call optimization]]. Without tail-call optimization, techniques such as [[trampoline (computers)|trampolining]], i.e., using a loop that iteratively invokes [[thunk]]-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]], 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 [[compiler|compilation]].

Functions using more than one continuation can be defined to capture various control flow paradigms, for example (in [[Scheme (programming language)|Scheme]]):
<syntaxhighlight lang=scheme>
(define (/& x y ok err)
 (=& y 0.0 (lambda (b)
            (if b
                (err (list "div by zero!" x y))
                (ok (/ x y))))))
</syntaxhighlight>

A CPS transform is conceptually a [[Yoneda embedding]].<ref>{{cite report |last1=Stay |first1=Mike |url=http://golem.ph.utexas.edu/category/2008/01/the_continuation_passing_trans.html |title=The Continuation Passing Transform and the Yoneda Embedding}}</ref> It is also similar to the embedding of [[lambda calculus]] in [[π-calculus]].<ref>Mike Stay, [http://golem.ph.utexas.edu/category/2009/09/the_pi_calculus_ii.html "The Pi Calculus II"]</ref><ref>{{cite CiteSeerX |first1=Gérard |last1=Boudol |year=1997 |citeseerx=10.1.1.52.6034 |title=The π-Calculus in Direct Style}}</ref>

==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 (linguist)|Chris Barker]] and his collaborators have suggested that specifying the denotations of sentences using CPS might explain certain phenomena in [[natural language]].<ref>{{Cite journal |last1=Barker |first1=Chris |date=2002-09-01 |title=Continuations and the Nature of Quantification |journal=Natural Language Semantics |volume=10 |issue=3 |pages=211–242 |language=en |doi=10.1023/A:1022183511876 |s2cid=118870676 |issn=1572-865X |url=http://www.semanticsarchive.net/Archive/902ad5f7/barker.continuations.pdf}}</ref>

In [[mathematics]], the [[Curry–Howard isomorphism]] between computer programs and mathematical proofs relates continuation-passing style translation to a variation of double-negation [[embedding]]s of [[classical logic]] into [[intuitionistic logic|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]] 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).<ref>{{cite book
 |last1=Griffin |first1=Timothy
 |date=January 1990
 |title=Proceedings of the 17th ACM SIGPLAN-SIGACT symposium on Principles of programming languages - POPL '90
 |chapter=A formulae-as-type notion of control
 |volume=17
 |pages=47–58
 |doi=10.1145/96709.96714
 |isbn=978-0-89791-343-0
 |s2cid=3005134
}}</ref>

==See also==
*[[Tail recursion#Through trampolining|Tail recursion through trampolining]]

==Notes==
{{Reflist}}

==References==
*Continuation Passing C (CPC) - [http://www.pps.univ-paris-diderot.fr/~kerneis/software/ programming language for writing concurrent systems], designed and developed by Juliusz Chroboczek and  Gabriel Kerneis. [https://github.com/kerneis/cpc github repository]
*The construction of a CPS-based compiler for [[ML (programming language)|ML]] is described in: {{cite book |last1=Appel |first1=Andrew W. |author1-link=Andrew Appel |year=1992 |title=Compiling with Continuations |publisher=Cambridge University Press |isbn=978-0-521-41695-5 |url=https://books.google.com/books?id=0Uoecu9ju4AC}}
*{{cite journal |last1=Danvy |first1=Olivier |author1-link=Olivier Danvy |last2=Filinski |first2=Andrzej |year=1992 |title=Representing Control, A Study of the CPS Transformation |journal=Mathematical Structures in Computer Science |volume=2 |issue=4 |pages=361–391 |doi=10.1017/S0960129500001535 |citeseerx=10.1.1.46.84 |s2cid=8790522}}
*[[Chicken Scheme compiler]], a [[Scheme (programming language)|Scheme]] to [[C (programming language)|C]] compiler that uses continuation-passing style for translating Scheme procedures into C functions while using the C-stack as the nursery for the [[Garbage collection (computer science)#Generational GC (aka Ephemeral GC)|generational garbage collector]]
*{{cite journal |last1=Kelsey |first1=Richard A. |date=March 1995 |title=A Correspondence between Continuation Passing Style and Static Single Assignment Form |journal=ACM SIGPLAN Notices |volume=30 |issue=3 |pages=13–22 |doi=10.1145/202530.202532 |citeseerx=10.1.1.3.6773}}
*{{cite journal |last1=Appel |first1=Andrew W. |author1-link=Andrew Appel |date=April 1998 |title=SSA is Functional Programming |journal=ACM SIGPLAN Notices |volume=33 |issue=4 |pages=17–20 |doi=10.1145/278283.278285 |url=http://www.cs.princeton.edu/~appel/papers/ssafun.ps |citeseerx=10.1.1.34.3282 |s2cid=207227209}}
*{{Cite journal |last1=Danvy |first1=Olivier |last2=Millikin |first2=Kevin |last3=Nielsen |first3=Lasse R. |year=2007 |title=On One-Pass CPS Transformations |journal=BRICS Report Series |page=24 |url=http://www.brics.dk/RS/07/6/ |id=RS-07-6 |issn=0909-0878 |access-date=26 October 2007}}
*{{cite book |first1=R. Kent |last1=Dybvig |author1-link=R. Kent Dybvig |year=2003 |url=http://www.scheme.com/tspl3/ |title=The Scheme Programming Language |publisher=Prentice Hall |page=64}} Direct link: [http://scheme.com/tspl3/further.html#./further:h4 "Section 3.4. Continuation Passing Style"].

{{DEFAULTSORT:Continuation-Passing Style}}
[[Category:Continuations]]
[[Category:Functional programming]]
[[Category:Implementation of functional programming languages]]
<!-- Hidden categories below -->
[[Category:Articles with example Java code]]
[[Category:Articles with example Scheme (programming language) code]]