[Haskell-beginners] Suspend/resume computation using Cont monad and callCC

[Dmitriy Matrosov]

> 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 line-numbers:

      type T r            = ContT r (Writer String)

    1   fT :: T r ()
    2   fT                  = do
    3       lift $ tell "I'm in f-1\n"
    4       k' <- callCC gT
    5       lift $ tell "I'm in f-2\n"
    6       k' undefined
    7       lift $ tell "I'm in f-3\n"
    8
    9   gT :: ((() -> T r ()) -> T r ()) -> T r (() -> T r ())
    10  gT k                = do
    11      lift $ tell "I'm in g-1\n"
    12      callCC k
    13      lift $ tell "I'm in g-2\n"
    14      return (\_ -> return ())


And here is illustrations of first part of execution:

      |
      v
  3 'f-1'
  4 k' <- callCC gT <--------------------------------
            \                                       |
             -------> 11 'g-1'                      |
                      12 callCC k                   |
                    /                               |
  5 'f-2'  <--------                                |
  6 k' -------------> 13 'g-2'                      |
                      14 return (\_ -> return ()) ---

I.e. after point 'f-1' function gT is called with continuation k to
line 5. Then after point 'g-1' 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
'f-2' 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 'f-1'
  4 k' <- callCC gT <---------------------------------
  5 'f-2'                                            |
  6 k'                 13 'g-2'                      |
  7 'f-3'              14 return (\_ -> return ()) ---

So, function f executes again from point 'f-2'.  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 'f-3'.

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 f-1" : []
        (ys, k') <- callCC (gM xs')
        let ys' = "I'm in f-2" : ys
        zs <- k' ys'
        let zs' = "I'm in f-3" : 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 g-1" : xs
        ys <- callCC (curry k xs')
        let ys' = "I'm in g-2" : 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 'f-2' 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