💻 computer science

Building Extensible Program Logics through Effect Handlers

Dit artikel stelt een aanpak voor voor het bouwen van uitbreidbare programmalogica's door effect handlers te implementeren binnen een basislogica om complexe gedragingen zoals concurrency en crash recovery te modelleren, waardoor de afleiding van expressieve redeneerregels en relationele verfijningen op een modulaire en herbruikbare wijze mogelijk wordt gemaakt.

Oorspronkelijke auteurs: Zichen Zhang, Simon Oddershede Gregersen, Joseph Tassarotti

Gepubliceerd 2026-07-15

📖 6 min leestijd🧠 Diepgaand

CC BY 4.0

Oorspronkelijke auteurs: Zichen Zhang, Simon Oddershede Gregersen, Joseph Tassarotti

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 superveilig fort probeert te bouwen om een digitaal kasteel te beschermen. In de wereld van de informatica worden deze fortressen programmalogica's genoemd. Dit zijn sets strikte regels die wiskundigen en programmeurs gebruiken om te bewijzen dat een stuk software nooit zal crashen, geheimen zal lekken of vreemd gedrag zal vertonen.

Lange tijd was het bouwen van deze fortressen alsof je elke steen met de hand uithakte. Als je een nieuwe functie wilde toevoegen—zoals een manier voor de software om met een stroomuitval om te gaan (crashherstel) of om te communiceren met andere computers aan de andere kant van de oceaan (gedistribueerde systemen)—moest je helemaal opnieuw beginnen. Je had een speciaal soort "steenhouder"-vaardigheid nodig die totaal anders was dan de vaardigheid die nodig was om het fort simpelweg te gebruiken. Het was moeilijk, traag, en je kon de stenen van een oud fort niet gemakkelijk hergebruiken om een nieuw fort te bouwen.

Het Grote Idee: De "Effect Handler" Gereedschapskist

Dit artikel, geschreven door Zichen Zhang, Simon Oddershede Gregersen en Joseph Tassarotti, stelt een nieuwe manier voor om deze fortressen te bouwen. In plaats van stenen met de hand uit te hakken, gebruiken ze een magisch hulpmiddel genaamd effect handlers.

Denk aan een effect handler als een aanpasbaar regelboek voor een spel. In een standaard videogame zijn de regels voor springen of schieten hardgecodeerd in de engine. Maar met effect handlers zegt de game-engine: "Ik weet nog niet wat 'springen' betekent; ik wacht gewoon tot iemand mij vertelt wat het is." Vervolgens kan een programmeur een klein script (een handler) schrijven dat zegt: "Oké, wanneer de speler probeert te springen, laat ik hem een seconde zweven."

De auteurs bouwden een piepkleine, lege taal genaamd FicusLang die geen enkele regel heeft, behalve dit "wacht op instructies"-kenmerk. Daarna schreven ze handlers om de regels te creëren voor zaken als:

Geheugen: Hoe het programma dingen onthoudt (zoals een briefje).
Concurrent Threads: Hoe het programma veel dingen tegelijk doet (zoals een chef die meerdere pannen jongleert).
Crashes: Wat er gebeurt als de stroom uitvalt en weer terugkomt.
Gedistribueerde Systemen: Hoe computers met elkaar praten over een wankele netwerkverbinding.

De Magische Truc: Opbouwen

Het coolste deel is dat ze deze regels niet alleen hebben gemaakt; ze hebben ze ook bewezen. Ze begonnen met de lege taal, schreven een handler voor "geheugen", en gebruikten een logicasysteem genoemd Ficus om te bewijzen dat hun geheugenhandler correct werkt. Zodra dat bewezen was, konden ze die "geheugen"-handler gebruiken om een "concurrency"-handler te bouwen.

Het is als het bouwen van een huis. Eerst bewijs je dat je fundering stevig is. Dan gebruik je die stevige fundering om de eerste verdieping te bouwen. Zodra die eerste verdieping bewezen veilig is, gebruik je die om de tweede verdieping te bouwen. Omdat ze het op deze manier hebben gebouwd, konden ze functies gemakkelijk mengen en combineren. Als je een huis wilde met zowel een zwembad als een garage, kon je de "zwembad-handler" en de "garage-handler" combineren zonder de hele fundering opnieuw te hoeven bouwen.

Sterkere Regels en Nieuwe Trucs

Omdat ze deze regels vanaf de grond opbouwden met behulp van handlers, ontdekten ze dat ze sterkere regels konden maken dan eerdere methoden.

