Qu'est-ce que le motif «Free Monad + Interpreter»?

J'ai vu des gens parler de Free Monad avec Interpreter , en particulier dans le contexte de l'accès aux données. Quel est ce modèle? Quand pourrais-je vouloir l'utiliser? Comment cela fonctionne-t-il et comment pourrais-je le mettre en œuvre?

Je comprends (à partir de messages comme celui- ci ) qu’il s’agit de séparer le modèle de l’accès aux données. En quoi diffère-t-il du modèle de référentiel bien connu? Ils semblent avoir la même motivation.

Le modèle actuel est en réalité beaucoup plus général qu'un simple accès aux données. C'est un moyen léger de créer un langage spécifique à un domaine qui vous donne un AST, puis de faire appel à un ou plusieurs interprètes pour "exécuter" l'AST comme bon vous semble.

La partie monad gratuite est simplement un moyen pratique d'obtenir un AST que vous pouvez assembler à l'aide des installations monad standard de Haskell (comme la notation Do) sans avoir à écrire beaucoup de code personnalisé. Cela garantit également que votre DSL est composable : vous pouvez le définir en plusieurs parties, puis les assembler de manière structurée, ce qui vous permet de tirer parti des abstractions normales de Haskell, telles que les fonctions.

L'utilisation d'une monade libre vous donne la structure d'un DSL composable; tout ce que vous avez à faire est de spécifier les pièces. Vous venez d'écrire un type de données qui englobe toutes les actions de votre DSL. Ces actions pourraient faire n'importe quoi, pas seulement un accès aux données. Cependant, si vous spécifiez tous vos accès aux données sous forme d'actions, vous obtiendrez un AST qui spécifie toutes les requêtes et commandes du magasin de données. Vous pouvez ensuite interpréter cela comme bon vous semble: exécutez-le sur une base de données dynamique, exécutez-le contre une maquette, enregistrez simplement les commandes pour le débogage ou même essayez d’optimiser les requêtes.

Regardons un exemple très simple pour, par exemple, un magasin de valeurs de clé. Pour le moment, nous allons simplement traiter les clés et les valeurs comme des chaînes, mais vous pouvez ajouter des types avec un peu d'effort.

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

Le nextparamètre nous permet de combiner des actions. Nous pouvons utiliser ceci pour écrire un programme qui obtient "foo" et définit "bar" avec cette valeur:

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

Malheureusement, cela ne suffit pas pour un DSL significatif. Depuis que nous avons utilisé nextpour la composition, le type de p1est la même longueur que notre programme (ie 3 commandes):

p1 :: DSL (DSL (DSL next))

Dans cet exemple particulier, l'utilisation de nextcette méthode semble un peu étrange, mais il est important si nous voulons que nos actions aient des variables de type différentes. Nous voudrons peut-être un type getet set, par exemple.

Notez en quoi le nextchamp est différent pour chaque action. Ceci suggère que nous pouvons l’utiliser pour faire DSLun foncteur:

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

En fait, c’est le seul moyen valable d’en faire un foncteur. Nous pouvons donc utiliser derivingpour créer l’instance automatiquement en activant l’ DeriveFunctorextension.

La prochaine étape est le Freetype lui-même. C'est ce que nous utilisons pour représenter notre structure AST , construite sur le DSLtype. Vous pouvez le voir comme une liste au niveau du type , où "inconvénients" consiste à imbriquer un foncteur tel que DSL:

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

Nous pouvons donc utiliser Free DSL nextpour donner aux mêmes types des programmes de tailles différentes:

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

Qui a le type beaucoup plus gentil:

p2 :: Free DSL a

Cependant, l'expression réelle avec tous ses constructeurs est encore très difficile à utiliser! C’est là que la partie de la monade entre en jeu. Comme l’ Freeappelle le nom "monade libre", il s’agit d’une monade - aussi longtemps que f(dans ce cas DSL), elle est un foncteur:

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

Maintenant, nous obtenons quelque chose: nous pouvons utiliser la donotation pour rendre nos expressions DSL plus agréables. La seule question est de savoir quoi mettre next? Eh bien, l’idée est d’utiliser la Freestructure pour la composition, nous allons donc mettre Returnpour chaque champ suivant et laisser la notation do faire toute la plomberie:

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

C'est mieux, mais c'est toujours un peu gênant. Nous avons Freeet Returnpartout. Heureusement, il y a un modèle que nous pouvons exploiter: la façon dont nous « lever » une action DSL en Freeest toujours le même , nous envelopper dans Freeet appliquer Returnpour next:

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

