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?

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