Les monades dans la programmation fonctionnelle

Shall I be pure or impure?

C’est par cette question que Philip Wadler commence, en 1992, un article qui se révélera décisif dans l’application des monades à la programmation fonctionnelle : Monads for functional programming.

Depuis, l’usage des monades s’est répandu dans plusieurs langages, et en particulier dans Haskell, auquel elles ont apporté une réponse élégante pour les entrées/sorties et pour le contrôle d’exécution.

Cet article va présenter les concepts élémentaires des monades, en s’appuyant sur les exemples introduits par Wadler en 1992.

Qu’est-ce qu’une monade ?

Mathématiquement, une monade est un triplet composé d’un foncteur et de deux transformations naturelles, choisis tels que trois lois soient vérifiées. Nous reviendrons juste après sur ces lois.

Appliquée à la programmation fonctionnelle, la monade sera définie par :

• un constructeur de type, qui sera donc un type monadique m ;
• une fonction nommée unit ou return, qui construira à partir d’un objet de type a, un autre objet de type monadique m a. À ce titre, il s’agira d’une fonction monadique, de signature return :: a -> m a ;
• une opération nommée bind, ou >>=, qui permettra de composer une fonction monadique à partir d’autres fonctions monadiques, en respectant une logique propre à chaque monade, de signature (>>=) :: m a -> (a -> m b) -> m b.

Les trois lois des monades sont exprimées ainsi :

• Composition neutre par return à gauche : (return x) >>= f ≡ f x
• Composition neutre par return à droite : m >>= return ≡ m
• Associativité : (m >>= f) >>= g ≡ m >>= ( \ x -> (f x >>= g) )

Un aspect intéressant des monades est qu’elles sont composables, à partir d’un jeu de fonctions monadiques. C’est pourquoi, en plus des trois éléments indispensables listés ci-dessus, la monade sera souvent accompagnée d’un jeu de fonctions monadiques utiles, qui lui seront propres. Le type d’une fonction monadique est le suivant :

∀m ∈ Monad, ∀a, ∀b, f ∈ FonctionsMonadiques ⇔ f : a → mb

À quoi cela peut-il bien servir ?

Pour un langage impur, c’est à dire permettant toute sorte d’effet de bord dans les fonctions, les monades ne sont pas d’une nécessité évidente, bien qu’elles puissent offrir une solution élégante et rapide à certaines catégories de problèmes.

En revanche, pour un langage fonctionnel pur, c’est à dire ne permettant aucun effet de bord, et aucun contrôle d’exécution implicite, les monades offrent une construction permettant d’enrichir les capacités des fonctions. Expliquons cela par un exemple : dans un langage pur, une fonction de type Int → Int → Int sera capable de prendre deux entiers pour en composer un autre. Point. C’est à dire que cette fonction ne pourra lire absolument aucun état du programme, ne pourra accéder ni à un fichier, ni à l’heure courante, ni même à un nombre aléatoire. Elle ne pourra pas non plus logger dans un terminal, ou écrire un rapport d’exécution dans une variable.

La signature de cette fonction a un sens très strict quant à ses capacités : elle peut lire deux entiers, et les utiliser pour en produire un autre. Elle est donc pure, et cela lui confère entre autres une propriété essentielle, le déterminisme. Appelée avec les mêmes arguments, elle produira inlassablement le même résultat, quel que soit l’état de son environnement d’exécution (programme, heure, fichiers, entrées de l’utilisateur etc).

Du code

Prenons un exemple élémentaire, celui d’un évaluateur qui calcule la valeur d’un arbre de divisions. L’arbre de division est défini par le type algébrique suivant.

data Term = Const Int | Div Term Term

Pour la suite de l’exemple, on va définir deux expressions de type Term, dont une qui posera un problème lors de l’évaluation. En Haskell, on peut utiliser le constructeur Div en infix si on l’encadre d’apostrophes inversées.

expr1, expr2 :: Term
expr1 = (Const 20) `Div` ((Const 10) `Div` (Const 2)) -- 20 / (10 / 2)
expr2 = (Const 20) `Div` ((Const 10) `Div` (Const 0)) -- 20 / (10 / 0)

Munis de notre type Term, nous allons écrire un évaluateur sous sa forme la plus simple. Un évaluateur prend un arbre de divisions, et le transforme en une valeur entière en l’évaluant, par la division euclidienne des entiers.

