Haskell: ¿Cómo escribir un intérprete interactivo sobre una mónada estatal?

interpreter interactive

Question

Estamos trabajando en un sistema de archivos modelo que utiliza una mónada de estado internamente. Tenemos una clase de tipos con operaciones como estas:

class Monad m => FS m where
isDirectory :: Path -> m Bool
children :: Path -> m [Path]
...

Estamos trabajando en un pequeño intérprete interactivo que ofrecerá comandos como cd , ls , cat , etc. Una operación en el intérprete se puede escribir de esta manera:

fsop :: FS m => Operation -> m Response

Las definiciones de Operation y Response no son importantes; Si quieres, tómalos como cuerdas.

El problema que estoy tratando de resolver es escribir un bucle de nivel superior en la mónada de E / S que interpreta las Operation sistema de archivos e imprime las respuestas. Si IO fuera una instancia de FS (es decir, si estuviéramos trabajando directamente con la mónada IO), la vida sería simple: podríamos escribir

loop :: Path -> IO ()
loop currentDir = do
op <- getLine
case read op of
ChangeDir d -> loop d -- should test ''isDirectory d'', but let''s not
Ls -> do { files <- children currentDir
; mapM_ putStrLn files
; loop currentDir }
Exit -> return ()

Pero eso no es lo que quiero. Quiero usar Control.Monad.State :

newtype Filesystem a = Filesystem (State (Data.Map.Map Path Contents) a)

y declarar

instance Monad Filesystem ...
instance FS Filesystem ...

Usando la abstracción de FS , puedo escribir una función de un solo paso que debería funcionar con cualquier instancia, y de hecho el siguiente código compila:

step :: FS fs => Path -> Operation -> fs (Path, Response)
step currentDir op =
case op of
ChangeDir d -> return (d, "")
Ls -> do { files <- children currentDir
; return (currentDir, unlines files) }

En este punto estoy totalmente atascado. Lo que quiero hacer es escribir un bucle interactivo en la mónada IO, que puede leer las Operation e imprimir las Response , pero que funciona en una mónada de estado que no es necesariamente IO. (Una de las razones para tener un modelo que no está en IO es que podemos probar las propiedades de QuickCheck).

Siento que esto tiene que ser un problema estándar, un bucle interactivo de lectura-evaluación en la parte superior de una abstracción con estado que no es IO pero debo faltar algo asombrosamente obvio porque parece que no puedo resolverlo. He mirado en línea pero no he sido iluminado.

Cualquier ayuda para escribir una computación interactiva de rendimiento de E / S que pueda llamar a un step sería muy apreciada.

Answer 1

¿Qué pasa con el uso de transformadores de mónada? Son una forma más o menos estándar de combinar mónadas. Aquí un ejemplo simplista:

type Foo a = StateT String IO a
replT :: Foo ()
replT = do
str <- liftIO getLine
state <- get
liftIO $ putStrLn ("current state: " ++ state)
liftIO $ putStrLn ("setting state: " ++ str)
put str
replT

A continuación se muestran los resultados de la ejecución de replT desde ghci.

*Main> runStateT replT "Initial state"
asd
current state: Initial state
setting state: asd
zxc
current state: asd
setting state: zxc
asdasd

Hay tres libs de transformadores de mónada. MTL, transformadores y monadLib. No puedo recomendar ninguno de ellos ya que no los uso mucho.

Answer 2

Exija que sus instancias de FS sean instancias de MonadIO , no solo Monad :

class MonadIO m => FS m where ...

Luego, tendrá disponible el método liftIO para elevar FS en IO :

liftIO :: MonadIO m => m a -> IO a

para que puedas escribir en la mónada IO :

files <- liftIO $ children currentDir

Por supuesto, eso significa que tendrá que implementar liftIO para cada FS incluso antes de escribir la instancia de FS, pero para esta aplicación (sin haber visto los detalles reales) parece que debería ser simple.

Answer 3

Puedo pensar en dos soluciones aquí:

1) Utilice una biblioteca de transformadores de mónada. No puedo mejorar la respuesta de Shimuuar, excepto en algunos detalles sobre las bibliotecas. Los transformadores por sí mismos no proporcionan las instancias necesarias; necesitaría usar transformadores y monads-tf o monads-fd, que ofrecen implementaciones basadas en familias de tipos y fundeps, respectivamente. Prefiero las mónadas-tf si vas por esta ruta. La api es casi idéntica a la de mtl. No tengo experiencia con MonadLib, pero también se ve bastante bien.

2) Escriba su bucle principal en IO, y para cada iteración de bucle llame a runState para evaluar la mónada de estado. Algo como lo siguiente:

loop path state = do
op <- readOp
let ((newpath, resp), newstate) = runState (step path op) state
print resp
loop newpath newstate

Esto debería funcionar, pero es mucho menos idiomático que el uso de transformadores de mónada.

Answer 4

Descargo de responsabilidad : no puedo prometer que lo siguiente es una buena manera de hacerlo, pero trabajar en eso suena divertido . Vamos a dar una vuelta, ¿vale?

Algunas importaciones obligatorias.

En primer lugar, vamos a tirar algunos tipos de datos por ahí. Voy a completar algunos detalles y modificar las cosas un poco para definir un "sistema de archivos" simple con el que podamos interactuar.

type Path = String
type Response = Maybe String
type Contents = [String]
data Operation = Cd Path
| Ls
| MkDir Path
| Quit
deriving (Read, Show)

A continuación, haremos algo un poco nervioso ... eliminar todas las mónadas. ¿Qué? ¡Esto es una locura! Quizás, pero a veces toda la tubería oculta que >>= proporciona oculta las cosas demasiado .

Para el sistema de archivos, solo almacenaremos el directorio de trabajo actual y un mapa de las rutas a sus hijos. También necesitaremos un puñado de funciones para interactuar con él.

data Filesystem = Filesystem { wd :: Path, files :: M.Map Path Contents }
deriving Show
newFS = Filesystem "/" (M.singleton "/" [])
isDirectory p fs = M.member p $ files fs
children p fs = fromMaybe [] . M.lookup p $ files fs
cd p fs = fs { wd = p }
create p fs = let newPath = wd fs ++ p ++ "/"
addPath = M.insert newPath [] . M.adjust (p:) (wd fs)
in (newPath, fs { files = addPath $ files fs })

Ahora para una versión sin monada de la función de step . Necesita tomar una Operation y un Filesystem , y devolver una Response y un Filesystem (posiblemente modificado):

step :: Operation -> Filesystem -> (Response, Filesystem)
step (Cd d) fs = (Just "Ok/n", cd d fs)
step (MkDir d) fs = first (/d -> Just $ "Created " ++ d ++ "/n") $ create d fs
step Ls fs = let files = children (wd fs) fs
in (Just $ unlines files, fs)
step Quit fs = (Nothing, fs)

... hmm, esa firma de tipo ya se parece mucho a las entrañas de una mónada State . Oh, bueno, solo ignóralo por ahora, y carga ciegamente hacia adelante.

Ahora, lo que queremos es una función que proporcione una interfaz de propósito general para un intérprete del Filesystem . En particular, queremos que la interfaz sea al menos algo autónoma, de modo que cualquier uso de la interfaz no tenga que pasar manualmente, sin embargo, queremos que la interfaz sea lo suficientemente ajena al código que la usa para que podamos conectarla a la mónada IO , alguna otra Monad , o incluso ninguna mónada.

Lo que esto nos dice principalmente es que tendremos que intercalar el código externo con el intérprete de alguna manera, en lugar de que cualquiera de las partes tenga el control. Ahora, Haskell es un lenguaje funcional , lo que significa que usar muchas funciones de orden superior es bueno, ¿verdad? Me suena plausible, así que aquí está la estrategia que usaremos: si una función no sabe qué hacer a continuación, le daremos otra función que asumimos que sí. Repita hasta que todos sepan lo que está pasando. Un plan impecable, ¿no?

El corazón de todo es la función de step , por lo que comenzaremos con solo llamar a eso.

interp1 :: Operation -> Filesystem -> (Response, Filesystem)
interp1 op fs = step op fs

... bueno, es un comienzo. Supongo. Pero espera, ¿de dónde viene la Operation ? Necesitamos el código externo para proporcionar eso, pero no podemos simplemente pedirlo sin mezclarnos con caracteres desagradables como IO . Entonces tenemos otra función para hacer el trabajo sucio por nosotros:

