Théorie des catégories et programmation :

Correspondance parfaite ou distraction abstraite ?

Ce billet est la traduction d'un billet écrit en anglais par cdsmith: Why do Monads Matter?

Théorie des catégories et programmation : correspondance parfaite ou distraction abstraite ?
Si vous êtes un développeur : avez-vous entendu parler des monades ? Vous êtes-vous demandé de quoi il s’agissait ? Avez-vous tenté d’apprendre Haskell et lutté avec cette notion ? Avez-vous regardé des vidéos de « Channel 9 » où un tas de chercheurs de Microsoft en parlent, mais ont du mal à faire le lien avec votre expérience de tous les jours ?

Si vous êtes un mathématicien : avez-vous entendu parler l’intérêt de la théorie des catégories pour la science informatique ? Avez-vous cherché un énoncé clair des raisons de cet intérêt ? Douté qu’il y en ait de satisfaisantes ? Peut-être que, comme un de mes amis qui m’a interrogé à ce sujet il y a un an, vous vous rappelez avoir entendu que la théorie des catégories avait suscité beaucoup d’excitation dans la recherche informatique des années 90, mais n’avez jamais su si c’était une impasse ou si cela avait débouché ?

C’est le genre de questions auxquelles je vais répondre. Mon but est de démontrer, précisions et exemples à l’appui:
- d’où viennent les idées et intuitions relatives à la théorie des catégories en informatique
- pourquoi le futur de la programmation repose sur ces idées, et pourquoi les ignorer, comme le font les langages les plus répandus, est dommageable
- quel est l’état de l’art dans l’application de la théorie des catégories aux problèmes posés par l’informatique

Si vous vous lancez dans cet article sans aucune notion sur la théorie des catégories, n’ayez pas peur ! C’est une des introductions les plus progressives aux catégories et aux monades que vous pourrez trouver. Cependant, lisez lentement pour bien comprendre la définition des catégories et des idées connexes, comme la composition de fonction, qui sont cruciales. Par ailleurs, vous pouvez passez outre ou rapidement sur la section « Quel est le rapport avec les monades ? » où j’explique en quoi le sujet correspond au sens donné traditionnellement aux monades par les mathématiques : il n’est pas vraiment nécessaire de le savoir.

En revanche, si vous êtes mathématicien, vous pouvez laisser tomber les rappels basiques sur la théorie des catégories et approfondir plutôt les passages où j’adopte la perspective des sciences informatiques. Attention tout de même, j’introduis les monades via les catégories de Kleisli, donc prenez le temps de vous assurer que vous êtes familiers de la relation entre les deux.

Prêts ? Allons-y !

Programmation informatique et fonctions : une relation ténue.
Question rapide : les programmeurs utilisent-ils des fonctions ?
Demandez à n’importe quel programmeur, il vous répondra : OUI ! Les fonctions sont un des outils les plus basiques de la programmation. Vous aurez droit à un regard atterré : bien sûr ! Autant demander si les charpentiers utilisent des clous, non ?

La vérité est pourtant un peu plus compliquée. Pour un mathématicien, une fonction associe simplement des valeurs d’entrée et des valeurs de sortie… et c’est tout ! Deux fonctions qui associent les mêmes valeurs d’entrée aux mêmes valeurs de sortie sont identiques. Vous pouvez représenter des fonctions par des formules, mais aussi, simplement, par des tables d’entrée/sortie, ou par des graphes s’il s’agit de nombres réels. Si vous demandez des exemples de fonctions à des programmeurs, pourtant, ils seront bien différents : pour les appeler des fonctions, il faudrait avoir raté le cours d’analyse. Ce sont des choses que les programmeurs appellent sans arrière-pensée des fonctions, mais qui n’en sont pas du tout pour les mathématiciens :
- des « fonctions » qui renvoient des nombres choisis au hasard… et donneront des résultats différents à chaque appel ;
- des « fonctions » qui renvoient une réponse le dimanche, mais une autre le lundi, encore une autre le mardi, et ainsi de suite ;
- des « fonctions » qui font apparaître des mots sur l’écran d’un ordinateur à chaque calcul d’une valeur.

Qu’est-ce que cela peut bien vouloir dire ? La plupart des programmeurs vivent paisiblement en appelant ces choses des fonctions, alors qu’elles en sont bien différentes. Mais une seconde ! Ces deux notions ont quand même beaucoup en commun. En particulier : (a) des paramètres, qui représentent leur domaine de départ et (b) des valeurs de retour, qui représentent leur domaine d’arrivée (bien des programmeurs parlent de fonction qui n’ont ni argument, ni valeur de retour… mais pas la peine d’être pointilleux, il suffit de regarder leurs domaines de départ et d’arrivée comme des ensembles à un élément, et on sauve les apparences)

