19 votos

Uso de continuación para adquirir los valores desde el futuro y el pasado

Estoy escribiendo un brainfuck intérprete de Haskell, y me encontré con lo que creo que es una muy interesante descripción de un programa:

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

Sin embargo, es difícil analizar una representación textual de un brainfuck programa en este tipo de datos. El problema surge con el intento de analizar correctamente los corchetes, porque hay algunos nudos que hacer para que el final Instruction dentro de un bucle enlaces para el bucle de la Control de nuevo.

Un poco más de información preliminar. Ver esta versión en la repo de github para todos los detalles.

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)

Aquí es lo que he intentado:

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)

Pensé que podría utilizar alguna de las continuaciones para comunicar la información de la '[' caso a la ']' de casos y viceversa, pero no tengo una firme comprensión de Cont a hacer cualquier cosa, además de montar salvaje conjeturas de algo que parece que podría funcionar, como se ha visto anteriormente con push y pop. Este se compila y ejecuta, pero los resultados son basura.

Puede Cont ser usado para atar el nudo de manera apropiada para esta situación? Si no, entonces, ¿qué técnica se debe usar para implementar toProgram?


Nota 1: yo antes tenía una lógica sutil error: loopControl = branch is0 tenía el Bools invertido.

Nota 2: me las arreglé para uso MonadFix (según lo sugerido por jberryman) con State a venir para arriba con una solución (ver el estado actual del repositorio de github). Yo todavía me gustaría saber cómo se podría hacer con Cont lugar.

Nota 3: Mi Chantajista mentor puesto similar Raqueta programa juntos para mí (vea todas las revisiones). Puede su tubo/de la tubería de salida de la técnica se traduce en Haskell usando Cont?


tl;dr me las arreglé para hacer esto usando MonadFix, y alguien se las arregló para hacer que el uso de la Raqueta de la continuación de combinadores. Estoy bastante seguro de que esto se puede hacer con Cont en Haskell. ¿Me puede mostrar cómo?

14voto

Sjoerd Visscher Puntos 8310

Reenvía estado viajando con una continuación mónada se parece a esto:

Cont (fw -> r) a

A continuación, el tipo del argumento a cont es

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

Por lo que obtener un fw pasó en el pasado que tienen que pasar a la continuación.

Hacia atrás viajando estado se parece a esto:

Cont (bw, r) a

A continuación, el tipo del argumento a cont es

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

I. e. usted obtener un bw de la continuidad que tiene que pasar en el pasado.

Estos pueden ser combinados en una continuación mónada:

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

Hay un problema cuando se aplica esto a su analizador, porque toProgramStep construye el programa a la inversa, por lo que la lista de ']' puntos es la siguiente estado, y la lista de '[' puntos es el retroceso del estado. También, me dio pereza y se omite el tal vez en parte, que debe coger a la coincidencia de patrones de errores en openBrace y 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)

4voto

jberryman Puntos 6615

Siendo terriblemente perezoso con esta respuesta, ya no me siento cómoda con Cont, pero es MonadFix quizás lo que está buscando? State es un ejemplo, aunque no Cont, y te permite hacer cosas que parecen (el uso de "recursiva hacer" notación):

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

Esta fue la solución que he descubierto para mi los actores de la biblioteca: queremos un spawn operación que devuelve el generado actor del buzón, pero entonces ¿cómo podemos lanzar mutuamente-la comunicación de los actores? O un actor con acceso a su propio buzón de correo?

Con un adecuado MonadFix ejemplo podemos hacer:

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

La esperanza de arriba te da ideas.

Iteramos.com

Iteramos es una comunidad de desarrolladores que busca expandir el conocimiento de la programación mas allá del inglés.
Tenemos una gran cantidad de contenido, y también puedes hacer tus propias preguntas o resolver las de los demás.

Powered by:

X