Pourquoi les effets algébriques sont nécessaires

• Les effets algébriques (effect handlers) sont des outils de contrôle de flux flexibles qui permettent d’implémenter au niveau bibliothèque diverses fonctionnalités de langage (gestion des exceptions, générateurs, coroutines, etc.)
• Ils peuvent aussi s’appliquer à des usages fréquents en programmation fonctionnelle, comme la gestion de contexte, l’injection de dépendances ou le remplacement de l’état global
• Ils contribuent à la simplicité de la conception d’API et à l’automatisation de la transmission d’état ou d’environnement dans le code
• Ils offrent aussi des avantages tels que la garantie de pureté fonctionnelle, la rejouabilité et l’audit de sécurité
• Les progrès récents des technologies de compilation ont également beaucoup amélioré les problèmes de performance

---

Vue d’ensemble des effets algébriques (Algebraic Effects)

Les effets algébriques (aussi appelés effect handlers) sont une fonctionnalité de langage de programmation qui attire beaucoup d’attention ces derniers temps. Ils s’imposent rapidement comme l’une des fonctionnalités clés d’Ante et de plusieurs langages de recherche (Koka, Effekt, Eff, Flix, etc.). De nombreuses ressources expliquent le concept des effect handlers, mais les explications approfondies sur le "pourquoi" de leur utilité réelle restent rares. Cet article présente aussi largement que possible les usages concrets et les avantages des effets algébriques.

Comprendre rapidement la syntaxe et la sémantique

• Les effets algébriques ressemblent à des "exceptions reprenables"
• Il est possible de déclarer une fonction d’effet comme effect SayMessage
• Comme dans foo () can SayMessage = ..., on peut indiquer qu’une fonction est susceptible d’utiliser cet effet
• Avec handle foo () | say_message () -> ..., on peut le gérer un peu comme avec un try/catch d’exception

Cette structure de base permet d’invoquer et de contrôler les effets.

Étendre le contrôle de flux défini par l’utilisateur

La raison principale d’utiliser les effets algébriques est qu’avec une seule fonctionnalité de langage, on peut implémenter sous forme de bibliothèque des mécanismes qui nécessitaient auparavant chacun une fonctionnalité dédiée du langage (générateurs, exceptions, coroutines, asynchrone, etc.).

• En plaçant une variable d’effet polymorphe (can e) sur une fonction, on peut transmettre et combiner différents effets comme arguments de fonction
• Par exemple, une fonction map peut être déclarée de façon à permettre à la fonction passée en argument d’utiliser un effet arbitraire e, ce qui permet de la combiner naturellement avec divers effets (sortie, asynchrone, etc.)

Exemples d’implémentation des exceptions et des générateurs

• Implémentation des exceptions : si l’on traite un effet déclenché sans appeler resume, il se comporte comme une exception
• Implémentation des générateurs : on définit un effet Yield ; à chaque fois qu’une valeur est yieldée, un handler externe intervient pour contrôler le flux selon certaines conditions, et même des motifs avancés comme le filtrage peuvent être écrits avec un code relativement simple

Le fait de pouvoir combiner plusieurs effets constitue aussi un avantage majeur par rapport aux techniques traditionnelles d’abstraction des effets.

Utilisation comme couche d’abstraction

Les effets algébriques ne servent pas seulement à étendre les fonctionnalités de programmation de base : ils sont aussi très utiles dans divers scénarios d’applications métier.

Injection de dépendances (Dependency Injection)

• Des dépendances telles que la base de données ou la sortie peuvent être abstraites sous forme d’effets et gérées par des handlers
• Il devient également possible d’implémenter avec souplesse le remplacement par des objets mock pour les tests ou la redirection de sortie

Journalisation conditionnelle ou gestion de la sortie

• On peut contrôler centralement l’affichage ou non des messages de log en fonction du niveau de journalisation

Simplification de la conception d’API et automatisation de la transmission du contexte

Utilisation des effets d’état (State)

