Pourquoi nous avons besoin des effets algébriques

• Les effets algébriques sont une fonctionnalité de langage qui capture et traite le flux de contrôle comme des exceptions reprenables. Ils constituent une fonctionnalité centrale d’Ante et sont aussi au cœur de langages de recherche comme Koka, Effekt, Eff et Flix.
• Avec le même mécanisme, on peut construire au niveau bibliothèque des générateurs, exceptions, async, coroutines et différentiation automatique ; grâce au polymorphisme d’effets, des fonctions comme map peuvent être écrites une seule fois, indépendamment du type d’effet.
• Si l’on transforme en effets l’injection de dépendances et la transmission de contexte — accès à une base de données, sortie, journalisation, passage d’état —, on peut gérer les mocks de test, la collecte de sorties et le filtrage des logs en remplaçant les handlers.
• Quand des effets comme can IO, can Print ou can Fail apparaissent dans la signature d’une fonction, cela aide à garantir la pureté, l’enregistrement/relecture et l’audit de sécurité ; toutefois, un effet déjà autorisé peut se propager involontairement vers un handler existant.
• La faiblesse traditionnelle était la crainte de coûts d’exécution, mais les langages récents réduisent ces coûts via l’optimisation des effets tail-resumptive, l’evidence passing, la limitation à un seul resume et la spécialisation des handlers.

---

Modèle de base des effets algébriques

• Les effets algébriques sont aussi appelés effect handlers ; on peut les comprendre comme un modèle d’« exceptions reprenables ».
• Dans le pseudo-code d’Ante, on déclare une fonction d’effet et l’on indique dans la signature d’une fonction qu’elle peut utiliser cet effet avec can.
  • Appeler une fonction d’effet comme say_message: Unit -> Unit revient à « lancer » un effet.
  • La fonction appelante expose dans sa signature la possibilité d’utiliser cet effet, par exemple foo () can SayMessage.
• Une expression handle capture un effet de façon similaire à try/catch, puis poursuit le calcul interrompu via un appel à resume.
  • Si le handler say_message exécute print "Hello World!" puis appelle resume (), le calcul d’origine continue et renvoie 42.
• Le terme « algebraic » est en grande partie un terme résiduel ; en pratique, effect handlers serait plus exact, mais on utilise « effets algébriques » car c’est le nom familier pour les utilisateurs.

Flux de contrôle définis par l’utilisateur

• Les effets algébriques permettent d’implémenter plusieurs fonctionnalités de langage avec un seul mécanisme.
  • Générateurs
  • Exceptions
  • async
  • Coroutines
  • Différentiation automatique
• Le polymorphisme d’effets réduit le problème what color is your function.
  • map (input: Vec a) (f: a -> b can e): Vec b can e exprime que, quel que soit l’effet e effectué par la fonction d’entrée f, map effectue le même effet.
  • Le même map peut être utilisé avec une sortie sur stdout, un appel de fonction asynchrone, un yield de flux, etc.
  • Dans beaucoup de langages à effect handlers, on peut omettre la variable d’effet e et écrire sous la forme familière map (input: Vec a) (f: a -> b): Vec b.
• Les exceptions peuvent être implémentées en n’appelant pas resume lors du traitement de l’effet.
  • On définit throw: a -> never_returns pour l’effet Throw a.
  • En cas de division par zéro, on appelle throw "error: Division by zero!", et le handler affiche le message sans reprendre le calcul.
• Les générateurs peuvent être implémentés avec yield: a -> Unit de l’effet Yield a.
  • On parcourt les éléments du vecteur et on appelle yield elem.
  • Le handler filter, si la valeur yielded satisfait la condition, appelle à nouveau yield x puis poursuit avec l’élément suivant via resume ().
  • Le handler my_for_each exécute la fonction f pour chaque valeur yielded et continue avec resume ().
• Un ordonnanceur coopératif peut aussi être construit avec un effet yield: Unit -> Unit, le handler prenant le contrôle pour basculer vers l’exécution d’une autre fonction.
  • L’exemple de scheduler d’Effekt montre ce patron.
• Plusieurs effets se composent bien entre eux, ce qui est présenté comme un avantage qui améliore l’utilisabilité par rapport à d’autres abstractions d’effets.

Injection de dépendances et testabilité

• Les effets peuvent aussi servir à l’injection de dépendances dans des applications métier classiques.
• Au lieu de passer directement un objet base de données comme argument de fonction, on peut définir un effet Database.
  • La forme classique reçoit l’objet DB en argument, comme business_logic (db: Database) (x: I32).
  • La forme fondée sur les effets devient business_logic (x: I32) can Database, et appelle query "..." en interne.
