使用Cont来获取未来和过去的价值 [英] Using Cont to acquire values from the future and the past

问题描述

$ b

 
 
 
 
 code> data程序m =指令（m（））（程序m）
 |控制（m（程序m））
 |暂停
  

然而，将脑子项目的文本表示解析为这种数据类型是非常棘手的。尝试正确解析方括号时会出现问题，因为有一些连接要这样做，以便循环内的最后一个指令链接到循环的再次控制。

稍微提供一些初步信息。有关所有详细信息，请参阅此版本的github回购。

  type TapeM = StateT磁带IO 
类型TapeP =程序磁带M 
类型TapeC =连续磁带P 
 
分支:: Monad m => m Bool  - >程序m  - >程序m  - >程序m 
分支cond trueBranch falseBranch = 
控制（（\ b  - >如果b然后是trueBranch else falseBranch）`liftM` cond）
 
 loopControl :: TapeP  - > ; TapeP  - > TapeP 
 loopControl = branch（不是< $> is0）
  

以下是我试过的：

  toProgram :: String  - > TapeP 
 toProgram =（`runCont` id）。 toProgramStep 
 
 liftI :: TapeM（） - >字符串 - > TapeC TapeP 
 liftI i cs =指令i< $> toProgramStep cs 
 
 toProgramStep :: String  - > TapeC TapeP 
 toProgramStep（'>'：cs）= liftI right cs 
  - 类似于其他指令
 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）
  

我想我可以以某种方式使用continuations将信息从'[' case'传递给']' case，反之亦然，但我没有足够牢固的把握，除了汇编看似可能工作的东西外，上面用 push 和 pop 见过。这个编译和运行，但结果是垃圾。

可以使用 Cont 适当地为此打结情况？如果没有，那么我应该用什么技术来实现到程序？

---

<注意1：我以前有一个微妙的逻辑错误： loopControl = branch is0 Bools颠倒了。

注2：我设法使用 MonadFix （如jberryman建议）并使用 State 来提出解决方案（请参阅 github仓库的当前状态）。我仍然想知道如何用 Cont 来完成。

注3：我的Racketeer导师为我安装类似的Racket程序（请参阅所有修订）。使用 Cont ？

---

$ b $可以将他的管道/管道输出技术转换成Haskell b

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

解决方案

使用延续monad转发移动状态看起来像这样：

  Cont（fw  - > r）a 
  

然后， cont 的参数类型为

  （a  - > fw  - > r） - > fw  - > r 
  

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

向后行驶状态如下所示：

 Cont（bw，r）a 
  

然后，参数 cont 是

 （a  - >（bw，r ）） - > （bw，r）
  

I。你会得到一个 bw ，你必须把它传递给过去。

这些可以合并成（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）
  

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 continuations to communicate information from the '[' case to the ']' 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 push and pop. This compiles and runs, but the results are garbage.

Can Cont be used to tie the knot appropriately for this situation? If not, then what technique should I use to implement toProgram?

---

Note 1: I previously had a subtle logic error: loopControl = branch is0 had the Bools reversed.

Note 2: I managed to use MonadFix (as suggested by jberryman) with State to come up with a solution (see the current state of the github repository). I'd still like to know how this could be done with Cont instead.

Note 3: My Racketeer mentor put a similar Racket program together for me (see all revisions). Can his pipe/pipe-out technique be translated into Haskell using Cont?

---

tl;dr 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 Cont in Haskell. Can you show me how?

解决方案

Forwards traveling state with a continuation monad looks like this:

Cont (fw -> r) a

Then the type of the argument to cont is

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

So you get a fw passed in from the past which you have to pass on to the continuation.

Backwards traveling state looks like this:

Cont (bw, r) a

Then the type of the argument to cont is

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

I.e. you get a bw from the continuation which you have to pass on to the past.

These can be combined into one continuation monad:

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

There's a catch when applying this to your parser, because toProgramStep builds the program in reverse, so the list of ']' points is the forward state, and the list of '[' points is the backward state. Also, I got lazy and skipped the Maybe part, which should catch the pattern matching errors in openBrace and 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)

这篇关于使用Cont来获取未来和过去的价值的文章就介绍到这了，希望我们推荐的答案对大家有所帮助，也希望大家多多支持IT屋！