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

12 Mar 2013

      ...
On Tue, 12 Mar 2013 12:53:37 +0100
Ertugrul Söylemez  wrote:
...
Dmitriy Matrosov  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  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