💻 computer science

Compositional Program Verification with Polynomial Functors in Dependent Type Theory

Dit artikel presenteert een in Agda geformaliseerd raamwerk voor compositievere programmacorrectheid in afhankelijke type-theorie, dat polynoomfunctoren gebruikt als interfaces en pre/postcondities, en dat de onderliggende categorische structuur voor compositie via wiring diagrams en Mealy-machines belicht.

Oorspronkelijke auteurs: C. B. Aberlé

Gepubliceerd 2026-04-03

📖 5 min leestijd🧠 Diepgaand

CC BY 4.0

Oorspronkelijke auteurs: C. B. Aberlé

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 een enorme, ingewikkelde machine bouwt, zoals een robot die een stad kan schoonmaken. De machine is zo groot en complex dat niemand meer weet hoe hij precies werkt van binnen. Het is een "zwarte doos".

Deze paper van C.B. Aberlé komt met een slimme manier om zulke grote systemen te bouwen, te testen en te begrijpen, zonder dat je de hele machine tegelijk hoeft te doorgronden. Het idee is: bouw het in losse blokken, test elk blokje apart, en koppel ze dan samen.

Hier is hoe dat werkt, vertaald naar alledaagse taal:

1. De Bouwblokken: "De Interface"

Stel je voor dat elke functie in je software een bestek heeft.

De Invoer (Positie): Wat moet je erin gooien? (Bijvoorbeeld: een stuk vuil).
De Uitvoer (Richting): Wat krijg je eruit? (Bijvoorbeeld: een schoon stuk).

In de paper noemen ze dit een polynoomfunctor. Klinkt ingewikkeld, maar het is gewoon een manier om te zeggen: "Als je dit invoert, krijg je dat terug." Dit is het interface van je blokje.

2. De Bouwplaat: "De Bedrading"

Hoe bouw je nu die grote robot? Je neemt losse blokken (zoals een 'veeg-arm' of een 'waterstraal') en je koppelt ze aan elkaar.

De uitgang van blok A gaat naar de ingang van blok B.
Soms heb je een blok dat twee dingen tegelijk moet doen, of een blok dat niets hoeft te doen (een lege doos).

De auteurs gebruiken bedradingsschema's (wiring diagrams). Denk aan een elektrisch schema of een LEGO-instructieboekje. Je ziet precies welk blokje waar zit en hoe de draden (de data) lopen. Het mooie is: als je weet dat blok A werkt en blok B werkt, en je weet hoe ze aan elkaar hangen, dan weet je automatisch dat het hele systeem werkt. Je hoeft niet alles opnieuw te testen.

3. De Regels: "De Waarborg"

Elk blokje heeft niet alleen een interface (wat het doet), maar ook een contract (hoe het het doet).

Pre-conditie (Voorwaarde): "Ik werk alleen als het vuil niet te nat is."
Post-conditie (Garantie): "Als het vuil niet te nat is, garandeer ik dat het stuk schoon is."

In de paper noemen ze dit afhankelijke polynomen. Het is een slimme manier om regels te schrijven die meedraaien met de data. Als je een blokje gebruikt, moet je bewijzen dat je aan de voorwaarden voldoet, en dan mag je vertrouwen op de garantie.

4. De Test: "De Simulator"

Hoe weet je of je blokjes echt werken? Je bouwt een Mealy-machine.
Stel je voor dat dit een simulator of een robot-acteur is.

Je geeft de simulator een input (bijv. "veeg").
De simulator voert de actie uit, verandert zijn interne staat (bijv. "blik is nu vol") en geeft een output.

Het geniale aan dit systeem is dat je de simulator kunt koppelen aan je code. Als je een nieuw blokje toevoegt, hoeft de simulator alleen maar te kijken naar de nieuwe bedrading. Hij "draait" je programma letterlijk, stap voor stap, en houdt de staat bij.

5. De Grote Droom: "Samenstellen zonder Chaos"

Het grootste probleem bij grote software is dat als je één ding aanpast, ergens anders iets kapot gaat.
De paper lost dit op door te zeggen:

Bouw je programma als een netwerk van blokken (interfaces).
Schrijf voor elk blokje een contract (voor- en na-voorwaarden).
Bewijs dat elk blokje zijn contract nakomt.
Koppel ze samen via de bedrading.

