# Continuation

### From HaskellWiki

(Difference between revisions)

EndreyMark (Talk | contribs) (→Citing haskellized Scheme examples from Wikipedia: fixing a mistyped link (I mixed up Wikipedia's two articles on CPS) and more exact description about the modifications in the quoted text) |
EndreyMark (Talk | contribs) m (Typographic corrections: (1) spell-check with ispell; (2) using <hask> instead of <code> at all _Haskell_ examples, even if no visual difference can be seen. Scheme examples remain between <code>'s) |
||

Line 28: | Line 28: | ||

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

− | Quoting the Scheme examples (with their explanatory texts) from Wikipedia's [http://en.wikipedia.org/wiki/Continuation-passing_style#Examples Continuation-passing style] article, but Scheme examples are translated to Haskell, and some straightforward modifications are made to the explanations (e.g. replacing word ''Scheme'' with ''Haskell'', or using | + | Quoting the Scheme examples (with their explanatory texts) from Wikipedia's [http://en.wikipedia.org/wiki/Continuation-passing_style#Examples Continuation-passing style] article, but Scheme examples are translated to Haskell, and some straightforward modifications are made to the explanations (e.g. replacing word ''Scheme'' with ''Haskell'', or using abbreviated name <hask>fac</hask> instead of <code>factorial</code>). |

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

Line 43: | Line 43: | ||

idCPS a ret = ret a | idCPS a ret = ret a | ||

</haskell> | </haskell> | ||

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

{| | {| | ||

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

Line 85: | Line 85: | ||

|} | |} | ||

− | The translations shown above show that CPS is a global transformation; the direct-style factorial, < | + | The translations shown above show that CPS is a global transformation; the direct-style factorial, <hask>fac</hask> takes, as might be expected, a single argument. The CPS factorial, <hask>facCPS</hask> 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, < | + | As an exception, <hask>mysqrt</hask> calls <hask>sqrt</hask> without a continuation — here <hask>sqrt</hask> is considered a primitive [http://en.wikipedia.org/wiki/Operator_%28programming%29 operator]; that is, it is assumed that <hask>sqrt</hask> 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. | The quotation ends here. | ||

Line 94: | Line 94: | ||

Maybe it is confusing, that | Maybe it is confusing, that | ||

− | * the type of the (non-continuation) argument of the discussed functions (< | + | * the type of the (non-continuation) argument of the discussed functions (<hask>idCPS</hask>, <hask>mysqrtCPS</hask>, <hask>facCPS</hask>) |

* and the type of the argument of the continuations | * 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: | 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: | ||

Line 104: | Line 104: | ||

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

</haskell> | </haskell> | ||

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

<haskell> | <haskell> | ||

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

Line 121: | Line 121: | ||

</haskell> | </haskell> | ||

− | You can | + | You can download the Haskell source code (the original examples plus the new ones): [[Media:Continuation.hs|Continuation.hs]]. |

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

## Revision as of 01:31, 25 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 the Scheme examples (with their explanatory texts) from Wikipedia's Continuation-passing style article, but Scheme examples are translated to Haskell, and some straightforward modifications are made to the explanations (e.g. replacing word*Scheme*with

*Haskell*, or using abbreviated name

fac

`factorial`

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

ret

k

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 |

fac

facCPS

mysqrt

sqrt

sqrt

sqrt

The quotation ends here.

### 2.2 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 uninteresting 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 download the Haskell source code (the original examples plus the new ones): Continuation.hs.

## 3 Continuation monad

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