Continuation
From HaskellWiki
(Difference between revisions)
EndreyMark (Talk  contribs) m (Typographic corrections: (1) spellcheck 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) 
EndreyMark (Talk  contribs) (→Functional metaphors: Adding HaWiki's short description, which can be important at managing cases, alternatives) 

Line 16:  Line 16:  
* “Continuations represent the future of a computation, as a function from an intermediate result to the final result“ ([http://www.nomaware.com/monads/html/contmonad.html#motivation Continuation monad] section in Jeff Newbern's All About Monads) 
* “Continuations represent the future of a computation, as a function from an intermediate result to the final result“ ([http://www.nomaware.com/monads/html/contmonad.html#motivation 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://www.isi.edu/~hdaume/htut/ Yet Another Haskell Tutorial] written by Hal Daume III, 4.6 Continuation Passing Style, pp 5356)) 
* “The idea behind CPS is to pass around as a function argument what to do next“ ([http://www.isi.edu/~hdaume/htut/ Yet Another Haskell Tutorial] written by Hal Daume III, 4.6 Continuation Passing Style, pp 5356)) 

−  +  * “Rather than return the result of a function, pass one or more [http://haskell.cs.yale.edu/hawiki/HigherOrderFunctions HigherOrderFunctions] to determine what to do with the result“ (HaWiki's [http://haskell.cs.yale.edu/hawiki/ContinuationPassingStyle ContinuationPassingStyle]). Yes, direct sum like things (or in generally, case analysis, managing cases, alternatives) can be implemented in CPS by passing ''more'' continuations. 

=== Links === 
=== Links === 

Revision as of 09:33, 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 thegoto
instruction (or rather, like a label for agoto
instruction); but a Grand High Exaltedgoto
instruction... The point aboutcall/cc
is that it is not a static (lexical)goto
instruction but a dynamic one“ (David Madore's A page aboutcall/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 5356))
 “Rather than return the result of a function, pass one or more HigherOrderFunctions to determine what to do with the result“ (HaWiki's ContinuationPassingStyle). Yes, direct sum like things (or in generally, case analysis, managing cases, alternatives) can be implemented in CPS by passing more continuations.
1.2 Links
 Wikipedia's Continuation is a surprisingly good introductory material on this topic. See also Continuationpassing style.
 Yet Another Haskell Tutorial written by Hal Daume III contains a section on continuation passing style (4.6 Continuation Passing Style, pp 5356)
 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 Continuationpassing 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 namefac
factorial
).
In the Haskell programming language, the simplest of directstyle 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 (noncontinuation) 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.