A Calculus of Inheritance

Dit paper introduceert de 'calculus of inheritance', een fundamenteel model voor declaratief programmeren dat klassen, methoden en objecten verenigt onder een enkele record-abstractie waarbij erfelijkheid als set-union wordt gemodelleerd, waardoor het meer expressief is dan de $\lambda$-calculus en problemen zoals meervoudige erfelijkheid en het Expressie-probleem structureel oplost.

De kern

Stel je voor dat je een enorme, complexe legpuzzel moet bouwen. In de wereld van de programmeertaal zijn er twee grote manieren om dit te doen:

1. De "Rekenmachine"-manier (Functioneel): Hierbij geef je instructies: "Neem dit stukje, doe dat erbij, en geef het resultaat terug." Dit is gebaseerd op de beroemde λ-calculus (lambda-calculus), die al decennia de basis vormt voor functies en berekeningen.
2. De "Bouwpakket"-manier (Declaratief): Hierbij geef je aan hoe het eindresultaat eruit moet zien, zonder te zeggen hoe je het bouwt. Je zegt: "Ik wil een huis met een dak, muren en een deur." Dit wordt gebruikt voor configuraties (zoals hoe je je computer of server instelt).

Deze twee methoden hebben altijd als aparte werelden bestaan. De "Rekenmachine" is heel krachtig maar lastig voor complexe configuraties. De "Bouwpakket" is makkelijk voor configuraties, maar mist de kracht om complexe logica te berekenen.

Deze paper introduceert een nieuwe taal: de "Inheritance-Calculus" (Erfelijkheids-Calculus).

De auteur, Bo Yang, zegt eigenlijk: "Waarom moeten we twee verschillende talen hebben? Laten we één taal maken die beide werelden verenigt."

Hier is de uitleg in simpele taal met een paar creatieve metaforen:

1. De Drie Bouwblokken

Net zoals de oude rekenmachine-taal drie basisdingen nodig had (functies maken, toepassen, variabelen), heeft deze nieuwe taal ook maar drie basisdingen nodig:

• Records (De dozen): Een verzameling eigenschappen (zoals een doos met daarin een knop, een lamp en een schakelaar).
• Definities (De labels): Het opschrijven wat er in die doos zit.
• Erfelijkheid (Het samenvoegen): Het vermogen om twee dozen te nemen en ze in elkaar te schuiven.

2. De Magie van "Samenvoegen" (Inheritance)

In de oude wereld van objecten (zoals in Java of C++), als je twee klassen samenvoegt, krijg je vaak een ruzie: "Wie is de baas? Welke versie van de code gebruiken we?" Dit heet het linearisatie-probleem. Het is alsof je twee mensen vraagt om een liedje te zingen, maar ze beginnen allebei tegelijk te zingen en het wordt een chaos.

In deze nieuwe taal is samenvoegen (inheritance) heel simpel en natuurlijk:

• Het is commutatief: Het maakt niet uit of je Doos A op Doos B legt, of Doos B op Doos A. Het resultaat is hetzelfde.
• Het is idempotent: Als je Doos A twee keer op Doos B legt, verandert er niets extra's. Het is alsof je een sticker twee keer op dezelfde plek plakt; het blijft één sticker.
• Het is associatief: Je kunt dozen in elke volgorde samenvoegen.

De Metafoor:
Stel je voor dat je een Kostuumkast hebt.

• Je hebt een basispak (een broek en een overhemd).
• Je hebt een jas.
• Je hebt een hoed.
  In de oude wereld zou je moeten beslissen: "Eerst de jas, dan de broek, of andersom?" en "Wat als de jas een zak heeft die de broek ook heeft?"
  In deze nieuwe taal is het alsof je alle kledingstukken in één grote, transparante plastic zak stopt. Alles wat erin zit, is erin. Als er twee zakken met een rode sok in zitten, heb je gewoon twee rode sokken (of één, afhankelijk van hoe je kijkt, maar er is geen ruzie). Het systeem "merge"t alles automatisch en diep.

3. Waarom is dit zo speciaal?

De paper laat zien dat je met deze simpele "doosjes samenvoegen" eigenlijk alles kunt doen wat je met de complexe rekenmachine-taal kunt doen.

• Functies zijn gewoon dozen: Een functie is gewoon een doos met een "ingang" (argument) en een "uitgang" (resultaat). Als je een functie toepast, leg je een andere doos erbij.
• Logica komt erbij: Als je twee dozen met getallen samenvoegt, krijg je automatisch alle mogelijke combinaties. Dit betekent dat je met deze taal ook logica-programmeren (zoals in databases) kunt doen, zonder extra regels. Het is alsof je twee lijsten met namen samenvoegt en automatisch alle mogelijke paren krijgt.

4. Het "Expression Problem" (Het Uitbreidingsprobleem)

In de programmeerwereld is het vaak lastig om nieuwe functies toe te voegen aan bestaande data zonder alles te moeten herschrijven.

