# Difference between revisions of "Continuation"

EndreyMark (talk | contribs) (Making the Haskell example downloadable: Continuation.hs) |
EndreyMark (talk | contribs) (Showing examples, where the type of the argument of the discussed function and type of the argument of the continuation do not coincide: CPS-ized length) |
||

Line 89: | Line 89: | ||

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

⚫ | |||

+ | The quotation ends here. |
||

+ | |||

+ | === More general examples === |
||

+ | |||

+ | Maybe it is confusing, that |
||

+ | * the type of the argument of the discussed functions (<code>idCPS</code>, <code>mysqrtCPS</code>, <code>facCPS</code>) |
||

+ | * and the type of the argument of the continuations |
||

+ | coincide in the above examples. It is not a necessity (it does not belong to the essence of the continuation concept), so I try to figure out an example which avoids this confusing coincidence: |
||

+ | <haskell> |
||

+ | newSentence :: Char -> Bool |
||

+ | newSentence = flip elem ".?!" |
||

+ | |||

+ | newSentenceCPS :: Char -> (Bool -> r) -> r |
||

+ | newSentenceCPS c k = k (elem c ".?!") |
||

+ | </haskell> |
||

+ | but this is a rather uninteresing example. Let us see another one that uses at least recursion: |
||

+ | <haskell> |
||

+ | mylength :: [a] -> Integer |
||

+ | mylength [] = 0 |
||

+ | mylength (_ : as) = succ (mylength as) |
||

+ | |||

+ | mylengthCPS :: [a] -> (Integer -> r) -> r |
||

+ | mylengthCPS [] k = k 0 |
||

+ | mylengthCPS (_ : as) k = mylengthCPS as (k . succ) |
||

+ | |||

+ | test8 :: Integer |
||

+ | test8 = mylengthCPS [1..2006] id |
||

+ | |||

+ | test9 :: IO () |
||

+ | test9 = mylengthCPS [1..2006] print |
||

+ | </haskell> |
||

+ | |||

⚫ | |||

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

## Revision as of 19:28, 24 May 2006

## Contents

## General or introductory materials

### Powerful metaphors, images

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

#### 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`

)

#### 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))

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

## Examples

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

The quotation ends here.

### More general examples

Maybe it is confusing, that

- the type of the argument of the discussed functions (
`idCPS`

,`mysqrtCPS`

,`facCPS`

) - and the type of the argument of the continuations

coincide in the above examples. It is not a necessity (it does not belong to the essence of the continuation concept), so I try to figure out an example which avoids this confusing coincidence:

```
newSentence :: Char -> Bool
newSentence = flip elem ".?!"
newSentenceCPS :: Char -> (Bool -> r) -> r
newSentenceCPS c k = k (elem c ".?!")
```

but this is a rather uninteresing example. Let us see another one that uses at least recursion:

```
mylength :: [a] -> Integer
mylength [] = 0
mylength (_ : as) = succ (mylength as)
mylengthCPS :: [a] -> (Integer -> r) -> r
mylengthCPS [] k = k 0
mylengthCPS (_ : as) k = mylengthCPS as (k . succ)
test8 :: Integer
test8 = mylengthCPS [1..2006] id
test9 :: IO ()
test9 = mylengthCPS [1..2006] print
```

You can dowload the Haskell source code (the original examples plus the new ones): Continuation.hs.

## Continuation monad

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