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?

Hazan

Using Sentinels to capture mutants from days of future past. – Hydrostat

In all seriousness, do you even need to use Cont? Couldn't you just count the number of instructions to jump, perhaps doing a mulit-pass parse, where the extra passes associate the number of instructions to jump (along with direction) with the '[' and ']' characters? That is, [Char] -> [JumpInfo Char] and then use your parser on the result, where data JumpInfo = JumpInfo Char (Maybe Integer). – Hydrostat

Alternatively, you can leave your data the same (or mostly, haven't put much brainpower into this), and still use a 1-pass parser, and do a poor man's approach by doing it at runtime, where you iteratively move the tape one by one at until you reach your destination. While this would work, it would be a slow jump. – Hydrostat

@trinithis sure, but I'm much more interested in learning about Cont than I am in implementing this particular interpreter. – Hazan

What happens if you encounter a ] before you've encountered any [? – Scrotum

@benmachine that would be an error, so perhaps I should change the type of toProgram to be String -> Maybe TapeP. – Hazan

You could write toProgram :: String -> (TapeP, String) that returned the unconsumed string in the case of failure, so e.g. toProgram ">]>>" = (Instruction right Halt, "]>>"). Then when encountering a [, you just parse the next bit of the program, and check the unconsumed string starts with ], then glue the bits together. I tried to write an answer in this style, but it turned out to be fiddlier than I expected, so maybe this won't work out, I'm not sure. – Scrotum

The aforementioned racketeer finally blogged about his "pipe" solution to this issue, quite a good read: jeapostrophe.github.com/blog/2012/06/18/pipe – Hazan

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)

Tamberg

I finally got around to refactoring my code so I could keep both the MonadFix and Cont implementations in the repositroy. I can now officially confirm that your implementation passes the "hello world" example. I made a few slight tweaks, so that the loopControl will be shared at both the opening and closing brace. github.com/DanBurton/bf-interp/blob/master/ParseMonad/Cont.hs – Hazan

Yes, I tested the code before I posted. (That's the least I could do for 250 extra points.) Good thing I did, or I would have failed to see that toProgramStep builds the program in reverse. And nice tweak! – Tamberg

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.

Ms

I initially tried working a solution with State, and I knew something like MonadFix existed, though I couldn't quite find it. I'll definitely look into it in the next few days and let you know how it works out for me. – Hazan

interested to see what you find out. FWIW it looks like many instances of MonadCont are also MonadFix. – Ms

Here's what I've got, it feels right but is still producing erroneous output. I'll have to take a deeper look to figure out why that is. – Hazan

Interestingly, the output from the Cont version and the MonadFix version is identical. So either the same thing is wrong with both of them, or they are both correct and the problem lies elsewhere. – Hazan

I fixed it! There was a problem with going to the wrong branch of the loop. The Cont version still manifests this problem after changing the loopControl combinator, while the MonadFix version does not, so there is still something wrong with my Cont code. But the MonadFix version works! Thanks for the suggestion. – Hazan