Continuation-passing style

From Wikipedia for FEVERv2
Jump to navigation Jump to search

In functional programming, continuation-passing style (CPS) is a style of programming in which control is passed explicitly in the form of a continuation. Continuation-passing style_sentence_0

This is contrasted with direct style, which is the usual style of programming. Continuation-passing style_sentence_1

Gerald Jay Sussman and Guy L. Steele, Jr. coined the phrase in AI Memo 349 (1975), which sets out the first version of the Scheme programming language. Continuation-passing style_sentence_2

John C. Reynolds gives a detailed account of the numerous discoveries of continuations. Continuation-passing style_sentence_3

A function written in continuation-passing style takes an extra argument: an explicit "continuation", i.e. a function of one argument. Continuation-passing style_sentence_4

When the CPS function has computed its result value, it "returns" it by calling the continuation function with this value as the argument. Continuation-passing style_sentence_5

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. Continuation-passing style_sentence_6

Expressing code in this form makes a number of things explicit which are implicit in direct style. Continuation-passing style_sentence_7

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. Continuation-passing style_sentence_8

Programs can be automatically transformed from direct style to CPS. Continuation-passing style_sentence_9

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). Continuation-passing style_sentence_10

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). Continuation-passing style_sentence_11

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. Continuation-passing style_sentence_12

CPS is used more frequently by compilers than by programmers as a local or global style. Continuation-passing style_sentence_13

Examples Continuation-passing style_section_0

In CPS, each procedure takes an extra argument representing what should be done with the result the function is calculating. Continuation-passing style_sentence_14

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. Continuation-passing style_sentence_15

This style also makes it easy to express unusual control structures, like catch/throw or other non-local transfers of control. Continuation-passing style_sentence_16

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). Continuation-passing style_sentence_17

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. Continuation-passing style_sentence_18

Some examples of code in direct style and the corresponding CPS appear below. Continuation-passing style_sentence_19

These examples are written in the Scheme programming language; by convention the continuation function is represented as a parameter named "k": Continuation-passing style_sentence_20

Note that 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 we would need to write these CPS versions of primitives, with for instance *& defined by: Continuation-passing style_sentence_21

To do this in general, we might write a conversion routine: Continuation-passing style_sentence_22

In order 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. Continuation-passing style_sentence_23

In the example above (assuming that CPS-style primitives have been provided), we might call (factorial& 10 (lambda (x) (display x) (newline))). Continuation-passing style_sentence_24

There is some variety between compilers in the way primitive functions are provided in CPS. Continuation-passing style_sentence_25

Above we have 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 ...))). Continuation-passing style_sentence_26

Similarly, sometimes the if primitive itself 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. Continuation-passing style_sentence_27

The translations shown above show that CPS is a global transformation. Continuation-passing style_sentence_28

The direct-style factorial takes, as might be expected, a single argument; the CPS factorial& takes two: the argument and a continuation. Continuation-passing style_sentence_29

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. Continuation-passing style_sentence_30

Thus, to ensure the total absence of a function stack, the entire program must be in CPS. Continuation-passing style_sentence_31

CPS in Haskell Continuation-passing style_section_1

In this section we will write a function pyth that calculates the hypotenuse using the Pythagorean theorem. Continuation-passing style_sentence_32

A traditional implementation of the pyth function looks like this: Continuation-passing style_sentence_33

To transform the traditional function to CPS, we need to change its signature. Continuation-passing style_sentence_34

The function will get another argument of function type, and its return type depends on that function: Continuation-passing style_sentence_35

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. Continuation-passing style_sentence_36

And so on until we reach the result of our calculations. Continuation-passing style_sentence_37

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. Continuation-passing style_sentence_38

The mtl library, which is shipped with GHC, has the module Control.Monad.Cont. Continuation-passing style_sentence_39

This module provides the Cont type, which implements Monad and some other useful functions. Continuation-passing style_sentence_40