Maintenant, en utilisant cela, nous pouvons écrire de belles versions de chacune de nos commandes et avoir un DSL complet:

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

En utilisant ceci, voici comment nous pouvons écrire notre programme:

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

Le bon truc, c’est que même si cela p4ressemble à un petit programme impératif, c’est en fait une expression qui a la valeur

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

Ainsi, la partie monade libre du modèle nous a donné un ADSL qui produit des arbres de syntaxe avec une belle syntaxe. Nous pouvons également écrire des sous-arbres composables en n'utilisant pas End; Par exemple, nous pourrions avoir followce qui prend une clé, obtient sa valeur et l'utilise ensuite comme clé elle-même:

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

Maintenant, followpeut être utilisé dans nos programmes comme getou set:

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

Nous obtenons donc également une belle composition et une abstraction pour notre DSL.

Maintenant que nous avons un arbre, nous arrivons à la seconde moitié du motif: l'interprète. Nous pouvons interpréter l’arbre comme bon nous semble, simplement en appliquant des motifs. Cela nous permettrait d'écrire du code sur un vrai magasin de données IO, ainsi que d'autres choses. Voici un exemple contre un magasin de données hypothétique:

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 ()

Cela évaluera avec plaisir n'importe quel DSLfragment, même celui qui ne se termine pas end. Heureusement, nous pouvons créer une version "sûre" de la fonction qui n'accepte que les programmes fermés enden définissant la signature de type d'entrée sur (forall a. Free DSL a) -> IO (). Alors que l'ancienne signature accepte un Free DSL apour tout a (comme Free DSL String, Free DSL Intetc.), cette version n'accepte qu'un Free DSL aqui fonctionne pour tous les cas possibles a- pour lesquels nous ne pouvons créer qu'avec end. Cela garantit que nous n'oublierons pas de fermer la connexion lorsque nous aurons terminé.

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

(Nous ne pouvons pas simplement commencer par donner runIOce type car il ne fonctionnera pas correctement pour notre appel récursif. Cependant, nous pourrions déplacer la définition de runIOdans un wherebloc safeRunIOet obtenir le même effet sans exposer les deux versions de la fonction.)

Utiliser notre code IOn'est pas la seule chose à faire. Pour tester, nous pourrions vouloir le lancer avec un pur State Map. Ecrire ce code est un bon exercice.

Donc, ceci est le modèle monade + interprète libre. Nous faisons un DSL, en profitant de la structure de monade libre pour faire toute la plomberie. Nous pouvons utiliser la notation do et les fonctions monad standard avec notre DSL. Ensuite, pour l’utiliser, nous devons l’interpréter d’une manière ou d’une autre; comme l’arborescence n’est finalement qu’une structure de données, nous pouvons l’interpréter à notre guise, à des fins différentes.

Lorsque nous utilisons cela pour gérer les accès à un magasin de données externe, cela ressemble en réalité au modèle de référentiel. Il sert d'intermédiaire entre notre magasin de données et notre code, en séparant les deux. À certains égards, cependant, il est plus spécifique: le "référentiel" est toujours un DSL avec un AST explicite que nous pouvons ensuite utiliser à notre guise.

Cependant, le schéma lui-même est plus général que cela. Il peut être utilisé pour beaucoup de choses qui n'impliquent pas nécessairement des bases de données externes ou du stockage. Cela a du sens partout où vous voulez un contrôle précis des effets ou des cibles multiples pour un DSL.

Une monade libre est fondamentalement une monade qui construit une structure de données dans la même "forme" que le calcul plutôt que de faire quelque chose de plus compliqué. ( Il y a des exemples disponibles en ligne. ) Cette structure de données est ensuite transmise à un morceau de code qui la consomme et effectue les opérations. * Je ne connais pas parfaitement le modèle de référentiel, mais ce que j'ai lu semble être une architecture de niveau supérieur, et un monad + interprète libre pourrait être utilisé pour la mettre en œuvre. D'autre part, l'interprète monade + gratuit pourrait également être utilisé pour implémenter des choses totalement différentes, telles que des analyseurs syntaxiques.

* Il est à noter que ce modèle n'est pas exclusif aux monades et qu'il peut en fait produire un code plus efficace avec des applications gratuites ou des flèches gratuites . (Les analyseurs en sont un autre exemple. )