Logo Questions Linux Laravel Mysql Ubuntu Git Menu
 

Jumping forward with the continuation monad

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.

like image 229
Bob Avatar asked Aug 20 '14 18:08

Bob


1 Answers

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.

like image 182
bennofs Avatar answered Sep 20 '22 03:09

bennofs