Personal tools

Continuation

From HaskellWiki

(Difference between revisions)
Jump to: navigation, search
(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)
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 abreviated name <code>fac</code> instead of <code>factorial</code>).
+
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 <code>ret</code> is the continuation argument (often also called <code>k</code>). A further comparison of direct and CPS style is below.
+
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, <code>fac</code> takes, as might be expected, a single argument. The CPS factorial, <code>facCPS</code> 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.
+
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, <code>mysqrt</code> calls <code>sqrt</code> without a continuation &mdash; 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, <hask>mysqrt</hask> calls <hask>sqrt</hask> without a continuation &mdash; 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 (<code>idCPS</code>, <code>mysqrtCPS</code>, <code>facCPS</code>)
+
* 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 uninteresing example. Let us see another one that uses at least recursion:
+
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 dowload the Haskell source code (the original examples plus the new ones): [[Media:Continuation.hs|Continuation.hs]].
+
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

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