💻 computer science

Proof Theory and Dependent Type Theory: Distinct Foundations for Designing Proof Assistants

Dit artikel betoogt dat de moderne structurele bewijstheorie, geëxemplifieerd door de sequentencalculus en geïmplementeerd in de Abella-bewijsassistent, een overtuigend alternatief biedt voor afhankelijke typentheorie voor het ontwerpen van bewijsassistenten door de logica beter te scheiden van de bewijsstructuur, strategisch gebruik te maken van niet-determinisme, complexe typologische kwesties te vermijden en een elegante benadering te bieden voor het afhandelen van bindingen.

Oorspronkelijke auteurs: Dale Miller (Inria Saclay,LIX, Institut Polytechnique de Paris)

Gepubliceerd 2026-07-15

📖 6 min leestijd🧠 Diepgaand

CC BY 4.0

Oorspronkelijke auteurs: Dale Miller (Inria Saclay,LIX, Institut Polytechnique de Paris)

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 de ultieme "Bewijsassistent" probeert te bouwen—een superintelligente robot die mensen helpt bij het controleren van hun wiskunde- en logicahuiswerk om er zeker van te zijn dat het 100% correct is. Decennialang zijn de meeste van deze robots gebouwd met een specifiek blauwdruk genaamd Dependent Type Theory (DTT). Het is alsof je een robot bouwt van een zeer complexe, hoogtechnologische Lego-set waarbij elke enkele steen een specifiek label heeft, en de robot controleert of de labels precies overeenkomen voordat hij je toestaat ze aan elkaar te klikken.

Maar in dit artikel suggereert auteur Dale Miller dat er een andere, misschien betere manier is om deze robots te bouwen. Hij stelt dat we naar Structural Proof Theory moeten kijken, specifits een raamwerk genaamd de Sequent Calculus. Denk hier niet aan als een rigide Lego-set, maar als een dynamische, bewegende puzzel waarbij de stukjes kunnen schuiven en van vorm kunnen veranderen, zolang de logica maar klopt.

Hier is de uiteenzetting van waarom Miller denkt dat deze "puzzel"-aanpak superieur zou kunnen zijn aan de "Lego"-aanpak, gebruikmakend van zes kernideeën:

1. Het scheiden van het "Wat" van het "Hoe"

In de Lego-wereld (DTT) beslist de robot twee dingen tegelijkertijd: wat voor logica je gebruikt en hoe het bewijs wordt opgebouwd. Het is alsof je zegt: "We mogen alleen torens bouwen met rode stenen, en de enige manier om ze te stapelen is recht omhoog."
Miller suggereert dat we dit moeten scheiden. We kunnen de logica bepalen (de regels van het spel) en vervolgens elke bewijsstructuur kiezen om het op te lossen. Het is alsof je besluit dat je voetbal wilt spelen, maar dan beseft dat je ook doelen kunt scoren door te trappen, te koppen of zelfs een netkanon te gebruiken als de regels dat toestaan. De Sequent Calculus laat je veel verschillende "zetten" gebruiken (zoals natuurlijke deductie, tableaux of resolutie) zonder je in één enkele, rigide stijl te dwingen.

2. Het probleem met "Bewijzen als Code"

De Lego-aanpak behandelt een bewijs als een computercode (een λ-term). Hoewel computers geweldig zijn in het uitvoeren van programma's, kunnen ze erg kieskeurig zijn. Soms neemt een programma een vreemd pad om tot het antwoord te komen, of loopt het vast omdat het wacht op een specifiek type invoer.
Miller wijst erop dat de Lego-aanpak te maken krijgt met rommelige zaken zoals "universe levels" (een complexe manier om types te organiseren zodat ze niet met elkaar botsen) en "proof irrelevance" (het verspillen van tijd aan het controleren van delen van het bewijs die er eigenlijk niet toe doen). De Sequent Calculus-aanpak is eenvoudiger; het hoeft zich geen zorgen te maken over deze zware typingsregels omdat het de bewijsstructuur directer behandelt, als een flowchart in plaats van een complex codescript.

3. Omgaan met "Klassieke" Logica (Het "Of/Of"-probleem)

