Continuing with continuations

As I alluded to in my previous post on continuations I was interested in them due to a suspicion that they might offer a nice way of dealing with an issue that came up with some code I was writing.

I spent some time the other night playing with continuations and I re-used the problem from an earlier post. There are a few differences this time around though, the main one is that there is no need to create a list of characters instead the goal is to string together the reading and the processing using continuations.

First off I should mention that I stuck -fno-monomorphism-restriction in my source file. Without it I got a lot of complaints from GHC.

I started with the most basic set of functions, one for reading a character and one for writing a character. I want the type to be ContT r IO Char for the former and ContT r IO () for the latter, but as always I don’t actually need to tell the compiler the exact types. Basically they correspond to getChat and putChar that way:

cpsGetChar = liftIO getChar
cpsPutChar c = liftIO $ putChar c

Running these two in sequence is done like this:

runContT (cpsGetChar >>= cpsPutChar) return

Running it just once isn’t enough though and I was pointed to the function forever by Cale in #haskell. It wasn’t actually in the version of GHC I have on my system (it’ll be in 6.7) so I had to define it:

forever x = x >> forever x

Using that it’s now easy to keep on reading an writing individual characters forever:

runContT (forever $ cpsGetChar >>= cpsPutChar) return

Since that doesn’t ever terminate it isn’t really what I want. Instead I want the two functions to be “mutually recursive with continuation”, for that I need to control the continuations more than return allows, I need to use callCC. First I started by rewriting the functions from above using callCC. That turned out like this:

cpsGetCharCC = callCC $
    \ k -> liftIO getChar >>= cpsPutCharCC >>= k
cpsPutCharCC c = callCC $
    \ k -> (liftIO $ putChar c) >> cpsGetCharCC >>= k

Running it should produce the same result as when using forever above:

runContT cpsGetCharCC return

Basically both functions defer calling the actual continuation until a call to the either cpsPutCharCC or cpsGetCharCC has been made. Still this never terminates, but rewriting the first function to terminate is simple:

cpsGetCharCC = do
    c <- liftIO getChar
    if c == 'q'
        then return ()
        else callCC $ \ k -> cpsPutCharCC c >>= k

Now, one thing that’s possible to do here, but which would be difficult to accomplish when mapping the handler on a list is to terminate in cpsPutCharCC. All that is required is to rewrite the handler similarly to what I just did with cpsGetCharCC:

cpsPutCharCC c = do
    liftIO $ putChar c
    if c == 'x'
        then return ()
        else callCC $ \ k -> cpsGetCharCC >>= k

Yes, there isn’t really that mcuh to all of this. Sorry if I’ve disappointed. The same functionality could be achieved using two regular mutually recursive functions:

mutGetChar = do
    c <- getChar
    if c == 'q'
        then return ()
        else mutPutChar c

mutPutChar c = do
    putChar c
    if c == 'x'
        then return ()
        else mutGetChar

And at this point I won’t do anything more except explain why I kind of like using continuations. It’s all about flexibility and composability. Say that we have a library for dealing with events and a developer wants to use it to do some processing of said events. I suspect that something that allows writing code like

runContT (setupWorld >>= receiveEvent handleEvent) postProcessWorld

is to prefer over a set of straight-forward functions, some which take “callbacks”. But hey! I might be wrong :-) I’m planning to see for myself!

Share

4 Comments

  1. Not to disparage your efforts, but your code strikes me as rather weird. What you’re essentially doing is, I think, at the end of each function, taking the continuation, and sticking something right before it (although that thing may in turn stick something right before it as well). That seems like no more than writing mutually recursive functions, only in a more verbose manner.

    The real neat thing about continuations, in my opinion, is that you can use ‘forever’, but still give the functions inside the loop the chance to break out (which I seem to recall Cale mentioning yesterday, but maybe it got lost in the shuffle). For example:

    foreverK fm = callCC (\k -> forever (fm k))
    
    getCharCC break = do c <- liftIO getChar
                         when (c == 'q') $ break ()
                         return c
    
    putCharCC break c = do liftIO $ putChar c
                           when (c == 'x') $ break ()
    
    getCharCC' break = do c <- liftIO getChar
                          when (c == 'q') $ break ()
                          putCharCC' break c
    
    putCharCC' break c = do liftIO $ putChar c
                            when (c == 'x') $ break ()
                            getCharCC' break
    
    test1 = foreverK (\k -> getCharCC k >>= putCharCC k)
    
    test2 = callCC getCharCC'
    

    So, there are two versions; one uses forever and the other just has mutually recursive functions. They’d both loop forever, except that we call ‘callCC’ outside of the infinite loop, and pass it in (as break), so that when one of the functions detects the exiting condition, it can return to the continuation of (essentially) the infinite loop itself, and terminate.

    You can also use the reader transformer to make things a bit less noisy:

    foreverK' m = callCC $ runReaderT (forever m)
    
    getCharCC'' = do c <- liftIO getChar
                     when (c == 'q') breakCC
                     return c
    
    putCharCC'' c = do liftIO $ putChar c
                       when (c == 'x') breakCC
    
    breakCC = ask >>= \k -> lift $ k ()
    
    test3 = foreverK' (getCharCC'' >>= putCharCC'')
    
  2. dolio, thanks for the comment. I did miss Cale’s comment about breaking out of forever.

    You’ve also prompted me to look at Reader, it’s one of the many monads I haven’t looked closer at.

  3. And if all you want is to jump out of the current chain of (>>=), then you don’t need all the complexity of continuations.

    For example: In playing with the DNA to RNA procedure from the ICFP2007 spec, there is a need to break out of the code to the end of the iteration.

    I used a “MaybeT” as the simplest solution [1]. Thus I could run (forever $ oneIter) and it would break out as needed by using the fail _ == mzero == Nothing command.

    If you need to pass out a result instead of a plain Nothing, then using ErrorT from Control.Monad.Error [2] which is actually ‘Either’ so (Left foo) is more informative than Nothing.

    [1] http://haskell.org/haskellwiki/New_monads/MaybeT [2] http://www.haskell.org/ghc/docs/latest/html/libraries/mtl/Control-Monad-Error.html

Leave a Reply

Your email address will not be published. Required fields are marked *

You may use these HTML tags and attributes: <a href="" title=""> <abbr title=""> <acronym title=""> <b> <blockquote cite=""> <cite> <code> <del datetime=""> <em> <i> <q cite=""> <strike> <strong>