# Continuation

### From HaskellWiki

m (misprint correction) |
DanielDeKok (Talk | contribs) m (Fix a 404.) |
||

(3 intermediate revisions by 3 users not shown) | |||

Line 14: | Line 14: | ||

==== Functional metaphors ==== | ==== Functional metaphors ==== | ||

− | * Continuations represent the future of a computation, as a function from an intermediate result to the final result ([http://www.haskell.org/ | + | * Continuations represent the future of a computation, as a function from an intermediate result to the final result ([http://www.haskell.org/haskellwiki/All_About_Monads#The_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 ([http://darcs.haskell.org/yaht/yaht.pdf Yet Another Haskell Tutorial] written by Hal Daume III, 4.6 Continuation Passing Style, pp 53-56). [http://en.wikibooks.org/wiki/Haskell/YAHT/Type_basics#Continuation_Passing_Style It can be read also in wikified format]. | * The idea behind CPS is to pass around as a function argument what to do next ([http://darcs.haskell.org/yaht/yaht.pdf Yet Another Haskell Tutorial] written by Hal Daume III, 4.6 Continuation Passing Style, pp 53-56). [http://en.wikibooks.org/wiki/Haskell/YAHT/Type_basics#Continuation_Passing_Style It can be read also in wikified format]. | ||

* Rather than return the result of a function, pass one or more [[Higher order function | Higher Order Functions]] to determine what to do with the result. Yes, direct sum like things (or in generally, case analysis, managing cases, alternatives) can be implemented in CPS by passing ''more'' continuations. | * Rather than return the result of a function, pass one or more [[Higher order function | Higher Order Functions]] to determine what to do with the result. Yes, direct sum like things (or in generally, case analysis, managing cases, alternatives) can be implemented in CPS by passing ''more'' continuations. | ||

Line 104: | Line 104: | ||

<haskell> | <haskell> | ||

multiCont :: [(r -> a) -> a] -> ([r] -> a) -> a | multiCont :: [(r -> a) -> a] -> ([r] -> a) -> a | ||

− | multiCont xs = runCont ( | + | multiCont xs = runCont (mapM Cont xs) |

withCStringArray0 :: [String] -> (Ptr CString -> IO a) -> IO a | withCStringArray0 :: [String] -> (Ptr CString -> IO a) -> IO a | ||

Line 112: | Line 112: | ||

(\rs -> withArray0 nullPtr rs act) | (\rs -> withArray0 nullPtr rs act) | ||

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

− | However, the right associativity of <hask> | + | However, the right associativity of <hask>mapM</hask> leads to inefficiencies here. |

See: | See: | ||

Line 151: | Line 151: | ||

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

− | * Jeff Newbern's [http://haskell.org/ | + | * Jeff Newbern's [http://www.haskell.org/haskellwiki/All_About_Monads All About Monads] contains a [http://www.haskell.org/haskellwiki/All_About_Monads#The_Continuation_monad section] on it. |

− | * [http://haskell.org/ | + | * [http://hackage.haskell.org/packages/archive/mtl/latest/doc/html/Control-Monad-Cont.html Control.Monad.Cont] is contained by Haskell Hierarchical Libraries. |

== Delimited continuation == | == Delimited continuation == |

## Revision as of 06:29, 12 April 2012

## 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 ([1] 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). It can be read also in wikified format.
- Rather than return the result of a function, pass one or more Higher Order Functions to determine what to do with the result. Yes, direct sum like things (or in generally, case analysis, managing cases, alternatives) can be implemented in CPS by passing
*more*continuations.

### 1.2 External links

- The appropriate section of Haskell: Functional Programming with Types.
- 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). It can be read also in wikified format, thanks to Eric Kow.
- 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. - Continuations section of article Functional Programming For The Rest of Us, an introductory material to functional programming.
- Continuations and delimited control

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

`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

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 quotation ends here.

### 2.2 Intermediate structures

The functionBut it does not provide it for external use but restricts the use of the C string to a sub-procedure, because it will cleanup the C string after its use.

It has signatureThis looks like continuation and the functions from continuation monad can be used, e.g. for allocation of a whole array of pointers:

multiCont :: [(r -> a) -> a] -> ([r] -> a) -> a multiCont xs = runCont (mapM Cont xs) withCStringArray0 :: [String] -> (Ptr CString -> IO a) -> IO a withCStringArray0 strings act = multiCont (map withCString strings) (\rs -> withArray0 nullPtr rs act)

See:

- Cale Gibbard in Haskell-Cafe on A handy little consequence of the Cont monad

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

## 4 Delimited continuation

- Library/CC-delcont
- Generic Zipper and its applications, writing that "Zipper can be viewed as a delimited continuation reified as a data structure" (links added).

## 5 Linguistics

Chris Barker: Continuations in Natural Language

## 6 Applications

- ZipperFS
- Oleg Kiselyov's zipper-based file server/OS where threading and exceptions are all realized via delimited continuations.