Using Cont to acquire values from the future and the past

continuations, haskell, monadfix, monads, tying-the-knot

Solution

Forwards traveling state with a continuation monad looks like this:

Cont (fw -> r) a

Then the type of the argument to `cont` is

(a -> fw -> r) -> fw -> r

So you get a `fw` passed in from the past which you have to pass on to the continuation.

Backwards traveling state looks like this:

Cont (bw, r) a

Then the type of the argument to `cont` is

(a -> (bw, r)) -> (bw, r)

I.e. you get a `bw` from the continuation which you have to pass on to the past.

These can be combined into one continuation monad:

Cont (fw -> (bw, r)) a

There's a catch when applying this to your parser, because `toProgramStep` builds the program in reverse, so the list of ']' points is the forward state, and the list of '[' points is the backward state. Also, I got lazy and skipped the Maybe part, which should catch the pattern matching errors in `openBrace` and `closeBrace`.

type ParseState = Cont ([TapeP] -> ([TapeP], TapeP))

toProgram :: String -> TapeP
toProgram = snd . ($ []) . (`runCont` (\a _ -> ([], a))) . toProgramStep


openBrace :: ParseState TapeP -> ParseState TapeP
openBrace mcontinue = do
  continue <- mcontinue
  cont $ \k (break:bs) -> let (cs, r) = k (loopControl continue break) bs in (continue:cs, r)

closeBrace :: ParseState TapeP -> ParseState TapeP
closeBrace mbreak = do
  break <- mbreak
  cont $ \k bs -> let (continue:cs, r) = k (loopControl continue break) (break:bs) in (cs, r)

Problem

I'm writing a brainfuck interpreter in Haskell, and I came up with what I believe to be a very interesting description of a program: ``` data Program m = Instruction (m ()) (Program m) | Control (m (Program m)) | Halt ``` However, it's tricky to parse a textual representation of a brainfuck program into this data type. The problem arises with trying to correctly parse square brackets, because there is some knot-tying to do so that the final `Instruction` inside a loop links to the loop's `Control` again. A bit more preliminary information. See this version on the github repo for all the details. ``` type TapeM = StateT Tape IO type TapeP = Program TapeM type TapeC = Cont TapeP branch :: Monad m => m Bool -> Program m -> Program m -> Program m branch cond trueBranch falseBranch = Control ((\b -> if b then trueBranch else falseBranch) `liftM` cond) loopControl :: TapeP -> TapeP -> TapeP loopControl = branch (not <$> is0) ``` Here's what I tried: ``` toProgram :: String -> TapeP toProgram = (`runCont` id) . toProgramStep liftI :: TapeM () -> String -> TapeC TapeP liftI i cs = Instruction i <$> toProgramStep cs toProgramStep :: String -> TapeC TapeP toProgramStep ('>':cs) = liftI right cs -- similarly for other instructions toProgramStep ('[':cs) = push (toProgramStep cs) toProgramStep (']':cs) = pop (toProgramStep cs) push :: TapeC TapeP -> TapeC TapeP push mcontinue = do continue <- mcontinue cont (\breakMake -> loopControl continue (breakMake continue)) pop :: TapeC TapeP -> TapeC TapeP pop mbreak = do break <- mbreak cont (\continueMake -> loopControl (continueMake break) break) ``` I figured I could somehow use continuations to communicate information from the `'['` case to the `']'` case and vice-versa, but I don't have a firm enough grasp of Cont to actually do anything besides assemble wild guesses of something that looks like it might work, as seen above with `push` and `pop`. This compiles and runs, but the results are garbage. Can `Cont` be used to tie the knot appropriately for this situation? If not, then what technique should I use to implement `toProgram`? Note 1: I previously had a subtle logic error: `loopControl = branch is0` had the Bools reversed. Note 2: I managed to use `MonadFix` (as suggested by jberryman) with `State` to come up with a solution (see the current state of the github repository). I'd still like to know how this could be done with `Cont` instead. Note 3: My Racketeer mentor put a similar Racket program together for me (see all revisions). Can his pipe/pipe-out technique be translated into Haskell using `Cont`? tl;dr I managed to do this using MonadFix, and someone else managed to do it using Racket's continuation combinators. I'm pretty sure this can be done with `Cont` in Haskell. Can you show me how?

Original source