Cont Verwenden von Werten aus der Zukunft zu erwerben und die Vergangenheit

Question

Ich bin ein Gehirnfick Dolmetscher in Haskell zu schreiben, und ich kam mit dem, was ich eine sehr interessante Beschreibung eines Programms zu sein glauben:

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

jedoch Es ist schwierig, eine Textdarstellung eines Brainfuck-Programms in diesen Datentyp zu zerlegen. Das Problem tritt auf, wenn man versucht, eckige Klammern korrekt zu analysieren, weil es einige Knotenknöpfe gibt, so dass das letzte Instruction innerhalb einer Schleife wieder mit der Control der Schleife verknüpft wird.

Ein bisschen mehr vorläufige Informationen. Alle Details finden Sie unter 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) 

Hier ist, was ich versuche:

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) 

ich dache, ich irgendwie Fortsetzungen nutzen könnte Informationen aus dem '[' Fall an den ']' Fall und umgekehrt zu kommunizieren, aber ich habe keine feste genug Verständnis von Cont, um tatsächlich etwas zu tun, außer dem Zusammensetzen von wüsten Vermutungen von etwas, das aussieht, als könnte es funktionieren, wie oben mit push und pop zu sehen. Dies kompiliert und läuft, aber die Ergebnisse sind Müll.

Kann Cont verwendet werden, um den Knoten für diese Situation geeignet zu binden? Wenn nicht, welche Technik sollte ich verwenden, um toProgram zu implementieren?

---

Anmerkung 1: Ich hatte vorher einen subtilen Logikfehler: loopControl = branch is0 hatte die Bools umgekehrt.

Hinweis 2: Ich habe es geschafft, MonadFix (wie von jberryman vorgeschlagen) mit State, um eine Lösung zu finden (siehe the current state of the github repository). Ich würde immer noch gerne wissen, wie dies mit Cont stattdessen getan werden könnte.

Hinweis 3: Mein Racketeer Mentor legte a similar Racket program zusammen für mich (siehe alle Revisionen). Kann seine Rohr/Rohr-Technik mit Cont in Haskell übersetzt werden?

---

tl; dr ich es geschafft, dies mit MonadFix zu tun, und jemand anderes schaffte es mit Racket der Fortsetzung combinators zu tun. Ich bin mir ziemlich sicher, dass dies mit Cont in Haskell gemacht werden kann. Kannst du mir zeigen wie?

Answer 1

Forwards Zustand mit einer Fortsetzung Monade Reisen sieht wie folgt aus:

Cont (fw -> r) a 

Dann

der Typ des Arguments cont ist

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

So erhalten Sie einen fw in der Vergangenheit geführt, die Sie Ich muss zur Fortsetzung weitergehen.

Rückwärtsfahrzustand sieht wie folgt aus:

Cont (bw, r) a 

Dann wird der Typ des Arguments cont ist

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

D.h. Sie erhalten eine bw von der Fortsetzung, die Sie in die Vergangenheit weitergeben müssen.

Diese können in eine Fortsetzung Monade kombiniert werden:

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

Es gibt einen Haken, wenn dies Ihre Parser Anwendung, weil toProgramStep das Programm in umgekehrtem baut, so dass die Liste von ‚]‘ Punkten ist der Vorwärts-Zustand , und die Liste von '[' Punkten ist der Rückwärts-Zustand. Außerdem wurde ich faul und übersprang den Maybe-Teil, der die Musterabgleichfehler in openBrace und closeBrace auffangen sollte.

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) 

Answer 2

Mit dieser Antwort schrecklich faul sein, da ich nicht mit Cont bequem bin, aber ist MonadFix vielleicht, was Sie suchen? State ist ein Beispiel, wenn auch nicht Cont, und es lässt Sie Dinge tun, die aussehen wie ("recursive do" notation verwenden):

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

Diese Lösung war ich für meine Schauspieler-Bibliothek entdeckt: Wir haben eine spawn Operation wollen, dass der erzeugte zurück Briefkasten des Schauspielers, aber wie können wir dann miteinander kommunizierende Schauspieler starten? Oder ein Schauspieler mit Zugang zu seiner eigenen Mailbox?

Mit einem geeigneten MonadFix Beispiel können wir tun:

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

Hoffnung Sie Ideen oben gibt.