Sommige logica is "intuïtionistisch" (je moet bewijzen dat iets bestaat door het te construeren), en sommige is "klassiek" (je kunt bewijzen dat iets bestaat door simpelweg aan te tonen dat het onmogelijk is dat het niet bestaat).
De Lego-aanpak heeft moeite om de "klassieke" stijl soepel af te handelen. Vaak moet er extra, onhandige regels worden toegevoegd om dit werkend te krijgen. Miller betoogt dat de Sequent Calculus er vanaf het begin voor is ontworpen om beide stijlen even goed te kunnen hanteren, als een universele adapter die in elke stekker past zonder dat er een lompe converter nodig is.

4. Het omarmen van "Misschien" (Niet-determinisme)

Dit is een grote. De Lego-robots zijn gebouwd om "deterministisch" te zijn, wat betekent dat ze een enkel, recht pad moeten volgen om een bewijs te controleren. Als ze een doodlopend spoor raken, stoppen ze.
Miller suggereert dat het toestaan van een beetje "niet-determinisme" (gokken en terugkeren/backtracking) eigenlijk een superkracht is. Stel je een doolhof voor. Een deterministische robot loopt één pad en stopt als hij tegen een muur loopt. Een niet-deterministische robot kan een pad proberen, tegen een muur aanlopen, "oeps" zeggen en onmiddellijk een ander pad proberen.
Miller betoogt dat door de bewijscontroleur te laten "gokken" en terug te keren, de "bewijs-certificaten" (het huiswerk dat je inlevert) veel kleiner kunnen zijn. De robot doet het zware werk van het zoeken, zodat jij niet elke stap hoeft op te schrijven. Het is een ruil: een kleiner huiswerkblaadje voor een robot die er wat harder over na moet denken.

5. De Magie van "Bewegende Binders"

Dit is de meest opwindende truc van het paper. In de logica hebben we vaak te maken met variabelen die "gebonden" zijn (zoals de "x" in "voor alle x..."). In de Lego-wereld zijn deze variabelen vaak op hun plek vastgezet, en het afhandelen ervan is een nachtmerrie van technische hoofdpijn (zoals de beroemde POPLMark-uitdaging).
Miller stelt een visie voor waarbij deze variabelen mobiel zijn. Hij noemt dit λ-tree syntax.
Stel je voor dat een variabele een naamkaartje is op een persoon. In de Lego-wereld kan het gebeuren dat als je de persoon verplaatst, het naamkaartje eraf valt of in de war raakt. In Miller's wereld is het naamkaartje aan de persoon vastgeplakt. Ongeacht hoe je de persoon door de kamer (of het bewijs) beweegt, het naamkaartje blijft bij hen.
Hij introduceert een speciaal hulpmiddel genaamd de ∇-kwantificator (uitgesproken als "nabla"). Zie dit als een "lokale scope"-knop. Wanneer je deze indrukt, zegt het: "Deze variabele behoort alleen tot dit specifieke deel van het bewijs, en kan nooit ontsnappen." Dit maakt het ongelooflijk eenvoudig om talen te redeneren die complexe regels hebben, zoals programmeertalen of de π-calculus (een manier om te modelleren hoe computers met elkaar communiceren).

6. De Abella Robot

Miller praat niet alleen over dit concept; hij heeft een robot gebouwd om te bewijzen dat het werkt. Die heet Abella.
Abella is een theorem prover die volledig is gebouwd op deze principes van de Sequent Calculus. Het gebruikt de "bewegende binders" en de ∇-kwantificator om complexe logica over talen en bindings met gemak af te handelen. Hoewel de Lego-gebaseerde robots (zoals Coq of Lean) erg populair zijn en enorme bibliotheken met vooraf gebouwde bewijzen hebben, suggereert Abella dat voor bepaalde lastige problemen—vooral die waarbij variabelen worden benoemd en verplaatst—deze nieuwe aanpak natuurlijker en eleganter is.

De Kern van het Verhaal

Miller zegt niet dat de Lego-robots (Dependent Type Theory) slecht zijn of dat ze weggegooid moeten worden. Hij erkent dat ze volwassen zijn, breed worden gebruikt en goed zijn in veel zaken.
Echter, hij suggereert dat voor de fundamenten van hoe we deze bewijsassistenten ontwerpen, de Sequent Calculus een flexibelere, eenvoudigere en krachtigere toolkit biedt. Het scheidt logica van structuur, omarmt slim gokken en handelt de lastige zaken rondom "bewegende variabelen" af met een elegantie die de huidige standaard moeilijk kan evenaren. Het is een uitnodiging om het probleem vanuit een andere hoek te bekijken, met een raamwerk dat succesvol is geweest in veel andere gebieden van de logica, maar nog niet eerder de hoofdrol heeft gespeeld in de wereld van interactieve bewijsassistenten.