The following snippet shows the pyth' function using Cont: Continuation-passing style_sentence_41

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. Continuation-passing style_sentence_42

This function has one argument of a function type; that function argument accepts the function too, which discards all computations going after its call. Continuation-passing style_sentence_43

For example, let's break the execution of the pyth function if at least one of its arguments is negative returning zero: Continuation-passing style_sentence_44

Continuations as objects Continuation-passing style_section_2

See also: Callback (computer programming) Continuation-passing style_sentence_45

Programming with continuations can also be useful when a caller does not want to wait until the callee completes. Continuation-passing style_sentence_46

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. Continuation-passing style_sentence_47

This call returns right away, allowing the application code to continue while the user interacts with the dialog box. Continuation-passing style_sentence_48

Once the user presses the "OK" button, the framework calls the continuation function with the updated fields. Continuation-passing style_sentence_49

Although this style of coding uses continuations, it is not full CPS. Continuation-passing style_sentence_50

A similar idea can be used when the function must run in a different thread or on a different processor. Continuation-passing style_sentence_51

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. Continuation-passing style_sentence_52

This is in Java using the Swing UI framework: Continuation-passing style_sentence_53

Using Java 8 lambda notation above code shortens to (final keyword might be skipped): Continuation-passing style_sentence_54

Tail calls Continuation-passing style_section_3

Every call in CPS is a tail call, and the continuation is explicitly passed. Continuation-passing style_sentence_55

Using CPS without tail call optimization (TCO) will cause not only the constructed continuation to potentially grow during recursion, but also the call stack. Continuation-passing style_sentence_56

This is usually undesirable, but has been used in interesting ways—see the Chicken Scheme compiler. Continuation-passing style_sentence_57

As CPS and TCO eliminate the concept of an implicit function return, their combined use can eliminate the need for a run-time stack. Continuation-passing style_sentence_58

Several compilers and interpreters for functional programming languages use this ability in novel ways. Continuation-passing style_sentence_59

Use and implementation Continuation-passing style_section_4

Continuation passing style can be used to implement continuations and control flow operators in a functional language that does not feature first-class continuations but does have first-class functions and tail-call optimization. Continuation-passing style_sentence_60

Without tail-call optimization, techniques such as 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. Continuation-passing style_sentence_61

Writing code in CPS, while not impossible, is often error-prone. Continuation-passing style_sentence_62

There are various translations, usually defined as one- or two-pass conversions of pure lambda calculus, which convert direct style expressions into CPS expressions. Continuation-passing style_sentence_63

Writing in trampolined style, however, is extremely difficult; when used, it is usually the target of some sort of transformation, such as compilation. Continuation-passing style_sentence_64

Functions using more than one continuation can be defined to capture various control flow paradigms, for example (in Scheme): Continuation-passing style_sentence_65

It is of note that CPS transform is conceptually a Yoneda embedding. Continuation-passing style_sentence_66

It is also similar to the embedding of lambda calculus in π-calculus. Continuation-passing style_sentence_67

Use in other fields Continuation-passing style_section_5

Outside of computer science, CPS is of more general interest as an alternative to the conventional method of composing simple expressions into complex expressions. Continuation-passing style_sentence_68

For example, within linguistic semantics, Chris Barker and his collaborators have suggested that specifying the denotations of sentences using CPS might explain certain phenomena in natural language. Continuation-passing style_sentence_69

In mathematics, the Curry–Howard isomorphism between computer programs and mathematical proofs relates continuation-passing style translation to a variation of double-negation embeddings of classical logic into intuitionistic (constructive) logic. Continuation-passing style_sentence_70

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. Continuation-passing style_sentence_71

Accordingly, the result is obtained by passing the identity function as a continuation to the CPS-style expression, as in the above example. Continuation-passing style_sentence_72

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). Continuation-passing style_sentence_73

See also Continuation-passing style_section_6

Continuation-passing style_unordered_list_0

Credits to the contents of this page go to the authors of the corresponding Wikipedia page: style.