eval :: Term -> Int
eval (Const c) = c
eval (Div n d) = div (eval n) (eval d) -- division entière

En observant la signature de notre évaluateur, nous savons qu’il ne pourra jamais produire de valeurs aléatoires, ni logger ses divisions, ni quoi que ce soit d’autre que fournir un entier. Ce qui nous amène à un premier constat :

• eval expr1 fonctionne parfaitement et retourne 4
• eval expr2 plante avec une exception « divide by zero »

Comme notre évaluateur ne peut renvoyer qu’un Int, il n’a aucun moyen de nous indiquer que le calcul est indéterminé pour cause de division par zéro. Nous allons arranger cela plus tard.

Tout d’abord, nous allons écrire une fonction chargée de construire un évaluateur (donc une fonction) plus souple. Notre fonction makeEvalM prendra en unique argument une fonction de type (Int -> Int -> m Int) qui sera notre diviseur monadique. Nous spécifions une contrainte : m doit être un type monadique. Peu importe quel type nous utiliserons plus tard, la signature du diviseur monadique indique que le résultat de la division sera un objet composé, principalement, d’un Int. Mais accessoirement, cet objet pourra également embarquer tout un tas d’autres informations sur la division. En assouplissant le type de retour du diviseur, nous lui permettons de transmettre des informations annexes à l’entier résultant.

Le retour de makeEvalM est un évaluateur monadique de Term, c’est à dire tout simplement une fonction monadique de type (Term -> m Int).

En appelant makeEvalM sur une fonction de division monadique, nous construisons une nouvelle fonction d’évaluation, spécifique à la logique de la monade m.

makeEvalM :: (Monad m) => (Int -> Int -> m Int)    -- diviseur monadique
            -> (Term -> m Int)          -- évaluateur monadique
makeEvalM divM = (\t -> return t >>= evalM) where
  evalM (Const c) = return c
  evalM (Div n d) = evalM n >>= \ a ->
    evalM d >>= \ b ->
    divM a b

Une première application, la monade Identité

Essayons d’appliquer notre makeEvalM dans le cas d’une monade simple, la monade Identité. Si tout se passe bien, nous obtiendrons au final un évaluateur de base, comme notre première version eval.

Le type monadique est Id, il enrobe une valeur de n’importe quel type, qu’on pourra extraire avec l’accesseur value.

data Id a = Id { value :: a }

On spécifie que Id est un type monadique en fournissant les deux fonctions requises. Ici, return enrobe simplement avec Id, et bind m k applique k à la valeur de m.

instance Monad Id where
  return = Id
  m >>= k = k $ value m

Maintenant que nous avons défini notre type monadique et ses deux fonctions, nous pouvons construire notre évaluateur monadique.

evalId :: Term -> Id Int
evalId = makeEvalM divId where
  divId :: Int -> Int -> Id Int
  divId a b = return $ div a b -- équivalent à Id $ div a b

Si on appelle value $ evalId expr1, on obtient 4 : tout va bien !

Une application utile, la monade Failable

Passons à une monade plus utile, que nous nommerons Failable, et qui représente le succès ou l’échec d’un calcul de type a. En cas de succès, on construira Ok a, et en cas d’échec, on construire Failed “Motif de l’erreur”. Oui, vous reconnaissez peut-être ici le principe des exceptions. Sauf que dans notre cas, le contrôle d’exécution n’est pas interrompu, et le type de retour est explicite, permettant une vérification statique complète des appels, donc un code beaucoup plus sûr et rapide.

data Failable a = Ok a | Failed String deriving Show
-- deriving Show permet d'afficher cet objet et son contenu

On spécifie ensuite le comportement monadique de notre type avec return et >>=. En l’occurrence, si le calcul précédent est Ok, on poursuit avec sa valeur, sinon on s’arrête et on renvoie le motif de l’erreur.

instance Monad Failable where
  return = Ok
  m >>= k = case m of { Ok v -> k v
                      ; Failed s -> Failed s }

Dernière étape pour cette monade Failable, on construit notre évaluateur. Vous l’aurez probablement deviné, notre objectif ici de composer un nouvel évaluateur capable de prendre en compte le cas d’une division par 0. La définition est toute simple, si on divise par zéro, on construit l’erreur, sinon on construit le résultat.