Het resultaat? Als je elk blokje apart hebt bewezen dat het werkt, en je hebt bewezen dat de bedrading klopt, dan is het hele systeem bewezen dat het werkt. Je hoeft niet naar de hele machine te kijken, alleen naar de losse onderdelen en de draden ertussen.

Een concreet voorbeeld: De "Stapel"

Stel je wilt een stapel borden maken.

Blok 1: Pakt een bord.
Blok 2: Legt het bord op een andere stapel.
Blok 3: Herhaalt dit voor een hele lading borden.

In plaats van te proberen te bewijzen dat de hele stapel correct is, bewijs je:

"Blok 2 legt een bord correct op een stapel."
"Blok 1 pakt een bord correct."
"Als je Blok 1 en 2 herhaalt (Blok 3), dan blijft de stapel netjes."

Door deze kleine bewijzen te stapelen (composeren), krijg je een bewijs voor de hele lading borden.

Waarom is dit belangrijk?

Vandaag de dag zijn computersystemen vaak "onzichtbaar" (zwarte dozen). We vertrouwen op AI-modellen en API's die we niet begrijpen. Deze methode geeft ons een manier om die systemen op te bouwen als LEGO. We kunnen zeggen: "Dit stukje is veilig, dat stukje is veilig, en de manier waarop ze aan elkaar hangen is veilig." Daardoor kunnen we grote, complexe systemen bouwen met een gerust hart, wetende dat ze veilig en correct werken.

Kortom: Bouw in blokken, test de regels, koppel de draden, en het geheel is gegarandeerd goed.

Titel: Compositional Program Verification with Polynomial Functors in Dependent Type Theory

Auteur: C.B. Aberlé (Carnegie Mellon University)
Context: ACT 2026, volledig geformaliseerd in Agda.

1. Het Probleem

Grote softwaresystemen zijn vaak ondoorzichtig ("opaque"). Het is moeilijk om het gedrag van complexe programma's te verifiëren omdat deze systemen uit vele onderdelen bestaan die sterk met elkaar verbonden zijn. De traditionele aanpak van het verifiëren van het hele systeem als één blok is vaak onhaalbaar. Er is behoefte aan een methode om systemen te ontleden in eenvoudigere componenten, deze onafhankelijk te verifiëren, en de resultaten vervolgens correct te combineren (compositional verification). De uitdaging ligt in het vinden van een raamwerk dat zowel de interfaces, de implementaties, de specificaties (voor- en nacomposties) als de operationele semantiek op een uniforme en samenstellende manier behandelt.

2. Methodologie

Het paper introduceert een raamwerk gebaseerd op polynomiale functors binnen afhankelijke type-theorie (dependent type theory). De kernideeën zijn:

Polynomiale Functors als Interfaces: Een polynomiale functor $P(y) = \sum_{a:A} y^{B(a)}$ wordt gebruikt om de interface van een afhankelijke functie $(a:A) \to B(a)$ te modelleren. Hierbij is $A$ het type van posities (inputs) en $B(a)$ het type van richtingen (outputs).
Implementaties als Kleisli-morfismen: Een implementatie van een interface $p$ die afhankelijk is van een interface $q$ , wordt voorgesteld als een morfisme $p \Rightarrow \text{Free}_q$ , waarbij $\text{Free}_q$ de vrije monad op $q$ is. Dit stelt programma's voor die $q$ kunnen aanroepen (0, 1 of meerdere keren) in een sequentiële structuur.
Specificaties als Afhankelijke Polynomen: Specificaties worden gecodeerd als afhankelijke polynomen (dependent polynomials). Een specificatie over een interface $p=(A,B)$ $p = (A, B)$ bestaat uit:
- Een familie van precondities $C: A \to \text{Set}$ .
- Een familie van postcondities $D: (a:A) \to C(a) \to B(a) \to \text{Set}$ .
  Dit fungeert als een polynomiaal equivalent van een Hoare-triplet.
Compositionaliteit via Bedradingsdiagrammen (Wiring Diagrams): Modules worden samengesteld via bedradingsdiagrammen. Deze diagrammen modelleren de afhankelijkheidsstructuur tussen modules. De compositie van implementaties en verificaties volgt strikt de structuur van deze diagrammen.
Operationele Semantiek via Mealy-machines: Om programma's daadwerkelijk uit te voeren, worden Mealy-machines gebruikt als een coalgebraïsche operationele semantiek. Een Mealy-machine met interface $p$ is een toestandsautomaat die, gegeven een input, een output produceert en de staat update.
Verificatie van Semantiek: Er wordt een "afhankelijke Mealy-machine" gedefinieerd die bewijst dat een Mealy-machine voldoet aan een gegeven specificatie.