• Lorsqu’il faut transmettre un objet de contexte ou des informations d’environnement, si l’on implémente cela sur la base d’effets en n’utilisant que get/set, il devient possible d’automatiser la gestion de l’état sans transmission explicite
• Auparavant, il fallait passer le contexte en argument à toutes les fonctions, mais un effet d’état permet de masquer cette partie

Remplacement des objets globaux

• Des états auparavant gérés par des objets globaux, comme les générateurs de nombres aléatoires ou l’allocation mémoire, peuvent aussi être abstraits sous forme d’effets, ce qui est avantageux en termes de clarté du code, de facilité de test et de support de la concurrence
• Il suffit de remplacer le handler pour changer de manière flexible la véritable source d’aléa

Prise en charge de l’écriture en style direct (Direct Style)

• Auparavant, il fallait gérer plusieurs objets imbriqués à l’aide de types optionnels, d’encapsulation des erreurs, etc.
• Les effets permettent d’exprimer proprement les chemins d’erreur ou d’effets de bord sans ce type d’encapsulation

Garantie de pureté et audit de sécurité

Explicitation des effets de bord

• Dans la plupart des langages avec effect handlers, une fonction qui produit des effets de bord doit obligatoirement les déclarer dans sa signature de type, par exemple can IO, can Print, etc.
• Des mécanismes comme la création de threads ou la mémoire transactionnelle logicielle (STM) exigent nécessairement des fonctions pures

Rejeu des logs et réseau déterministe

• En s’appuyant sur la pureté, on peut créer des handlers comme record et replay afin de reproduire les résultats d’exécution
• Cela permet de prendre en charge des résultats déterministes et les rollbacks pour le débogage, les bases de données, les réseaux de jeux, etc.

Prise en charge de la sécurité basée sur les capacités (Capability-based Security)

• Toutes les effets non traités étant exposés dans la signature de type d’une fonction, cela est efficace pour l’audit de sécurité de bibliothèques externes
• Si une fonction auparavant sans effets de bord est mise à jour et se retrouve avec can IO, le code qui l’appelle peut le détecter immédiatement

Cependant, comme tous les effets se propagent automatiquement, il peut aussi arriver que des effets soient traités de façon involontaire.

Efficacité et conclusion

• Autrefois, l’efficacité d’exécution était un point faible, mais récemment les optimisations ont énormément progressé dans de nombreux cas, notamment pour les effets tail-resumptive
• Selon les langages, différentes stratégies de compilation efficaces sont appliquées (closure call, evidence passing, spécialisation des handlers, etc.)

On peut s’attendre à ce que les effets algébriques occupent une place bien plus centrale dans les langages de programmation du futur.

[GN⁺]

Commentaires sur Hacker News

