Difference between revisions of "Continuation"
EndreyMark (talk | contribs) (→Citing haskellized Scheme examples from Wikipedia: Quoting Wikipedia's Continuation#Examples, but Scheme examples are translated to Haskell, and some straightforward modifications are made) |
EndreyMark (talk | contribs) (Making the Haskell example downloadable: Continuation.hs) |
||
Line 88: | Line 88: | ||
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. You can dowload the Haskell source code of the example: [[Media:Continuation.hs|Continuation.hs]]. |
||
== Continuation monad == |
== Continuation monad == |
Revision as of 18:29, 24 May 2006
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 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
)
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. You can dowload the Haskell source code of the example: Continuation.hs.
Continuation monad
- Jeff Newbern's All About Monads contains a section on it.
- Control.Monad.Cont is contained by Haskell Hierarchical Libraries.