3. Belangrijkste Bijdragen

Unificatie van Interfaces, Implementaties en Specificaties:
Het paper toont aan dat polynomiale functors een natuurlijke taal bieden om zowel de structuur van modules (interfaces) als hun gedrag (implementaties) en hun correctheid (specificaties) te modelleren.
Compositionaliteit van Verificatie:
De centrale stelling is dat verificaties samenstellen op exact dezelfde manier als implementaties. Als module $A$ correct is geverifieerd ten opzichte van zijn specificatie, en module $B$ (die $A$ gebruikt) is correct geverifieerd, dan is de samengestelde module $A \circ B$ automatisch correct. Dit wordt bewezen via de compositie van afhankelijke vrije monaden en het gebruik van bedradingsdiagrammen.
Coalgebraïsche Semantiek en Effecten:
Het paper introduceert een manier om stateful berekeningen (effecten) te modelleren via Mealy-machines. Een Mealy-machine fungeert als een "runner" voor effecten. Dit maakt het mogelijk om stateful programma's (zoals een Fibonacci-generator met interne staat) te verifiëren binnen hetzelfde raamwerk.
Abstract Categorisch Raamwerk:
De auteurs identificeren de onderliggende categorische structuur als een monoidale functor van specificaties naar interfaces, gekoppeld aan een monoidale natuurlijke transformatie tussen lax monoidale presheaves. Dit abstracte niveau maakt het mogelijk om het raamwerk uit te breiden naar andere categorieën en monoidale producten.
Formalisatie in Agda:
Het gehele raamwerk, inclusief de theorie, de voorbeelden (zoals fold, append, concat en Fibonacci) en de bewijzen, is volledig geformaliseerd in het Agda bewijshulpmiddel. Dit garandeert de wiskundige correctheid van de voorgestelde theorie.

4. Resultaten en Voorbeelden

Fold, Append en Concat: Het paper demonstreert het raamwerk aan de hand van lijstoperaties. Een generieke fold-module wordt gedefinieerd die afhankelijk is van een base- en een step-interface. Door specifieke implementaties voor append en concat te leveren, worden deze modules samengesteld. De verificatie toont aan dat append correct werkt door inductie (via de fold-structuur) te combineren met de verificaties van de basis- en stapgevallen.
Fibonacci met State: Een Fibonacci-machine wordt geïmplementeerd die gebruikmaakt van een State-effect. Het paper verifieert niet alleen dat de output de Fibonacci-rij is, maar ook dat de interne staat een invariant behoudt (dat de staat altijd twee opeenvolgende Fibonacci-getallen bevat).
Parallelle Compositionaliteit (Appendix A): Het paper schetst een uitbreiding voor concurrerende modules door de coproduct $\oplus$ te vervangen door een parallelle som $\parallel$ . Dit stelt het raamwerk in staat om race-conditions te voorkomen en relationele specificaties (zoals non-interferentie) te verifiëren.

5. Betekenis en Toekomstperspectief

De betekenis van dit werk ligt in het bieden van een rigoureuze, compositionalle basis voor het verifiëren van complexe softwaresystemen.

Automatisering: Omdat het raamwerk volledig compositional is, is het zeer geschikt voor automatisering. Bewijsassistenten (zoals Agda, Lean, Coq) kunnen lokale verificaties van modules automatisch combineren tot een globaal bewijs, wat de last voor de gebruiker vermindert.
Toepasbaarheid op Moderne Systemen: In een wereld waar systemen steeds vaker worden opgebouwd uit "ondoorzichtige" componenten (zoals API-calls en ML-modellen), biedt dit raamwerk een manier om veiligheid en correctheid op interface-niveau te garanderen zonder de interne werking van die componenten volledig te hoeven kennen.
Generalisatie: De abstracte categorische formulering opent de deur voor generalisaties naar andere domeinen, zoals concurrentie, relationele verificatie en informatieflow-beveiliging.

Kortom, dit paper levert een fundamentele bijdrage aan de theoretische informatica door een brug te slaan tussen polynomiale functors, afhankelijke type-theorie en operationele semantiek, met als doel het verifiëren van software op een schaalbare en wiskundig onderbouwde manier.