¿Qué es el patrón "Mónada libre + intérprete"?

He visto personas hablando de Free Monad with Interpreter , particularmente en el contexto del acceso a datos. ¿Cuál es este patrón? ¿Cuándo podría querer usarlo? ¿Cómo funciona y cómo lo implementaría?

Entiendo (de publicaciones como esta ) que se trata de separar el modelo del acceso a los datos. ¿En qué difiere del conocido patrón de repositorio? Parecen tener la misma motivación.

El patrón real es en realidad significativamente más general que solo el acceso a datos. Es una forma liviana de crear un lenguaje específico de dominio que le brinda un AST, y luego tener uno o más intérpretes para "ejecutar" el AST como desee.

La parte de mónada gratuita es solo una forma práctica de obtener un AST que puede ensamblar utilizando las instalaciones de mónada estándar de Haskell (como la anotación) sin tener que escribir mucho código personalizado. Esto también asegura que su DSL sea componible : puede definirlo en partes y luego juntar las partes de una manera estructurada, permitiéndole aprovechar las abstracciones normales de Haskell como funciones.

El uso de una mónada gratis le brinda la estructura de un DSL composable; todo lo que tienes que hacer es especificar las piezas. Simplemente escriba un tipo de datos que abarque todas las acciones en su DSL. Estas acciones podrían estar haciendo cualquier cosa, no solo el acceso a datos. Sin embargo, si especificó todos sus accesos a datos como acciones, obtendría un AST que especifica todas las consultas y comandos para el almacén de datos. A continuación, puede interpretar esto como desee: ejecútelo en una base de datos en vivo, ejecútelo en una simulación, simplemente registre los comandos para la depuración o incluso intente optimizar las consultas.

Veamos un ejemplo muy simple para, por ejemplo, un almacén de valores clave. Por ahora, trataremos las claves y los valores como cadenas, pero puede agregar tipos con un poco de esfuerzo.

data DSL next = Get String (String -> next)
              | Set String String next
              | End

El nextparámetro nos permite combinar acciones. Podemos usar esto para escribir un programa que obtenga "foo" y establezca "bar" con ese valor:

p1 = Get "foo" $ \ foo -> Set "bar" foo End

Desafortunadamente, esto no es suficiente para un DSL significativo. Como utilizamos nextpara la composición, el tipo de p1es de la misma longitud que nuestro programa (es decir, 3 comandos):

p1 :: DSL (DSL (DSL next))

En este ejemplo en particular, usar nextesto parece un poco extraño, pero es importante si queremos que nuestras acciones tengan diferentes variables de tipo. Podríamos querer un mecanografiado gety set, por ejemplo.

Observe cómo el nextcampo es diferente para cada acción. Esto sugiere que podemos usarlo para hacer DSLun functor:

instance Functor DSL where
  fmap f (Get name k)          = Get name (f . k)
  fmap f (Set name value next) = Set name value (f next)
  fmap f End                   = End

De hecho, esta es la única forma válida de convertirlo en Functor, por lo que podemos usarlo derivingpara crear la instancia automáticamente al habilitar la DeriveFunctorextensión.

El siguiente paso es el Freetipo en sí. Eso es lo que usamos para representar nuestra estructura AST , construir sobre el DSLtipo. Puede pensarlo como una lista en el nivel de tipo , donde "contras" simplemente anida un functor como DSL:

-- compare the two types:
data Free f a = Free (f (Free f a)) | Return a
data List a   = Cons a (List a)     | Nil

Entonces, podemos usar Free DSL nextpara dar a los programas de diferentes tamaños los mismos tipos:

p2 = Free (Get "foo" $ \ foo -> Free (Set "bar" foo (Free End)))

Que tiene el tipo mucho más agradable:

p2 :: Free DSL a

Sin embargo, la expresión real con todos sus constructores sigue siendo muy difícil de usar. Aquí es donde entra la parte de la mónada. Como el nombre "mónada libre" implica, Freees una mónada, siempre y cuando f(en este caso DSL) sea un functor:

instance Functor f => Monad (Free f) where
  return         = Return
  Free a >>= f   = Free (fmap (>>= f) a)
  Return a >>= f = f a

Ahora estamos llegando a algún lado: podemos usar la donotación para que nuestras expresiones DSL sean más agradables. ¿La única pregunta es para qué poner next? Bueno, la idea es usar la Freeestructura para la composición, por lo que solo pondremos Returnpara cada campo siguiente y dejaremos que la notación do haga toda la plomería:

p3 = do foo <- Free (Get "foo" Return)
        Free (Set "bar" foo (Return ()))
        Free End

Esto es mejor, pero sigue siendo un poco incómodo. Tenemos Freey por Returntodo el lugar. Afortunadamente, hay un patrón podemos explotar: la forma en que "levantar" una acción de DSL en Freees siempre el mismo: la envolvemos en Freey aplicamos Returnpara next:

