# Continuation

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

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

Direct style
Continuation passing style
``` 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 (non-continuation) 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.