Probleemstelling
Het artikel behandelt de fundamentele ontwerpkeuzes die ten grondslag liggen aan interactieve stellingbewijzers (proof assistants). Terwijl het dominante paradigma in grote systemen (bijv. Coq, Lean, Agda) steunt op Afhankelijke Type Theorie (DTT) en het "bewijzen-als-termen"-paradigma — waarbij bewijzen worden gerepresenteerd als afhankelijk getypeerde $\lambda$ -termen — betoogt de auteur dat de moderne structurele bewijstheorie, specifiek de sequentencalculus, een overtuigend, maar onderbenut alternatief kader biedt. Het artikel stelt dat de DTT-benadering de logica die wordt geformaliseerd verzwakt met de structuur van het bewijs, wat leidt tot complexiteiten bij het afhandelen van klassieke logica, non-determinisme en syntactische bindingen die een bewijstheoretisch perspectief eleganter zou kunnen oplossen.

Methodologie
De auteur hanteert een vergelijkende theoretische analyse, waarbij de ontwerpnarratieven van op DTT gebaseerde systemen worden gecontrasteerd met die afgeleid van de structurele bewijstheorie. De methodologie omvat:

Historisch en Theoretisch Onderzoek: Het traceren van de oorsprong van natuurlijke deductie en de sequentencalculus (Gentzen) en hun daaropvolgende toepassingen in consistentiebewijzen, onafhankelijkheidsbewijzen en logica-programmering.
Conceptuele Decompositie: Het scheiden van de vraag "welke logica wordt geformaliseerd" van "wat een bewijs constitueert", waarbij wordt geargeerd dat DTT vaak de bewijsstructuur (natuurlijke deductie gecodeerd als $\lambda$ -termen) samen met de logica vastlegt, terwijl de bewijstheorie diverse bewijsstructuren (sequentencalculus, tableaux, resolutie) voor één enkele logica toestaat.
Kritische Analyse van DTT-beperkingen: Het onderzoeken van specifieke technische hindernissen in DTT, zoals de vermenging van bewijs-onrelevantie (proof irrelevance), universumniveaus en impliciete argumenten, en de moeilijkheden bij het uniform afhandelen van klassieke logica (bijv. de uitsluiting van multiple-conclusion sequenten).
Voorstel van Bewijstheoretische Mechanismen: Het introduceren van specifieke bewijstheoretische concepten — polariteit, focussering, en met name de mobiliteit van binders via $\lambda$ -tree syntaxis en de $\nabla$ -kwantificator — als superieure mechanismen voor het afhandelen van syntactische bindingen en metatheoretisch redeneren.
Illustratie via Implementatie: Het gebruik van de Abella stellingbewijzer als een concrete realisatie van deze principes om te demonstreren hoe het theoretische kader in de praktijk functioneert.

Belangrijkste Bijdragen
Het artikel identificeert zes specifieke onderwerpen waar het bewijstheoretische perspectief duidelijke voordelen biedt ten opzichte van DTT:

Scheiding van Logica en Bewijsstructuur: In tegen tegenstelling tot DTT, dat vaak een specifieke logica koppelt aan een specifieke bewijsencoding (natuurlijke deductie als $\lambda$ -termen), staat de bewijstheorie meerdere bewijsstructuren (sequentencalculus, tableaux, etc.) toe voor dezelfde logica, wat diverse inferentiestrategieën (forward/backward chaining) faciliteert.
Vermijden van DTT-complexiteit: De bewijstheoretische benadering omzeilt complexe typering-disciplines die inherent zijn aan DTT, zoals het beheren van universumniveaus, het afhandelen van bewijs-onrelevantie en het omgaan met de redundantie van expliciete versus impliciete typering.
Afhandeling van Klassieke Logica: Terwijl DTT moeite heeft met het uniform representeren van klassieke logica (vaak vereist het axioma's zoals de uitgesloten derde), biedt de sequentencalculus (met name multiple-conclusion) een natuurlijk, uniform kader voor zowel klassieke als intuïtionistische logica, wat structuren zoals Herbrand-disjuncties en resolutie-refutaties ondersteunt.
Strategisch Gebruik van Non-determinisme: Het artikel betoogt dat bewijscontroleurs niet strikt deterministisch hoeven te zijn. Het toestaan van non-determinisme (bijv. via backtracking search) in de kernel maakt waardevolle afruilingen mogelijk tussen de grootte van bewijs-certificaten en de tijd die nodig is voor controle, een hulpbron die vaak genegeerd wordt in functionele, deterministische DTT-kernels.
Behandeling van Bindingen (Binder Mobiliteit): Dit wordt gepresenteerd als de meest significante bijdrage. Het artikel pleit voor het behandelen van binders niet als functieruimten (extensionele visie) maar als verplaatsbare abstracties over syntaxis (intensionele visie). Dit wordt bereikt door $\lambda$ -tree syntaxis, waarbij binders kunnen bewegen van term-niveau naar formule-niveau naar bewijs-niveau (eigenvariabelen) zonder ooit vrij te worden.
De $\nabla$ -Kwantificator: De introductie van de $\nabla$ -kwantificator (een nieuwe formule-niveau binder) maakt het mogelijk om generieke oordelen te specificeren en het afhandelen van lokale binding-signature te faciliteren. Deze is zelf-duaal en interageert natuurlijk met gelijkheid, wat een robuust mechanisme biedt voor het redeneren over syntaxis met bindingen.

Resultaten
Het artikel presenteert geen nieuwe experimentele benchmarks of empirische gegevens, maar is een theoretische synthese en een demonstratie van haalbaarheid via de Abella stellingbewijzer.

Capabilities van Abella: Er wordt aangetoond dat Abella succesvol gebruikmaakt van $\lambda$ -tree syntaxis en de $\nabla$ -kwantificator om te redeneren over de metatheorie van talen en logica's die complexe binding bevatten.
Specifieke Toepassingen: Het artikel citeert succesvolle specificaties binnen Abella, waaronder:
- Formuleringen van de $\lambda$ -kubus en hoger-gerangschikte polymorfe type-inferentie.
- Formalisaties van Barendregts theorie van de lambda-calculus.
- Operationele semantiek en metatheorie van de $\pi$ -calculus, inclusief het onderscheid tussen open en gesloten bisimulatie en het vastleggen van modale operatoren.
Theoretische Equivalentie: Het artikel demonstreert dat de formule $\forall w. \lambda x.x \neq \lambda x.w$ bewijsbaar is in dit kader omdat het hogere-orde unificatieprobleem $(\lambda x.x = \lambda x.w)$ geen unifiers heeft, wat de kracht van de intentionele visie op binders illustreert.

Significantie
Het artikel beweert dat de moderne structurele bewijstheorie een "robuust en overtuigend fundamenteel alternatief" biedt voor het ontwerp van interactieve stellingbewijzers ten opzichte van het DTT-paradigma. De significantie ligt in:

Herformulering van het Ontwerpnarratief: Het daagt de aanname uit dat afhankelijk getypeerde $\lambda$ -calculus de enige of beste manier is om bewijzen te representeren, en suggereert dat de sequentencalculus een flexibeler en natuurlijker kader biedt, met name voor metatheoretisch redeneren.
Oplossen van Binding-problemen: Het stelt voor dat de benadering van "mobiliteit van binders" langlopende uitdagingen bij het coderen van syntactische bindingen (verwezen als de POPLMark-uitdaging) oplost, door een canonieke behandeling te bieden die de noodzaak voor complexe encodings zoals de Bruijn-indices of benoemde variabelen in de logische specificatie van de gebruiker vermijdt.
Fundamentele Helderheid: Door logica te scheiden van bewijsstructuur en non-determinisme te omarmen, maakt de benadering directere en elegantere specificaties van complexe systemen mogelijk, zoals blijkt uit de capaciteiten van de Abella-bewijzer.

De auteur concludeert dat hoewel DTT volwassen implementaties en brede adoptie heeft, het bewijstheoretische perspectief een dieper en flexibeler ontwerpondergaan biedt, met name voor systemen die een geavanceerd redeneren over binding en metatheorie vereisen.