A Calculus of Inheritance

Ce papier présente un calcul d'héritage fondé sur trois primitives (enregistrement, définition, héritage) qui unifie les concepts de programmation déclarative en modélisant l'héritage comme une union d'ensembles, éliminant ainsi les problèmes de linéarisation et offrant une expressivité supérieure à celle du $\lambda$-calcul grâce à une sémantique dénotative et fixpoint-computable.

L'essentiel

Imaginez que vous êtes un architecte chargé de construire une ville entière, mais au lieu de poser des briques une par une, vous avez une boîte magique de Lego. Dans cette boîte, chaque pièce a une étiquette (comme "porte", "fenêtre", "toit").

Le papier que nous allons explorer, "A Calculus of Inheritance" (Un calcul de l'héritage), propose une nouvelle façon de penser le code informatique, non pas comme une suite d'instructions complexes (comme en programmation classique), mais comme un jeu de superposition de ces pièces de Lego.

Voici l'explication simple, étape par étape, avec des analogies du quotidien.

1. Le Problème : Deux mondes qui ne se parlent pas

Pendant des décennies, l'informatique a eu deux grands royaumes :

• Le Royaume des Fonctions (Lambda-calcul) : C'est comme une cuisine où l'on mélange des ingrédients. On a des recettes (fonctions) qui prennent des ingrédients et produisent un plat. C'est puissant, mais c'est très "mathématique" et parfois difficile à modifier sans tout casser.
• Le Royaume de la Configuration (Langages déclaratifs) : C'est comme un formulaire de demande de prêt ou un fichier de configuration d'ordinateur. On dit "Je veux une fenêtre ici, une porte là". C'est simple, mais on ne peut pas faire de calculs complexes dedans.

L'auteur, Bo Yang, dit : "Pourquoi ne pas fusionner ces deux mondes ?" Il a découvert que l'héritage (le fait de copier-coller et modifier des configurations) est en fait beaucoup plus puissant qu'on ne le pensait.

2. La Solution : Le "Calcul de l'Héritage"

L'auteur propose une nouvelle règle du jeu basée sur trois choses simples :

1. Le Record (La Boîte) : Une boîte avec des étiquettes.
2. La Définition (L'Étiquette) : Mettre quelque chose dans la boîte.
3. L'Héritage (La Superposition) : Prendre deux boîtes et les coller l'une sur l'autre.

L'analogie du "Calque Transparent" :
Imaginez que vous avez un dessin sur une feuille de papier (la base). Vous prenez une feuille transparente par-dessus et vous dessinez une porte. Vous en prenez une autre et vous dessinez une fenêtre.

• Dans les systèmes classiques, si vous essayez de mettre deux portes au même endroit, ça plante (conflit).
• Dans ce nouveau système, les calques fusionnent magiquement. Si vous avez deux portes, le système ne panique pas : il les met côte à côte ou les fusionne intelligemment. C'est comme si vous aviez une boîte de Lego où, si deux pièces tentent d'occuper le même espace, elles s'assemblent parfaitement au lieu de se casser.

3. Les Trois Super-Pouvoirs Magiques

Ce système a trois propriétés mathématiques qui le rendent incroyable :

• Commutatif : Peu importe l'ordre dans lequel vous empilez les calques (A sur B, ou B sur A), le résultat est le même.
• Idempotent : Si vous empilez le même calque deux fois, ça ne change rien (A + A = A). Pas de doublons gênants.
• Associatif : (A + B) + C est la même chose que A + (B + C). Vous pouvez empiler vos pièces comme vous voulez.

Pourquoi est-ce important ?
Dans la programmation classique (comme en Java ou C++), si vous héritez de plusieurs classes, le système doit décider "qui gagne" quand deux classes ont la même méthode. C'est le fameux "problème du diamant" qui rend les développeurs fous. Ici, ce problème n'existe plus. Tout se fusionne naturellement. C'est comme si vous aviez un puzzle où toutes les pièces s'emboîtent parfaitement, peu importe l'ordre.

4. La Révolution : Les Fonctions sont devenues des Boîtes

Le plus fou, c'est que l'auteur montre que les fonctions mathématiques complexes peuvent être construites uniquement avec ces boîtes d'héritage.

• Au lieu d'écrire f(x) = x + 1, vous créez une boîte "Fonction" avec un trou pour l'entrée et un trou pour la sortie.
• Pour appliquer la fonction, vous "héritez" de cette boîte en y glissant votre valeur.
• Résultat : Vous pouvez faire des calculs, de la logique, et même créer des programmes complexes sans jamais écrire une seule "fonction" traditionnelle.

C'est comme si vous pouviez construire un moteur de voiture uniquement en empilant des boîtes de conserve, sans jamais avoir besoin de visser des pièces ensemble avec des outils complexes.

5. L'Effet "Choc" : La Programmation Relationnelle

Le papier montre un autre phénomène étrange et génial.
Si vous prenez deux nombres (par exemple 1 et 2) et que vous les mettez dans une boîte, puis que vous faites une opération d'addition avec une autre boîte (3 et 4), le système ne donne pas juste un résultat. Il donne toutes les combinaisons possibles.

• 1+3, 1+4, 2+3, 2+4.
  C'est comme si votre calculatrice devenait un chef de cuisine qui prépare tous les plats possibles avec les ingrédients que vous lui donnez, au lieu de n'en faire qu'un seul. Cela permet de faire de la programmation logique (comme en base de données) sans effort spécial.

6. En Résumé : Pourquoi c'est génial ?

Imaginez que vous construisez une maison.

• L'ancien monde : Vous devez décider à l'avance exactement où va chaque brique. Si vous voulez ajouter une fenêtre plus tard, vous devez démolir un mur et reconstruire.
• Le nouveau monde (Inheritance-Calculus) : Vous avez des murs préfabriqués. Vous pouvez en ajouter un autre par-dessus, et le système fusionne tout automatiquement. Vous pouvez ajouter une porte, une fenêtre, ou un étage, et tout le monde s'adapte.

Les avantages concrets :

1. Pas de conflits : Vous pouvez ajouter de nouvelles fonctionnalités sans casser les anciennes (on appelle ça résoudre le "Problème de l'Expression").
2. Flexibilité totale : Le même code peut fonctionner aussi bien en mode "synchronisé" (comme un film) qu'en mode "asynchrone" (comme un film en streaming), selon comment vous assemblez les pièces.
3. Simplicité : Tout repose sur l'idée de "fusionner des listes de choses". Pas besoin de concepts mathématiques obscurs.

Conclusion

Ce papier nous dit que nous avons peut-être tort de voir la programmation comme une suite d'instructions séquentielles. Peut-être que la vraie nature du logiciel, c'est simplement l'art de superposer des couches d'informations pour créer quelque chose de plus grand, où chaque nouvelle couche améliore la précédente sans la détruire.

C'est une vision où le code n'est pas une machine rigide, mais un organisme vivant qui grandit en s'adaptant, un peu comme un écosystème où chaque nouvelle plante s'intègre naturellement au jardin existant.

Résumé technique

Voici un résumé technique détaillé de l'article « A Calculus of Inheritance » (Un calcul de l'héritage) par Bo Yang.

1. Problématique et Contexte

Les langages de configuration et déclaratifs modernes (NixOS, Jsonnet, CUE, Dhall, etc.) sont omniprésents dans l'ingénierie logicielle pour gérer des structures de données complexes. Cependant, contrairement au calcul $\lambda$ qui sert de fondement théorique unifié à la programmation fonctionnelle, il n'existe pas de modèle computationnel formel équivalent pour la programmation déclarative basée sur l'héritage.

Les défis majeurs identifiés sont :

• L'incompatibilité apparente : La complétude de Turing semble incompatible avec des contraintes de valeurs immuables et l'absence de fonctions de première classe, pourtant présentes dans ces langages.
• Le problème de linéarisation : Dans les systèmes à héritage multiple (mixin), la résolution de l'ordre d'héritage (ex: C3 linearization) est souvent complexe, non commutative et source d'erreurs.
• Le problème de l'expression (Expression Problem) : La difficulté d'étendre un système de types ou de données avec de nouvelles opérations ou de nouveaux types de données sans modifier le code existant.
• L'absence de sémantique unifiée : Les systèmes actuels (comme NixOS) fonctionnent empiriquement mais manquent d'une théorie formelle expliquant leur expressivité et leur comportement face à la récursivité et à l'héritage multiple.

2. Méthodologie et Approche

L'auteur propose de réduire les systèmes de configuration complexes à un modèle minimaliste appelé Inheritance-Calculus (Calcul de l'Héritage).

