Les monades sont un des concepts les plus compliqués que j’ai pu rencontrer en apprenant la programmation fonctionnelle. Et malheureusement, comme beaucoup de développeurs, je n’utilise probablement qu’en partie tout leur potentiel. Mais avant de rentrer dans le vif du sujet, il est intéressant de comprendre d’où viennent les monades. Elles viennent des mathématiques, et sont utilisées, à ce que je sache, dans deux langages de programmation : Haskell et C#.

L’idée principale derrière la conception du Haskell était la création d’un langage purement fonctionnel, ie. sans effet de bord. Pourtant, il existe quand même des effets que l’on ne peut éviter. Un premier effet de bord me venant à l’esprit est celui des entrées/sorties (IO). En effet, si vos fonctions devaient toujours renvoyer la même sortie à partir de la même entrée, il serait impossible de représenter des fonctions comme celle renvoyant une string [chaine de caractères si l'on est vraiment chauvin] à partir d’une ligne entrée au clavier par un utilisateur. En fait, les interactions avec la réalité créent des effets de bord.

Afin d’éviter de créer un langage inutilisable, les concepteurs du Haskell ont donc cherché un moyen de séparer les parties de code liées aux effets de bord du reste du code, de façon à ce que les codes pur et impur ne puissent se mélanger. Ainsi, si vous introduisez une fonction impure dans une fonction pure en Haskell, le code est considéré comme impur. Et c’est à ce moment-là que le concept de monades entre en jeu.

Les monades représentent vraiment un concept générique puissant, et qui a beaucoup d’autres applications : comme vous le verrez plus loin, F# n’utilise même pas les monades pour résoudre le problème des IO.

Que sont les monades ?

Wikipedia:

“In functional programming, a monad is a programming structure that represents computations. Monads are a kind of abstract data type constructor that encapsulate program logic instead of data in the domain model. A defined monad allows the programmer to chain actions together and build different pipelines that process data in various steps, in which each action is decorated with additional processing rules provided by the monad. For example, a sequence of arithmetic operations can be controlled to avoid division by zero in intermediate results. Programs written in functional style can make use of monads to structure procedures that include sequenced operations,[1][2] or to define some arbitrary control flows (like handling concurrency, continuations, side effects such as input/output and variable assignment, or exceptions).

Formally, a monad is constructed by defining two operations (bind and return) and a type constructor M that must fulfill several properties to allow the correct composition of monadic functions (i.e. functions that use values from the monad as their arguments). The return operation takes a value from a plain type and puts it into a monadic container of type M. The bind operation performs the reverse process, extracting the original value from the container and passing it to the associated next function in the pipeline.

A programmer uses an existing monad by composing monadic functions to define a new data-processing pipeline. The monad acts as a framework, as it's a reusable behavior that decides the order in which the specific monadic functions in the pipeline are called, and manages all the undercover work required by the computation.[3] The bind and return operators interleaved in the pipeline will be executed after each monadic function returns control, and will take care of the particular aspects handled by the monad.

The name is taken from the mathematical monad construct in category theory, though the two concepts are not identical.”

La définition des monades est assez longue, et difficile à comprendre, gardons-en les idées les plus importantes :

  • “A monad is a programming structure that represents computations” - une monade est une structure de programmation qui représente des calculs
  • « A defined monad allows the programmer to chain actions together » – une monade, lorsqu’elle est définie en amont, permet au développeur d’enchainer une séquence d’actions
  • « A monad is constructed by defining two operations (bind and return) and a type constructor M that must fulfill several properties to allow the correct composition of monadic functions » – une monade se construit par la définition de 2 opérations (appelées bind et return) et d’un constructeur de type, noté M, qui doit vérifier un ensemble de propriétés permettant la composition de fonctions monadiques.

 

Mieux vaut un bon exemple qu’un long discours

Disons que vous voulez définir une fonction permettant de chercher un élément présent dans une liste de paires (clé, valeur), avec en entrée sa clé associée. Cette fonction pourrait avoir le type suivant : (‘a –> (‘a * ‘b) list –> ‘b) si un opérateur d’égalité est défini pour le type ‘a.

Dans l’exemple qui suit, la liste de paires correspond à un annuaire. Cet annuaire associe des noms à leurs numéros de téléphone. Dans cette liste, je veux récupérer un numéro de téléphone à partir d’un nom donné :

image

À propos des noms choisis dans cet exemple : À l’époque des Royaumes Combattants (époque Sengoku), tout le cours de l’histoire du Japon aurait pu être changé le 21 juin 1582, si seulement Hideyoshi avait eu un téléphone portable. Car c’est parce qu’une simple lettre est arrivée en retard, que le Daimyo (noble Japonais) le plus puissant de l’époque, Oda Nobunaga est mort, assassiné par un de ses hommes, le samouraï Mitsuhide, qui avait mal interprété ses véritables intentions !

clip_image002

Notre fonction lookFor marche bien, mais son comportement est assez lourd : lorsque la clé donnée n’est pas trouvée, elle lance une exception. Dans le cas d’un langage typé dynamiquement, on pourrait retourner une valeur qui aurait un certain sens au regard de cette fonction de recherche : une valeur booléenne fausse par exemple si la clé cherchée n’est pas trouvée. Dans des langages comme le C#, vous pourriez utiliser la valeur null, mais vous savez probablement déjà que null ne doit être utilisé en prenant quelques précautions. Si ces précautions ne sont pas prises en amont, des null reference exceptions pourraient apparaître dans votre code : les valeurs retournées doivent ainsi être vérifiées à chaque nouvel appel de fonction. C’est pourquoi en C#, sans la notion d’exception, la propagation et la gestion des erreurs ressembleraient à peu près à du C :

clip_image003

A ce stade, il est intéressant de noter que l’indentation fait que le code se déporte sur la droite, et à quel point de ce fait il devient difficile de le lire. J’en reparlerai un peu plus tard.

Nous voudrions que nos fonctions puissent retourner soit un résultat valide soit une valeur ayant assez de sens pour nous indiquer que l’opération a échoué. S’il y a échec de l’opération, le statut devrait être propagé et les étapes de calcul suivantes sautées. Et si possible, tout cela en évitant d’avoir à écrire tout le code permettant d’arriver à effectuer cette propagation (et qui fait que le code se déporte peu à peu vers la droite, comme on a pu le voir ci-dessus).

Croyez-le ou non, mais les Monades peuvent nous aider à atteindre cet objectif.

Dans un premier temps, on va créer un type représentant le fait que l’opération puisse retourner avec succès ou non une valeur. Et puis, on va redéfinir notre fonction lookFor de façon à ce qu’elle utilise ce nouveau type.

clip_image004

Le type maybe est un type générique : quand la fonction trouve une valeur, Just value est retourné, et lorsqu’elle n’en trouve pas, Nothing va être retourné :

clip_image005

Bien qu’ayant un peu plus de sens, on n’a rien ici de plus qu’un équivalent du pattern « retourner une valeur valide ou retourner null » que l’on a pu voir plus haut avec le C#.

Remarque : Il existe déjà un équivalent au type Maybe<’a>, il est défini dans la bibliothèque standard de F# et s’appelle option<’a>.

Disons que je veuille créer une fonction qui, à partir d’un annuaire, va vérifier que tous les contacts de mes amis sont dedans, et me retourner leurs numéros. Si un des numéros ne se trouve pas dans l’annuaire, la fonction devrait me signaler qu’elle n’a pas réussi à le trouver. Si vous suivez le modèle mettant en place une cascade de if, vous devriez vous retrouver avec un code à peu près comme celui-ci :

clip_image006

C’est plutôt moche non ? On se retrouve encore avec toutes ces redondances pour vérifier les valeurs retournées, et le code continu à se déporter vers la droite. On va essayer de factoriser un peu tout ça dans un premier temps :

clip_image007

On utilise ici un pattern assez commun dans les langages de programmation fonctionnelle qui consiste à capturer les continuations à l’aide de clôtures (cf. mon article sur les continuations). Si vous êtes un(e) habitué(e) des langages non fonctionnels et que vous avez fait du code asynchrone, vous connaitrez peut-être le concept des callbacks qui est assez similaire à ce pattern.

Ici, nous avons donc réussi à factoriser les expressions conditionnelles match en définissant en amont une fonction de vérification. Cette fonction prend en entrées une valeur Maybe et une fonction représentant une continuation ; et, en fonction de la valeur, son exécution s’arrête ou continue en prenant la valeur encapsulée par le constructeur Just.

Nous nous rapprochons de la notion de Monade, en fait en généralisant un tout petit peu plus notre code, on arrive à cette notion. Conceptuellement, nous avons : un contexte (le type représentant la possibilité d’avoir un échec), ce contexte encapsule une valeur, et grâce à une fonction (check dans notre exemple) nous sommes capables de propager ce contexte au travers des différentes étapes de notre calcul en extrayant et en encapsulant à nouveau la valeur au sein du contexte. La fonction que nous utilisons pour encapsuler à nouveau la valeur dans un contexte est dans notre cas particulier le constructeur de type Just.

Si vous vous rappelez, un des points que nous avons souligné au début du post est : “A monad is constructed by defining two operations (bind and return) and a type constructor M that must fulfill several properties to allow the correct composition of monadic functions” - Une monade se construit par la définition de 2 opérations (appelées bind et return) et d’un constructeur de type, noté M, qui doit vérifier un ensemble de propriétés permettant la composition de fonctions monadiques.

La fonction check que nous avons définie tout à l’heure correspond justement à l’opération bind, et notre constructeur Just à l’opération return :

clip_image008

OK, je sais ce que vous pensez : j’ai juste renommé quelques fonctions. Mais il est important de bien voir ces deux opérations. Et en les définissant, nous avons officiellement créé notre première Monade !

 

Mais une Monade, en fait, c’est juste ça ???

Non non, ne vous inquiétez pas, il y en a encore en réserve. Le pattern que je vous ai montré précédemment peut apparaître comme particulièrement adapté à mon problème de gestion d’erreur, mais en réalité c’est un pattern très générique ! Tellement générique que les monades ont leur propre syntaxe en Haskell et en F#.

Mais, dans un premier temps, je dois vous avouer que je vous ai menti : les monades ne sont pas vraiment appelées monades en F#, mais plutôt workflows, ou « expressions de calcul» (computational expressions). Et si vous vous rappelez bien du deuxième point que nous avions souligné dans la définition d’une monade : « A defined monad allows the programmer to chain actions together » – Une monade, lorsqu’elle est définie en amont, permet au développeur d’enchainer une séquence d’actions ; vous pouvez désormais mieux comprendre pourquoi nous l’avions mis en exergue. Cet enchainement d’actions correspond exactement à ce que l’on a pu faire dans notre exemple de gestion d’erreur : nous avons enchainé les appels de fonctions, de façon à ce que le contexte d’échec soit géré et propagé entre les différents appels.

Pour définir une monade en F# et utiliser les avantages de la syntaxe que je vais vous présenter dans un court instant, nous avons besoin de définir un type constructeur.

Un constructeur est une classe .NET qui contient des définitions de méthodes : pour les opérations bind et return, et éventuellement aussi pour d’autres opérations liées aux monades en F#. Pour que cette classe soit correctement définie, nous devons implémenter au moins 3 méthodes : Return(value), Bind (value, continuation) et Zero(). La méthode Zero() retourne la valeur monadique par défaut. Une fois que l’on a mis en place cette classe, on l’instancie.

clip_image009

La méthode ci-dessus est la méthode correcte pour définir une monade de base en F#.

On peut alors profiter d’une syntaxe plus sympathique pour réécrire notre fonction getContactNumbers.

clip_image010

Admirez donc ce code !

Notre code qui auparavant se déportait sur la droite et n’était que difficilement lisible est maintenant véritablement propre et concis. Que s’est-il passé pour qu’on puisse arriver à un si joli résultat ? Nous avons en fait utilisé notre instance, une jolie typo et les nouveaux mots-clés let ! et return de façon à améliorer la lisibilité. En réalité, let ! ne fait qu’appeler l’opération Bind(…) de notre monade, capturant de façon implicite la continuation actuelle, tandis que le mot-clé return appelle notre méthode Return(…). Si vous êtes un (e) habitué (e) de la programmation impérative, il est vraiment important que vous compreniez que le mot-clé return n’a rien à voir avec le mot-clé return tel que vous pourriez le rencontrer en C, C++ ou en C# par exemple : ça ne va pas arrêter l’exécution, return correspond juste au moyen d’encapsuler une valeur dans un contexte tel qu’il est exprimé par la monade utilisée.

 

Vous connaissez déjà bien une monade…

Je vous ai expliqué le concept de monade : bien qu’étrange au premier abord, c’est un concept générique et vraiment puissant. La preuve en est que si vous avez lu mon article précédent, qui était sur les séquences, vous avez déjà rencontré et utilisé les monades.

En effet, les séquences en F# sont des monades ! Et en Haskell, même les listes sont des monades. Et pourquoi ça ? Tout simplement, parce que si vous prenez le temps de bien y réfléchir, les listes ou les séquences sont simplement un contexte entourant des valeurs, et vous voulez peut-être propager ce contexte que forment les séquences au travers d’un enchainement de calculs tout en modifiant les valeurs qui y sont encapsulées.

clip_image011

Ici, le mot-clé yield est un mot-clé strictement équivalent au mot-clé return, il a été introduit pour rendre l’utilisation du mot-clé return plus naturel pour les séquences. Si vous connaissez la notion de générateurs dans des langages tels que le Python ou le C#, vous comprendrez probablement pourquoi.

Windows 8, bientôt là…

Comme vous le savez probablement déjà, Windows 8 sortira dans quelques semaines. Si vous essayez déjà de voir comment développer des applications avec une interface Metro en C#, vous avez du rencontrer 2 nouveaux mots-clés (C# 5.0) : async et await.

WinRT, la bibliothèque native qui se cache derrière Metro, a été conçue pour utiliser et forcer l’utilisation d’un modèle asynchrone pour gérer le parallélisme. L’utilisation du parallélisme est nécessaire pour gérer, hors du thread UI dédié à l’interface utilisateur, des opérations chronophages, de façon à éviter un freeze de l’interface utilisateur et une dégradation de l’expérience utilisateur.

Le principal avantage du modèle asynchrone est que cela empêche la plupart des développeurs (95 % d’entre eux ?) de continuer à manipuler au petit bonheur la chance les threads et la synchronisation objet. En effet, la plupart des développeurs ne savent pas comment utiliser correctement le parallélisme et…

UN DEVELOPPEUR NEOPHYTE + THREADING + EFFETS DE BORD = CHAOS

Vous pouvez remplacer chaos par :

    • Interblocage (Deadlocks)
    • Incapacité à déboguer correctement les programmes
    • Un programme qui crashe une à deux fois par mois sans raison
    • Crashs informatiques
    • Accidents de train
    • Accidents d’avion
    • Fin du monde ?

Et maintenant, je suis même en train de me demander si ce n’est pas la raison pour laquelle la programmation fonctionnelle a récemment fait son comeback.

En effet, nous sommes dans l’ère du parallélisme : des processeurs multicœurs/ calculs distribués et ressources partagées avec le Cloud/ web et communication (avec une augmentation de la part des entrées/sorties dans les programmes). Les langages de programmation fonctionnelle, en décourageant les effets de bord, rendent le parallélisme plus sûr, et facilitent son usage grâce à de nombreux concepts puissants.

Le principal désavantage du modèle asynchrone est qu’il n’est pas naturel. Regardons par exemple ce programme en C# :

clip_image012

Grâce à toutes ces lignes de code, je ne fais que lire 3 lignes d’un Stream en utilisant une méthode asynchrone, puis je les affiche. Admirez à quel point ce code peut être intuitif …Et réjouissez-vous : sans clôture en C#, vous ne pourriez pas l’écrire si facilement.

Plus haut, lorsque nous étions en route vers une meilleure compréhension du concept de monades, j’ai écrit que les callbacks pouvaient être considérés comme un concept similaire aux continuations. Regardez le code : il se déporte vers la droite, et nous capturons des continuations, le fameux « quelle opération devrait s’exécuter ensuite ». Vous le devinez maintenant, il y a une monade pour s’occuper des opérations asynchrones.

En F#, elle correspond à async et s’utilise ainsi :

clip_image013

Ici, let ! permet de capturer la continuation actuelle et de l’appeler avec le résultat une fois que la page est téléchargée.

C# : le prochain langage de programmation fonctionnelle ?

Croyez-le ou non, mais après avoir emprunté le concept de ramasse-miettes (LISP), du paradigme de la POO (LISP), des clotûres, Linq, C# emprunte désormais un autre concept puissant au monde de la programmation fonctionnelle : les monades, et plus précisément la monade async.

Les concepteurs de WinRT ont fait un choix : entre donner la permission aux développeurs d’utiliser les threads – ie. « permettre à des enfants de jouer avec un bazooka » - et passer à un modèle de programmation peu naturel pour les langages impératifs. Pour transformer le C#, asynchrone, en un langage utilisable, ils avaient besoin d’un ajout puissant venant de la programmation fonctionnelle.

Mais il nous reste quand même un problème : qui, parmi les développeurs C#, connaît les monades ?

Qui sait que le mot clé await est en réalité un bind déguisé qui capture la continuation actuelle au sein d’une méthode async ?

Vous pourriez arguer, et vous auriez raison, que la remarque n’est pas forcément très pertinente, car l’important est de savoir comment se servir du concept. Et moi, je vous répondrais que les concepteurs de SE pensaient la même chose quand ils ont introduit la notion d’ordonnancement préemptif et ont donné aux développeurs des APIs process et threading.

 

- Dorian Corompt -

- Traduit de l’anglais par Céline Bouillon -