De "Pauze"-truc: In standaard concurrente programmering kan de computer een taak op elk klein moment stoppen om over te schakelen naar een andere taak. Dit creëert een enorme chaos aan mogelijkheden die moeilijk te volgen is. De handler van de auteurs schakelt alleen tussen taken wanneer een specifieke "effect" optreedt (zoals een verzoek om een bestand te lezen). Dit vermindert de chaos. Ze bewezen dat deze "pauzeer alleen wanneer gevraagd"-methode net zo veilig is als de "pauzeer op elk moment"-methode, maar veel gemakkelijker te redeneren is.
De "Kristallen Bol" (Prophecy Variables): Soms, om te bewijzen dat een programma veilig is, moet je weten wat een willekeurige gebeurtenis zal doen voordat het gebeurt. De auteurs creëerden een "kristallen bol"-effect handler. Het stelt de bewijsvoering in staat om te zeggen: "Ik voorspel dat dit willekeurige getal een 5 zal zijn," en controleert later of dat klopte. Ze lieten zien dat je lokale kristallen bollen (voor een specifieke variabele) kunt bouwen uit een grote globale een, en zelfs dat ze automatisch kunnen verschijnen voor geheugenoperaties zonder dat de programmeur extra code hoeft te schrijven.

De "Relationele" Logica: De Tweelingtest

Het artikel introduceert ook een nieuw hulpmiddel genaamd RelFicus. Stel je voor dat je twee identieke tweelingen hebt, Programma A en Programma B. Je wilt bewijzen dat als je ze dezelfde input geeft, ze zich altijd op dezelfde manier zullen gedragen, zelfs als de een een iets andere versie van de ander is.

RelFicus is een logica waarmee je deze twee programma's zij aan zij in je hoofd kunt draaien (met behulp van "ghost state" of denkbeeldige bronnen) om te bewijzen dat ze tweelingen zijn. Dit is cruciaal om te bewijzen dat hun nieuwe "pauzeer-alleen-wanneer-gevraagd" concurrency-handler daadwerkelijk veilig is. Ze gebruikten deze tweelingtest om te bewijzen dat het toevoegen van extra "pauzepunten" (preemption) de uitkomst van het programma niet zou veranderen, wat hun eenvoudigere, gemakkelijker te gebruiken model rechtvaardigt.

Wat Ze Niet Hebben Gedaan (en Wat Ze Hebben Afgewezen)

Het is belangrijk om te weten wat dit artikel niet is.

Ze zeggen niet dat de oude manier van het bouwen van logica's (de "handgehakte steen"-methode) nutteloos is. Ze zeggen alleen dat het moeilijk is om te hergebruiken en moeilijk om op voort te bouwen.
Ze wijzen het idee af dat je complexe, abstracte wiskundige structuren (zoals de in eerder werk genoemde "ITrees") moet begrijpen om deze logica's te bouwen. Ze beargumenteren dat hun aanpak toegankelijker is omdat het standaard programmeerconcepten gebruikt (handlers) die al bekend zijn bij ontwikkelaars.
Ze beweren niet dat ze elk probleem in de computerbeveiliging hebben opgelost. Ze hebben specifelijk handlers gebouwd voor geheugen, concurrency, crashes en gedistribueerde systemen, maar ze erkennen dat andere functies nieuwe handlers kunnen vereisen.

Hoe Zeker Zijn Ze?

De auteurs zijn zeer zelfverzekerd, maar ook precies. Ze hebben niet alleen "gesuggereerd" dat dit zou kunnen werken; ze hebben het bewezen.

Ze hebben het volledige logicasysteem geschreven in een tool genaamd Rocq Prover (een computerprogramma dat wiskundige bewijzen controleert).
Ze hebben een stelling bewezen genaamd Adequacy, die garandeert dat als hun logica zegt dat een programma veilig is, het programma ook daadwerkelijk zal draaien zonder vast te lopen.
Ze hebben bewezen dat hun nieuwe concurrency-model gelijkwaardig is aan de standaard, complexere modellen.
Ze hebben aangetoond dat hun "kristallen bol" (prophecy) functies werken door ze af te leiden uit een globale versie, waarbij ze bewezen dat de wiskunde standhoudt.

De Kernboodschap

