# Continuation

### From HaskellWiki

EndreyMark (Talk | contribs) ((1) /*Imperative metaphors*/ split off from - →Functional metaphors: (2) Adding Daume III's ``what to do next'' metaphor.) |
EndreyMark (Talk | contribs) (→Citing haskellized Scheme examples from Wikipedia: Quoting Wikipedia's Continuation#Examples, but Scheme examples are translated to Haskell, and some straightforward modifications are made) |
||

Line 23: | Line 23: | ||

* HaWiki has a page on [http://haskell.cs.yale.edu/hawiki/ContinuationPassingStyle ContinuationPassingStyle], and some related pages linked from there, too. | * HaWiki has a page on [http://haskell.cs.yale.edu/hawiki/ContinuationPassingStyle ContinuationPassingStyle], and some related pages linked from there, too. | ||

* David Madore's [http://www.madore.org/~david/computers/callcc.html A page about <code>call/cc</code>] describes the concept, and his [http://www.madore.org/~david/programs/unlambda/ The Unlambda Programming Language] page shows how he implemented this construct in an esoteric functional programming language. | * David Madore's [http://www.madore.org/~david/computers/callcc.html A page about <code>call/cc</code>] describes the concept, and his [http://www.madore.org/~david/programs/unlambda/ The Unlambda Programming Language] page shows how he implemented this construct in an esoteric functional programming language. | ||

+ | |||

+ | == Examples == | ||

+ | |||

+ | === Citing haskellized Scheme examples from Wikipedia === | ||

+ | |||

+ | Quoting Wikipedia's [http://en.wikipedia.org/wiki/Continuation Continuation#Examples], but Scheme examples are translated to Haskell, and some straightforward modifications are made. | ||

+ | |||

+ | In the Haskell programming language, the simplest of direct-style functions is the identity function: | ||

+ | |||

+ | <haskell> | ||

+ | id :: a -> a | ||

+ | id a = a | ||

+ | </haskell> | ||

+ | |||

+ | which in CPS becomes: | ||

+ | |||

+ | <haskell> | ||

+ | idCPS :: a -> (a -> r) -> r | ||

+ | idCPS a ret = ret a | ||

+ | </haskell> | ||

+ | where ''ret'' is the continuation argument (often also called ''k''). A further comparison of direct and CPS style is below. | ||

+ | {| | ||

+ | !<center>Direct style</center>!!<center>Continuation passing style</center> | ||

+ | |- | ||

+ | | | ||

+ | <haskell> | ||

+ | mysqrt :: Floating a => a -> a | ||

+ | mysqrt a = sqrt a | ||

+ | print (mysqrt 4) :: IO () | ||

+ | </haskell> | ||

+ | || | ||

+ | <haskell> | ||

+ | mysqrtCPS :: a -> (a -> r) -> r | ||

+ | mysqrtCPS a k = k (sqrt a) | ||

+ | mysqrtCPS 4 print :: IO () | ||

+ | </haskell> | ||

+ | |- | ||

+ | | | ||

+ | <haskell> | ||

+ | mysqrt 4 + 2 :: Floating a => a | ||

+ | </haskell> | ||

+ | || | ||

+ | <haskell> | ||

+ | mysqrtCPS 4 (+ 2) :: Floating a => a | ||

+ | </haskell> | ||

+ | |- | ||

+ | | | ||

+ | <haskell> | ||

+ | fac :: Integral a => a -> a | ||

+ | fac 0 = 1 | ||

+ | fac n'@(n + 1) = n' * fac n | ||

+ | fac 4 + 2 :: Integral a => a | ||

+ | </haskell> | ||

+ | || | ||

+ | <haskell> | ||

+ | facCPS :: a -> (a -> r) -> r | ||

+ | facCPS 0 k = k 1 | ||

+ | facCPS n'@(n + 1) k = facCPS n $ \ret -> k (n' * ret) | ||

+ | facCPS 4 (+ 2) :: Integral a => a | ||

+ | </haskell> | ||

+ | |} | ||

+ | |||

+ | The translations shown above show that CPS is a global transformation; the direct-style factorial, <code>fac</code> takes, as might be expected, a single argument. The CPS factorial, <code>facCPS</code> 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. | ||

+ | |||

+ | As an exception, <code>mysqrt</code> calls <code>sqrt</code> without a continuation — here <code>sqrt</code> is considered a primitive [http://en.wikipedia.org/wiki/Operator_%28programming%29 operator]; that is, it is assumed that <code>sqrt</code> will compute its result in finite time and without abusing the stack. Operations considered primitive for CPS tend to be arithmetic, constructors, accessors, or mutators; any [http://en.wikipedia.org/wiki/Big_O_notation O(1) operation] will be considered primitive. | ||

== Continuation monad == | == Continuation monad == |

## Revision as of 18:10, 24 May 2006

## Contents |

## 1 General or introductory materials

### 1.1 Powerful metaphors, images

Here is a collection of short descriptions, analogies or metaphors, that illustrate this difficult concept, or an aspect of it.

#### 1.1.1 Imperative metaphors

- “In computing, a continuation is a representation of the execution state of a program (for example, the call stack) at a certain point in time” (Wikipedia's Continuation).
- “At its heart,
`call/cc`

is something like the`goto`

instruction (or rather, like a label for a`goto`

instruction); but a Grand High Exalted`goto`

instruction... The point about`call/cc`

is that it is not a*static*(lexical)`goto`

instruction but a*dynamic*one“ (David Madore's A page about`call/cc`

)

#### 1.1.2 Functional metaphors

- “Continuations represent the future of a computation, as a function from an intermediate result to the final result“ (Continuation monad section in Jeff Newbern's All About Monads)
- “The idea behind CPS is to pass around as a function argument what to do next“ (Yet Another Haskell Tutorial written by Hal Daume III, 4.6 Continuation Passing Style, pp 53-56))

### 1.2 Links

- Wikipedia's Continuation is a surprisingly good introductory material on this topic. See also Continuation-passing style.
- Yet Another Haskell Tutorial written by Hal Daume III contains a section on continuation passing style (4.6 Continuation Passing Style, pp 53-56)
- HaWiki has a page on ContinuationPassingStyle, and some related pages linked from there, too.
- David Madore's A page about
`call/cc`

describes the concept, and his The Unlambda Programming Language page shows how he implemented this construct in an esoteric functional programming language.

## 2 Examples

### 2.1 Citing haskellized Scheme examples from Wikipedia

Quoting Wikipedia's Continuation#Examples, but Scheme examples are translated to Haskell, and some straightforward modifications are made.

In the Haskell programming language, the simplest of direct-style functions is the identity function:

id :: a -> a id a = a

which in CPS becomes:

idCPS :: a -> (a -> r) -> r idCPS a ret = ret a

where *ret* is the continuation argument (often also called *k*). A further comparison of direct and CPS style is below.

mysqrt :: Floating a => a -> a mysqrt a = sqrt a print (mysqrt 4) :: IO () |
mysqrtCPS :: a -> (a -> r) -> r mysqrtCPS a k = k (sqrt a) mysqrtCPS 4 print :: IO () |

mysqrt 4 + 2 :: Floating a => a |
mysqrtCPS 4 (+ 2) :: Floating a => a |

fac :: Integral a => a -> a fac 0 = 1 fac n'@(n + 1) = n' * fac n fac 4 + 2 :: Integral a => a |
facCPS :: a -> (a -> r) -> r facCPS 0 k = k 1 facCPS n'@(n + 1) k = facCPS n $ \ret -> k (n' * ret) facCPS 4 (+ 2) :: Integral a => a |

The translations shown above show that CPS is a global transformation; the direct-style factorial, `fac`

takes, as might be expected, a single argument. The CPS factorial, `facCPS`

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.

As an exception, `mysqrt`

calls `sqrt`

without a continuation — here `sqrt`

is considered a primitive operator; that is, it is assumed that `sqrt`

will compute its result in finite time and without abusing the stack. Operations considered primitive for CPS tend to be arithmetic, constructors, accessors, or mutators; any O(1) operation will be considered primitive.

## 3 Continuation monad

- Jeff Newbern's All About Monads contains a section on it.
- Control.Monad.Cont is contained by Haskell Hierarchical Libraries.