• Primitives Fondamentales : Le calcul repose sur trois primitives uniquement :
  1. Enregistrement (Record) : Une structure de données transparente.
  2. Définition (Definition) : L'association d'une étiquette à une valeur (ℓ ↦→ e).
  3. Héritage (Inheritance) : La fusion de structures via l'union de sets ({e1, e2}).
• Modélisation de l'Héritage : L'héritage est modélisé simplement comme une union d'ensembles (set union). Contrairement aux modèles orientés objet classiques, il n'y a pas de méthodes opaques ; chaque valeur est un enregistrement transparent. L'héritage effectue une fusion profonde (deep merge) récursive des sous-arbres.
• Sémantique Observationnelle : Le calcul est défini par six équations récursives de premier ordre (First-Order) sur les chemins (paths) dans un arbre de mixins. La sémantique est dénotationnelle, fixpoint-computable (calculable par point fixe) et paresseuse (lazy).
• Résolution Multi-chemin : Une innovation clé est la résolution de this (auto-référence) qui n'est pas unique mais multi-chemin. Lorsqu'un objet hérite de plusieurs sources, this renvoie un ensemble de chemins, permettant une résolution naturelle sans conflit, contrairement aux systèmes qui rejettent les héritages multiples (comme Scala/DOT).

3. Contributions Clés