Encore plus important, ces « fonctions » ont en commun avec les fonctions mathématiques d’être constamment composées, en prenant en paramètre le résultat d’une autre fonction. Quand je parle de composition, c’est presqu’exactement au sens mathématique : (f . g) (x) = f(g(x)). D’ailleurs, la raison pour laquelle les fonctions existent est pour pouvoir les composer entre elles ! Autrefois, dans les premiers temps de l’informatique, on se satisfaisait de garder trace d’une information en la stockant à un endroit déterminé de la mémoire; mais devoir garder trace de tous ces emplacements compliquait l’écriture séparée des parties d’un programme pour les assembler ensuite ; on est donc passé à l’utilisation de fonctions et de leur composition.

Récapitulons une première fois :

Quand les programmeurs parlent de fonctions, il s’agit d’un concept différent de celui des mathématiciens.
Ce qu’ils entendent c’est : des valeurs d’entrée (le domaine d’entrée) et des valeurs de retour (domaine d’arrivée), et encore plus important, la composition de ces objets.

Puis vint la théorie des catégories…
Nous avons conclu la section précédente les mains pleines de choses qui ressemblent à des fonctions, qui ont des domaines d’entrée et d’arrivée, et peuvent être composées. Pour autant, elles diffèrent des fonctions au sens mathématique. Déconcertant ? Non, pas vraiment. Les mathématiciens connaissent bien cela : ils ont un nom pour les systèmes d’objets « fonctionnesques » de ce genre, et ce nom est … roulement de tambours… CATEGORIES !

