19

我正在用 Haskell 编写一个笨拙的解释器，我想出了我认为对程序非常有趣的描述：

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 is0布尔值反转了。

注意 2：我设法使用MonadFix（如 jberryman 建议的那样）State提出了一个解决方案（请参阅github 存储库的当前状态）。我仍然想知道如何做到这一点Cont。

注 3：我的 Racketeer 导师为我准备了一个类似的 Racket 程序（查看所有修订版）。他的管道/管道输出技术可以使用 翻译成 HaskellCont吗？

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

4

2 回答 2

14

带有 continuation monad 的前向旅行状态如下所示：

Cont (fw -> r) a

那么参数的类型cont是

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

所以你fw从过去得到一个传递，你必须传递给延续。

倒车状态如下：

Cont (bw, r) a

那么参数的类型cont是

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

即你bw从你必须传递给过去的延续中得到一个。

这些可以组合成一个延续单子：

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

将其应用于解析器时有一个问题，因为toProgramStep逆向构建程序，因此 ']' 点的列表是前向状态，而 '[' 点的列表是后向状态。另外，我变得懒惰并跳过了 Maybe 部分，它应该会捕获openBraceand中的模式匹配错误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)
于 2012-05-21T09:27:28.373 回答
4

因为我不喜欢这个答案，所以非常懒惰Cont，但MonadFix可能是您正在寻找的吗？State是一个实例，虽然不是Cont，它可以让你做一些看起来像的事情（使用“递归做”符号）：

{-# LANGUAGE DoRec #-}
parseInst str = do
    rec ctl <- parseInstructionsLinkingTo ctl str

这是我为我的演员库发现的解决方案：我们想要一个spawn返回生成演员邮箱的操作，但是我们如何启动相互通信的演员？还是可以访问自己邮箱的演员？

使用合适的MonadFix实例，我们可以这样做：

fork3 = do
    rec mb1 <- spawn $ actorSpamming mb2 mb3
        mb2 <- spawn $ actorSpamming mb1 mb2
        mb3 <- spawn $ actorSpamming mb2 mb3
    send "go" mb1

希望上面能给你一些想法。

于 2012-05-12T20:59:14.917 回答