使用Cont从未来和过去获取值

Question

我正在Haskell写一个brainfuck解释器,我想出了一个我认为对程序非常有趣的描述:

data Program m = Instruction (m ()) (Program m)
               | Control (m (Program m))
               | Halt

但是,将brainfuck程序的文本表示解析为此数据类型是很棘手的.尝试正确解析方括号时会出现问题,因为有一些结点可以使Instruction循环中的最终内容Control再次链接到循环.

更多初步信息.有关所有详细信息,请参阅github repo上的此版本.

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)

这是我试过的:

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)

我想我可以以某种方式使用延续来将信息从'['案例传达到']'案例,反之亦然,但我没有足够的把握Cont来实际做任何事情,除了汇集对看起来可能有用的东西的猜测,如上所述push和pop.这编译并运行,但结果是垃圾.

可以Cont用来为这种情况适当打结？如果没有,那么我应该使用什么技术来实现toProgram？

---

注1:我之前有一个微妙的逻辑错误:loopControl = branch is0Bools逆转了.

注2:我设法使用MonadFix(如jberryman所建议的)State来提出解决方案(参见github存储库的当前状态).我仍然想知道如何才能做到这一点Cont.

注3:我的Racketeer导师为我制作了一个类似的Racket程序(参见所有修订版).他的管道/管道输出技术可以转换成Haskell Cont吗？

---

tl; dr我设法使用MonadFix做到了这一点,而其他人设法使用Racket的延续组合器来做到这一点.我很确定这可以Cont在Haskell中完成.你能告诉我怎么样吗？

Answer 1

具有延续monad的前进旅行状态如下所示:

Cont (fw -> r) a

那么参数的类型cont是

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

所以你fw从过去传入了你必须传递给延续的东西.

向后旅行状态如下:

Cont (bw, r) a

那么参数的类型cont是

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

也就是说,你得到的是bw你必须传承到过去的延续.

这些可以组合成一个延续monad:

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

将此应用于解析器时有一个问题,因为toProgramStep反向构建程序,因此']'点列表是正向状态,'['点列表是反向状态.另外,我懒惰,跳过也许部分,它应该抓住的图案匹配误差openBrace和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)