Using Cont to acquire values from the future and the past

Question

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?

Answer 1

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)

Answer 2

Being terribly lazy with this answer since I'm not comfortable with Cont, but is MonadFix perhaps what you're looking for? State is an instance, though not Cont, and it lets you do things that look like (using "recursive do" notation):

{-# LANGUAGE DoRec #-}
parseInst str = do
    rec ctl <- parseInstructionsLinkingTo ctl str

This was the solution I discovered for my actors library: we want a spawn operation that returns the spawned actor's mailbox, but then how can we launch mutually-communicating actors? Or an actor with access to its own mailbox?

With a suitable MonadFix instance we can do:

fork3 = do
    rec mb1 <- spawn $ actorSpamming mb2 mb3
        mb2 <- spawn $ actorSpamming mb1 mb2
        mb3 <- spawn $ actorSpamming mb2 mb3
    send "go" mb1

Hope above gives you ideas.