evalFailable :: Term -> Failable Int
evalFailable = makeEvalM divFailable where
  divFailable :: Int -> Int -> Failable Int
  divFailable a b = case b of { 0 -> Failed "Division par zéro"
                              ; x -> Ok $ div a x }

Si on teste evalFailable expr1, on obtient Ok 4, alors que si l’on teste evalFailable expr2, on obtient Failed “Division par zéro”. Parfait, en une dizaine de lignes nous venons de rendre le système des exceptions complètement caduc. Continuons !

Tenir un journal d’activité avec la monade Logger

Imaginons maintenant que nous souhaitons un journal des activités de divisions de notre évaluateur. En quelque sorte, nous voulons conserver une trace des divisions, ainsi que des opérandes, pour les afficher dans un terminal, ou simplement pour les consulter plus tard.

Nous définissons notre type polymorphique paramétré Logger o r, composé d’un log de type o et d’un résultat de type r.

Nous spécifions le comportement monadique, avec une hypothèse particulière sur le type o, que l’on souhaite être un monoïde pour pouvoir composer le log de façon abstraite. Ceci n’a rien à voir avec les monades, mais nous permet simplement de gagner en généricité sur la définition de la monade.

Ici, le comportement de return est d’initialiser un logger, avec l’élément neutre du monoïde comme log initial. Celui de bind m k est d’executer m, en extrayant le log o1 et la valeur a, puis d’exécuter k a en extrayant le log o2 et la valeur b. Ensuite, il compose o1 et o2 avec l’opération du monoïde, et finalement retourne le log composé ainsi que la valeur résultante.

import Data.Monoid

data Logger o r = Logger { output :: o
                         , result :: r } deriving Show

instance (Monoid o) => Monad (Logger o) where
  return e = Logger mempty e
  m >>= k = let (Logger o1 a) = m
                (Logger o2 b) = k a
                out = mappend o1 o2 in
            Logger out b

Première application de cette monade, très simple, pour compter le nombre de divisions qui ont lieu dans l’évaluation. Pour cela, il suffit de faire la division et de renvoyer le résultat, accompagné de (Sum 1), qui forme le monoïde (Sum 1, 0, +).

evalCount :: Term -> Logger (Sum Int) Int
evalCount = makeEvalM divCount where
  divCount :: Int -> Int -> Logger (Sum Int) Int
  divCount a b = Logger (Sum 1) (div a b)

Dans notre cas, output (evalCount expr1) renvoie 2, ce qui est bien le nombre de divisions qui ont eu lieu.

Autre utilisation classique, la tenue d’un journal d’activité. (String, ““, ++) est un monoïde, nous l’utiliserons donc pour ce journal. Ici, notre divLogger fait la division, et tient son journal. Il retourne simplement les deux, dans un objet *Logger.

evalLogger :: Term -> Logger String Int
evalLogger = makeEvalM divLogger where
  divLogger :: Int -> Int -> Logger String Int
  divLogger a b = 
    let r = div a b
        out = concat ["Division : ",
                      show a, " / ", show b,
                       " = ", show r, "\n"] 
    in Logger out r

Si on évalue output $ evalLogger expr1, on obtient :

• Division : 10 / 2 = 5
• Division : 20 / 5 = 4

ce qui est ce que nous souhaitions. On peut également accèder au résultat en direct avec result $ evalLogger expr1 qui renvoie tout simplement 4.

Conclusion

Nous avons vu ici un petit exemple d’application des monades en Haskell. Le concept des monades étant très vaste, elles ne sont pas limitées à la construction d’évaluateurs ni aux entrées sorties, vous pourrez donc trouver de nombreux autres exemples d’applications, sans rapport direct avec ce que nous avons vu ici, si ce n’est la définition de fonctions monadiques composables.

À Demotera, nous utilisons actuellement Snap, un serveur HTTP haute performance, écrit en Haskell et proposant de nombreuses constructions monadiques pour le parser et pour le contrôle d’execution. À en juger les performances et la facilité d’utilisation (nous faisons un proxy authentifiant avec), il semble que la programmation fonctionnelle pure s’impose comme une alternative sérieuse aux traditionnels langages non-purs. Par ailleurs, de nombreux composants critiques dans le logiciel de gestion de projets AtikTeam sont écrits en programmation fonctionnelle, par souci de fiabilité.

Qu’en pensez-vous ?

Voir aussi :

• Conception d’un parser simple en programmation fonctionnelle
• La conception par les catégories