• Je vois deux inconvénients
  Le premier, c’est qu’en regardant l’extrait de code donné, rien n’indique que foo ou bar puissent échouer
  Pour savoir que ce type d’appel peut déclencher un gestionnaire d’erreur, il faut aller chercher la signature de type soi-même, et selon le contexte cela peut demander un travail manuel sans l’aide de l’IDE
  Le second, c’est qu’une fois qu’on a compris que foo et bar peuvent échouer, pour trouver quel code s’exécute en cas d’échec il faut remonter loin dans la pile d’appels pour dénicher une expression with, puis redescendre en suivant le gestionnaire concerné
  Il est impossible de suivre statiquement ce comportement ou de sauter directement à la définition dans l’IDE, puisque my_function peut être appelée à plusieurs endroits avec différents gestionnaires
  Je trouve le concept très original, mais au final j’ai des inquiétudes sur la lisibilité du code et le débogage

  • À propos du problème consistant à retrouver quel code s’exécute quand l’exécution échoue, c’est précisément le cœur de l’injection de code dynamique
    Comme avec le shallow-binding, le deep-binding et d’autres fonctionnalités dynamiques, les liaisons se font en remontant la pile d’appels
    Si l’analyse statique ou le saut IDE sont impossibles, c’est justement à cause de cette nature dynamique
    Mais je pense qu’en pratique ce n’est pas si important
    Parce qu’on ajoute seulement des effets à du code pur, ce qui permet ensuite de les brancher dans divers contextes, que ce soit avec des mocks de test, en production, ou avec des effets purs ou impurs selon le besoin
    Le principe est proche de l’injection de dépendances
    On peut implémenter quelque chose de similaire avec des monades traditionnelles, mais là aussi, pour savoir où une monade est réellement instanciée, il faut finir par examiner la pile d’appels
    Ces techniques ont des avantages, mais elles ont aussi clairement un coût
    Elles sont utiles pour les tests et le sandboxing, mais rendent moins évident ce qui se passe réellement dans le code

  • Quelqu’un partage avoir écrit un mémoire de licence sur le support IDE des effets lexicaux et de leurs gestionnaires
    Selon lui, tous les points soulevés plus haut sont tout à fait réalisables
    Lien vers le mémoire

  • Sur l’écosystème .NET, on parle de la tendance à surutiliser les interfaces, au point de devoir passer par plusieurs étapes avant de pouvoir sauter à l’implémentation réelle d’une méthode
    Quand l’implémentation se trouve dans un autre assembly, il arrive souvent que les fonctionnalités de l’IDE deviennent inutiles
    Dans des systèmes avancés de Dependency Injection, notamment Autofac, on construit des scopes hiérarchiques comme avec des variables à portée dynamique en LISP, afin de déterminer à l’exécution à quelle instance un service sera lié
    Dans cette logique, on pourrait injecter les effets sous forme d’instances d’interface comme ISomeEffectHandler, puis représenter l’effet par un appel à la méthode correspondante
    Le comportement concret du gestionnaire, par exemple lever une exception ou journaliser, serait décidé dynamiquement par la configuration DI
    Au lieu d’utiliser le schéma habituel qui consiste à throw une exception, on pourrait expliciter les effets via des interfaces et déléguer entièrement leur traitement à la DI
    La question des itérateurs, comme yield, n’a pas été explorée en profondeur

  • Le point central, selon un autre commentaire, c’est justement l’absence d’indication visible que foo et bar peuvent échouer
    Cela permet d’écrire du code en style direct sans se préoccuper du contexte effectif
    Le fait de devoir chercher quel code s’exécute en cas d’échec relève de la nature même de l’abstraction
    Le gestionnaire d’effet réellement associé sera décidé plus tard, au moment de l’exécution
    C’est le même principe que dans f : g:(A -> B) -> t(A) -> B, où l’on ne peut pas savoir à l’avance quel code sera exécuté quand g sera appelé

  • Quelqu’un dit ne pas être d’accord avec l’idée qu’il serait impossible de faire une analyse statique en remontant la pile d’appels pour trouver le gestionnaire
    En pratique, une analyse statique est possible, et on pourrait utiliser dans l’IDE une fonction du type « aller aux appelants » pour choisir quel gestionnaire est utilisé

• Le « pseudo-code » d’Ante est très impressionnant
  On a l’impression d’un mariage réussi entre les caractéristiques de Haskell et l’expressivité pratique d’Elixir
  Cela donne l’image d’un Haskell conçu pour les développeurs
  J’espère que le compilateur va gagner en maturité
  J’aimerais vraiment essayer de développer une application avec Ante

