Editing Continuation (section)

== Examples ==

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

<haskell>
 id :: a -> a
 id a = a
</haskell>

which in CPS becomes:

<haskell>
 idCPS :: a -> (a -> r) -> r
 idCPS a ret = ret a
</haskell>
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>
|-
|
<haskell>
 mysqrt :: Floating a => a -> a
 mysqrt a = sqrt a
 print (mysqrt 4) :: IO ()
</haskell>
||
<haskell>
 mysqrtCPS :: a -> (a -> r) -> r
 mysqrtCPS a k = k (sqrt a)
 mysqrtCPS 4 print :: IO ()
</haskell>
|-
|
<haskell>
 mysqrt 4 + 2 :: Floating a => a
</haskell>
||
<haskell>
 mysqrtCPS 4 (+ 2) :: Floating a => a
</haskell>
|-
|
<haskell>
 fac :: Integral a => a -> a
 fac 0 = 1
 fac n'@(n + 1) = n' * fac n
 fac 4 + 2 :: Integral a => a
</haskell>
||
<haskell>
 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
</haskell>
|}

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

=== Intermediate structures ===

The function <hask>Foreign.C.String.withCString</hask> converts a Haskell string to a C string.
But 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 signature <hask>withCString :: String -> (CString -> IO a) -> IO a</hask>.
This looks like continuation and the functions from continuation monad can be used,
e.g. for allocation of a whole array of pointers:
<haskell>
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)
</haskell>
However, the right associativity of <hask>mapM</hask> leads to inefficiencies here.

See:
* Cale Gibbard in Haskell-Cafe on [http://www.haskell.org/pipermail/haskell-cafe/2008-February/038963.html A handy little consequence of the Cont monad]

=== More general examples ===

Maybe it is confusing, that
* 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
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:
<haskell>
 newSentence :: Char -> Bool
 newSentence = flip elem ".?!"

 newSentenceCPS :: Char -> (Bool -> r) -> r
 newSentenceCPS c k = k (elem c ".?!")
</haskell>
but this is a rather uninteresting example. Let us see another one that uses at least recursion:
<haskell>
 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
</haskell>

You can download the Haskell source code (the original examples plus the new ones): [[Media:Continuation.hs|Continuation.hs]].

=== Monads as stylised continuation-passing ===

<blockquote>
After class today, a few of us were discussing the market for functional programmers. Talk turned to Clojure and Scala. A student who claims to understand monads said:

:<i>To understand monad tutorials, you really have to understand monads first.</i>

Priceless. The topic of today's class was mutual recursion. I think we are missing a base case here.

:<small>[http://www.cs.uni.edu/~wallingf/blog/archives/monthly/2013-02.html#e2013-02-12T14_53_00.htm Knowing and Doing: Student Wisdom on Monad Tutorials], Eugene Wallingford.</small>
</blockquote>

The partial application of <code>(>>=)</code> to monadic values means they can be used in the traditional continuation-passing style:

{|
!<center>Monadic style</center>!!<center>Continuation-passing style</center>
|-
|<haskell>
m     :: M T


h     :: U -> M V


(>>=) :: M a -> (a -> M b) -> M b
</haskell>
|<haskell>
m'    :: (T -> M b) -> M b
m'    =  (>>=) m

h'    :: U -> (V -> M b) -> M b
h' x  =  (>>=) (h x)

--
</haskell>
|}