19

私は Haskell でブレインファック インタープリターを書いていますが、プログラムの非常に興味深い説明であると思われるものを思いつきました。

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

ただし、brainfuck プログラムのテキスト表現をこのデータ型に解析するのは難しいです。角かっこを正しく解析しようとすると問題が発生します。これは、ループ内の最後の部分が再びInstructionループにリンクするように結び目を作る必要があるためです。Control

もう少し予備的な情報。すべての詳細については、github リポジトリでこのバージョンを参照してください。

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の提案に従って）使用することができました（ githubリポジトリの現在の状態をState参照してください）。代わりにこれをどのように行うことができるかを知りたいです。Cont

注 3: 私の Racketeer メンターは、同様の Racket プログラムをまとめてくれました (すべてのリビジョンを参照)。彼のパイプ/パイプアウト手法は、を使用して Haskell に変換できますContか?

tl;dr私は MonadFix を使用してこれを行うことができ、他の誰かが Racket の継続コンビネータを使用してそれを行うことができました。ContこれはHaskellでできると確信しています。方法を教えてもらえますか？

4

2 に答える 2

14

継続モナドを持つ前方移動状態は次のようになります。

Cont (fw -> r) a

次に、への引数の型contは

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

つまりfw、継続に渡さなければならない過去から渡されたものを取得します。

後進状態は次のようになります。

Cont (bw, r) a

次に、への引数の型contは

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

bwつまり、過去に渡さなければならない継続から取得します。

これらは 1 つの継続モナドに結合できます。

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

これをパーサーに適用するとtoProgramStep、プログラムが逆方向にビルドされるため、']' ポイントのリストが順方向の状態になり、'[' ポイントのリストが逆方向の状態になるため、注意が必要です。openBraceまた、私は怠惰になり、 と のパターン マッチング エラーをキャッチするはずの Maybe の部分をスキップしました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、次のようなことができます ( 「再帰的 do」表記を使用):

{-# 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 に答える