• À propos de l’idée selon laquelle les AE (Algebraic Effects) généralisent le contrôle de flux au point de permettre aussi l’implémentation de coroutines
  Je pense que, dans un nouveau runtime de langage, la manière la plus simple d’implémenter les AE consiste justement à s’appuyer sur des coroutines, puis à ajouter par-dessus une couche syntaxique autour du mécanisme de base yield/resume
  Je me demande s’il me manque quelque chose

  • Une différence représentative entre les AE et les coroutines, c’est la sûreté de type
    Avec les AE, on peut déclarer explicitement dans le code source quels effets une fonction peut utiliser
    Par exemple, si on a query_db(): User can Database, alors la fonction peut accéder à la base de données et il faut obligatoirement fournir un gestionnaire Database lors de l’appel
    La structure rend très explicites les contraintes sur ce qu’un code peut ou ne peut pas faire
    Un peu comme dans NextJS où un composant serveur ne peut pas utiliser directement des fonctionnalités client, ce type de contrainte de sûreté est populaire dans de nombreux domaines

  • Effect-TS se rapproche de cette approche en JavaScript, avec usage de coroutines, mais on n’est pas sûr au final que ce soit vraiment une bonne idée
    Comme avec la DI du framework Spring, on craint que les AE se propagent dans tout le code et n’ajoutent finalement que de la complexité
    D’ailleurs, les présentations d’EffectDays sur l’usage des effets côté frontend ne semblaient être, pour la plupart, qu’une accumulation de boilerplate sans grand intérêt
    Le concept d’AE est séduisant, mais le fait de devoir encapsuler énormément d’opérations dans des fonctions peut nuire à la facilité d’écriture propre à JavaScript
    À l’inverse, des approches comme motioncanvas, qui reposent uniquement sur les coroutines pour exprimer facilement des scénarios graphiques 2D complexes, ont aussi de grands atouts
    Vidéo EffectDays associée
    MotionCanvas

  • Certains affirment qu’au sein d’un thread, un gestionnaire d’AE peut reprendre (resume) le code plusieurs fois, un peu comme call/cc
    À l’inverse, avec des coroutines, chaque yield ne peut être repris qu’une seule fois
    Comme ce type de flux d’exécution incertain rend les choses plus difficiles à prévoir, certains préfèrent retourner explicitement des fonctions appelables plusieurs fois, ou utiliser d’autres structures comme les itérateurs

• D’un point de vue abstraction de programmation, certains trouvent ce concept extrêmement séduisant
  En faisant de la programmation noyau chez Sun, ils trouvaient très pratique de pouvoir appeler quelque chose comme sleep(foo) puis reprendre avec un code concis lorsque foo réveillait l’exécution
  Cela réduit le poids de tous les cas limites qu’il faudrait sinon traiter un par un via le contrôle de flux
  À condition de faire attention aux questions de localité mémoire, il y aurait quelque chose de très plaisant à initialiser plusieurs fonctions à l’avance dans un état d’attente, puis à exprimer directement un algorithme comme la mutation de chacune de ces unités

• À propos de l’affirmation « les effets algébriques, ce sont des exceptions qu’on peut reprendre »
  Quelqu’un demande en quoi cela diffère concrètement de classes de types comme ApplicativeError ou MonadError
  La manière d’indiquer quels effets une fonction peut utiliser ressemble à des checked exceptions, et le fait de traiter un effet avec une expression handle paraît très proche de try/catch
  Ces classes de types savent déjà gérer la capture d’exceptions avec des fonctions comme handleError et handleErrorWith
  On dit parfois que les effets algébriques apportent des avantages pour les langages « du futur », mais en pratique ce sont des idées qui sont déjà très utilisables aujourd’hui
  Explication cats

  • S’il ne s’agit que d’un seul effet, il n’y a peut-être pas une grande différence
    En revanche, dès qu’il faut combiner plusieurs effets à la fois, la prise en charge directe des effets devient bien plus propre et intuitive qu’un empilement explicite de monades
    Avec des monades combinées, on se heurte vite à des problèmes pénibles d’ordre de composition, ou au fait que le jeu de monades attendu par certaines fonctions ne correspond pas à celui qu’on a déjà

  • Personnellement, je pense que monades et effets ne sont pas vraiment en concurrence, mais offrent plutôt des interprétations complémentaires
    Voir par exemple ce papier : papier sur Koka

  • Les effets algébriques opèrent sur la pile du programme, comme les delimited continuations
    Avec un simple truc de monade, on ne peut pas instantanément remonter jusqu’au gestionnaire d’effet situé cinq frames plus haut dans la pile, modifier seulement les variables locales de cette frame, puis redescendre cinq niveaux ensuite

  • La différence tient au caractère statique ou dynamique du comportement
    Quand on programme avec des monades, il faut implémenter explicitement toutes les méthodes concernées, alors qu’avec un système d’effets on peut installer dynamiquement un gestionnaire d’effet à n’importe quel moment et surcharger souplement un gestionnaire existant
    Par exemple, on peut utiliser plus bas dans la pile une monade spécialisée ayant des propriétés d’IO pour les tests, puis n’installer un gestionnaire d’effet qu’encore plus bas dans cette même structure

  • Les ressemblances sont fortes, mais l’ergonomie diffère
    Les effets algébriques ressemblent à des monades free, sauf qu’ils sont intégrés au langage, avec une syntaxe plus simple et une meilleure composabilité
    Dans des langages centrés sur les monades comme Haskell, on peut obtenir un effet similaire en apparence grâce à l’inférence de classes de types (style mtl) et à la syntaxe intégrée de bind

