Programs can be automatically transformed from direct style to CPS. Functional and logic compilers often use CPS as an intermediate representation where a compiler for an imperative or procedural programming language would use static single assignment form (SSA); however, SSA and CPS are equivalent (Kelsey 1995) [technically there are constructions in CPS that cannot be translated to SSA, but they do not occur in practice]. Functional compilers can also use Administrative Normal Form (ANF) instead of or in conjunction with CPS. CPS is used more frequently by compilers than by programmers as a local or global style.
The key to CPS is to remember that (a) every function takes an extra argument, 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! Some examples of code in direct style and the corresponding CPS style appear below. These examples are written in the Scheme programming language.
In order to call a procedure written in CPS from a procedure written in direct style, it is necessary to provide a continuation. In the example above, we might call
(factorial 10 identity). This will not work directly with the code above, because in the CPS version we are assuming that primitives like
* are in CPS, so to make the above example work in a Scheme system we would need to write new CPS versions of these primitives and use them instead:
cps* instead of
*, etc, where
(define (cps* x y k) (k (* x y))), etc. 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))))))) then
(define cps* (cps-prim *))
(define cps+ (cps-prim +)), etc.
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 take two continuations, so
(if (= a b) c d) in direct style would be translated to
(= a b (lambda (k c)) (lambda (k d))). Similarly, sometimes
if itself is not included in CPS, and instead a primitive function
%if is provided which takes three arguments: a boolean condition and two continuations 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.
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.
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 using the Swing UI framework:
As CPS and TCO eliminate the concept of an implicit function return, their combined use can eliminate the need for a runtime stack. Several compilers and interpreters for functional programming languages use this ability in novel ways.
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 compilation.
In mathematics, the Curry-Howard isomorphism between computer programs and mathematical proofs relates continuation-passing style translation to double-negation embeddings of classical logic into intuitionistic (constructive) logic. Classical logic itself relates to manipulating the continuation of programs directly, as in Scheme's call-with-current-continuation control operator.
US Patent Issued to International Business Machines on March 15 for "Method of Delegating Activity in Service Oriented Architectures Using Continuations" (North Carolina Inventor)
Mar 22, 2011; ALEXANDRIA, Va., March 22 -- United States Patent no. 7,908,162, issued on March 15, was assigned to International Business...