Continuation

From HaskellWiki

(Difference between revisions)

Revision as of 00:09, 9 October 2006

1 General or introductory materials
- 1.1 Powerful metaphors, images
  - 1.1.1 Imperative metaphors
  - 1.1.2 Functional metaphors
- 1.2 Links
2 Examples
- 2.1 Citing haskellized Scheme examples from Wikipedia
- 2.2 More general examples
3 Continuation monad

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

instead of 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

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

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.

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.
HaWiki's MonadicContinuationPassingStyle and also MonadCont mentions also an interesting example: PythonGenerator.

Retrieved from "http://www.haskell.org/haskellwiki/Continuation"

Categories: Idioms | Glossary

@@ Line 9: / Line 9: @@
 ==== 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 [http://en.wikipedia.org/wiki/Continuation Continuation]).
+* 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 [http://en.wikipedia.org/wiki/Continuation Continuation]).
-*  “At its heart, <code>call/cc</code> is something like the <code>goto</code> instruction (or rather, like a label for a <code>goto</code> instruction); but a Grand High Exalted <code>goto</code> instruction... The point about <code>call/cc</code> is that it is not a ''static'' (lexical) <code>goto</code> instruction but a ''dynamic'' one“ (David Madore's [http://www.madore.org/~david/computers/callcc.html#sec_intro A page about <code>call/cc</code>])
+*  At its heart, <code>call/cc</code> is something like the <code>goto</code> instruction (or rather, like a label for a <code>goto</code> instruction); but a Grand High Exalted <code>goto</code> instruction... The point about <code>call/cc</code> is that it is not a ''static'' (lexical) <code>goto</code> instruction but a ''dynamic'' one (David Madore's [http://www.madore.org/~david/computers/callcc.html#sec_intro A page about <code>call/cc</code>])
 ==== Functional metaphors ====
-* “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 53-56))
+* 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 53-56))
-* “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.
+* 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 ===
@@ Line 130: / Line 130: @@
 [[Category:Idioms]]
+[[Category:Glossary]]

Personal tools

Views