haskell - recreativos - juegos para trabajar valores

Usando Cont para adquirir valores del futuro y del pasado.

Question

Estoy escribiendo un intérprete para el cerebro en Haskell, y se me ocurrió lo que creo que es una descripción muy interesante 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 programa de intercambio de ideas en este tipo de datos. El problema surge al tratar de analizar correctamente los corchetes, porque hay que hacer algunos nudos para que la Instruction final dentro de un bucle vuelva a enlazar con el Control del bucle.

Un poco más de información preliminar. Ver esta versión en el repositorio 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)

Esto es lo que intenté:

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 de alguna manera podría usar las continuaciones para comunicar información del caso ''['' caso ''['' '']'' y viceversa, pero no tengo un conocimiento lo suficientemente firme de Cont como para hacer algo más que armar suposiciones locas de algo que Parece que podría funcionar, como se ve arriba con push y pop . Esto se compila y se ejecuta, pero los resultados son basura.

¿Se puede usar Cont para atar el nudo apropiadamente para esta situación? Si no, ¿qué técnica debo usar para implementar toProgram ?

Nota 1: Anteriormente tuve un error lógico sutil: loopControl = branch is0 tenía los Bools invertidos.

Nota 2: MonadFix usar MonadFix (como lo sugirió jberryman) con State para encontrar una solución (consulte el estado actual del repositorio de github ). Todavía me gustaría saber cómo se podría hacer esto con Cont .

Nota 3: Mi mentor de Racketeer organizó un programa de Racket similar para mí (ver todas las revisiones). ¿Se puede traducir su técnica de tubería / tubería en Haskell usando Cont ?

tl; dr logré hacer esto usando MonadFix, y alguien más logró hacerlo usando los combinadores de continuación de Racket. Estoy bastante seguro de que esto se puede hacer con Cont en Haskell. ¿Me puede mostrar cómo?

Answer 1

El estado que viaja hacia adelante con una mónada de continuación se ve así:

Cont (fw -> r) a

Entonces el tipo de argumento para cont es

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

De este modo, se obtiene una fw del pasado que se debe transmitir a la continuación.

El estado de desplazamiento hacia atrás se ve así:

Cont (bw, r) a

Entonces el tipo de argumento para cont es

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

Es decir, recibes un bw de la continuación que debes transmitir al pasado.

Estos se pueden combinar en una mónada de continuación:

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

Hay un problema al aplicar esto a su analizador, porque toProgramStep crea el programa a la inversa, por lo que la lista de puntos '']'' es el estado hacia adelante, y la lista de los puntos ''['' es el estado hacia atrás. Además, me openBrace y closeBrace la parte Maybe, que debería detectar los errores de coincidencia de patrones 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)

Answer 2

Siendo terriblemente perezoso con esta respuesta, ya que no estoy cómodo con Cont , pero ¿es MonadFix lo que estás buscando? State es una instancia, aunque no es Cont , y te permite hacer cosas que parecen (usando la notación "hacer recursivo" ):

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

Esta fue la solución que descubrí para mi biblioteca de actores: queremos una operación de spawn que devuelva el buzón del actor generado, pero ¿cómo podemos lanzar actores que se comunican entre sí? ¿O un actor con acceso a su propio buzón?

Con una instancia adecuada de MonadFix 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.