Editing Continuation-passing style (section)

{{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.