Continuation-passing style

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 calls, 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. Compilers for functional and logic programming languages often use CPS as an intermediate representation where a compiler for an imperative or procedural programming language would use static single assignment form (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 thunks (described in the examples below) in CPS. CPS is used more frequently by compilers 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:

<span id="mwAdc"></span><span class="p" id="mwAdg">(</span><span class="k" id="mwAdk">define</span><span class="w" id="mwAdo"> </span><span class="p" id="mwAds">(</span><span class="nf" id="mwAdw">*&</span><span class="w" id="mwAd0"> </span><span class="nv" id="mwAd4">x</span><span class="w" id="mwAd8"> </span><span class="nv" id="mwAeA">y</span><span class="w" id="mwAeE"> </span><span class="nv" id="mwAeI">k</span><span class="p" id="mwAeM">)</span> <span class="w" id="mwAeQ"> </span><span class="p" id="mwAeU">(</span><span class="nf" id="mwAeY">k</span><span class="w" id="mwAec"> </span><span class="p" id="mwAeg">(</span><span class="nb" id="mwAek">*</span><span class="w" id="mwAeo"> </span><span class="nv" id="mwAes">x</span><span class="w" id="mwAew"> </span><span class="nv" id="mwAe0">y</span><span class="p" id="mwAe4">)))</span>

To do this in general, we might write a conversion routine:

<span id="mwAfI"></span><span class="p" id="mwAfM">(</span><span class="k" id="mwAfQ">define</span><span class="w" id="mwAfU"> </span><span class="p" id="mwAfY">(</span><span class="nf" id="mwAfc">cps-prim</span><span class="w" id="mwAfg"> </span><span class="nv" id="mwAfk">f</span><span class="p" id="mwAfo">)</span> <span class="w" id="mwAfs"> </span><span class="p" id="mwAfw">(</span><span class="k" id="mwAf0">lambda</span><span class="w" id="mwAf4"> </span><span class="nv" id="mwAf8">args</span> <span class="w" id="mwAgA"> </span><span class="p" id="mwAgE">(</span><span class="k" id="mwAgI">let</span><span class="w" id="mwAgM"> </span><span class="p" id="mwAgQ">((</span><span class="nf" id="mwAgU">r</span><span class="w" id="mwAgY"> </span><span class="p" id="mwAgc">(</span><span class="nb" id="mwAgg">reverse</span><span class="w" id="mwAgk"> </span><span class="nv" id="mwAgo">args</span><span class="p" id="mwAgs">)))</span> <span class="w" id="mwAgw"> </span><span class="p" id="mwAg0">((</span><span class="nb" id="mwAg4">car</span><span class="w" id="mwAg8"> </span><span class="nv" id="mwAhA">r</span><span class="p" id="mwAhE">)</span><span class="w" id="mwAhI"> </span><span class="p" id="mwAhM">(</span><span class="nb" id="mwAhQ">apply</span><span class="w" id="mwAhU"> </span><span class="nv" id="mwAhY">f</span> <span class="w" id="mwAhc"> </span><span class="p" id="mwAhg">(</span><span class="nb" id="mwAhk">reverse</span><span class="w" id="mwAho"> </span><span class="p" id="mwAhs">(</span><span class="nb" id="mwAhw">cdr</span><span class="w" id="mwAh0"> </span><span class="nv" id="mwAh4">r</span><span class="p" id="mwAh8">)))))))</span> <span class="p" id="mwAiA">(</span><span class="k" id="mwAiE">define</span><span class="w" id="mwAiI"> </span><span class="nv" id="mwAiM">*&</span><span class="w" id="mwAiQ"> </span><span class="p" id="mwAiU">(</span><span class="nf" id="mwAiY">cps-prim</span><span class="w" id="mwAic"> </span><span class="nb" id="mwAig">*</span><span class="p" id="mwAik">))</span> <span class="p" id="mwAio">(</span><span class="k" id="mwAis">define</span><span class="w" id="mwAiw"> </span><span class="nv" id="mwAi0">+&</span><span class="w" id="mwAi4"> </span><span class="p" id="mwAi8">(</span><span class="nf" id="mwAjA">cps-prim</span><span class="w" id="mwAjE"> </span><span class="nb" id="mwAjI">+</span><span class="p" id="mwAjM">))</span>

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 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 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 can be written in Haskell. A traditional implementation of the pyth function looks like this:

<span id="mwAkg"></span><span class="nf" id="mwAkk">pow2</span><span class="w" id="mwAko"> </span><span class="ow" id="mwAks">::</span><span class="w" id="mwAkw"> </span><span class="kt" id="mwAk0">Float</span><span class="w" id="mwAk4"> </span><span class="ow" id="mwAk8">-></span><span class="w" id="mwAlA"> </span><span class="kt" id="mwAlE">Float</span> <span class="nf" id="mwAlI">pow2</span><span class="w" id="mwAlM"> </span><span class="n" id="mwAlQ">x</span><span class="w" id="mwAlU"> </span><span class="ow" id="mwAlY">=</span><span class="w" id="mwAlc"> </span><span class="n" id="mwAlg">x</span><span class="w" id="mwAlk"> </span><span class="o" id="mwAlo">**</span><span class="w" id="mwAls"> </span><span class="mi" id="mwAlw">2</span> <span class="nf" id="mwAl0">add</span><span class="w" id="mwAl4"> </span><span class="ow" id="mwAl8">::</span><span class="w" id="mwAmA"> </span><span class="kt" id="mwAmE">Float</span><span class="w" id="mwAmI"> </span><span class="ow" id="mwAmM">-></span><span class="w" id="mwAmQ"> </span><span class="kt" id="mwAmU">Float</span><span class="w" id="mwAmY"> </span><span class="ow" id="mwAmc">-></span><span class="w" id="mwAmg"> </span><span class="kt" id="mwAmk">Float</span> <span class="nf" id="mwAmo">add</span><span class="w" id="mwAms"> </span><span class="n" id="mwAmw">x</span><span class="w" id="mwAm0"> </span><span class="n" id="mwAm4">y</span><span class="w" id="mwAm8"> </span><span class="ow" id="mwAnA">=</span><span class="w" id="mwAnE"> </span><span class="n" id="mwAnI">x</span><span class="w" id="mwAnM"> </span><span class="o" id="mwAnQ">+</span><span class="w" id="mwAnU"> </span><span class="n" id="mwAnY">y</span> <span class="nf" id="mwAnc">pyth</span><span class="w" id="mwAng"> </span><span class="ow" id="mwAnk">::</span><span class="w" id="mwAno"> </span><span class="kt" id="mwAns">Float</span><span class="w" id="mwAnw"> </span><span class="ow" id="mwAn0">-></span><span class="w" id="mwAn4"> </span><span class="kt" id="mwAn8">Float</span><span class="w" id="mwAoA"> </span><span class="ow" id="mwAoE">-></span><span class="w" id="mwAoI"> </span><span class="kt" id="mwAoM">Float</span> <span class="nf" id="mwAoQ">pyth</span><span class="w" id="mwAoU"> </span><span class="n" id="mwAoY">x</span><span class="w" id="mwAoc"> </span><span class="n" id="mwAog">y</span><span class="w" id="mwAok"> </span><span class="ow" id="mwAoo">=</span><span class="w" id="mwAos"> </span><span class="n" id="mwAow">sqrt</span><span class="w" id="mwAo0"> </span><span class="p" id="mwAo4">(</span><span class="n" id="mwAo8">add</span><span class="w" id="mwApA"> </span><span class="p" id="mwApE">(</span><span class="n" id="mwApI">pow2</span><span class="w" id="mwApM"> </span><span class="n" id="mwApQ">x</span><span class="p" id="mwApU">)</span><span class="w" id="mwApY"> </span><span class="p" id="mwApc">(</span><span class="n" id="mwApg">pow2</span><span class="w" id="mwApk"> </span><span class="n" id="mwApo">y</span><span class="p" id="mwAps">))</span>

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:

<span id="mwAp8"></span><span class="nf" id="mwAqA">pow2'</span><span class="w" id="mwAqE"> </span><span class="ow" id="mwAqI">::</span><span class="w" id="mwAqM"> </span><span class="kt" id="mwAqQ">Float</span><span class="w" id="mwAqU"> </span><span class="ow" id="mwAqY">-></span><span class="w" id="mwAqc"> </span><span class="p" id="mwAqg">(</span><span class="kt" id="mwAqk">Float</span><span class="w" id="mwAqo"> </span><span class="ow" id="mwAqs">-></span><span class="w" id="mwAqw"> </span><span class="n" id="mwAq0">a</span><span class="p" id="mwAq4">)</span><span class="w" id="mwAq8"> </span><span class="ow" id="mwArA">-></span><span class="w" id="mwArE"> </span><span class="n" id="mwArI">a</span> <span class="nf" id="mwArM">pow2'</span><span class="w" id="mwArQ"> </span><span class="n" id="mwArU">x</span><span class="w" id="mwArY"> </span><span class="n" id="mwArc">cont</span><span class="w" id="mwArg"> </span><span class="ow" id="mwArk">=</span><span class="w" id="mwAro"> </span><span class="n" id="mwArs">cont</span><span class="w" id="mwArw"> </span><span class="p" id="mwAr0">(</span><span class="n" id="mwAr4">x</span><span class="w" id="mwAr8"> </span><span class="o" id="mwAsA">**</span><span class="w" id="mwAsE"> </span><span class="mi" id="mwAsI">2</span><span class="p" id="mwAsM">)</span> <span class="nf" id="mwAsQ">add'</span><span class="w" id="mwAsU"> </span><span class="ow" id="mwAsY">::</span><span class="w" id="mwAsc"> </span><span class="kt" id="mwAsg">Float</span><span class="w" id="mwAsk"> </span><span class="ow" id="mwAso">-></span><span class="w" id="mwAss"> </span><span class="kt" id="mwAsw">Float</span><span class="w" id="mwAs0"> </span><span class="ow" id="mwAs4">-></span><span class="w" id="mwAs8"> </span><span class="p" id="mwAtA">(</span><span class="kt" id="mwAtE">Float</span><span class="w" id="mwAtI"> </span><span class="ow" id="mwAtM">-></span><span class="w" id="mwAtQ"> </span><span class="n" id="mwAtU">a</span><span class="p" id="mwAtY">)</span><span class="w" id="mwAtc"> </span><span class="ow" id="mwAtg">-></span><span class="w" id="mwAtk"> </span><span class="n" id="mwAto">a</span> <span class="nf" id="mwAts">add'</span><span class="w" id="mwAtw"> </span><span class="n" id="mwAt0">x</span><span class="w" id="mwAt4"> </span><span class="n" id="mwAt8">y</span><span class="w" id="mwAuA"> </span><span class="n" id="mwAuE">cont</span><span class="w" id="mwAuI"> </span><span class="ow" id="mwAuM">=</span><span class="w" id="mwAuQ"> </span><span class="n" id="mwAuU">cont</span><span class="w" id="mwAuY"> </span><span class="p" id="mwAuc">(</span><span class="n" id="mwAug">x</span><span class="w" id="mwAuk"> </span><span class="o" id="mwAuo">+</span><span class="w" id="mwAus"> </span><span class="n" id="mwAuw">y</span><span class="p" id="mwAu0">)</span> <span class="c1" id="mwAu4">-- Types a -> (b -> c) and a -> b -> c are equivalent, so CPS function</span> <span class="c1" id="mwAu8">-- may be viewed as a higher order function</span> <span class="nf" id="mwAvA">sqrt'</span><span class="w" id="mwAvE"> </span><span class="ow" id="mwAvI">::</span><span class="w" id="mwAvM"> </span><span class="kt" id="mwAvQ">Float</span><span class="w" id="mwAvU"> </span><span class="ow" id="mwAvY">-></span><span class="w" id="mwAvc"> </span><span class="p" id="mwAvg">((</span><span class="kt" id="mwAvk">Float</span><span class="w" id="mwAvo"> </span><span class="ow" id="mwAvs">-></span><span class="w" id="mwAvw"> </span><span class="n" id="mwAv0">a</span><span class="p" id="mwAv4">)</span><span class="w" id="mwAv8"> </span><span class="ow" id="mwAwA">-></span><span class="w" id="mwAwE"> </span><span class="n" id="mwAwI">a</span><span class="p" id="mwAwM">)</span> <span class="nf" id="mwAwQ">sqrt'</span><span class="w" id="mwAwU"> </span><span class="n" id="mwAwY">x</span><span class="w" id="mwAwc"> </span><span class="ow" id="mwAwg">=</span><span class="w" id="mwAwk"> </span><span class="nf" id="mwAwo">\</span><span class="n" id="mwAws">cont</span><span class="w" id="mwAww"> </span><span class="ow" id="mwAw0">-></span><span class="w" id="mwAw4"> </span><span class="n" id="mwAw8">cont</span><span class="w" id="mwAxA"> </span><span class="p" id="mwAxE">(</span><span class="n" id="mwAxI">sqrt</span><span class="w" id="mwAxM"> </span><span class="n" id="mwAxQ">x</span><span class="p" id="mwAxU">)</span> <span class="nf" id="mwAxY">pyth'</span><span class="w" id="mwAxc"> </span><span class="ow" id="mwAxg">::</span><span class="w" id="mwAxk"> </span><span class="kt" id="mwAxo">Float</span><span class="w" id="mwAxs"> </span><span class="ow" id="mwAxw">-></span><span class="w" id="mwAx0"> </span><span class="kt" id="mwAx4">Float</span><span class="w" id="mwAx8"> </span><span class="ow" id="mwAyA">-></span><span class="w" id="mwAyE"> </span><span class="p" id="mwAyI">(</span><span class="kt" id="mwAyM">Float</span><span class="w" id="mwAyQ"> </span><span class="ow" id="mwAyU">-></span><span class="w" id="mwAyY"> </span><span class="n" id="mwAyc">a</span><span class="p" id="mwAyg">)</span><span class="w" id="mwAyk"> </span><span class="ow" id="mwAyo">-></span><span class="w" id="mwAys"> </span><span class="n" id="mwAyw">a</span> <span class="nf" id="mwAy0">pyth'</span><span class="w" id="mwAy4"> </span><span class="n" id="mwAy8">x</span><span class="w" id="mwAzA"> </span><span class="n" id="mwAzE">y</span><span class="w" id="mwAzI"> </span><span class="n" id="mwAzM">cont</span><span class="w" id="mwAzQ"> </span><span class="ow" id="mwAzU">=</span><span class="w" id="mwAzY"> </span><span class="n" id="mwAzc">pow2'</span><span class="w" id="mwAzg"> </span><span class="n" id="mwAzk">x</span><span class="w" id="mwAzo"> </span><span class="p" id="mwAzs">(</span><span class="nf" id="mwAzw">\</span><span class="n" id="mwAz0">x2</span><span class="w" id="mwAz4"> </span><span class="ow" id="mwAz8">-></span><span class="w" id="mwA0A"> </span><span class="n" id="mwA0E">pow2'</span><span class="w" id="mwA0I"> </span><span class="n" id="mwA0M">y</span><span class="w" id="mwA0Q"> </span><span class="p" id="mwA0U">(</span><span class="nf" id="mwA0Y">\</span><span class="n" id="mwA0c">y2</span><span class="w" id="mwA0g"> </span><span class="ow" id="mwA0k">-></span><span class="w" id="mwA0o"> </span><span class="n" id="mwA0s">add'</span><span class="w" id="mwA0w"> </span><span class="n" id="mwA00">x2</span><span class="w" id="mwA04"> </span><span class="n" id="mwA08">y2</span><span class="w" id="mwA1A"> </span><span class="p" id="mwA1E">(</span><span class="nf" id="mwA1I">\</span><span class="n" id="mwA1M">anb</span><span class="w" id="mwA1Q"> </span><span class="ow" id="mwA1U">-></span><span class="w" id="mwA1Y"> </span><span class="n" id="mwA1c">sqrt'</span><span class="w" id="mwA1g"> </span><span class="n" id="mwA1k">anb</span><span class="w" id="mwA1o"> </span><span class="n" id="mwA1s">cont</span><span class="p" id="mwA1w">)))</span>

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, which is shipped with Glasgow Haskell Compiler (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:

<span id="mwA2o"></span><span class="nf" id="mwA2s">pow2_m</span><span class="w" id="mwA2w"> </span><span class="ow" id="mwA20">::</span><span class="w" id="mwA24"> </span><span class="kt" id="mwA28">Float</span><span class="w" id="mwA3A"> </span><span class="ow" id="mwA3E">-></span><span class="w" id="mwA3I"> </span><span class="kt" id="mwA3M">Cont</span><span class="w" id="mwA3Q"> </span><span class="n" id="mwA3U">a</span><span class="w" id="mwA3Y"> </span><span class="kt" id="mwA3c">Float</span> <span class="nf" id="mwA3g">pow2_m</span><span class="w" id="mwA3k"> </span><span class="n" id="mwA3o">a</span><span class="w" id="mwA3s"> </span><span class="ow" id="mwA3w">=</span><span class="w" id="mwA30"> </span><span class="n" id="mwA34">return</span><span class="w" id="mwA38"> </span><span class="p" id="mwA4A">(</span><span class="n" id="mwA4E">a</span><span class="w" id="mwA4I"> </span><span class="o" id="mwA4M">**</span><span class="w" id="mwA4Q"> </span><span class="mi" id="mwA4U">2</span><span class="p" id="mwA4Y">)</span> <span class="nf" id="mwA4c">pyth_m</span><span class="w" id="mwA4g"> </span><span class="ow" id="mwA4k">::</span><span class="w" id="mwA4o"> </span><span class="kt" id="mwA4s">Float</span><span class="w" id="mwA4w"> </span><span class="ow" id="mwA40">-></span><span class="w" id="mwA44"> </span><span class="kt" id="mwA48">Float</span><span class="w" id="mwA5A"> </span><span class="ow" id="mwA5E">-></span><span class="w" id="mwA5I"> </span><span class="kt" id="mwA5M">Cont</span><span class="w" id="mwA5Q"> </span><span class="n" id="mwA5U">a</span><span class="w" id="mwA5Y"> </span><span class="kt" id="mwA5c">Float</span> <span class="nf" id="mwA5g">pyth_m</span><span class="w" id="mwA5k"> </span><span class="n" id="mwA5o">a</span><span class="w" id="mwA5s"> </span><span class="n" id="mwA5w">b</span><span class="w" id="mwA50"> </span><span class="ow" id="mwA54">=</span><span class="w" id="mwA58"> </span><span class="kr" id="mwA6A">do</span> <span class="w" id="mwA6E"> </span><span class="n" id="mwA6I">a2</span><span class="w" id="mwA6M"> </span><span class="ow" id="mwA6Q"><-</span><span class="w" id="mwA6U"> </span><span class="n" id="mwA6Y">pow2_m</span><span class="w" id="mwA6c"> </span><span class="n" id="mwA6g">a</span> <span class="w" id="mwA6k"> </span><span class="n" id="mwA6o">b2</span><span class="w" id="mwA6s"> </span><span class="ow" id="mwA6w"><-</span><span class="w" id="mwA60"> </span><span class="n" id="mwA64">pow2_m</span><span class="w" id="mwA68"> </span><span class="n" id="mwA7A">b</span> <span class="w" id="mwA7E"> </span><span class="n" id="mwA7I">anb</span><span class="w" id="mwA7M"> </span><span class="ow" id="mwA7Q"><-</span><span class="w" id="mwA7U"> </span><span class="n" id="mwA7Y">cont</span><span class="w" id="mwA7c"> </span><span class="p" id="mwA7g">(</span><span class="n" id="mwA7k">add'</span><span class="w" id="mwA7o"> </span><span class="n" id="mwA7s">a2</span><span class="w" id="mwA7w"> </span><span class="n" id="mwA70">b2</span><span class="p" id="mwA74">)</span> <span class="w" id="mwA78"> </span><span class="n" id="mwA8A">r</span><span class="w" id="mwA8E"> </span><span class="ow" id="mwA8I"><-</span><span class="w" id="mwA8M"> </span><span class="n" id="mwA8Q">cont</span><span class="w" id="mwA8U"> </span><span class="p" id="mwA8Y">(</span><span class="n" id="mwA8c">sqrt'</span><span class="w" id="mwA8g"> </span><span class="n" id="mwA8k">anb</span><span class="p" id="mwA8o">)</span> <span class="w" id="mwA8s"> </span><span class="n" id="mwA8w">return</span><span class="w" id="mwA80"> </span><span class="n" id="mwA84">r</span>

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:

<span id="mwA9U"></span><span class="nf" id="mwA9Y">pyth_m</span><span class="w" id="mwA9c"> </span><span class="ow" id="mwA9g">::</span><span class="w" id="mwA9k"> </span><span class="kt" id="mwA9o">Float</span><span class="w" id="mwA9s"> </span><span class="ow" id="mwA9w">-></span><span class="w" id="mwA90"> </span><span class="kt" id="mwA94">Float</span><span class="w" id="mwA98"> </span><span class="ow" id="mwA-A">-></span><span class="w" id="mwA-E"> </span><span class="kt" id="mwA-I">Cont</span><span class="w" id="mwA-M"> </span><span class="n" id="mwA-Q">a</span><span class="w" id="mwA-U"> </span><span class="kt" id="mwA-Y">Float</span> <span class="nf" id="mwA-c">pyth_m</span><span class="w" id="mwA-g"> </span><span class="n" id="mwA-k">a</span><span class="w" id="mwA-o"> </span><span class="n" id="mwA-s">b</span><span class="w" id="mwA-w"> </span><span class="ow" id="mwA-0">=</span><span class="w" id="mwA-4"> </span><span class="n" id="mwA-8">callCC</span><span class="w" id="mwA_A"> </span><span class="o" id="mwA_E">$</span><span class="w" id="mwA_I"> </span><span class="nf" id="mwA_M">\</span><span class="n" id="mwA_Q">exitF</span><span class="w" id="mwA_U"> </span><span class="ow" id="mwA_Y">-></span><span class="w" id="mwA_c"> </span><span class="kr" id="mwA_g">do</span><span class="w" id="mwA_k"> </span><span class="c1" id="mwA_o">-- $ sign helps to avoid parentheses: a $ b + c == a (b + c)</span> <span class="w" id="mwA_s"> </span><span class="n" id="mwA_w">when</span><span class="w" id="mwA_0"> </span><span class="p" id="mwA_4">(</span><span class="n" id="mwA_8">b</span><span class="w" id="mwBAA"> </span><span class="o" id="mwBAE"><</span><span class="w" id="mwBAI"> </span><span class="mi" id="mwBAM">0</span><span class="w" id="mwBAQ"> </span><span class="o" id="mwBAU">||</span><span class="w" id="mwBAY"> </span><span class="n" id="mwBAc">a</span><span class="w" id="mwBAg"> </span><span class="o" id="mwBAk"><</span><span class="w" id="mwBAo"> </span><span class="mi" id="mwBAs">0</span><span class="p" id="mwBAw">)</span><span class="w" id="mwBA0"> </span><span class="p" id="mwBA4">(</span><span class="n" id="mwBA8">exitF</span><span class="w" id="mwBBA"> </span><span class="mf" id="mwBBE">0.0</span><span class="p" id="mwBBI">)</span><span class="w" id="mwBBM"> </span><span class="c1" id="mwBBQ">-- when :: Applicative f => Bool -> f () -> f ()</span> <span class="w" id="mwBBU"> </span><span class="n" id="mwBBY">a2</span><span class="w" id="mwBBc"> </span><span class="ow" id="mwBBg"><-</span><span class="w" id="mwBBk"> </span><span class="n" id="mwBBo">pow2_m</span><span class="w" id="mwBBs"> </span><span class="n" id="mwBBw">a</span> <span class="w" id="mwBB0"> </span><span class="n" id="mwBB4">b2</span><span class="w" id="mwBB8"> </span><span class="ow" id="mwBCA"><-</span><span class="w" id="mwBCE"> </span><span class="n" id="mwBCI">pow2_m</span><span class="w" id="mwBCM"> </span><span class="n" id="mwBCQ">b</span> <span class="w" id="mwBCU"> </span><span class="n" id="mwBCY">anb</span><span class="w" id="mwBCc"> </span><span class="ow" id="mwBCg"><-</span><span class="w" id="mwBCk"> </span><span class="n" id="mwBCo">cont</span><span class="w" id="mwBCs"> </span><span class="p" id="mwBCw">(</span><span class="n" id="mwBC0">add'</span><span class="w" id="mwBC4"> </span><span class="n" id="mwBC8">a2</span><span class="w" id="mwBDA"> </span><span class="n" id="mwBDE">b2</span><span class="p" id="mwBDI">)</span> <span class="w" id="mwBDM"> </span><span class="n" id="mwBDQ">r</span><span class="w" id="mwBDU"> </span><span class="ow" id="mwBDY"><-</span><span class="w" id="mwBDc"> </span><span class="n" id="mwBDg">cont</span><span class="w" id="mwBDk"> </span><span class="p" id="mwBDo">(</span><span class="n" id="mwBDs">sqrt'</span><span class="w" id="mwBDw"> </span><span class="n" id="mwBD0">anb</span><span class="p" id="mwBD4">)</span> <span class="w" id="mwBD8"> </span><span class="n" id="mwBEA">return</span><span class="w" id="mwBEE"> </span><span class="n" id="mwBEI">r</span>

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.

<span id="mwBE0"></span><span class="kd" id="mwBE4">function</span><span class="w" id="mwBE8"> </span><span class="nx" id="mwBFA">confirmName</span><span class="p" id="mwBFE">()</span><span class="o" id="mwBFI">:</span><span class="w" id="mwBFM"> </span><span class="nx" id="mwBFQ">none</span><span class="w" id="mwBFU"> </span><span class="p" id="mwBFY">{</span> <span class="w" id="mwBFc"> </span><span class="nx" id="mwBFg">fields</span><span class="p" id="mwBFk">.</span><span class="nx" id="mwBFo">name</span><span class="w" id="mwBFs"> </span><span class="o" id="mwBFw">=</span><span class="w" id="mwBF0"> </span><span class="nx" id="mwBF4">name</span><span class="p" id="mwBF8">;</span> <span class="w" id="mwBGA"> </span><span class="nx" id="mwBGE">framework</span><span class="p" id="mwBGI">.</span><span class="nx" id="mwBGM">Show_dialog_box</span><span class="p" id="mwBGQ">(</span><span class="nx" id="mwBGU">fields</span><span class="p" id="mwBGY">,</span><span class="w" id="mwBGc"> </span><span class="nx" id="mwBGg">confirmNameContinuation</span><span class="p" id="mwBGk">);</span> <span class="p" id="mwBGo">}</span> <span class="kd" id="mwBGs">function</span><span class="w" id="mwBGw"> </span><span class="nx" id="mwBG0">confirmNameContinuation</span><span class="p" id="mwBG4">(</span><span class="nx" id="mwBG8">fields</span><span class="o" id="mwBHA">:</span><span class="w" id="mwBHE"> </span><span class="kt" id="mwBHI">Fields</span><span class="p" id="mwBHM">)</span><span class="o" id="mwBHQ">:</span><span class="w" id="mwBHU"> </span><span class="nx" id="mwBHY">none</span><span class="w" id="mwBHc"> </span><span class="p" id="mwBHg">{</span> <span class="w" id="mwBHk"> </span><span class="nx" id="mwBHo">name</span><span class="w" id="mwBHs"> </span><span class="o" id="mwBHw">=</span><span class="w" id="mwBH0"> </span><span class="nx" id="mwBH4">fields</span><span class="p" id="mwBH8">.</span><span class="nx" id="mwBIA">name</span><span class="p" id="mwBIE">;</span> <span class="p" id="mwBII">}</span>

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 8 using the Swing UI framework:

<span id="mwBIg"></span><span class="kn" id="mwBIk">import</span><span class="w" id="mwBIo"> </span><span class="nn" id="mwBIs">javax.swing.SwingUtilities</span><span class="p" id="mwBIw">;</span> <span class="kt" id="mwBI0">void</span><span class="w" id="mwBI4"> </span><span class="nf" id="mwBI8">buttonHandler</span><span class="p" id="mwBJA">()</span><span class="w" id="mwBJE"> </span><span class="p" id="mwBJI">{</span> <span class="w" id="mwBJM"> </span><span class="c1" id="mwBJQ">// This is executing in the Swing UI thread.</span> <span class="w" id="mwBJU"> </span><span class="c1" id="mwBJY">// We can access UI widgets here to get query parameters.</span> <span class="w" id="mwBJc"> </span><span class="kt" id="mwBJg">int</span><span class="w" id="mwBJk"> </span><span class="n" id="mwBJo">parameter</span><span class="w" id="mwBJs"> </span><span class="o" id="mwBJw">=</span><span class="w" id="mwBJ0"> </span><span class="n" id="mwBJ4">getField</span><span class="p" id="mwBJ8">();</span> <span class="w" id="mwBKA"> </span><span class="n" id="mwBKE">Thread</span><span class="w" id="mwBKI"> </span><span class="n" id="mwBKM">t</span><span class="w" id="mwBKQ"> </span><span class="o" id="mwBKU">=</span><span class="w" id="mwBKY"> </span><span class="k" id="mwBKc">new</span><span class="w" id="mwBKg"> </span><span class="n" id="mwBKk">Thread</span><span class="p" id="mwBKo">(()</span><span class="w" id="mwBKs"> </span><span class="o" id="mwBKw">-></span><span class="w" id="mwBK0"> </span><span class="p" id="mwBK4">{</span> <span class="w" id="mwBK8"> </span><span class="c1" id="mwBLA">// This code runs in a separate thread.</span> <span class="w" id="mwBLE"> </span><span class="c1" id="mwBLI">// We can do things like access a database or a </span> <span class="w" id="mwBLM"> </span><span class="c1" id="mwBLQ">// blocking resource like the network to get data.</span> <span class="w" id="mwBLU"> </span><span class="kt" id="mwBLY">int</span><span class="w" id="mwBLc"> </span><span class="n" id="mwBLg">result</span><span class="w" id="mwBLk"> </span><span class="o" id="mwBLo">=</span><span class="w" id="mwBLs"> </span><span class="n" id="mwBLw">lookup</span><span class="p" id="mwBL0">(</span><span class="n" id="mwBL4">parameter</span><span class="p" id="mwBL8">);</span> <span class="w" id="mwBMA"> </span><span class="n" id="mwBME">SwingUtilities</span><span class="p" id="mwBMI">.</span><span class="na" id="mwBMM">invokeLater</span><span class="p" id="mwBMQ">(()</span><span class="w" id="mwBMU"> </span><span class="o" id="mwBMY">-></span><span class="w" id="mwBMc"> </span><span class="p" id="mwBMg">{</span> <span class="w" id="mwBMk"> </span><span class="c1" id="mwBMo">// This code runs in the UI thread and can use</span> <span class="w" id="mwBMs"> </span><span class="c1" id="mwBMw">// the fetched data to fill in UI widgets.</span> <span class="w" id="mwBM0"> </span><span class="n" id="mwBM4">setField</span><span class="p" id="mwBM8">(</span><span class="n" id="mwBNA">result</span><span class="p" id="mwBNE">);</span> <span class="w" id="mwBNI"> </span><span class="p" id="mwBNM">});</span> <span class="w" id="mwBNQ"> </span><span class="p" id="mwBNU">});</span> <span class="w" id="mwBNY"> </span><span class="n" id="mwBNc">t</span><span class="p" id="mwBNg">.</span><span class="na" id="mwBNk">start</span><span class="p" id="mwBNo">();</span> <span class="p" id="mwBNs">}</span>