Is there a way to capture the continuations in a do notation?

Question

Since the following do block:

do
  x <- foo
  y <- bar
  return x + y

is desugared to the following form:

foo >>= (\x -> bar >>= (\y -> return x + y))

aren't \x -> ... and y -> ... actually continuations here?

I was wondering if there is a way to capture the continuations in the definition of bind, but I can't get the types right. I.e:

data Pause a = Pause a | Stop

instance Monad Pause where
  return x = Stop
  m >>= k = Pause k         -- this doesn't work of course

Now I tried muddling around with the types:

data Pause a = Pause a (a -> Pause ???) | Stop
                       ------- k ------

But this doesn't work either. Is there no way to capture these implicit continuations?

Btw, I know about the Cont monad, I'm just experimenting and trying out stuff.

Answer 1

OK I'm not really sure, but let me put a few thoughts. I'm not quite sure what it ought to mean to capture the continuation. You could, for example, capture the whole do block in a structure:

{-# LANGUAGE ExistentialQuantification #-}

import Control.Monad

data MonadExp b = Return b | forall a. Bind (MonadExp a) (a -> MonadExp b)

instance Monad MonadExp where
    return x = Return x
    f >>= g = Bind f g

For example:

block :: MonadExp Int
block = do
    x <- return 1
    y <- return 2
    return $ x + y

instance Show (MonadExp a) where
    show (Return _) = "Return _"
    show (Bind _ _) = "Bind _ _"

print block
>> Bind _ _

And then evaluate the whole thing:

finish :: MonadExp a -> a
finish (Return x) = x
finish (Bind f g) = finish $ g (finish f)

print $ finish block
>> 3

Or step through it and see the parts

step :: MonadExp a -> MonadExp a
step (Return _) = error "At the end"
step (Bind f g) = g $ finish f

print $ step block
>> Bind _ _
print $ step $ step block
>> Return _

Well, now that I think about it more, that's probably not what you're asking. But maybe it'll help you think.

Answer 2

Well, I don't know if your lambdas are continuations in the strictest sense of the term, but they also look similar to this concept in my eye.

But note that if they are continuations, then the desugared monadic code is already written in continuation passing style (CPS). The usual notion of a control operator that "captures" a continuation is based on direct-style programs; the "captured" continuation is only implicit in the direct-style program, but the CPS transformation makes it explicit.

Since the desugared monadic code is already in CPS or something like it, well, maybe a way to frame your question is whether monadic code can express some of the control flow tricks that CPS code can. Typically, those tricks boil down to the idea that while under the CPS regime it is conventional for a function to finish by invoking its continuation, a function can choose to replace its continuation with another of its choosing. This replacement continuation can be constructed with a reference to the original continuation, so that it can in turn "restore" that original one if it chooses. So for example, coroutines are implemented as a mutual "replace/restore" cycle.

And looked at in this light, I think your answer is mostly no; CPS requires that in foo >>= bar, foo must be able to choose whether bar will be invoked at all, and foo must be abble to supply a substitute for bar, but (>>=) by itself does not offer a mechanism for foo to do this, and more importantly, (>>=) is in control of the execution flow, not foo. Some specific monads implement parts or all of it (for example, the Maybe monad allows foo to forego execution of bar by producing a Nothing result), but others don't.

Closest I could get is to forego (>>=) and use this instead:

-- | Execute action @foo@ with its "continuation" @bar@.
callCC :: Monad m => ((a -> m b) -> m b) -> (a -> m b) -> m b
foo `callCC` bar = foo bar

Here foo can choose whether bar will be used at all. But notice that this callCC is really just ($)!