💻 computer science

Guard Analysis and Safe Erasure Gradual Typing: a Type System for Elixir

Cet article introduit un nouveau système de typage progressif pour Elixir qui combine le sous-typage sémantique avec l'analyse de garde à l'exécution afin de permettre un typage statique sûr et un raffinement précis des types sans modifier le pipeline de compilation ou les performances d'exécution du langage.

Auteurs originaux : Giuseppe Castagna, Guillaume Duboc

Publié 2026-06-03

📖 7 min de lecture🧠 Analyse approfondie

CC BY 4.0

Auteurs originaux : Giuseppe Castagna, Guillaume Duboc

Article original sous licence CC BY 4.0 (http://creativecommons.org/licenses/by/4.0/). ✨ Ceci est une explication générée par l'IA de l'article ci-dessous. Elle n'a pas été rédigée ni approuvée par les auteurs. Pour une précision technique, consultez l'article original. Lire la clause de non-responsabilité complète

Imaginez que vous dirigez un restaurant très fréquenté (le langage de programmation Elixir). La cuisine est chaotique, rapide, et repose sur des chefs (la machine virtuelle Erlang) qui savent instinctivement si un ingrédient est sûr à utiliser. Si un chef essaie de hacher une pierre au lieu d'un oignon, la machine arrête le processus et crie : « Hé, ce n'est pas de la nourriture ! » C'est ainsi qu'Elixir fonctionne aujourd'hui : il est dynamique, ce qui signifie qu'il ne vérifie pas tout avant de cuisiner ; il vérifie simplement pendant que vous cuisinez.

Les auteurs de ce document, Giuseppe Castagna et Guillaume Duboc, ont construit un nouvel « Inspecteur de Sécurité » pour cette cuisine. Leur objectif était de permettre aux inspecteurs d'examiner les recettes avant que la cuisson ne commence pour détecter les erreurs, sans ralentir la cuisine ni changer la façon dont les chefs cuisinent.

Voici comment leur système fonctionne, expliqué par des analogies simples :

1. La stratégie de l'« Effacement Sécurisé » : Lire le menu, pas changer la cuisine

Habituellement, lorsque vous ajoutez un inspecteur de sécurité dans une cuisine, vous pouvez forcer les chefs à porter un équipement de protection supplémentaire ou à s'arrêter pour obtenir un deuxième avis avant chaque découpe. Cela ralentit tout.

Le système des auteurs est différent. Ils l'appellent l'« Effacement Sécurisé » (Safe Erasure).

La métaphore : Imaginez que l'inspecteur écrit un rapport de sécurité détaillé sur la fiche de la recette. Mais, une fois que la cuisson commence, l'inspecteur efface le rapport. Les chefs ne portent pas d'équipement supplémentaire ; ils cuisinent exactement comme ils le faisaient toujours.
Pourquoi cela fonctionne : Les auteurs ont réalisé que la machine de la cuisine (la VM) possède déjà des contrôles de sécurité intégrés. Si un chef essaie d'ajouter une pierre à une soupe, la machine l'arrêtera de toute façon. L'inspecteur n'a donc pas besoin d'ajouter de nouveaux contrôles ; il doit simplement savoir quels contrôles la machine possède déjà. Cela permet à l'inspecteur d'être très précis sans ralentir la cuisine.

2. Les « Fonctions Fortes » : Le Chef Défensif

Parfois, une recette dit : « Prenez n'importe quel légume et hachez-le. » Si vous donnez cette recette à une pierre, la machine va planter.
Mais, une « Fonction Forte » est comme un chef défensif.

La métaphore : Ce chef dit : « Je hacherai n'importe quel légume, mais si vous me donnez une pierre, je la jetterai immédiatement (échec) au lieu d'essayer de la hacher. »
Le résultat : Parce que ce chef possède un filet de sécurité intégré (une « garde » ou un contrôle), l'inspecteur peut affirmer avec confiance : « Si ce chef renvoie un résultat, ce sera définitivement des légumes hachés. » Même si le chef reçoit un ingrédient mystère (un type « dynamique »), l'inspecteur sait que le résultat sera sûr parce que le chef est très prudent.

3. L'Analyse des Gardes : Le filtre « Peut-être / Définitivement »

En Elixir, les chefs utilisent souvent des « gardes » pour décider quoi faire. Par exemple : « Si l'ingrédient est un oignon, le tranchez ; si c'est une pomme de terre, écrasez-la. »

Le problème : Parfois, les règles sont complexes. « Si l'ingrédient est un légume rouge OU s'il a la même taille que la poêle... » Il est difficile de savoir exactement quels ingrédients correspondent.
La solution : Les auteurs ont construit un système qui analyse ces règles et crée deux listes pour chaque règle :
1. La liste des « Définitivement Acceptés » : Les ingrédients qui passeront définitivement cette règle (ex: « Oignons rouges »).
2. La liste des « Peut-être Acceptés » : Les ingrédients qui pourraient passer, mais dont nous ne sommes pas sûrs à 100 % (ex: « Choses rouges qui pourraient être des oignons »).
Pourquoi c'est important : Cela permet à l'inspecteur d'être extrêmement précis. Si une recette comporte plusieurs étapes, l'inspecteur peut soustraire les éléments « Définitivement Acceptés » de la première étape pour voir exactement ce qui reste pour la seconde étape. Cela empêche l'inspecteur de deviner et de manquer des erreurs.

4. Le Type « Dynamique » : La Boîte Mystère

En programmation, il arrive que l'on ne sache pas ce qu'est un ingrédient avant d'ouvrir la boîte. C'est ce qu'on appelle un type « dynamique ».

Le défi : Si vous avez une boîte mystère, un inspecteur standard dira : « Je ne sais pas ce que c'est, donc je ne peux pas vous dire si la recette est sûre. »
L'innovation : Ce système utilise la « Propagation Dynamique ». Il dit : « D'accord, c'est une boîte mystère, mais si le chef est une 'Fonction Forte' (le chef défensif), nous savons que le résultat sera sûr même si la boîte est un mystère. »
L'analogie : C'est comme dire : « Je ne sais pas si cette boîte contient un marteau ou un tournevis, mais je sais que l'outil que j'utilise fonctionnera en toute sécurité avec l'un ou l'autre. » Cela permet de garder le système flexible (graduel) tout en restant sûr.

5. Les Fonctions Multi-Arité : La règle du « Nombre de Mains »

En Elixir, une fonction peut prendre un ingrédient, deux ingrédients ou trois.

Le problème : Les anciens inspecteurs traitaient une « recette à deux ingrédients » exactement de la même manière qu'une « recette à un ingrédient », en prétendant que les deux ingrédients étaient un seul gros paquet. Cela confondait les contrôles de sécurité.
La correction : Les auteurs ont créé une nouvelle façon de compter les « mains » (arguments). Ils peuvent désormais dire spécifiquement : « Cette recette nécessite exactement deux mains. » Cela leur permet de détecter les erreurs où un chef essaie d'utiliser une recette à deux mains avec un seul ingrédient, une chose que les systèmes précédents avaient manquée.

Le Test en Conditions Réelles

Les auteurs n'ont pas seulement construit cela en théorie ; ils l'ont intégré dans le langage Elixir réel (en commençant par la version 1.17).

Le résultat : Ils ont testé cela sur de vastes bases de code réelles (comme le framework web Phoenix et le gestionnaire de paquets Hex).
Les conclusions :
- Cela a trouvé des bugs qui se cachaient depuis des années (comme une recette qui essayait d'utiliser un champ qui n'existait pas).
- Cela a trouvé du « code mort » (des recettes qui avaient été écrites mais qui n'étaient jamais utilisées).
- Crucialement : Tout cela a été fait sans ralentir la cuisine. Le « temps d'inspection » était une fraction infime du temps de cuisson total (souvent moins de 5 %).

Résumé

Le document présente une nouvelle façon d'ajouter des contrôles de sécurité stricts à un langage de programmation flexible et rapide. En réalisant que le moteur du langage possède déjà des freins de sécurité, les auteurs ont construit un « inspecteur intelligent » qui lit les recettes, prédit là où les freins fonctionneront, et vous avertit des erreurs — le tout sans jamais toucher au moteur ni ralentir la voiture. C'est un système d'« effacement sécurisé » : les contrôles de sécurité sont effacés du produit final, mais la sécurité est garantie par les propres règles du moteur.

Résumé Technique : Analyse des Gardes et Typage Graduel à Effacement Sûr pour Elixir

1. Énoncé du Problème

Elixir est un langage fonctionnel dynamique tournant sur la machine virtuelle Erlang (BEAM), largement adopté pour les applications scalables et concurrentes. Bien que des outils comme Dialyzer existent, ils manquent d'une base théorique formelle pour un système de types statiques sonore et expressif. Le défi consiste à introduire le typage statique dans un langage dynamique sans modifier son pipeline de compilation ou son comportement d'exécution (la contrainte d'« effacement »), tout en maintenant la sonorité.

Les approches classiques de typage graduel font face à une dichotomie :

Vérifications à l'exécution (Runtime Checks) : Insérer des vérifications dynamiques au moment de l'exécution pour appliquer les types (ex: Reticulated Python). Cela est incompatible avec la conception d'Elixir, qui repose sur les vérifications existantes de la BEAM et vise un coût d'exécution nul pour les annotations de type.
Effacement Complet (Full Erasure) : Supprimer entièrement les annotations de type (ex: TypeScript). Cela conduit souvent à une imprécision ou à des approximations grossières car le système de types ne peut pas tirer parti des garanties d'exécution.

Les difficultés techniques spécifiques pour Elixir incluent :

Complexité des Gardes : Elixir repose fortement sur le pattern matching et des gardes complexes (ex: is_integer(elem(x,1))) pour le contrôle de flux. Les systèmes de types existants peinent à analyser précisément ces gardes pour affiner les types.
Fonctions Multi-arité : Les fonctions Elixir possèdent une arité explicite (ex: f/2 vs f/3), qui fait partie de leur identité et est testable via des gardes (is_function(f, 2)). Les théories de sous-typage sémantique standard modélisent souvent les fonctions comme des fonctions unaires sur des tuples, échouant ainsi à capturer les propriétés spécifiques à l'arité.
Fonctions Fortes (Strong Functions) : Le système doit distinguer les fonctions qui sont simplement typées de celles qui sont « fortes » — c'est-à-dire des fonctions qui, même appliquées à des arguments hors de leur domaine déclaré, soit échouent, soit retournent une valeur dans leur codomaine déclarée grâce à des vérifications d'exécution (soit par le programmeur via des gardes, soit par la BEAM).

2. Méthodologie

Les auteurs formalisent un système de types pour un sous-ensemble central d'Elixir (Core Elixir) et un sous-ensemble « Featherweight » (FW-Elixir) qui correspond à la syntaxe concrète. La méthodologie repose sur trois piliers :

A. Typage Graduel à Effacement Sûr

Le système adopte une stratégie d'« effacement sûr » où les annotations de type sont effacées avant l'exécution. La sonorité n'est pas imposée par l'insertion de nouvelles vérifications à l'exécution, mais en exploitant :

Vérifications Implicites : Les vérifications de type inhérentes à la BEAM (ex: opérations arithmétiques sur des entiers).
Vérifications Explicites : Les gardes écrites par le programmeur.
Le système introduit des Fonctions Fortes, qui reçoivent des types précis même lorsqu'elles sont appliquées à des arguments dynamic() (notés ?), à condition que le corps de la fonction garantisse un résultat dans le codomaine ou un échec.

B. Sous-typage Sémantique avec Types Théoriques d'Ensembles

Le système utilise le sous-typage sémantique, interprétant les types comme des ensembles de valeurs. Cela permet l'utilisation d'opérateurs d'ensembles (union, intersection, différence) et fournit une relation de sous-typage décidable.

Types Graduels : Le type dynamic() est géré via le sous-typage cohérent et la matérialisation. Un type graduel $t$ est équivalent à $t^\downarrow \lor (? \land t^\uparrow)$ , où $t^\downarrow$ et $t^\uparrow$ sont les matérialisations statiques minimale et maximale.
Propagation Dynamique : Pour préserver la flexibilité du typage graduel, le système propage le ? à travers les résultats (ex: int() and ?), permettant aux expressions d'être utilisées dans des contextes exigeant soit le type statique, soit n'importe quel type dynamique.

C. Analyse des Gardes

Une analyse novatrice est développée pour caractériser l'ensemble des valeurs acceptées par les gardes.

Types Possibilitément/Sûrement Acceptés : Pour une garde $g$ $g$ , le système calcule :
- Type Possiblement Accepté ( $\mathcal{I}g\mathcal{H}$ ) : Une sur-approximation des valeurs qui pourraient satisfaire la garde.
- Type Sûrement Accepté ( $\mathcal{H}g\mathcal{I}$ ) : Une sous-approximation des valeurs qui satisfont certainement la garde.
Affinement (Refinement) : L'analyse partitionne le type d'entrée basé sur les clauses de garde, en soustrayant les types sûrement acceptés des clauses précédentes pour typer les branches suivantes. Cela gère les gardes complexes impliquant des combinaisons booléennes, des égalités et des projections de tuples.
Affinement Naïf de Type : Le système affine les types des variables au sein des branches en intersectant le squelette de l'expression matchée avec les contraintes de la garde.

D. Multi-Arité et Flèches Fortes

Multi-Arité : Le système de types étend le sous-typage sémantique pour supporter $(t_1, \dots, t_n) \to t$ directement, plutôt que d'encoder ces fonctions comme des fonctions unaires sur des tuples. Cela permet un typage précis des vérifications d'arité.
Flèches Fortes (Strong Arrows) : Un nouveau constructeur de type $(t_1 \to t_2)^\star$ désigne les fonctions qui sont sûres à appliquer à n'importe quel argument, retournant $t_2$ ou échouant, même si l'argument est hors de $t_1$ .

3. Contributions Clés

Typage Graduel à Effacement Sûr : L'article définit ce qui est affirmé être le premier système de typage graduel à effacement sûr. Il atteint la sonorité sans insérer de nouvelles vérifications à l'exécution, en s'appuyant sur les garanties existantes de la BEAM et les gardes du programmeur.
Fonctions Fortes : Formalisation des « fonctions fortes » et de la propagation des types dynamic(). Cela permet au système d'inférer des types statiques précis (ex: integer()) pour des expressions impliquant des entrées dynamic(), à condition que le corps de la fonction contienne des vérifications suffisantes.
Analyse des Gardes : Une analyse fine des gardes Elixir qui produit des types « sûrement » et « possiblement » acceptés. Cela permet un affinement précis des types pour les expressions case et les définitions de fonctions multi-clauses, supportant l'inférence de types pour le code non annoté.
Extension du Sous-typage Sémantique : Une extension conservatrice de la théorie du sous-typage sémantique pour supporter les espaces de fonctions multi-arité et les flèches fortes, incluant des algorithmes pour décider le sous-typage dans ces domaines étendus.
Inférence de Types : Techniques pour inférer les types des fonctions anonymes et multi-clauses en tirant parti de l'analyse des gardes, réduisant ainsi le besoin d'annotations explicites.
Implémentation et Évaluation : Le système a été implémenté dans le compilateur Elixir (à partir de la v1.17). L'article présente des résultats empiriques sur de grandes bases de code industrielles (Phoenix, Livebook, etc.), démontrant la détection de code mort et d'erreurs de type sans surcharge significative de compilation.

4. Résultats

Statut d'Implémentation : Le système de types est intégré dans Elixir v1.17 jusqu'à v1.20 (versions candidates). Il supporte les atomes, les tuples, les maps, les listes et les types de fonctions, y compris le typage des protocoles.
Performance : Sur de grandes bases de code (ex: Remote avec >1M de lignes de code), le temps de vérification des types constitue un faible pourcentage du temps total de compilation (allant de ~1,6% à ~9,3% selon la base de code et la version). La surcharge est comparable aux vérifications ad-hoc existantes dans le compilateur.
Précision et Détection d'Erreurs :
- Le système a identifié avec succès du code mort (clauses inutilisées, chemins inaccessibles) dans des projets majeurs comme Phoenix, Postgrex et Flame.
- Il a détecté des erreurs d'exécution qui n'avaient pas été détectées par les tests, telles qu'un appel de protocole avec un argument de type tuple dans une branche d'erreur du framework Phoenix.
- L'analyse des gardes s'est montrée très efficace pour partitionner les types pour les fonctions multi-clauses, important souvent des types d'intersection précis sans annotations.
Comparaison : L'article note que bien que l'intégration actuelle utilise des types conservateurs et fortement dynamiques pour éviter les faux positifs dans le code existant, le système sous-jacent est capable d'une haute précision lorsque les annotations sont fournies ou lorsque les gardes sont explicites.

5. Signification et Revendications

Les auteurs positionnent ce travail comme la fondation théorique du nouveau système de types d'Elixir.

Nouveauté Théorique : Ils affirment avoir établi le premier système de typage graduel à effacement sûr, résolvant la tension entre la sonorité et l'absence d'instrumentation d'exécution dans un langage dynamique.
Impact Pratique : Ce travail fournit un modèle pour intégrer des types théoriques d'ensembles dans des langages dynamiques existants possédant des bases de code substantielles. Il démontre qu'une analyse statique de haute précision est possible sans compromettre la nature dynamique et la performance du langage.
Limitations : Les auteurs sont modestes quant aux limitations actuelles :
- Affinement de Type (Type Narrowing) : Le système implémente une forme « naïve » d'affinement de type ; il manque de la granularité de systèmes de raffinement plus avancés.
- Reconstruction de Type : Une reconstruction de type de style ML complète pour les fonctions anonymes n'est pas implémentée en raison des coûts computationnels, bien que le système supporte l'inférence basée sur les gardes.
- Portée : La formalisation et l'implémentation actuelles se concentrent sur les fonctionnalités de base (gardes, fonctions fortes, multi-arité) ; d'autres aspects comme le polymorphisme paramétrique et les records sont traités dans des travaux compagnons ou des travaux futurs.

En résumé, l'article présente un système de types rigoureux, implémenté et évalué qui réussit à combler le fossé entre le runtime dynamique d'Elixir et le besoin de sécurité statique, en exploitant les propriétés uniques de la BEAM et la syntaxe des gardes d'Elixir pour atteindre la sonorité sans pénalité d'effacement.