[Haskellbeginners] Suspend/resume computation using Cont monad and callCC
Dmitriy Matrosov
sgf.dma at gmail.com
Tue Mar 12 21:16:05 CET 2013
> On Tue, 12 Mar 2013 12:53:37 +0100
> Ertugrul Söylemez <es at ertes.de> wrote:
>
> > Dmitriy Matrosov <sgf.dma at gmail.com> wrote:
> >
> > I have two functions f and g, and i want them to execute in
> > following order: first function f runs, then suspends and passes
> > control to function g. Function g runs, then suspends and
> > "unpauses" function f. Function f finishes and passes control to
> > function g, which also finishes. Here is illustration ('o' means
> > start of function, dot means suspend and pass control to other
> > function, 'x' means end of function):
> >
> > [...]
> >
> > I want to implement this using Cont monad and callCC.
>
> Not directly answering your question, but what you need is called
> coroutines, and there are better monads for that purpose. This is how
> the Cont monads are defined:
>
> newtype Cont r a = Cont ((a > r) > r)
>
> But what you really need here is called a Coroutine monad:
>
> newtype Coroutine f a = Coroutine (Either (f (Coroutine f a)) a)
>
> Don't worry about that scary type, because if you look closely you
> will find that this is just Free as defined in the 'free' package:
>
> data Free f a
> = Free (f (Free f a))
>  Pure a
>
> On Tue, 12 Mar 2013 17:54:16 +0000
> Stephen Tetley <stephen.tetley at gmail.com> wrote:
>
> The resumption monad is even simpler, unfortunately I'm not aware of
> any beginner level tutorials.
>
> William Harrison at the University of Missouri has some papers
> introducing resumption monads but the presentations then move very
> quickly.
Thanks for suggestions! I'll try them (though, i suppose, to understand Free i
should read at least something about category theory first).
Anyway, i think, that i understand why my implementation works so and
can explain it.
First, i want to remind the implementation of callCC (omiting Cont
wrapper):
callCC f = \k > let g x = \_ > k x
in (f g) k
So, actually, callCC provides to function f continuation to monad
following callCC itself. This will be the key in my explanation.
Let's start with first question and explain how fT/gT pair works. Here
is the code from my previous mail with linenumbers:
type T r = ContT r (Writer String)
1 fT :: T r ()
2 fT = do
3 lift $ tell "I'm in f1\n"
4 k' < callCC gT
5 lift $ tell "I'm in f2\n"
6 k' undefined
7 lift $ tell "I'm in f3\n"
8
9 gT :: ((() > T r ()) > T r ()) > T r (() > T r ())
10 gT k = do
11 lift $ tell "I'm in g1\n"
12 callCC k
13 lift $ tell "I'm in g2\n"
14 return (\_ > return ())
And here is illustrations of first part of execution:

v
3 'f1'
4 k' < callCC gT <
\ 
> 11 'g1' 
12 callCC k 
/ 
5 'f2' < 
6 k' > 13 'g2' 
14 return (\_ > return ()) 
I.e. after point 'f1' function gT is called with continuation k to
line 5. Then after point 'g1' function gT calls this continuation k
and execution jumps back to line 5 in function f. But because
continuation k have been called in callCC, callCC throws continuation
k' to line 13 (in function g) into continuation k. Then after point
'f2' function f calls continuation k' to line 13. Function g resumes
execution and finishes. But what is the next continuation now? The one
supplied by (callCC gT) ! And this is again continuation to line 5 in
function f. Here i proceed to second illustration:
3 'f1'
4 k' < callCC gT <
5 'f2' 
6 k' 13 'g2' 
7 'f3' 14 return (\_ > return ()) 
So, function f executes again from point 'f2'. And meet continuation
k' again, but now k' is continuation returned by function gT at line
14. I.e. it is just (\_ > return ()). Thus, it does nothing and i
proceed to point 'f3'.
This explains track produced by Writer monad. But there is one more
question: why track produced using monad result differs?
Here is the code from my previous mail:
type M r = Cont r
fM :: M r [String]
fM = do
let xs' = "I'm in f1" : []
(ys, k') < callCC (gM xs')
let ys' = "I'm in f2" : ys
zs < k' ys'
let zs' = "I'm in f3" : zs
return zs'
gM :: [String]
> (([String], [String] > M r [String]) > M r [String])
> M r ([String], [String] > M r [String])
gM xs k = do
let xs' = "I'm in g1" : xs
ys < callCC (curry k xs')
let ys' = "I'm in g2" : ys
return (ys', \_ > return ys')
And if you "trace" its execution in the same manner, you'll notice the
answer: result of monad fM actually determined by call of continuation
k', which occurs during "second" function fM run. And during this
"second" run continuation k' will be (\_ > return ys'), where ys' is
from function gM. But when ys' had been evaluated in function gM,
second pass through 'f2' not yet happen! That's why it is missed from
the result as well.
Ugh, well.. that was useless, but still so fascinating :)

Dmitriy Matrosov
More information about the Beginners
mailing list