• Le choix de la base de données concrète revient au handler situé plus haut dans la pile d’appels.
  • On peut remplacer la DB de production par une autre DB ou par une DB mock pour les tests.
  • Le handler mock_database peut ignorer le message query et reprendre avec resume en renvoyant toujours DbResponse.Ok.
• Si l’on traite aussi la sortie comme un effet, on peut collecter des chaînes pendant les tests sans écrire directement sur stdout.
  • Le handler print_to_string capture les appels print msg et les accumule avec des retours à la ligne dans la chaîne all_messages.
  • output_messages peut vérifier la valeur de retour 1234 et la chaîne de messages sans sortie réelle.
• La journalisation peut devenir une sortie conditionnelle avec un effet Log et LogLevel.
  • log_handler appelle print msg si le niveau du message est supérieur ou égal au seuil configuré.
  • foo () with log_handler Error n’affiche que les logs d’erreur.

API plus propres et passage de contexte

• Les effets algébriques peuvent représenter sous forme d’effets le patron d’objet Context transmis à travers un programme ou une bibliothèque.
• L’effet Use a peut être vu comme un effet d’état et fournit get: Unit -> a et set: a -> Unit.
  • Le handler state conserve l’état initial, renvoie le contexte courant pour get et le met à jour avec un nouveau contexte pour set.
  • L’exemple de définition de state ignore les règles de possession ; une implémentation réelle pourrait nécessiter une contrainte Copy a.
• L’exemple qui stocke des chaînes dans un vecteur et passe des indices comme clés illustre le coût du passage de contexte.
  • Sans effets, push_string, get_string, append_with_separator, example, etc., doivent continuer à recevoir strings comme argument.
  • Dans l’implémentation fondée sur les effets, les opérations primitives push_string et get_string appellent get/set, et le code de plus haut niveau n’a pas besoin de passer directement strings.
• Cette approche convient bien quand une bibliothèque encapsule le passage de contexte interne.
  • L’utilisateur de la bibliothèque n’a pas à se soucier des détails internes du passage de contexte.
  • Pour éviter d’être lié à un type de contexte particulier, les fonctions nécessaires peuvent être abstraites via une interface.

Remplacer les variables globales et style direct

• Les API qui semblent sans état en surface mais nécessitent en réalité un état, comme la génération de nombres aléatoires ou l’allocation mémoire, peuvent être représentées par des effets au lieu de variables globales.
• L’exemple de génération de nombres aléatoires montre la charge que représente le passage direct d’un objet Prng dans tout le programme.
  • Un Prng global est pratique, mais il hérite des inconvénients des valeurs globales, comme la nécessité d’assurer la sûreté vis-à-vis des threads.
  • Avec random: Unit -> U8 de l’effet Random, l’utilisateur n’a qu’à indiquer une initialisation via un handler quelque part plus haut dans la pile d’appels.
  • Pour passer ensuite à /dev/urandom ou à une autre source d’aléa, il suffit de remplacer le handler ; le reste du code dans la pile d’appels n’a pas besoin de changer.
• L’allocation mémoire peut aussi être représentée par un effet Allocate.
  • allocate: (size: Usz) -> Alignment -> Ptr a
  • free: Ptr a -> Unit
  • La plupart des appels utilisent un allocator global, et dans une tight loop, on peut ajouter un handler au corps de la boucle pour passer à un arena allocator.
• Les effets permettent un style direct, plutôt que de passer des résultats enveloppés dans des valeurs dédiées.
  • Avec Maybe t, il faut enchaîner le chemin de succès avec and_then et map.
  • Le sucre syntaxique comme ? en Rust sert à se concentrer sur le chemin heureux.
  • Avec les effets, get_line_from_stdin (): String can Fail, IO et parse (s: String): U32 can Fail s’écrivent comme du code séquentiel ordinaire : line = ..., x = ..., x * 2.
• La gestion des échecs peut être traitée en appliquant un handler qui s’écarte du chemin heureux.
  • get_line_from_stdin () with default "42" traite l’effet Fail avec une valeur par défaut.
• Différents types d’erreurs se composent naturellement sous forme de listes d’effets.
  • LibraryA.foo (): U32 can Throw LibraryA.Error
  • LibraryB.bar (): U32 can Throw LibraryB.Error
  • my_function peut déclarer ensemble Throw LibraryA.Error, Throw LibraryB.Error et Throw MyError.
  • Si la répétition devient longue, on peut créer un alias de type comme AllErrors = can Throw ....
  • Un même effet Throw String est fusionné en un seul ; si l’on veut les séparer, il faut un type wrapper comme MyError.