• Voorbeeld: Je hebt een systeem voor dieren. Je wilt nu een nieuwe soort "Dinosaurussen" toevoegen én een nieuwe eigenschap "Kan vliegen". In oude talen moet je vaak alles opnieuw schrijven.
• In deze taal: Je maakt gewoon een nieuw bestandje met "Dinosaurussen" en een ander met "Kan vliegen". Je voegt ze samen. Het systeem werkt direct. Je hoeft niets aan de oude code te veranderen. Het is alsof je een nieuwe module in een Lego-set klikt; hij past direct, ongeacht wat er al in zit.

5. De "Kleurblindheid" van Functies

Een van de coolste dingen die de paper ontdekt: Het maakt niet uit of je code draait op een snelle server of in een trage browser. Omdat de code alleen beschrijft wat er moet gebeuren (de structuur van de dozen) en niet hoe het moet gebeuren, werkt dezelfde code overal. Het is alsof je een recept schrijft dat werkt in een oven, een magnetron én op een kampvuur, zolang je maar de ingrediënten (de dozen) correct samenvoegt.

Conclusie

Deze paper zegt: "Stop met het maken van ingewikkelde regels voor hoe we code samenvoegen. Laten we teruggaan naar de basis: dozen met eigenschappen die we simpelweg in elkaar schuiven."

Door te laten zien dat dit simpele "samenvoegen" net zo krachtig is als de complexe wiskunde van de rekenmachine-taal, biedt het een nieuwe, eenvoudigere manier om software te bouwen die:

1. Makkelijker te begrijpen is.
2. Makkelijker uit te breiden is (je kunt altijd nieuwe stukjes toevoegen).
3. Zelfs complexe berekeningen en logica aankan zonder ingewikkelde functies.

Het is alsof we ontdekken hebben dat je met alleen Lego-blokjes (samenvoegen) net zo goed een kasteel kunt bouwen als met blauwdrukken en gereedschap (de oude rekenmachine-taal), maar dat het bouwen met blokken veel leuker en flexibeler is.

Technische samenvatting

Hier is een gedetailleerde technische samenvatting van het paper "A Calculus of Inheritance" van Bo Yang, in het Nederlands.

Titel: A Calculus of Inheritance

Auteur: Bo Yang (Figure AI Inc., USA)

---

1. Het Probleem

In de moderne software-engineering zijn declaratieve en configuratietalen (zoals NixOS, Jsonnet, CUE, Dhall) overal aanwezig. Deze talen gebruiken vaak mechanismen voor het samenvoegen van gestructureerde data via erfelijkheid (inheritance) of mergen. Ondanks hun praktische succes ontbreekt er een fundamentele computationele theorie die verklaart waarom deze mechanismen zo expressief zijn.

Er is een kloof tussen de twee dominante paradigma's:

• Functioneel programmeren: Gebaseerd op de $\lambda$-calculus, met functies als eerste-class burgers, maar vereist mutable state of complexe substitutie voor recursie.
• Declaratief/Configuratie: Gebaseerd op onveranderlijke (immutable) waarden zonder eerste-class functies.

De klassieke modellen van berekenbaarheid (Turing Machine, RAM Machine, $\lambda$-calculus) voldoen niet aan de eisen voor een model dat tegelijkertijd Turing-compleet, onveranderlijk en vrij van functies is. Configuratie-talen lijken deze "lege cel" in te vullen, maar hun semantiek is vaak ad-hoc. Bestaande objectgeoriënteerde modellen (zoals mixins en traits) kampen met problemen zoals de "linearization problem" bij meervoudige erfelijkheid (C3-algoritme) en conflicten bij zelfreferentie in meervoudige paden.

2. Methodologie

De auteur introduceert Inheritance-calculus, een minimaal computationeel model voor declaratief programmeren. De methode bestaat uit de volgende stappen:

• Primitieven: Het model reduceert declaratief programmeren tot drie primitieven:
  1. Record: Een verzameling van definities en erfelijkheidsbronnen.
  2. Definitie: Een label dat een waarde koppelt (ℓ ↦→ e).
  3. Erfelijkheid (Inheritance): Een referentie die omhoog navigeert in de scope-hiërarchie en vervolgens eigenschappen naar beneden projecteert.
• Semantiek: In plaats van functietoepassing ($\beta$-reductie) wordt diepe samenvoeging (deep merge) gebruikt. Erfelijkheid wordt gemodelleerd als set-union. Dit maakt erfelijkheid inherent commutatief, idempotent en associatief.
• Zelfreferentie: Zelfreferentie wordt opgelost via een "multi-path" mechanisme. In plaats van één this-object, wordt een verzameling van paden (een "frontier") bijgehouden die naar de definitie leiden. Dit elimineert de noodzaak voor een vaste-puntcombinator in de objecttaal.
• Embedding: De auteur toont aan dat de $\lambda$-calculus kan worden vertaald naar Inheritance-calculus door $\lambda$-abstrakties te vertalen naar records met een argument en result slot, en applicaties naar erfelijkheid.
• Implementatie: De theorie is geïmplementeerd in MIXINv2, een Python-gebaseerde taal die alleen deze drie constructies gebruikt.

