Day 12: Cont — Spaghetti

A continuation is “the rest of the program” represented as a value that you can do value things to: stick it in a variable, store it in a data structure, pass it around to other functions, as well as (if you want) actually cause it to run.

But wait! That’s just like the right hand side of >>= in every monad!

The Cont monad leaves executing the rest of the program up to the action on the left hand side of >>=: when you bind first_bit >>= rest_of_program, all that happens is that first_bit is called with rest_of_program as a extra parameter. >>= doesn’t then go on to execute rest_of_program.

So control of the rest of the program flow has been made entirely the responsibility of the monadic code, rather than being handled by the monad implementation itself — if you want the rest of the program to run, you have to run it yourself.

What does it look like to write programs? Using ContT IO as an example, you can lift IO actions, and nothing looks very different at all — lift performs the action and then invokes the rest of the program for you, so that this behaves as you’d expect:

prog :: ContT () IO ()
prog = do 
  lift $ putStrLn "Enter your name"  
  name <- lift $ getLine
  lift $ putStr "Hello to "
  lift $ putStrLn name
> runContT prog return
Enter your name
Ben
Hello to Ben

But here is something more interesting:

both (person1, person2) = ContT $ \rest_of_program -> do
  rest_of_program person1
  rest_of_program person2
prog2 = do
  lift $ putStrLn "Person 1 and person 2 enter your names"
  p1 <- lift $ getLine
  p2 <- lift $ getLine
  name <- both (p1, p2)
  lift $ putStr "Hello to "
  lift $ putStrLn name
> runContT prog2 return
Person 1 and person 2 enter your names
Ben
Phil
Hello to Ben
Hello to Phil

The program runs linearly (“normally”) up until both at which point the rest of the program runs twice, once for each person — both acts a bit like choosing from a two element list in [].

Actions are under no obligation to call rest_of_program at all or in any particular way (just like free monad interpreters, or other implementations of >>=) — they can not call it at all (for exception-like behaviour) or call it many times (for non-deterministic behaviour) or stash it away somewhere and do something else entirely (for conduit- or LogicT-style co-routines) or whatever.

Some Uses

http://blog.sigfpe.com/2011/10/quick-and-dirty-reinversion-of-control.html uses ContT to let a graphics library drive a Haskell process — the graphics library makes a callback, but the callback actually invokes a continuation, which is the next piece of the Haskell process. Callback-style coding can benefit from continuations in other situations too.

I’ve written an experimental DNS tree walker that lets a query return multiple times, both for answers already in the cache and for answers yet to be discovered — this is a bit like LogicT, but because of how DNS works, different results may appear at different times.

A return value subtlety

A monadic action’s type signature contains the type of the value that is bound to the next step in the computation — the “return value” if you like.

The type of the continuation contains not just that type, but another type: the type of the end result of the whole computation when all of the actions have been composed together: invoking a continuation action might not actually continue to the next bound action, but might instead forget the rest of the program and do something else entirely. But the program, to be well typed, still needs to end up with a result of the expected type, so that “something else” needs to end up with a result of that type.

In the examples above, that is the () in ContT () IO a.

This gives me a slightly awkward feeling of violation of modularity and composability, although that final value can be left as a free variable. For example, both has the inferred type where a1 is the free final type.

> :t both
both :: Monad m => (a, a) -> ContT a1 m a

Why you shouldn’t use this monad

Because it is very hard to reason about what on earth is going on.

For example, it is hard to do resource management — you can’t twice run a rest-of-program that reads from an open file handle and closes that handle; and if you never run it, that file handle becomes a resource leak.

Lots of the behaviour of other monads that I’ve talked about on other days can be implemented on top of continuations, and because that could happen anywhere in your monad code, you can end up in a spaghetti-like tangle.

Instead (in my opinion) it might be better to write your novel monad-like functionality as a monad (by implementing >>= or using free/effects libraries), and then layer application code on top of that — rather than making continuations available everywhere.