Dit artikel is alsof je computerwetenschappers een set Lego-blokjes geeft in plaats van een hoop natte klei. Voorheen, als je een nieuw type kasteel wilde bouwen, moest je de klei zelf mengen. Nu heb je vooraf gemaakte, geteste blokken voor "geheugen", "crashes" en "netwerken". Je kunt ze aan elkaar klikken, en de wiskunde garandeert dat het kasteel niet instort. Het maakt het bouwen van complexe, veilige software minder een solo kunstproject en meer een gezamenlijke bouwplaats waar iedereen de beste onderdelen kan hergebruiken.

Technische Samenvatting: Het bouwen van uitbreidbare programmalogica's via effect handlers

Probleemstelling

Programmalogica's zijn krachtige instrumenten voor het verifiëren van complexe programmeerfuncties zoals concurrency (gelijktijdigheid), weak memory (zwak geheugen), gedistribueerde uitvoering en crash recovery (herstel na een crash). De traditionele aanpak voor het ontwikkelen van deze logica's staat echter een aanzienlijke barrière op de weg:

Toegankelijkheid: Het ontwikkelen van een nieuwe programmalogica vereist gespecialiseerde vaardigheden die verschillen van de vaardigheden die nodig zijn om een logica te gebruiken, wat het creëren van nieuwe logica's uitdagend maakt.
Herbruikbaarheid en Compositie: Het is moeilijk om componenten van bestaande logica's te hergebruiken of om ondersteuning voor verschillende effecten te combineren (bijvoorbeeld het combineren van concurrency met crash recovery).
Operationele Semantiek: Recente alternatieve benaderingen (bijvoorbeeld het gebruik van ITrees) lossen de herbruikbaarheid op, maar vertrouwen op denotatieve semantiek die niet direct een operationeel begrip van programmeergedrag oplevert, wat vragen oproept over de uitvoerbaarheid op realistische machines.

Bestaande logica's voor effect handlers gaan er vaak van uit dat een basisprogrammeer-taal met primitieve effecten (zoals mutable state of concurrency) al ingebouwd is. Dit compliceert de bewijsvoering van de juistheid (soundness) doordat de complexiteit van primitieve effecten wordt vermengd met de handler-logica, in plaats van handlers te gebruiken als het primaire mechanisme om effecten te bootstrappen.

Methodologie

De auteurs stellen een aanpak voor om operationeel uitbreidbare programmalogica's te bouwen door effect handlers te gebruiken om alle programmeereffecten te modelleren, beginnend bij een minimale, staatloze kern-taal genaamd FicusLang.

Kerncomponenten

FicusLang: Een minimale ML-stijl lambda-calculus met effect handlers. Het bevat twee primitieve effecten: pick (niet-deterministische boolean) en observe (gelabelde transities voor ghost code). De auteurs merken op dat zelfs deze primitieven uiteindelijk kunnen worden gecodeerd met behulp van handlers.
Ficus (Unary Logic): Een uitbreidbare separation logic gebaseerd op het Iris-framework, aangepast van de Hazel-logica.
- Protocols: Ficus gebruikt protocollen ( $\Psi$ ) om het gedrag van effect handlers te specificeren. Een weakest precondition assertie ewp e <Ψ> {Φ} stelt dat als e wordt uitgevoerd onder handlers die voldoen aan $\Psi$ , het niet vast komt te zitten en zal voldoen aan de postconditie $\Phi$ .
- Extensible Worlds: Om concurrency en coördinatie te ondersteunen, introduceert Ficus "extensible worlds". In tegenstelling tot standaard Iris, waar invarianten vaststaan, parametriseert Ficus de ewp en de fancy update modalities met aanpasbare werelden ( $W$ ). Dit stelt implementeerders van handlers in staat om hun eigen begrippen van invarianten en atomiciteit te definiëren die geschikt zijn voor het specifieke effect dat wordt gemodelleerd.
- Handler Implementatie: De auteurs implementeren handlers voor mutable state, shared-memory concurrency, gedistribueerde uitvoering en crash recovery binnen FicusLang. Door deze handlers te verifiëren met behulp van Ficus, leiden zij bewijsregels af die analoog zijn aan gespecialiseerde logica's voor deze functies.
RelFicus (Relational Logic): Een relationele logica voor het bewijzen van contextuele verfijningen tussen programma's met behulp van effecten.
- Het embedt relationele redenering in de unaire logica door een tweede "specificatie"-programma als ghost state te coderen.
- Het maakt gebruik van dezelfde extensible worlds en protocollen als Ficus, wat compositionele redenering mogelijk maakt over de relationele eigenschappen van effectful programma's.