• Quelqu’un explique qu’il croyait à tort que les effets algébriques relevaient uniquement des systèmes de types statiques, mais a découvert récemment qu’il existait aussi des structures dynamiques
  Il cite notamment deux billets anciens sur la version dynamique d’Eff, le premier et le second, qui l’ont particulièrement marqué
  Des notions comme les « opérations paramétrées à arité généralisée » lui semblent aussi très intéressantes lorsqu’on relie abstraction et programmation

  • Quelqu’un demande ce qui déplaît exactement dans les systèmes de types statiques

• Certains soulignent qu’il s’agit d’un vieux concept réapparu récemment sous un nouveau nom et un nouveau cadrage
  Présentation du LISP Condition System
  Retour d’expérience sur les Algebraic Effects

• Retour d’expérience d’une personne qui a fait du protohackers avec les effects dans l’alpha d’OCaml 5
  C’était amusant, mais la toolchain était un peu pénible à l’époque
  Ante donne une impression similaire, donc on attend avec intérêt son évolution

  • Depuis OCaml 5.3, les effects sont dans un bien meilleur état qu’avant
    Il n’y a toujours pas de système de types attaché, mais l’ensemble est maintenant nettement plus propre

• Quelqu’un explique avoir passé beaucoup de temps avec Prolog et chercher un langage qui permette de composer facilement des fonctions non déterministes avec vérification de types à la compilation
  Ante fait partie des candidats qui l’intéressent
  Il ajoute qu’il ne faut pas oublier les outils pour développeurs et les plugins d’éditeur comme LSP ou tree-sitter

  • L’auteur d’Ante répond qu’il y a déjà un support LSP, certes très basique
    Selon lui, un nouveau langage doit absolument penser au tooling dès le début
    Il accorde aussi beaucoup d’importance à l’expérience de débogage, et envisage donc de fournir par défaut, au moins en mode debug, des fonctions de replayabilité

• À propos de l’affirmation « les effets algébriques, ce sont des exceptions qu’on peut reprendre »
  Quelqu’un demande si cela ressemble aux conditions de Common Lisp
  Il trouve intéressant de voir de vieux concepts revenir sous d’autres noms

  • Les effets algébriques sont bien plus généraux que le système de conditions de LISP
    Le fait que les continuations puissent être multi-shot les rapproche de call/cc en Scheme
    Il est aussi mentionné que ce type de parallélisme peut parfois produire de pires résultats que son absence

  • Smalltalk possède aussi des « resumable exceptions »

  • Pour quelqu’un d’autre, réduire simplement les effets à un changement de nom de l’ancien condition system n’aide pas vraiment à faire avancer la discussion
    Les effets algébriques actuellement discutés ont des différences réelles qui vont au-delà du simple concept historique

  • La Dependency Injection est également mentionnée dans un registre proche