1. Le Calcul de l'Héritage : Un modèle computationnel minimaliste pour la programmation déclarative, unifiant classes, méthodes, objets et propriétés sous une seule abstraction de mixin.
2. Élimination du problème de linéarisation : Grâce à la fusion profonde et aux propriétés de l'union d'ensembles, l'héritage est intrinsèquement commutatif, idempotent et associatif. Le problème de l'ordre d'héritage disparaît structurellement.
3. Sémantique de Premier Ordre : Contrairement au calcul $\lambda$ qui nécessite des espaces de fonctions (higher-order), la sémantique de ce calcul repose uniquement sur des ensembles de chemins et des équations récursives. Cela permet d'obtenir une sémantique dénotationnelle complète sans utiliser de domaines réflexifs complexes (comme $D \cong [D \to D]$).
4. Imbriquement du Calcul $\lambda$ : L'article démontre que le calcul $\lambda$ (sous forme normale A) peut être macro-translaté dans le Calcul de l'Héritage en cinq règles locales. Cela prouve que le Calcul de l'Héritage est Turing-complet.
5. Asymétrie Expressive : Le Calcul de l'Héritage est strictement plus expressif que le calcul $\lambda$ paresseux (au sens de Felleisen). Il permet d'ajouter de nouvelles projections observables à des définitions existantes sans les modifier (extension ouverte), ce que le calcul $\lambda$ ne permet pas sans modifier le code source.
6. Émergence de la Sémantique Relationnelle : L'arithmétique ordinaire et la logique booléenne implémentées dans ce calcul produisent naturellement une sémantique relationnelle (produits cartésiens, jointures) sans mécanisme dédié, grâce à la structure en arbre (trie) des valeurs.

4. Résultats et Preuves

• Équivalence avec les Arbres de Böhm : L'article prouve que la convergence d'un terme dans le Calcul de l'Héritage correspond exactement à l'existence d'une forme normale de tête (Head Normal Form) dans le calcul $\lambda$ (via les arbres de Böhm).
• Convergence des Programmes Récursifs : Une découverte surprenante est que certains programmes $\lambda$ qui divergent sous la réduction $\beta$ (boucles infinies) peuvent converger sous la sémantique du point fixe minimal ($lfp(T_P)$) du Calcul de l'Héritage. Cela suggère une sémantique plus robuste pour les programmes récursifs.
• Résolution du Problème de l'Expression : Le modèle résout nativement le problème de l'expression. Il est possible d'ajouter de nouvelles opérations (ex: égalité) et de nouveaux types de données (ex: booléens) dans des fichiers séparés qui s'assemblent par héritage, sans modifier les fichiers existants.
• Implémentation (MIXINv2) : Toutes les constructions ont été implémentées et testées dans un langage concret appelé MIXINv2 (disponible en open source). Les tests couvrent la logique booléenne, l'arithmétique naturelle, et des applications web, validant la théorie par la pratique.
• Encodage de Datalog : L'article montre comment encoder le langage de programmation logique Datalog directement dans ce calcul, démontrant que les jointures et la récursivité émergent naturellement des équations de fusion.

5. Signification et Impact

Ce travail a des implications profondes pour la théorie des langages de programmation et l'ingénierie logicielle :

• Nouveau Paradigme Théorique : Il établit que la programmation déclarative basée sur l'héritage n'est pas seulement une pratique empirique, mais possède une fondation mathématique rigoureuse, aussi solide que celle du calcul $\lambda$ pour la programmation fonctionnelle.
• Simplification de l'Héritage Multiple : En rendant l'héritage commutatif et associatif, il élimine les complexités liées à la linéarisation (C3) qui sont souvent des sources de bugs dans les langages comme Java, Scala ou C++.
• Extensibilité Universelle : Le modèle offre une solution structurelle au problème de l'expression, permettant une extensibilité "par défaut" (open extension) qui est souvent difficile à obtenir dans les langages traditionnels.
• Unification des Paradigmes : Il unifie la programmation fonctionnelle, la programmation orientée objet et la programmation logique (via Datalog) sous un seul formalisme basé sur les ensembles et les chemins.
• Applications Pratiques : Les résultats valident et théorisent les mécanismes de systèmes de configuration puissants comme NixOS, suggérant que ces systèmes sont plus expressifs qu'on ne le pensait et ouvrant la voie à de nouveaux langages de configuration plus robustes et prévisibles.

En résumé, Bo Yang démontre que l'héritage, lorsqu'il est défini comme une fusion profonde d'ensembles de chemins, constitue un modèle computationnel complet, plus expressif que le calcul $\lambda$ dans certains aspects, et capable de résoudre des problèmes fondamentaux de modularité et de sémantique dans les langages modernes.