Belangrijkste Bijdragen

Het artikel levert de volgende specifieke bijdragen:

Ficus: De ontwikkeling van een uitbreidbare unaire programmalogica gebaseerd op effect handlers. Het gebruikt protocollen om de redenering over handlers en client-code te ontleden en introduceert extensible worlds om resources te delen tussen client-code.
RelFicus: Een relationele logica voor het bewijzen van contextuele verfijningen in de aanwezigheid van effect handlers, waarbij Ficus-protocollen worden aangepast naar de relationele setting om hergebruik en uitbreidbaarheid mogelijk te maken.
Case Studies: De auteurs demonstreren de aanpak door functies uit bestaande logica's te reconstrueren en uit te breiden:
- Prophecy Variables: Het afleiden van lokale prophecy variabelen uit globale prophecies en het implementeren van een "prophetic heap" die impliciet prophecy variabelen associeert met heap locaties, waardoor expliciete client-instrumentatie overbodig wordt.
- Crash Recovery: Een logica voor crash-recovery met asynchrone duurzame opslag die kenmerken van de Perennial-logica herstelt, maar met een eenvoudiger model en nieuwe ondersteuning voor crash-bewuste prophecy variabelen.
- Gedistribueerde Systemen: Een logica voor gedistribueerde systemen met IronFleet-stijl atomic blocks.
Sterkere Bewijsregels: De handler-gebaseerde aanpak levert sterkere redeneerregels op dan eerder werk op twee manieren:
1. Hiërarchische Effecten: Latere effecten kunnen worden gebouwd met behulp van eerdere effecten (bijv. het afleiden van lokale prophecies uit globale), waardoor de bewijsregels kunnen worden hergebruikt.
2. Niet-standaard Semantiek: Handlers kunnen niet-standaard versies van effecten implementeren die gemakkelijker te redeneren zijn (bijv. een concurrency handler die minder interleavings genereert dan standaard preemptive semantiek). De auteurs rechtvaardigen dit via RelFicus, door te bewijzen dat ze contextueel equivalent zijn aan standaard semantiek.
Ergonomie: Ficus bevat een flexibel tactieken-systeem waardoor specificaties kunnen worden toegepast, zelfs met verschillende protocollen, wat een bewijservaring biedt die vergelijkbaar is met standaard Iris-gebaseerde logica's.

Resultaten en Validatie

Mechanisatie: Het gehele werk is gemecaniseerd in het Iris separation logic framework en de Rocq Prover.
Adequacy Theorems: De auteurs bewijzen adequatheidstheorema's voor zowel Ficus als RelFicus, wat garandeert dat de logische afleidingen overeenkomen met de operationele semantiek van de taal.
Contextuele Equivalentie: Met behulp van RelFicus bewijzen de auteurs dat hun concurrency handler, die alleen preemption triggert wanneer een effect wordt opgeroepen, contextueel equivalent is aan een standaard preemptive semantiek waarbij preemption op elke stap kan voorkomen. Dit rechtvaardigt het gebruik van hun "zwakkere" interleaving model voor sterkere invariant-opening regels.
Impliciete Prophecies: De "prophetic heap" case study demonstreert dat heap operaties automatisch kunnen worden uitgebreid met prophecy capaciteiten zonder dat het client-programma handmatig moet worden geannoteerd met prophecy operaties.

Betekenis

Het artikel stelt dat deze aanpak de ontwikkeling van programmalogica's toegankelijker en modulaireer maakt. Door effect handlers te gebruiken als het primaire mechanisme om logica's te bootstrappen, kunnen ontwikkelaars:

Logica's Componeren: Ondersteuning voor verschillende effecten combineren (bijv. concurrency + crash recovery) door handlers te nesten, in plaats van monolithische logica's vanaf nul op te bouwen.
Sterkere Regels Afleiden: Profiteren van de mogelijkheid om niet-standaard, handler-specifieke semantiek te definiëren die gemakkelijker te redeneren is, mits deze via relationele logica als equivalent aan standaard semantiek worden bewezen.
Operationele Helderheid: Een operationeel begrip van programmeergedrag behouden, waardoor de resulterende logica's geworteld blijven in uitvoerbare semantiek.

Dit werk overbrugt de kloof tussen het toegankelijk maken van het gebruiken van programmalogica's en de complexiteit van het ontwikkelen ervan, door een framework te bieden waar nieuwe logica's voor complexe systemen stapsgewijs en compositioneel gebouwd kunnen worden.