Jumping forward with the continuation monad

Question

It is possible to jump backward in a program with the continuation monad:

{-# LANGUAGE RecursiveDo #-}

import Control.Monad.Fix
import Control.Monad.Trans.Cont

setjmp = callCC (\c -> return (fix c))

backward = do
  l <- setjmp
  -- some code to be repeated forever
  l

But when I try to jump forward, it is not accepted by GHC:

forward = mdo
  l
  -- some dead code
  l <- setjmp  
  return ()

This does not work because there is no instance for MonadFix (ContT r m) for the continuation monad transformer ContT defined in Control.Monad.Trans.Cont. See Section 5.1 of Levent Erkok's thesis for further details.

Is there a way to encode forward jump without value recursion for the continuation monad?

Is there an alternative definition of ContT that has an instance for MonadFix (ContT r m)? There is an unpublished draft by Magnus Carlsson that makes such proposal but I am not sure what to do of it in my case.

I am not sure it is possible to do much better than @bennofs's suggestion (although you could probably define some helping functions to make it less awkward.) For example, what should mdo l; x <- lift $ getChar; l <- setjmp; print x do, and how would you implement it? — Ørjan Johansen
@ØrjanJohansen: Good point! (1) What it should do: execution should be suspended until the value of x is ready for print (in your example, it is never ready so it is suspended forever). (2) How do I implement it: This should be automatic by laziness. — Bob
Is there a somewhat more complete example of what you're trying to accomplish? You can jump back with arguments, maybe that's sufficient for your task? — John L
@JohnL: I just want to understand continuations. I read that continuations are enough to implement goto in a functional language. But I cannot see how to jump forward in Haskell. Please write an answer about "jumping with arguments". — Bob
Maybe you are asking about Monad Goto. Try this : hackage.haskell.org/package/GotoT-transformers-1.0.0.1/docs/… — viorior

bennofs bennofs · Accepted Answer · 2014-08-20T19:39:13

You can do it if you move your dead code inside the callCC, like this:

import Control.Monad.Cont

forward :: ContT () IO ()
forward = do
  callCC $ \skip -> do
    skip ()
    lift $ putStrLn "This is not executed"
  lift $ putStrLn "Control flow continues here"

main :: IO ()
main = runContT forward return

It's not possible to do exactly what you want. To see why, consider this example:

mdo
  l
  c <- lift getChar
  l <- if c == 'a' then setjmp else return (return ())
  lift $ putStrLn "end"

What should this do?

You can also jump back later to the code that was skipped. You just need to pass a continuation to the code you skipped. Using your example, goto L2: L1: some code; goto END; L2: goto L1; END: return can be implemented as:

import Control.Monad.Cont

forward :: ContT () IO ()
forward = do
  callCC $ \end -> do
    l1 <- callCC $ \l2 -> do
      callCC $ \l1 -> l2 l1
      liftIO $ putStrLn "In L1"
      end ()
    liftIO $ putStrLn "In L2"
    l1 ()
  liftIO $ putStrLn "End"

main :: IO ()
main = runContT forward return

Here we pass the continuation to the part we skipped (l1) back to the outer code so that it can jump there.

Jumping forward with the continuation monad

1 Answers