3. Belangrijkste Bijdragen

• Unificatie van Concepten: Inheritance-calculus verenigt klassen, methoden, objecten en eigenschappen onder één abstractie: het diep-samenvoegbare mixin. Method-level overriding wordt vervangen door diepe samenvoeging van mixin-bomen.
• Oplossing van het Linearisatie-probleem: Omdat erfelijkheid commutatief, idempotent en associatief is, is er geen behoefte aan een volgorde (linearization) bij meervoudige erfelijkheid. Conflicten worden opgelost door eigenschappen te samenvoegen in plaats van te overschrijven.
• Eerste-orde Semantiek: De semantiek wordt gedefinieerd door zes wederzijds recursieve eerste-orde vergelijkingen over paden (sequenties van labels) en verzamelingen van paden. Er zijn geen functieruimtes, closures of strategieën nodig. De semantiek is denotationeel en fixpoint-berekenbaar (via de Knaster-Tarski stelling).
• Expressieve Asymmetrie: Inheritance-calculus is strikt expressiever dan de lazy $\lambda$-calculus (in de zin van Felleisen). Hoewel de $\lambda$-calculus kan worden gemacro-expressie in Inheritance-calculus, kan de $\lambda$-calculus de erfelijkheidsconstructies niet macro-expresseren. Dit komt doordat Inheritance-calculus "open extensie" toestaat: bestaande definities krijgen nieuwe waarneembare projecties zonder dat de oorspronkelijke code wordt gewijzigd.
• Emergente Fenomenen:
  • Relationale Semantiek: Eenvoudige rekenkundige operaties op Church-coderingen resulteren automatisch in relationele semantiek (Cartesisch product), vergelijkbaar met logica-programmering (Datalog).
  • Immunititeit tegen niet-uitbreidbaarheid: Het model is structureel immuun voor het "Expression Problem". Nieuwe data-types en operaties kunnen onafhankelijk worden toegevoegd zonder bestaande code te wijzigen.
  • Function Color Blindness: Dezelfde code kan zowel synchroon als asynchroon worden uitgevoerd door de implementatie van de "slots" via erfelijkheid in te vullen, zonder de business logica te wijzigen.

4. Resultaten

• Correctheid van de Vertaling: Er is bewezen dat de vertaling van de $\lambda$-calculus naar Inheritance-calculus de Böhm-boom-equivalentie behoudt. Dit betekent dat de eerste-orde semantiek van Inheritance-calculus volledig abstract is voor een sub-taal van de lazy $\lambda$-calculus.
• Convergentie: Recursieve $\lambda$-programma's die in de standaard $\lambda$-calculus divergeren (oneindige recursie), kunnen convergeren in Inheritance-calculus onder de lfp(TP) (least fixed point) semantiek. Dit komt doordat de evaluatie gebaseerd is op het observeren van paden in een trie-structuur in plaats van het uitvoeren van substitutie.
• Case Study (Nat Arithmetic): De auteur heeft Booleaanse logica en natuurlijke getallen (unair en binair) geïmplementeerd in MIXINv2. Door bestanden onafhankelijk te combineren (bijv. NatPlus en NatEquality), ontstond automatisch een systeem dat zowel optellen als vergelijken ondersteunde, inclusief het verwerken van Cartesisch producten (bijv. {1,2} + {3,4} = {4,5,6}).
• Vergelijking met Bestaande Systemen: Het paper toont aan dat systemen zoals Scala (DOT calculus) en het NixOS module-systeem falen bij meervoudige zelfreferentie-paden (multi-path self-reference) omdat ze uitgaan van een enkelvoudige this-referentie. Inheritance-calculus lost dit op door de this-referentie als een verzameling paden te behandelen.

5. Betekenis en Impact

• Fundamentele Theorie: Dit paper vult een langdurige leemte in de computationele theorie door een model te bieden dat Turing-compleet is zonder mutable state of first-class functies. Het stelt dat "functies syntactisch suiker zijn voor erfelijkheid".
• Praktische Toepassingen: De inzichten verklaren waarom configuratie-systemen zoals NixOS zo krachtig zijn en bieden een theoretisch fundament voor het bouwen van nieuwe, uitbreidbare talen.
• Oplossing voor het Expression Problem: Het model biedt een natuurlijke, structurele oplossing voor het Expression Problem, waarbij uitbreidbaarheid inherent is en niet opt-in moet worden.
• Relatie tot Logica: Het paper verbindt declaratief programmeren direct met relationele algebra en Datalog, waarbij het "trie"-gedrag van records de basis vormt voor join-operaties en recursieve query's.

Kortom, "A Calculus of Inheritance" presenteert een revolutionair perspectief waarbij erfelijkheid niet slechts een syntactisch hulpmiddel is, maar de fundamentele bouwsteen van berekenbaarheid, met een semantiek die eenvoudiger, meer uitbreidbaar en theoretisch robuuster is dan traditionele functionele of objectgeoriënteerde modellen.