🔢 mathematics

Bidirectional Interpolation for the Lambda-Calculus -- Revisiting and Formalising Craig-Čubrić Interpolation

Dit artikel presenteert een nieuw bewijs en een formalisatie in Rocq van Čubrić's bewijs-relevante interpolatiestelling voor de lambda-calculus, gebaseerd op principes van bidirectioneel typen.

Oorspronkelijke auteurs: Meven Lennon Bertrand, Alexis Saurin

Gepubliceerd 2026-03-04

📖 4 min leestijd🧠 Diepgaand

CC BY 4.0

Oorspronkelijke auteurs: Meven Lennon Bertrand, Alexis Saurin

Oorspronkelijk artikel gelicentieerd onder CC BY 4.0 (http://creativecommons.org/licenses/by/4.0/). ✨ Dit is een AI-gegenereerde uitleg van het onderstaande artikel. Het is niet geschreven of goedgekeurd door de auteurs. Raadpleeg het oorspronkelijke artikel voor technische nauwkeurigheid. Lees de volledige disclaimer

Stel je voor dat je twee mensen hebt die over iets praten, maar ze gebruiken totaal verschillende woorden. De ene spreekt alleen over "appels" en "koffie", de andere alleen over "fietsen" en "regen". Als ze toch een gesprek willen voeren, hebben ze een vertaler nodig. Deze vertaler mag alleen woorden gebruiken die beide mensen begrijpen.

In de wiskunde en informatica heet dit een interpolatie. Het is een bewijs dat je een logische redenering van A naar B kunt maken via een tussenstap (de vertaler) die alleen gebruikmaakt van de gedeelde concepten.

Dit artikel van Lennon-Bertrand en Saurin gaat over een heel specifiek soort "vertalen" binnen de programmeertaaltheorie, maar dan niet voor mensen, maar voor computers en hun bewijzen. Hier is de uitleg in gewone taal:

1. Het Probleem: De "Vervormde" Vertaler

Vroeger hadden wiskundigen al een manier gevonden om deze vertalers te maken (het werk van Čubrić). Maar hun methode was als een ingewikkeld, rommelig recept. Je moest stap voor stap kleine stukjes van een bewijs vervangen door variabelen, en het was erg lastig om te volgen. Het was alsof je een auto probeert te repareren door hem volledig uit elkaar te halen, zonder een duidelijke handleiding.

Bovendien was hun methode alleen goed voor "perfecte" bewijzen (bewijzen die al volledig zijn uitgewerkt en geen onnodige stappen meer bevatten). In de echte wereld zijn bewijzen vaak rommelig en zitten er nog "rekenfouten" of onnodige stappen in.

2. De Oplossing: Een Nieuwe Kijk met "Bidirectioneel Typen"

De auteurs van dit artikel hebben een nieuwe manier gevonden om dit probleem op te lossen. Ze gebruiken een concept dat ze "bidirectioneel typen" noemen.

Stel je een fabriek voor waar producten worden geassembleerd:

Inferentie (Aanwijzen): Je kijkt naar een onderdeeltje en vraagt: "Wat is dit?" (De machine zegt: "Dit is een wiel").
Checken (Controleren): Je hebt een specificatie en vraagt: "Past dit onderdeeltje hier?" (De machine zegt: "Ja, dit wiel past op deze auto").

De auteurs ontdekten dat deze manier van werken (soms vragen, soms controleren) perfect overeenkomt met de manier waarop "nette" bewijzen eruitzien. Door hun bewijs op te bouwen met deze twee richtingen, kregen ze een veel strakker en logischer recept. Het is alsof ze van een rommelige schets zijn overgestapt op een heldere architectuurtekening.

3. De "Commuterende Conversies": Het Oplossen van de Knoop

Een groot probleem bij bewijzen met sommen (keuzes, zoals "of dit, of dat") is dat je soms een knoop moet ontwarren. Stel je voor dat je een pakketje hebt dat eerst moet worden geopend, en dan pas wordt gecontroleerd. Soms is het handiger om eerst te controleren en dan pas te openen.

In de wiskunde noemen ze dit commuterende conversies. Het artikel laat zien hoe je deze knopen kunt ontwarren zonder de logica te breken. Ze hebben een nieuw systeem ontwikkeld om te bewijzen dat elk bewijs uiteindelijk kan worden omgezet in een "net" versie (een normaal vorm) die deze knopen niet meer heeft.

4. Wat hebben ze gedaan? (De "Rocq" Formalisatie)

Ze hebben niet alleen een nieuw bewijs bedacht, maar ze hebben dit ook gecodeerd in een computerprogramma genaamd Rocq (een tool die controleert of wiskundige bewijzen 100% correct zijn).

De prestatie: Ze hebben de eerste computer-gecontroleerde bewijzen gemaakt voor deze specifieke regels in een taal met "sommen" (keuzes).
De uitkomst: Hun bewijs is niet alleen correct, maar ook veel korter en begrijpelijker dan de oude versie. Het is alsof ze een oud, zwaar boek hebben herschreven tot een strak, modern handboek.

5. Waarom is dit belangrijk?

Betrouwbaarheid: Omdat het in Rocq staat, weten we met 100% zeker dat de regels kloppen. Geen menselijke fouten meer.
Nieuwe inzichten: Ze laten zien dat de manier waarop computers typen controleren (bidirectioneel) eigenlijk precies hetzelfde is als de manier waarop wiskundigen bewijzen structureren. Dit verbindt twee werelden die vaak gescheiden worden gezien.
Toekomst: Dit legt de basis voor nog complexere systemen. Misschien kunnen we in de toekomst ook bewijzen maken voor programmeertalen die nog ingewikkelder zijn, of voor systemen die "uniform" werken (waarbij één regel voor heel veel situaties geldt).

Samenvattend

Stel je voor dat je een oude, rommelige brug moet vervangen. De oude ingenieurs (Čubrić) hadden een plan, maar het was moeilijk te bouwen en alleen voor perfecte omstandigheden.
De auteurs van dit artikel hebben een nieuwe, strakke brug ontworpen. Ze gebruiken een slimme techniek (bidirectioneel typen) om te zorgen dat de brug stevig staat, zelfs als de grond eronder niet perfect is. En het beste van alles: ze hebben de blauwdrukken digitaal laten verifiëren door een supercomputer, zodat we weten dat de brug nooit zal instorten.

Dit maakt het mogelijk om in de toekomst nog complexere digitale systemen te bouwen met de zekerheid dat ze logisch kloppen.

Probleemstelling

Het artikel adresseert de uitdaging om Craig's interpolatiestelling te herformuleren en te formaliseren in de context van de simply-typed lambda-calculus met sommen (STLC+).

Interpolatie en Bewijsrelevantie: Craig's interpolatiestelling stelt dat voor een logische afleiding $A \vdash B$ , er een tussenliggende formule $I$ bestaat die alleen gebruikmaakt van de symbolen die zowel in $A$ als in $B$ voorkomen. Traditioneel is dit een semantisch of syntactisch resultaat over formules. De auteurs richten zich echter op bewijs-relevante interpolatie (zoals geïntroduceerd door Čubrić), waarbij niet alleen de formules worden gefactoreerd, maar ook de bewijstermen (proof terms). Het doel is om een term $t$ van type $A \to B$ te decomponeren in twee termen $u$ en $v$ zodanig dat $u$ een type $C$ heeft (de interpolant), $v$ van $C$ naar $B$ gaat, en de samenstelling $(\lambda y.v) u$ gelijk is aan de oorspronkelijke term $t$ .
Complexiteit van STLC+: De specifieke uitdaging bij STLC+ (met somtypes $+$ en de lege type $\bot$ ) is dat de standaard $\beta$ -normaalvormen niet voldoen aan de subformule-eigenschap (subformula property) die nodig is voor interpolatie. In aanwezigheid van somtypes zijn "commuterende conversies" (commuting conversions) nodig om eliminatoren over elkaar heen te schuiven om een adequate normaalvorm te krijgen.
Gebrek aan Formalisatie: De oorspronkelijke bewijzen van Čubrić (gebaseerd op Prawitz) zijn complex, niet-esthetisch, en berusten op inductie over de grootte van termen met het vervangen van subtermen door variabelen. Een geval dat als "gelijk aan het vorige" werd afgedaan, bleek in werkelijkheid fundamenteel anders. Bovendien ontbreekt er een volledige mechanische formalisatie van deze theorie, inclusief normalisatie voor STLC+ met commuterende conversies.

Methodologie

De auteurs hanteren een nieuwe, gestructureerde aanpak die de theorie herformuleert rondom bidirectioneel typen (bidirectional typing) en inductieve karakterisaties van normaalvormen.

Bidirectioneel Typen en Normaalvormen:
- De auteurs introduceren een bidirectioneel typesysteem dat de typen van termen splitst in inferentie (waarbij het type wordt afgeleid) en controle (waarbij het type als input dient).
- Ze definiëren neutrale termen (die niet reduceren maar kunnen worden geëlimineerd) en normaalvormen (die niet reduceren).
- Cruciaal is dat ze aantonen dat de inductieve definitie van normaalvormen in dit bidirectionele systeem precies overeenkomt met termen die voldoen aan de subformule-eigenschap (na toepassing van $\beta$ -reductie en commuterende conversies). Dit lost het probleem op dat $\beta$ -normaalvormen alleen onvoldoende zijn voor STLC+.
Logische Relaties voor Normalisatie:
- Om te bewijzen dat elke goed getypeerde term reduceert tot een normaalvorm, gebruiken ze een logische relatie (logical relations) argument.
- Ze definiëren "waarden" (values) en "reducibiliteit" (reducibility) die rekening houden met de specifieke structuur van positieve types (sommen en $\bot$ ) via een concept genaamd "covering". Dit concept vangt termen op die de vorm hebben van een case-tree met eliminaties op neutrale termen.
- Dit leidt tot een bewijs van normalisatie voor STLC+ met commuterende conversies, wat een meta-theoretisch resultaat is dat eerder niet volledig was geformaliseerd.
Inductief Bewijs van Interpolatie:
- In plaats van inductie over de grootte van termen (zoals Čubrić), gebruiken de auteurs mutuele inductie over de inductieve definitie van normaalvormen en neutrale termen in het bidirectionele systeem.
- Ze introduceren een context-partitie ( $\Gamma = \Gamma_s \cup \Gamma_t$ ) om te onderscheiden welke variabelen "van de bron" (source) komen en welke "van het doel" (target).
- Het bewijs construeert de interpolant-type $M$ en de termen $l$ en $r$ direct door de structuur van de term te analyseren, waarbij ze rekening houden met de polariteit van de types (positief vs. negatief).
Formalisatie in Rocq:
- Het gehele bewijs en de meta-theorie zijn geïmplementeerd in de Rocq (voorheen Coq) bewijshulp.
- Ze maken gebruik van de AutoSubst2-tool voor het beheer van substituties en de Sulfur-plugin (hoewel hier beperkingen waren) voor automatisering.
- Ze formaliseren ook de normalisatie voor STLC+ met commuterende conversies, wat een eerste is.

Belangrijkste Bijdragen

Nieuw Bewijs voor Bewijs-Relevante Interpolatie: Een nieuwe, gestructureerde en meer intuïtieve bewijsvoering voor Čubrić's stelling, gebaseerd op bidirectioneel typen in plaats van complexe substitutie-inductie.
Formalisatie in Rocq: De eerste volledige mechanische formalisatie van proof-relevante interpolatie voor STLC+ met somtypes.
Normalisatie voor STLC+: De eerste geformaliseerde bewijsvoering van normalisatie voor de simply-typed lambda-calculus met somtypes en commuterende conversies, inclusief de definitie van "covering" voor positieve types.
Link tussen Bidirectioneel Typen en Subformule-eigenschap: Een expliciete en gedetailleerde analyse van hoe bidirectioneel typen de subformule-eigenschap naturally vastlegt, zelfs in de aanwezigheid van somtypes (waarbij vaak wordt gedacht dat deze link breekt).
Verbeterde Interpolant: De geconstrueerde interpolanten zijn vaak compacter dan die van Čubrić (ze gebruiken producttypes om argumenten te groeperen in plaats van iteratieve functietypes, wat resulteert in een "uncurried" versie).

Resultaten

Hoofdstelling (Theorem 25): Voor elke goed getypeerde term $t$ $t$ in een context $\Gamma$ $Γ$ met type $T$ $T$ , en voor een partitionering van de context en constanten, bestaat er een type $M$ $M$ (de interpolant) en termen $l$ $l$ en $r$ $r$ zodanig dat:
- $M$ alleen symbolen bevat die voorkomen in zowel de bron- als doel-variabelen/constanten.
- $t$ is gelijk aan de samenstelling $r[l..]$ .
- De constructie werkt voor termen met somtypes en de lege type, mits ze gereduceerd zijn tot de specifieke normaalvormen gedefinieerd door het bidirectionele systeem.
Normalisatie: Elk goed getypeerd woord in STLC+ reduceert tot een normaalvorm (Corollary 19).
Efficiëntie: De formalisatie is compact (ongeveer 4000 regels code, inclusief gegenereerde code) en compileert snel (ongeveer 30 seconden op een standaard laptop), wat aanzienlijk sneller is dan vergelijkbare werken in Agda of Rocq voor logische interpolatie.

Betekenis en Toekomstperspectief

Theoretische Inzicht: Het artikel verduidelijkt de diepe relatie tussen de structuur van normaalvormen, de subformule-eigenschap en bidirectioneel typen. Het toont aan dat bidirectioneel typen een krachtig hulpmiddel is voor het bewijzen van structurele eigenschappen van bewijssystemen.
Praktische Toepassing: De mechanische formalisatie biedt een betrouwbaar fundament voor verdere onderzoek naar proof-relevante interpolatie, wat nuttig kan zijn voor toepassingen zoals modulaire model-checking, database query planning en het begrijpen van de interne taal van bi-cartesisch gesloten categorieën (biCCCs).
Toekomstig Werk: De auteurs identificeren drie richtingen:
1. Interpolatie voor niet-normale termen: Uitbreiden naar termen met redexes (bijv. door annotaties toe te voegen om cuts zichtbaar te maken).
2. Uniforme Interpolatie: Onderzoeken of een enkele interpolant kan worden gegenereerd die werkt voor een hele sub-taal, niet alleen voor een specifieke afleiding.
3. Dependente Types: Uitbreiden naar dependente type-theorieën, wat complexer is vanwege de interactie tussen types en termen en de uitdagingen bij commuterende conversies in dat kader.

Kortom, dit werk biedt een modern, geformaliseerd en gestructureerd perspectief op een klassiek probleem in de logica, met een sterke nadruk op de computatiele en bewijs-theoretische aspecten van de lambda-calculus.