interp2 :: ((Operation -> (Response, Filesystem)) -> t) -> Filesystem -> t
interp2 inp fs = inp (/op -> step op fs)

Por supuesto, ahora todo lo que tenemos es una estupidez de que ni siquiera sabemos qué es. Sabemos que tiene que haber una Response y un Filesystem de Filesystem en alguna parte, pero no podemos hacer nada con eso, por lo que se lo devolveremos a otra función, junto con algunas instrucciones sobre cómo proceder ... Por supuesto implican pasar aún más funciones. Es funciones todo el camino hacia abajo, ya sabes.

interp3 :: ((Operation -> (Response, Filesystem)) -> a)
-> (a -> ((Response, Filesystem) -> b) -> c)
-> (Filesystem -> b)
-> (String -> Filesystem -> b)
-> Filesystem
-> c
interp3 inp check done out fs = check (inp (/op -> step op fs)) test
where test (Nothing, fs) = done fs
test (Just s, fs) = out s fs

... bueno eso es bastante feo. Pero no te preocupes, todo va según lo planeado. Podemos hacer un par de observaciones a continuación:

• El tipo a solo existe entre inp y check , por lo tanto, en retrospectiva, podríamos combinarlos de antemano y pasar la función compuesta al intérprete.
• Cuando hacemos el llamado, debe significar exactamente lo que dice en la lata. Por lo tanto, el tipo de retorno para done debería ser el mismo que el intérprete completo, lo que significa que b y c deberían ser del mismo tipo.

Ahora, si se done termina todo, ¿qué pasa? Como su nombre indica de forma no muy sutil, proporciona salida al código externo, pero ¿a dónde va después? Debe volver al intérprete de alguna manera, y podemos notar que nuestro intérprete aún no es recursivo. El camino a seguir es claro: el intérprete, como Jormungand, se apodera de su propia cola; dando vueltas indefinidamente hasta que la interpretación termine (o hasta Ragnarök, lo que ocurra primero).

interp4 :: ((Operation -> (Response, Filesystem))
-> ((Response, Filesystem) -> r) -> r)
-> (Filesystem -> r)
-> (String -> Filesystem -> (Filesystem -> r) -> r)
-> Filesystem
-> r
interp4 checkInp done out fs = checkInp (/op -> step op fs) test
where loop = interp4 checkInp done out
test (Nothing, fs) = done fs
test (Just s, fs) = out s fs loop

... oh, ¿mencioné que funciona ahora? ¡No en serio!

Aquí hay un código IO para usar la interfaz:

ioIn f k = putStr "> " >> (k . f =<< readLn)
ioDone fs = putStrLn "Done" >> return fs
ioOut x fs k = putStr x >> k fs
ioInterp :: IO Filesystem
ioInterp = interp4 ioIn ioDone ioOut newFS

Y aquí está el código que ejecuta una lista de comandos, produciendo una lista de cadenas de salida:

scriptIn f k (x:xs) = k (f x) xs
scriptDone fs xs = ["Done/n"]
scriptOut r fs k xs = r : k fs xs
scriptInterp :: [Operation] -> [String]
scriptInterp = interp4 scriptIn scriptDone scriptOut newFS

Ejemplos de ejecución de ambos en GHCi aquí , si solo el código no hace cosquillas a su imaginación lo suficiente.

Bueno, eso es todo. ¿O es eso? Francamente, ese intérprete es un código que solo una madre podría amar. ¿Hay algo que lo uniría todo elegantemente? ¿Algo para revelar la estructura subyacente del código?

... bueno, entonces es bastante obvio a donde lleva esto. El diseño general de las funciones de llamada de cola en círculos se parece mucho al estilo de paso de continuación, y no una sino dos veces en la firma de tipo del intérprete se puede encontrar el patrón característico (foo -> r) -> r , más conocido como la mónada de continuación.

Desafortunadamente, incluso después de todo eso, las continuaciones hacen que me duela la cabeza y no estoy seguro de cuál es la mejor manera de desentrañar la estructura muy ad hoc del intérprete en un cálculo que se ejecuta en un MonadCont .