haskell - 使用 Cont 获取 future 和过去的值

Question

我正在用 Haskell 编写一个该死的解释器，我想出了一个我认为非常有趣的程序描述:

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

但是，将 Brainfuck 程序的文本表示解析为这种数据类型是很棘手的。尝试正确解析方括号时会出现问题，因为需要进行一些打结操作，以便循环内的最终 Instruction 再次链接到循环的 Control。

更多初步信息。请参阅this version on the 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 is0 bool 值颠倒了。

注 2:我设法将 MonadFix (按照 jberryman 的建议)与 State 结合使用来提出解决方案(请参阅 the current state of the github repository )。我仍然想知道如何使用 Cont 来完成此操作。

注3:我的Racketeer导师把a similar Racket program为我而在一起(查看所有修订)。他的管道/管道输出技术可以使用 Cont 翻译成 Haskell 吗？

<小时/>

tl;dr 我设法使用 MonadFix 做到了这一点，其他人也设法使用 Racket 的连续组合器做到了这一点。我很确定这可以通过 Haskell 中的 Cont 来完成。你能告诉我怎么做吗？

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 反向构建程序，因此“]”点列表是前向状态，“[”点列表是落后状态。另外，我很懒，跳过了 Maybe 部分，它应该捕获 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)