StackOverflow2013

Note that there are some explanatory texts on larger screens.

plurals

POUsing Cont to acquire values from the future and the past
text
Body
copied!<p>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:</p> <pre><code>data Program m = Instruction (m ()) (Program m) | Control (m (Program m)) | Halt </code></pre> <p>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 <code>Instruction</code> inside a loop links to the loop's <code>Control</code> again.</p> <p>A bit more preliminary information. See <a href="https://github.com/DanBurton/bf-interp/blob/1150f2c1da54bfd4e2f09dafb44a7a82967c9693/Parser.hs" rel="nofollow noreferrer">this version on the github repo</a> for all the details.</p> <pre><code>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) </code></pre> <p>Here's what I tried:</p> <pre><code>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) </code></pre> <p>I figured I could somehow use continuations to communicate information from the <code>'['</code> case to the <code>']'</code> 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 <code>push</code> and <code>pop</code>. This compiles and runs, but the results are garbage.</p> <p>Can <code>Cont</code> be used to tie the knot appropriately for this situation? If not, then what technique should I use to implement <code>toProgram</code>?</p> <hr> <p>Note 1: I previously had a subtle logic error: <code>loopControl = branch is0</code> had the Bools reversed.</p> <p>Note 2: I managed to use <code>MonadFix</code> (as suggested by jberryman) with <code>State</code> to come up with a solution (see <a href="https://github.com/DanBurton/bf-interp/blob/master/Parser.hs" rel="nofollow noreferrer">the current state of the github repository</a>). I'd still like to know how this could be done with <code>Cont</code> instead.</p> <p>Note 3: My Racketeer mentor put <a href="https://github.com/jeapostrophe/exp/blob/master/bf-1.rkt" rel="nofollow noreferrer">a similar Racket program</a> together for me (see all revisions). Can his pipe/pipe-out technique be translated into Haskell using <code>Cont</code>?</p> <hr> <p><strong>tl;dr</strong> 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 <code>Cont</code> in Haskell. Can you show me how?</p>

Querying!

Guidance

An individual column

Larger individual text columns get their own page to allow for proper reading.

SQuiL has stopped working due to an internal error.

If you are curious you may find further information in the browser console, which is accessible through the devtools (F12).

Reload