liftFree :: Functor f => f a -> Free f a
liftFree action = Free (fmap Return action)

Ahora, usando esto, podemos escribir buenas versiones de cada uno de nuestros comandos y tener un DSL completo:

get key       = liftFree (Get key id)
set key value = liftFree (Set key value ())
end           = liftFree End

Usando esto, así es como podemos escribir nuestro programa:

p4 :: Free DSL a
p4 = do foo <- get "foo"
        set "bar" foo
        end

El buen truco es que, si bien p4parece un pequeño programa imperativo, en realidad es una expresión que tiene el valor

Free (Get "foo" $ \ foo -> Free (Set "bar" foo (Free End)))

Entonces, la parte libre del mónada del patrón nos ha dado un DSL que produce árboles de sintaxis con buena sintaxis. También podemos escribir subárboles compostables al no usar End; por ejemplo, podríamos tener el followque toma una clave, obtiene su valor y luego lo usa como una clave en sí misma:

follow :: String -> Free DSL String
follow key = do key' <- get key
                get key'

Ahora followpuede usarse en nuestros programas como geto set:

p5 = do foo <- follow "foo"
        set "bar" foo
        end

Así que también obtenemos buena composición y abstracción para nuestro DSL.

Ahora que tenemos un árbol, llegamos a la segunda mitad del patrón: el intérprete. Podemos interpretar el árbol como nos guste simplemente haciendo coincidir patrones en él. Esto nos permitiría escribir código contra un almacén de datos real IO, así como otras cosas. Aquí hay un ejemplo contra un almacén de datos hipotético:

runIO :: Free DSL a -> IO ()
runIO (Free (Get key k)) =
  do res <- getKey key
     runIO $ k res
runIO (Free (Set key value next)) =
  do setKey key value
     runIO next
runIO (Free End) = close
runIO (Return _) = return ()

Esto evaluará felizmente cualquier DSLfragmento, incluso uno que no haya terminado end. Afortunadamente, podemos hacer una versión "segura" de la función que solo acepte programas cerrados endal establecer la firma del tipo de entrada en (forall a. Free DSL a) -> IO (). Si bien la firma anterior acepta una Free DSL apara cualquier a (como Free DSL String, Free DSL Intetc.), esta versión solo acepta una Free DSL aque funcione para todas las posibles a, con las que solo podemos crear end. Esto garantiza que no olvidaremos cerrar la conexión cuando hayamos terminado.

safeRunIO :: (forall a. Free DSL a) -> IO ()
safeRunIO = runIO

(No podemos simplemente comenzar dando runIOeste tipo porque no funcionará correctamente para nuestra llamada recursiva. Sin embargo, podríamos mover la definición runIOa un wherebloque safeRunIOy obtener el mismo efecto sin exponer ambas versiones de la función).

Ejecutar nuestro código IOno es lo único que podemos hacer. Para la prueba, es posible que queramos ejecutarlo contra un puro State Map. Escribir ese código es un buen ejercicio.

Este es el patrón de mónada + intérprete gratuito Hacemos un DSL, aprovechando la estructura de mónada libre para hacer toda la fontanería. Podemos usar do-notation y las funciones estándar de mónada con nuestro DSL. Luego, para usarlo realmente, tenemos que interpretarlo de alguna manera; Como el árbol es, en última instancia, solo una estructura de datos, podemos interpretarlo de la manera que queramos para diferentes propósitos.

Cuando usamos esto para administrar los accesos a un almacén de datos externo, de hecho es similar al patrón del Repositorio. Se intermedia entre nuestro almacén de datos y nuestro código, separando los dos. Sin embargo, en algunos aspectos, es más específico: el "repositorio" siempre es un DSL con un AST explícito que luego podemos usar como queramos.

Sin embargo, el patrón en sí es más general que eso. Se puede usar para muchas cosas que no implican necesariamente bases de datos externas o almacenamiento. Tiene sentido donde quiera que desee un control preciso de los efectos o múltiples objetivos para un DSL.

Una mónada libre es básicamente una mónada que construye una estructura de datos en la misma "forma" que el cálculo en lugar de hacer algo más complicado. ( Hay ejemplos que se pueden encontrar en línea. ) Esta estructura de datos se pasa a un código que la consume y lleva a cabo las operaciones. * No estoy completamente familiarizado con el patrón de repositorio, pero por lo que he leído parece para ser una arquitectura de nivel superior, y podría usarse un mónada + intérprete gratuito para implementarla. Por otro lado, el mónada + intérprete gratuito también podría usarse para implementar cosas completamente diferentes, como los analizadores.

* Vale la pena señalar que este patrón no es exclusivo de las mónadas, y de hecho puede producir un código más eficiente con solicitantes gratuitos o flechas libres . ( Los analizadores son otro ejemplo de esto ) .