Pureté, rejouabilité et audit de sécurité

• Dans la plupart des langages à effect handlers, à l’exception à peu près d’OCaml, les effets sont utilisés là où des effets de bord peuvent survenir.
  • Dans Ante, on ne peut pas utiliser d’effets de bord sans les indiquer, par exemple avec can Print ou can IO.
  • Les définitions extern ne peuvent pas être vérifiées par le compilateur, il faut donc faire confiance à la définition de type.
  • Pouvoir effectuer un effet IO uniquement en mode debug afin de préserver la sûreté des effets en mode release est une fonctionnalité prévue.
• Certaines fonctions exigent en entrée des fonctions pures.
  • Lorsqu’on crée un thread, le thread créé ne doit pas pouvoir appeler des handlers appartenant au thread courant.
  • spawn_all (functions: Vec (Unit -> a pure)): Vec a can IO est une forme qui n’accepte que des fonctions pures, exécute toutes les fonctions dans des threads et attend leur fin.
• La Software Transactional Memory (STM) est une technique de concurrence qui nécessite des fonctions pures.
  • Elle exécute plusieurs fonctions simultanément et, si une valeur est modifiée par un autre thread pendant la transaction, redémarre cette transaction.
  • Une implémentation de preuve de concept dans Effekt se trouve dans effekt-stm.
• La pureté peut permettre l’enregistrement/relecture, de façon similaire à l’utilitaire de débogage rr.
  • Deux handlers, record et replay, traitent les effets de plus haut niveau émis par main, généralement IO.
  • record enregistre les occurrences d’effets et leurs résultats, puis les remonte vers le handler IO intégré pour le traitement réel.
  • replay n’effectue pas de véritable IO et utilise les résultats du journal d’effets.
  • En enregistrant par défaut dans les builds debug, on peut obtenir un débogage déterministe.
• La liste des effets dans les signatures de fonction aide à l’audit de sécurité, de façon similaire à la Capability Based Security.
  • get_pi: Unit -> F64 permet de savoir que la fonction ne fait pas secrètement d’IO en arrière-plan.
  • Si, après une mise à jour de bibliothèque, elle devient get_pi: Unit -> F64 can IO, le code recevra une erreur, sauf si la fonction appelante exige déjà IO.
  • Il est préférable de ne déclarer que les effets minimaux, par exemple seulement Print plutôt que tout IO.
  • L’ajout d’un nouvel effet est traité comme une modification qui casse le semantic versioning.
  • Les ressources connexes incluent Capability Based Security et Designing with Static Capabilities and Effects.

Limites et stratégies d’implémentation

• L’une des limites de l’approche par effets est la possibilité d’un traitement involontaire.
  • Même si une fonction se met à exiger IO, il peut ne pas y avoir d’erreur si la fonction appelante autorise déjà IO.
  • Il en va de même pour l’effet Fail : si une fonction de bibliothèque qui n’échouait pas auparavant peut ensuite produire Fail, cela peut se propager vers le handler Fail existant.
  • Ce comportement peut être acceptable selon le contexte, mais il peut diverger de l’intention si l’on voulait un traitement distinct, comme fournir une valeur par défaut.
• Le principal inconvénient traditionnel était la crainte de coûts d’exécution, mais la sortie compilée des effets récents s’est nettement améliorée.
• Beaucoup de langages à effets algébriques optimisent les effets tail-resumptive en simples appels de closures.
  • Un effet tail-resumptive est un effet dont le handler appelle resume en dernier.
  • La majorité des effets réels entrent dans cette catégorie, tout comme la plupart des exemples de ce texte.
  • Les exceptions sont classées comme un cas à part, car elles n’appellent jamais resume.
• Les stratégies d’optimisation varient aussi selon les langages.
  • Koka utilise l’evidence passing, remonte les effets jusqu’aux handlers et compile en C sans runtime.
  • Ante et OCaml limitent resume à un seul appel au maximum.
    • Cette restriction exclut certains effets comme le non-déterminisme.
    • En contrepartie, elle simplifie la gestion des ressources et permet d’implémenter plus efficacement les continuations internes avec des techniques comme les segmented stacks.
  • Effekt spécialise complètement les handlers dans le programme jusqu’à les éliminer.
    • Cette approche impose la limite que la plupart des fonctions deviennent second-class.
    • On peut obtenir des fonctions first-class sous forme boxed et passer à un modèle pay-as-you-go.
    • Les ressources connexes incluent la documentation d’Effekt sur les captures et l’article.