Dans le jargon mathématique, les catégories sont :
- des collections « d’objets » (pensez à des ensembles),
- et de « flèches » (pensez à des fonctions entre les ensembles)
- où chaque flèche a une domaine d’entrée et de sortie
- chaque objet a une flèche « identité » (pensez à la fonction d’identité f(x) = x
- et où les flèches peuvent être composées quand les domaines d’arrivée et d’entrée correspondent

Avant d’accepter quelque chose comme une catégorie, il faut ajouter quelques règles : une fonction composée avec la fonction d’identité ne change pas, et la composition de fonctions obéit à la loi d’associativité. Cela n’est en soi pas surprenant, donc si cela devait vous paraître étrange, prenez un stylo, travaillez la définition de la composition de fonctions ( (f . g) (x) = f(g(x)) ) et simplifiez.

Voilà l’intérêt des catégories : ce n’est pas une abstraction inventée sans but par une bande de mathématiciens. Les catégories sont définies de cette façon parce qu’on a remarqué que des centaines d’objets ressemblaient à des fonctions, avec des domaines d’entrée et de sortie et des compositions. Des objets de l’algèbre, comme les groupes, les anneaux et les espaces vectoriels ; des objets de l’analyse, comme les espaces métriques et topologiques ; des objets de l’analyse combinatoire, comme les éléments d’ensembles partiellement ordonnés ou les chemins des graphes ; des objets de la logique formelle, comme les preuves et les propositions. Ces objets peuvent presque tous être décrits avec les idées que nous venons de voir ! En bref, les catégories sont l’intuition juste pour traiter des objets qui ont un domaine d’entrée et de sortie et se composent. Et c’est justement ce que nous cherchons à faire.

Les quatre cavaliers de la Catapocalypse
Vous voyez maintenant ce que viennent faire ici les catégories : elles sont l’intuition juste de choses qui ne sont peut-être pas des fonctions, mais peuvent être composées comme des fonctions. Plus encore, ces idées de la théorie des catégorie répondent à des problèmes rencontrés par les développeurs informatiques.

Il est temps d’être plus spécifique et d’introduire les quatre exemples qui nous guideront dans notre exploration. Chaque exemple illustre une façon dont les « fonctions » utilisées par les programmeurs diffèrent des fonctions des mathématiciens. Ces exemples reprennent des problèmes réels rencontrés par les programmeurs. Nous reviendrons sur l’aspect pratique de la question mais, pour l’instant, prenons le temps de nous familiariser avec chacun d’entre eux .

Le premier cavalier : l’échec.
Le premier problème est celui de l’échec. Un programmeur tente souvent des choses qui peuvent échouer. Lire un fichier (il peut ne pas exister, on peut être privés des droits d’accès), communiquer par Internet (le réseau peut être coupé ou trop lent), et même faire de bons vieux calculs avec une grande quantité de données (on peut manquer de mémoire). En conséquence, l’échec est un souci constant.

En général, les outils modernes de programmation informatique comptent sur la possibilité d’échec d’une fonction. Vous pouvez disposer d’une valeur de retour, mais vous pouvez aussi recevoir une raison pour l’échec de la tâche demandée. Quand cela se produit, le programmeur est responsable de la réponse à apporter : avertir quelqu’un, nettoyer la mémoire de l’ordinateur, ou parfois remettre les choses en état pour continuer. La façon dont ils permettent de traiter la possibilité constante d’un échec est un élément majeur dans le choix des techniques et des outils de développement.

Le deuxième cavalier : la dépendance
Le deuxième cavalier est la dépendance à des informations extérieures. Tandis que les fonctions des mathématiciens ne dépendent que de leurs arguments, les programmeurs n’ont pas ce luxe. Les applications sont souvent un cauchemar de paramètres de configuration. Même les téléphones mobiles les plus simples ont des pages et des pages de paramètres : quelle est la langue de l’utilisateur ? la fréquence de sauvegarde ? faut-il crypter les communications ? Rares sont les applications qui n’ont pas un menu « paramètres » ou « préférences ». Dans bien d’autres contextes, les programmes dépendent d’informations qui sont un genre de « savoir partagé » de l’application ou d’une partie de celle-ci.

La façon de traiter la question a évolué à travers les âges. Quand l’information était de toute façon rangée dans des régions bien connues de la mémoire, il était assez facile de la retrouver ; mais cela conduisait à d’autres problèmes quand différentes parties du programme devaient stocker différentes informations et pouvaient se marcher sur les pieds. La technique extrêmement influente de la programmation orientée objet peut être vue, au moins partiellement, comme une tentative de résolution du problème, par le regroupement de fonctions dans un objet contenant le contexte dont elles dépendent… mais quand les dépendances sont nombreuses, passer tout ces paramètres n’a plus rien de pratique.

Le troisième cavalier : l’incertitude
Le troisième problème est l’incertitude, ou encore non-déterminisme. Une fonction normale associe une valeur d’entrée et une valeur de sortie. Une fonction non-déterministe associe une valeur d’entrée à un certain nombre de valeurs de sorties possibles. Le non-déterminisme est moins bien connu que les deux premiers problèmes, mais peut-être parce qu’il n’a pas encore été résolu par un langage généraliste !

En effet, si la science informatique théorique traite abondamment du sujet, parce que c’est l’approche adaptée à un grand nombre de problèmes tels que l’analyse syntaxique, la vérification ou simplement les recherches, il n’a pas encore fait son chemin dans la pratique informatique.
Le non déterminisme apparaît lorsque de multiples réponses peuvent correspondre à une requête ou une recherche, c’est-à-dire précisément là où le programmeur finit par dépendre d’outils extérieurs comme SQL, Prolog ou, plus récemment, LINQ et d’autres technologies intégrées au langage.
Et lorsqu’une tâche ne paraît pas justifier l’utilisation d’un outil calibré pour le requêtage intensif ou les recherches, on finit par écrire ses propres boucles imbriquées et des structures de contrôles pour parcourir tous les possibles. Ce genre de situation est responsable de structures de code parmi les plus complexes qu’on puisse rencontrer aujourd’hui.

Tandis que les deux premiers problèmes, échec et dépendance, ont été en partie résolus par des langages couramment utilisés, ce problème est traité principalement au moyen de sous-langages spécialisés, à la notable exception de LINQ.

Le quatrième cavalier : destruction.
Le quatrième problème est la destruction. Evaluer une fonction mathématique a pour seul effet d’obtenir la valeur retour. Mais dans un programme, les fonctions peuvent avoir un effet permanent sur le reste du monde : afficher une information, attendre les réponses d’autres ordinateurs, imprimer des documents et même envoyer des missiles, pour des systèmes militaires ! En conséquence, des points qui n’ont pas besoin d’être précisés en mathématiques, comme l’ordre d’évaluation, restent très importants.

La nature destructrice (par quoi j’entends : qui a des effets irréversibles) des programmes informatiques a de nombreuses conséquences. Elle augmente le nombre d’erreurs commises. Elle rend plus difficile de diviser une tâche et de l’accomplir simultanément en plusieurs endroits, comme on pourrait vouloir le faire sur un ordinateur multi-cœur moderne, parce que l’ordre dans lequel on le fait peut être incorrect. Mais d’un autre côté, la destruction est justement l’intérêt premier de la programmation : une application qui n’aurait pas d’effet observable ne vaudrait pas la peine d’être lancée ! Donc nos fonctions doivent affronter la question de la destruction, dans tous les langages couramment utilisés.

Retour aux fonctions
Nous avons inspecté des problèmes trouvés dans le monde informatique : le développement de logiciels qui peuvent échouer, doivent gérér plein de paramètres contextuels, modélisent des choix non-déterministes et ont parfois des effets sur les monde qui contraignent l’ordre des calculs.

Il peut sembler que nous sommes très loin du monde simple et gentil des mathématiques. Et pourtant ! En y regardant de plus près –et en louchant suffisamment- chacune de ces quasi-fonctions peut être reconnue, après tout, comme une bonne petite fonction bien élevée. Il y a un coût, néanmoins : pour les transformer en de véritables fonctions nous devons modifier leur domaine d’arrivée. Voici comment cela fonctionne pour chacun des cavaliers.

Fonctions et échec
Notre premier exemple était les fonctions qui peuvent échouer. Il n’est pas si difficile de voir qu’une fonction susceptible d’échec est en fait une fonction dont le résultat inclut :
- des succès, qui sont les résultats possibles et attendus
- des échecs, qui décrivent la raison de l’échec

Donc pour tout ensemble A, nous pouvons définir un nouvel ensemble Err(A) qui contient A et les différentes raisons pour lesquelles l’échec est possible. Une fonction susceptible d’échec avec un domaine d’entrée A et un domaine d’arrivée B est en fait une fonction de A vers Err(B).

Fonctions et dépendance
Nos deuxièmes pseudo-fonctions sont celles qui dépendent d’informations extérieures, comme les paramètres d’une application. Nous utilisons ici une astuce similaire : pour un ensemble A, nous définissons un ensemble Param(A) qui est l’ensemble des fonctions partant des paramètres de l’application pour parvenir à l’ensemble A. Dès lors, une fonction « à contexte » de A à B est une fonction ordinaire de A à Param(B). Autrement dit, vous lui donnez une valeur issue de A et elle vous rend une fonction qui lie les paramètres de l’application à l’ensemble B.

Aussi déconcertant que cela puisse paraître, une fonction dont le domaine d’arrivée est une autre fonction est simplement une fonction à deux arguments, à l’exception du fait qu’elle prend ses arguments un à la fois ! Prenez une minute pour vous en convaincre. La conversion entre ces deux idées équivalentes est parfois appelée « currying ». Donc en modifiant le domaine d’arrivée de cette fonction, nous lui avons en fait adjoint un nouveau paramètre : les préférences enregistrées par l’application. Bien que ce ne soit pas très pratique (nous couvrirons cet aspect plus tard) , c’est exactement ce que nous souhaitions.

Fonctions et incertitude
C’est peut-être l’exemple le plus facile à résoudre. Notre troisième type recouvrait les fonctions qui représentent le non-déterminisme : au lieu d’une réponse déterminée, elles renvoient toutes celles qui sont possibles. Il suffit donc de définir, pour tout ensemble A, P(A) comme l’ensemble des sous-ensembles de A. Une fonction non-déterministe de A à B est une fonction ordinaire de A à P(B).

Fonctions et destruction
Nous devons enfin traiter les fonctions qui ont un effet destructeur. Notre réponse sera un peu plus élaborée : pour tout ensemble A, nous définissions IO(A) (pour input/output, qui correspond à la notion d’effets résultant de l’interaction avec le reste du monde). Un élément de l’ensemble IO(A) est une liste d’instructions pour obtenir un membre de A : ce n’est donc pas un membre de A, mais plutôt la façon d’en obtenir un, et cette procédure peut avoir un nombre quelconque d’effets observables.

Nous utilisons la même astuce et modifions le domaine d’arrivée : une fonction destructrice de A à B est une fonction mathématique ordinaire de A à IO(B). Autrement dit, si vous me donnez un A, comme je suis une simple fonction mathématique, je ne peux pas parcourir les étapes jusqu’à B mais je peux vous dire lesquelles il faut respecter.

Mais qu’en est-il de la composition ? C’est merveilleux d’être de retour dans le monde simple des fonctions, mais vous souvenez-vous de ce qui nous y a conduit ? Nous voulions des fonctions parce que nous voulions pouvoir les composer, mais il semble que ce ne soit plus possible ! J’avais des fonctions, susceptibles d’échec, de A à B et de B à C, je les ai échangées contre des fonctions de A à Err(B) et de B à Err(C) et les domaines ne correspondent plus, je ne peux plus les composer !

Oh non !

Retenez vos montures, Heinrich Kleisli arrive à la rescousse
Bon, tout n’est pas perdu, c’est juste que je n’ai pas dit encore comment composer ces fonctions « spéciales ».

Parce qu’un matheux a découvert ces choses avant nous, on les appelle par son nom : ce sont les flèches de Kleisli. Faites attention parce qu’il y a deux choses à garder à l’esprit : premièrement, les flèches de Kleisli sont de bonnes vieilles fonctions, on peut les composer comme des fonctions et c’est parfait; mais en même temps elles sont « spéciales » et on peut également les composer comme des flèches de Kleisli.

Vous vous souvenez de ce qu’on avait dit ? La bonne façon de penser la composition est de penser par catégorie. Les ensembles sont une catégorie, et c’est celle qu’utilise les fonctions mathématiques. Mais nous voulons un autre genre de catégorie désormais, appelée catégorie de Kleisli. Si vous avez oublié la définition des catégories, c’est le moment de la revoir. Pour définir une catégorie, on a besoin d’objets, de flèches, d’identités et de composition.

Pour rester simple, les objets de la nouvelle catégorie seront les mêmes : ce sont juste des ensembles de choses.
Les flèches, sans surprise, sont des flèches de Kleisli.

Je ne vous ai pas encore dit à quoi ressemblent les identités et la composition, alors voici :

Commençons par l’échec : soient une flèche de Kleisli « échec » de A à B, et une de B à C. Nous cherchons à les composer en une flèche Kleisli de A à C. En d’autres mots, nous avons une fonction ordinaire de A à Err(B) et une autre de B à Err(C) et nous en cherchons une qui va de A à Err(C). Prenez une minute pour y réfléchir.

L’idée centrale de la gestion des erreurs est que si la première fonction donne une erreur, il faut s'arrêter et déclarer l’erreur. C’est seulement si la première fonction réussi qu’il faut passer à la seconde, et donner le résultat (qu’il s’agisse d’un succès ou d’un échec). Pour résumer :

Si g(x) donne une erreur, alors (f . g)(x) = g(x)
Si g(x) réussit, alors (f . g)(x) = f(g(x))

Pour achever la définition d’une catégorie, nous devons choisir les flèches de Kleisli « identité ». Ce sont celles qui ne font rien du tout, donc qu’on peut composer avec une autre flèche sans la modifier. Les identités sont des fonctions de A vers Err(A) et il se trouve qu’elles sont simplement en l’occurrence les fonctions f(x) = x, comme pour les ensembles. Remarquez qu’elles ne renvoient jamais d’échec, mais toujours des succès.

Je passerai plus rapidement sur les trois exemples suivants, mais j’encourage les lecteurs qui ne trouvent pas le sujet encore assez clair à les travailler plus en détail et à utiliser cette opportunité de se familiariser avec la définition d’une flèche de Kleisli.

Pour les flèches de Kleisli « dépendance », qui sont des fonctions de A à Param(B), souvenez-vous qu’elles équivalent à ajouter un paramètre représentant les préférences de l’application. L’idée maîtresse est que, si mes deux fonctions ont besoin de connaître les préférences de l’application, je dois donner le même paramètre aux deux. Donc composer ces deux flèches de Kleisli construit une nouvelle fonction qui reçoit les préférences comme paramètre et les transmet à ses deux composantes. Quant aux identités, il s’agit de flèches de Kleisli qui reçoivent le paramètre « préférences » mais l’ignorent et renvoient leur valeur d’entrée.

Les flèches de Kleisli « incertitude » ou « non-déterminisme » sont des fonctions de A à P(B), l’ensemble des sous-ensemble de B. Cette fois-ci l’idée est d’essayer toutes les valeurs générées à chaque étape et de collecter l’ensemble des résultats. Donc la composition calcule la deuxième fonction pour chacun des résultats de la première et les résultats sont fusionnés par union des ensembles. Les identités, bien sûr, ne sont pas réellement non-déterministes mais retournent des ensembles d’un élément contenant leur valeur d’entrée.

Enfin, les flèches de Kleisli pour les effets destructeurs sont des fonctions de A à IO(B). Là, l’idée est de combiner les instructions en les suivant étape par étape : la première d’abord, puis la suivante. Donc la composition consiste à écrire les instructions nécessaires à la première action, puis à la deuxième, dans cet ordre. Une flèche de Kleisli « identité » est l’instruction de ne rien faire et de renvoyer la valeur d’entrée comme résultat.
Ainsi, pour chacun de ces problèmes, nous avons créé une nouvelle catégorie de Kleisli.

Ces nouvelles catégories ont chacune en propre leurs identités, composition et autres aspects des fonctions, qui expriment la nature d’un problème spécifique. En utilisant la notion de composition dans la flèche de Kleisi appropriée, vous pouvez résoudre n’importe lequel de ces problèmes anciens de l’informatique de façon aisée et modulaire.

Et voilà la raison pour laquelle il faut s’intéresser aux monades.

Aux monades ? ? ! Ah, oui, il faut quand même que je précise que vous venez de découvrir les monades. Simplement sans utiliser le mot.

Quel est le rapport avec les monades ?
Cette section est destinée à ceux qui veulent connaître les relations entre ce que nous venons de décrire et les monades telles qu’elles sont définies en mathématiques. Si vous ouvrez Wikipedia ou un manuel de théorie des catégories, ce que vous y rencontrerez sera assez différent de ce que nous venons de voir. Vous entendrez parler d’endo-foncteurs, de deux transformations naturelles et de propriétés de commutation entre triangles et carrés.

Nous n’avons pas du tout parlé de foncteurs, et encore moins de transformations naturelles… donc comment aurions-nous pu apprendre ce que sont les monades ? Il s’avère qu’il existe plus d’une façon de décrire les monades. Celle que nous avons utilisée est tout à fait valide. Les déplacements que nous avons fait subir aux domaines d’arrivée de nos fonctions –Err, Param, P et IO- sont véritablement des exemples de monades. Pour s’assurer que ce sont des monades au sens mathématiques, il faudrait travailler dur : prouver que ce sont des foncteurs, élaborer deux transformations naturelles  et  et prouver qu’elles sont naturelles, et enfin prouver les trois lois des monades.

Heureusement, il existe une façon plus simple d’y parvenir. Heinrich Kleisli, que nous avons déjà rencontré, a montré que, s’il est possible de construire une catégorie comme celles de la section précédente, dont les flèches sont simplement des fonctions au domaine d’arrivée modifié, alors il est garanti que votre catégorie constitue également une monade. Ce qui est bien pratique, parce que, comme programmeurs, nous nous intéressons nettement plus à nos flèches de Kleisli qu’au concept mathématique de monade. Rappel : ces flèche de Kleisli sont exactement cette variation sur la notion des fonctions que nous avons utilisée, bien avant de parler de théorie des catégories ! Et Kleisli nous démontre que, tant que la composition fonctionne comme attendu pour nos flèches de Kleisli (associativité + identité), il n’est plus besoin de prouver quoique ce soit d’autre pour être sûr de disposer d’une monade.

Cela reste intéressant, à titre auxiliaire, d’étudier la relation entre les deux. Je ne donnerai pas tous les détails mais au moins la structure et laisserai au lecteur intéressé, un peu familier avec la théorie des catégories, le soin de faire la preuve des propriétés pertinentes. Nous utiliserons Err comme monade, pour choisir un des exemples –mais rien n’est spécifique à Err.

Nous commençons avec Err, qui est déjà une application d’un ensemble vers un autre. Mais la définition traditionnelle demande également que ce soit un foncteur. Donc, si j’ai une fonction f de A à B, j’ai besoin de pouvoir construire une fonction Err(f) de Err(A) à Err(B). Je peux le faire de la façon suivante : dans la catégorie sous-jacente (la catégorie des ensembles, pas la catégorie de Kleisli), je prends une fonction d’identité de Err(A) à Err(A) ; puis je prends l’identité de Kleisli de B à Err(B). Je compose cette identité de Kleisli avec f pour parvenir à une fonction de A vers Err(B). Je peux donc utiliser la composition de Kleisli entre Err(A) -> Err(A) et A -> Err(B) pour parvenir à Err(A) -> Err(B), c’est-à-dire Err(f).
Ensuite, j’ai besoin d’une transformation naturelle , provenant du foncteur identité vers Err : rien de compiqué, les composantes de  sont les identités de Kleisli.
Enfin, je dois trouver une transformation naturelle µ de Err² à Err. Pour accéder au composant de µ auprès de A, je prends la fonctions d’identité de la catégorie sous-jacente de Err(Err A) vers Err(Err A), puis de Err(A) vers Err(A) et je les combine avec la composition de Kleisli pour obtenir la fonction de Err(Err A) à Err A. Voilà le composant de µ.

La construction dans le sens opposé est nettement plus facile. En partant d’une monade Err avec  et µ, la catégorie de Kleisli est construite de la façon suivante :
- les identités sont les composantes de 
- soient une fonction f de A à Err(B) et une fonction g de B à Err(C), je les compose par : µ . Err(g) . f

Encore une fois, les détails des preuves sont laissées au lecteur. J’espère que ce bref détour aura été utile. Dorénavant, j’utiliserai le mot « monade », mais entends à nouveau les monades via les catégories de Kleisli.

Rejoindre la révolution monadique
Récapitulons une fois de plus :
- les programmeurs travaillent par compositions de choses qu’on appelle fonctions
- ces fonctions ne sont pas des fonctions au sens usuel, mais forment une catégorie
- en fait, ce sont bien des fonctions au sens usuel, mais uniquement si l’on en transforme les domaines d’arrivée en quelque chose d’étrange
- la catégorie qu’elles forment est appelée une catégorie de Kleisli, c’est-à-dire en fait une autre façon de voir les monades
- ces monades décrivent de façon satisfaisante les techniques utilisées pour résoudre des problèmes pratiques

Les quatre exemples cités n’épuisent pas le sujet. Ils sont représentatifs de beaucoup, beaucoup d’autres idées qui peuvent être décrites dans le même cadre de pensée. Il me paraît démontré, à ce stade, que celui qui cherche à étudier et analyser les langages de programmation devrait être familier avec certaines idées de la théorie des catégories, et avec les monades en particulier.

Mais qu’en est-il de l’humble développeur, qui n’est pas en train de créer un nouveau langage, ne publie pas d’articles sur l’analyse des langages, mais veut simplement résoudre les problèmes qui se posent à lui tous les jours ? On est en droit de poser la question. Tant que les monades resteront un simple formalisme mathématique pour comprendre ce que les programmeurs entendent par fonction, des préoccupations pratiques justifieront de ne pas chercher à les comprendre.

Il devient de plus en plus clair, cependant, que les monades ont entamé leur chemin vers les question pratiques de la programmation. Dans le passé, les flèches de Kleisli, cette forme modifiée des « fonctions », était déjà utilisée pour construire les langages de programmation. Les fonctions en C utilisaient une certaine flèche de Kleisli, et les fonctions en C++ une autre. Le standard du langage indiquait ce qui était possible et ce qui ne l’était pas, et si nous voulions quelque chose de différent, tant pis. Chaque décennie, peut-être, nous passions à un langage tout neuf et lézardions aux rayons d’une nouvelle caractéristique pour quelque temps.

Le passé : gestion des erreurs
Prenons l’exemple de la monade Err, qui nous fournit des fonctions qui peuvent échouer et faire part de leur échec de façon structurée : réserve faite de quelques détails et extensions, il s’agit au fond de la gestion structurée des exceptions. Les programmeurs ont travaillé sans disposer de gestion des exceptions dans leur langage pendant de nombreuses années. Bien sûr, des langages comme le C sont Turing-complets et peuvent résoudre n’importe quel problème de calcul, y compris la gestion des erreurs. Mais nous n’utilisons pas le concept de catégorie pour penser les calculs possibles : il sert à penser la composition. Sans gestion des erreurs au sein même de la notion de fonction adoptée par des langages comme le C, la composition restait à la charge des programmeurs, « à la main ».

En conséquence, une fonction C qui pouvait échouer devait indiquer un échec dans sa valeur de retour. Dans de nombreux cas, la convention était : « les valeurs de retour ne sont pas là pour indiquer le résultat, mais le succès ou l’échec ». Les bonnes pratiques appelaient à faire suivre chaque appel de fonction ou presque d’instructions de vérification du succès, et le code en devenait à peine lisible. C’était le temps des algorigrammes et autre pseudo-code, parce qu’on n’espérait plus que le code soit lisible au premier regard ! En réalité, en fait, les programmeurs ne testaient le succès de leur fonction que lorsqu’ils croyaient l’échec possible, et de nombreuses erreurs n’étaient pas détectées. Les programmes n’étaient souvent pas fiables et un nombre inconnu de milliards a été probablement dépensé en développement supplémentaire et en correction de bugs.

Pourquoi cela ? C’est assez simple : parce que le C et les autres langages du temps reposaient sur un type de flèche de Kleisli insuffisant ! Si leur flèche de Kleisli avait inclus les fonctionnalités de la monade Err que nous avons définie, cela aurait pu être évité. Mais le concept de fonction supporté par le C étant fixe, la seule solution était de faire avec, et finalement de migrer vers un autre langage de programmation, avec réécriture de tout un tas de logiciels, et dépense d’un nouveau nombre inconnu de milliards.

Le présent : variables globales et contexte
Qu’en est-il de la monade Param et des autres évoquées ? Comme nous l’avons dit, il s’agit de définir des opérations ayant accès à une information extérieure et à l’état du reste du monde.

Dans le passé, nous utilisions des variables globales, l’équivalent à peine plus moderne du stockage d’information à un endroit connu de la mémoire. Vite fait, mal fait, et les programmeurs d’il y a 30 ans savaient déjà que ce n’était pas une solution satisfaisante, impraticable pour des applications de plus grande taille. La programmation orientée objet a permis d’atténuer ce problème, en plaçant les fonctions dans un « objet » qui leur sert de contexte et qui est transmis implicitement. Pour obtenir ce résultat, il a fallu changer de langage de programmation pour améliorer, une fois de plus, la flèche de Kleisli utilisée. Néanmoins, la solution apportée par les langages orientés-objet reste imparfaite.

Le futur proche (/présent) : pureté, effets, parallélisme, non-déterminisme, continuations et plus !
Je parle ici au futur, mais tout est déjà possible, à condition de choisir le langage approprié !

Un des défis adressés à la communauté des programmeurs est de trouver une façon efficace de gérer le parallélisme. Paradoxalement, tandis que les exemples précédents montraient des problèmes causés par une flèche de Kleisli pas assez puissante, cette fois-ci le problème est à l’opposé. Les fonctions nues (ou pures) offrent un grand nombre d’opportunité pour le parallélisme. Lorsqu’elles sont exécutées en parallèle, cela peut-être plus rapide, cela peut-être aussi plus lent si le parallélisme est mal conçu, mais elles donneront de toute façon le même résultat. Mais si la flèche de Kleisli incorpore les modifications destructrices, ce n’est plus le cas : le parallélisme est risqué et peu donner des résultats incorrects en raison de ce qu’on appelle les accès concurrents (« race conditions »).

Cependant, il est impossible de retirer les modifications destructrices de la flèche de Kleisli d’un langage. Un programme qui n’a pas d’effets observables n’est pas utile, tout simplement. Ce qu’il faut pouvoir faire est de séparer les parties du code qui effectuent des modifications destructrices de celles qui opèrent avec des fonctions pures. Donc, ce dont nous avons besoin, c’est d’un langage qui possède plusieurs sortes de flèches de Kleisli !

Il existe déjà au moins un langage qui offre cette possibilité. Les utilisateurs d’Haskell peuvent créer leurs propres monades et travailler dans la catégorie de Kleisli de leu choix. La langage dispose d’une syntaxe qui rend cette approche lisible et aisée. Si une fonction peut échouer, on la met dans Err ; si elle a besoin d’accéder aux paramètres de l’application, dans Param ; de procéder à des entrées/sorties, dans IO. Les frameworks pour des applications web et d’autres projets similaires commencent par définir la monade appropriée pour ce qu’ils ont à faire.

Une autre tendance de la communauté des développeurs, en ce moment, est de créer davantage de modèles de programmation spécifiques à un domaine. Le langage Erlang est devenu populaire parce qu’il fournit un modèle de programmation avantageux pour le parallélisme. Le framework .NET propose LINQ, qui offre un modèle de programmation efficace pour traiter et requêter des collections de données. Rails a popularisé les langages spécifiques au domaine de la programmation web. D’autres langages proposent des continuations pour construire des opérations d’une manière plus flexible. Tous ces exemples montrent le besoin de travailler avec les flèches de Kleisli appropriées à la tâche entreprise.

Au fond, si nous croyons qu’il existe une seule notion de « fonction » appropriée pour l’ensemble des programmes informatiques, et qu’un langage existant la définit, nous pouvons rejeter, en tant que programmeurs, les idées générales de monade et de flèche de Kleisli comme une lubie de théoriciens. Mais nous n’en prenons pas le chemin. La communauté des programmeurs s’est engagée résolument dans une direction où plusieurs définitions de la fonction coexistent, selon le contexte, la tâche à accomplir, ou même pour une application donnée. C’est pourquoi il est important de disposer du langage, des outils, et des intuitions nécessaires à la comparaison de ces abstractions. Tout cela, les monades nous les donnent.

Les abstractions construites sur les monades
Un langage qui permet de choisir ses monades offre encore d’autres avantages, en particulier un nouveau niveau d’abstraction. En Haskell, par exemple, il est possible d’écrire du code applicable à différentes monades. De façon surprenante, une part importante du code écrit pour une certaine monade fait sens pour d’autres monades également. Prenons par exemple le type Haskell suivant :

sequence : : Monad m => [m a] -> m [a]

Cela signifie, pour une monade M quelconque, que sequence convertit une liste de valeurs M(A) en M(List A), c’est-à-dire applique la monade à la liste elle-même. Prenons une minute pour en voir la signification pour nos quatre exemples. Pour Err, sequence prend une liste de résultats qui pourraient être un échec, et si l’un d’entre eux est un échec, toute la séquence échoue. C’est simplement une façon pratique de vérifier l’échec d’une liste complète d’opérations. Pour Param, sequence prend un ensemble unique de préférences, le distribue à tous les éléments d’une liste et retourne une liste de résultats. Pour la monade P (ensemble des sous-ensembles), sequence prend une liste d’ensembles et retourne l’ensemble de toutes les façons de choisir un élément par ensemble. Enfin pour IO, il prend une liste de listes d’instruction, et retourne une liste unique de toutes les instructions à réaliser dans l’ordre.
Une unique fonction, avec une seule implémentation, fait sens –et quelque chose d’utile- pour nos quatre exemples de monades !

Avec le choix des monades vient la capacité de s’abstraire de ce choix et d’écrire du code significatif pour n’importe laquelle des monades que l’on choisira.

Voyant toutes ces forces à l’œuvre, je prédis que, d’ici dix ans, on attendra des développeurs logiciels qu’ils discutent des monades de la même façon qu’on attend d’eux aujourd’hui qu’ils discutent des design patterns ou des méthodologies agiles.

Au-delà des monades : plus de programmation par les catégories
Même si la plupart de ce qui a été dit concerne les monades, je ne voudrais pas laisser l’impression qu’elles sont la seule preuve de l’influence de la théorie des catégories sur la programmation. Toutes les idées ci-après on fait leur chemin dans la pratique de la programmation, le plus souvent (jusqu’ici) dans la communauté Haskell à cause de la flexibilité du langage et de ses profondes racines académiques.

Les transformateurs de monade constituent une technique puissante pour combiner les effets de plusieurs monades et construire des modèles de programmation variés et performants.
Les foncteurs et les foncteurs applicatifs sont moins puissants que les monades, mais d’une utilisation encore plus large.
D’autres genres de catégories, qui ne sont pas des catégories de Kleisli peuvent souvent être définies pour résoudre des problèmes spécifiques, dont les catégories de Freyd.

Je m’arrête ici, mais uniquement pour vous encourager à rechercher vous-mêmes les abstractions variées de la théorie des catégories que les programmeurs ont trouvées utiles. Un bon point de départ est la Typeclassopedia (spécifique à Haskell) de Brent Yorgey. Et ce n’est qu’une porte donnant sur les possibilités nombreuses d’application de la théorie des catégories.

J’espère avoir été capable de convaincre que ces idées n’ont pas été simplement inventées mais sont l’extension naturelle de ce qu’ont fait les programmeurs pendant des décennies.