19
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 co