💻 computer science

Automated Reasoning with Nested Datatypes

Dit artikel introduceert een theorie van geneste datatypen die de combinatie van datatypen en arrays beperkt om niet-standaardmodellen te voorkomen, biedt een bewezen correcte beslissingsprocedure hiervoor, en evalueert een implementatie van deze procedure op real-world en handgemaakte benchmarks.

Oorspronkelijke auteurs: Tomer Hakak, Yoni Zohar, Andrew Reynolds, Clark Barrett, Cesare Tinelli

Gepubliceerd 2026-07-01

📖 5 min leestijd🧠 Diepgaand

CC BY 4.0

Oorspronkelijke auteurs: Tomer Hakak, Yoni Zohar, Andrew Reynolds, Clark Barrett, Cesare Tinelli

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 complexe digitale stad bouwt met twee verschillende soorten Lego-blokjes: Datatypen en Arrays.

Datatypen zijn als stambomen of organigrammen. Ze zijn hiërarchisch. Een "Persoon" kan een "Kind" hebben, en dat Kind kan weer een eigen "Kind" hebben. De regel hier is simpel: Niemand kan zijn eigen voorouder zijn. Je kunt geen stamboom hebben waarbij een persoon zijn eigen grootouder is; dat creëert een logische lus (een cyclus) die de structuur verbreekt.
Arrays zijn als brievenbussen of lockers. Ze zijn plat en maken het mogelijk om direct elk item op te pakken aan de hand van het nummer (index). Je kunt alles in een brievenbus stoppen, inclusief een hele stamboom.

Het Probleem: De "Oneindige Lus" Valstrik

Het paper wijst eerst op een gevaarlijke glitch die optreedt wanneer je deze twee systemen naïef combineert.

Stel je voor dat je een Persoon (een datatype) hebt die een veld heeft genaamd "Familie". In een normale wereld is "Familie" een lijst met mensen. Maar in deze glitchy wereld is "Familie" een Array (een locker).

Je plaatst een specifieke Persoon (laten we hem Bob noemen) in Locker #5.
Vervolgens definieer je het "Familie"-veld van Bob als Locker #5.

Kijk nu wat er gebeurt:

Om de familie van Bob te vinden, open je Locker #5.
Binnenin Locker #5 vind je Bob.
Om de familie van Bob te vinden, open je Locker #5 opnieuw.
Je vindt Bob opnieuw.

Je zit vast in een oneindige lus. In de informatica wordt dit een niet-standaard model genoemd. Het is als een slang die zijn eigen staart opeet. Hoewel een computer dit technisch gezien zou kunnen toestaan, doorbreekt het de intuïtieve regels van hoe datastructuren zouden moeten werken. Het creëert een "cyclus" die er niet zou mogen zijn.

De Oplossing: De "Nested Datatype" Theorie

De auteurs, Tomer Hakak en zijn team, zeggen: "We hebben een regelboek nodig dat dit scenario van de slang die zijn eigen staart opeet voorkomt."

Ze introduceren een nieuwe theorie genaamd Nested Datatypes. Denk hierbij aan een strikte bouwcode voor je digitale stad.

De Regel: Je kunt een stamboom in een locker plaatsen, en je kunt een locker in een stamboom plaatsen, MAAR je mag geen pad creëren dat je terugleidt naar waar je begon.
Het Doel: Als je een pad volgt van een persoon, via hun familie-array, naar een andere persoon, en terug via diens familie-array, mag je nooit weer bij de oorspronkelijke persoon uitkomen.

Hoe ze het hebben opgelost: De "Translator" Machine

Het moeilijke deel is dat computers erg goed zijn in het controleren of een stamboom geldig is, en ook erg goed in het controleren of lockers geldig zijn. Maar ze zijn slecht in het controleren of een combinatie van de twee een lus creëert.

De auteurs hebben een Translator (een beslissingsprocedure) gebouwd. Zo werkt het, met behulp van een metafoor:

Stel je voor dat je een puzzel hebt met twee verschillende soorten stukjes: Boomstukjes en Boxstukjes. De computer weet niet hoe hij moet controleren op lussen wanneer deze gemengd zijn.

De Vertaling: Het algoritme van de auteurs neemt de gemengde puzzel en vertaalt deze naar een taal die de computer wel begrijpt. Het verandert de "Boxstukjes" in speciale "Boomstukjes" die op boxen lijken maar zich gedragen als bomen.
Het Veiligheidsnet: Ze voegen extra "vangrails" (lemmas) toe aan de vertaling. Deze vangrails zorgen ervoor dat als er een lus zou bestaan in de oorspronkelijke gemengde puzzel, de vertaalde boomversie onmiddellijk een tegenstrijdigheid zal tonen (zoals het proberen te bous een toren die de zwaartekracht tart).
De Controle: De computer controleert de vertaalde puzzel.
- Als de vertaalde puzzel onmogelijk is (onvervulbaar), dan betekende dit dat de oorspronkelijke gemengde puzzel een verboden lus bevatte.
- Als de vertaalde puzzel werkt, is de oorspronkelijke puzzel veilig.

Waarom dit ertoe doet (volgens het paper)

De auteurs hebben niet alleen een theorie geschreven; ze hebben een prototype gebouwd binnen een echt computerprogramma genaamd cvc5 (een tool die wordt gebruikt om software te verifiëren).

Real-World Test: Ze hebben het getest op benchmarks van de Move Prover, een tool die wordt gebruikt om smart contracts (digitale geldovereenkomsten) te verifiëren. Deze contracten maken vaak gebruik van complexe geneste data.
Synthetische Test: Ze hebben nep-puzzels gemaakt die specifiek ontworpen zijn om andere solvers in oneindige lussen te lokken.
Het Resultaat: Hun nieuwe methode heeft succesvol de lussen opgevangen die andere methoden misten. In veel gevallen was het sneller en nauwkeuriger dan de bestaande tool (Z3) die voor soortgelijke taken wordt gebruikt.

Samenvatting

Kortom, dit paper gaat over het oplossen van een bug in hoe computers complexe data begrijpen.

De Bug: Het mengen van "stambomen" en "brievenbussen" kan per ongeluk oneindige lussen creëren waarbij een persoon zijn eigen voorouder is.
De Fix: Een nieuwe set regels (Theory of Nested Datatypes) die deze lussen strikt verbiedt.
De Tool: Een vertaler die deze complexe gemengde regels omzet in een formaat dat computers gemakkelijk kunnen controleren op veiligheid, zodat je digitale datastructuren logisch en vrij van lussen blijven.

Technische Samenvatting: Geautomatiseerd Redeneren met Geneste Datatypen

1. Probleemstelling

De SMT-LIB-theorie van datatypen biedt een handige codering voor datastructuren zoals lijsten en bomen, wat essentieel is voor softwareverificatie. De expressiviteit hiervan wordt echter beperkt door het gebrek aan update-operatoren en random-access mogelijkheden. Om dit aan te pakken, wordt vaak een naïeve combinatie van datatypen met de theorie van arrays geprobeerd.

Het kernprobleem dat in dit werk wordt geïdentificeerd, is dat een dergelijke naïeve combinatie niet-standaard modellen introduceert. Specifiek wordt het principe van acycliciteit — dat bepaalt dat een datatype-waarde zichzelf niet kan bevatten — omzeild wanneer arrays betrokken zijn. Een datatype-waarde kan verschijnen als een element van een array, waarbij die array op zijn beurt een veld is van dezelfde datatype-waarde. Dit creëert een cyclus die de standaardcombinatie van theorieën (via Nelson-Oppen) niet detecteert omdat de cyclus "gesplitst" is tussen de datatype- en array-componenten. Deze niet-standaard modellen zijn ongewenst omdat ze niet overeenkomen met de intuïtieve semantiek van geneste datastructuren die bedoeld zijn voor verificatie.

2. Methodologie

De auteurs stellen een theorie van geneste datatypen voor die deze niet-standaard modellen expliciet uitsluit. De methodologie bestaat uit twee hoofdcomponenten: een formele definitie van de theorie en een beslissingsprocedure gebaseerd op reductie.

2.1. Formele Definitie

De theorie wordt gedefinieerd door de standaardcombinatie van datatypen en arrays te beperken.

Welgevormdheid: De auteurs introduceren een nieuwe definitie van welgevormde sorts (Definitie 10) die rekening houdt met de aanwezigheid van array-sorts. Dit zorgt ervoor dat de recursieve structuur van datatypen welgevormd blijft, zelfs wanneer array-elementen betrokken zijn.
NDT-relatie: Om niet-standaard modellen uit te sluiten, definiëren de auteurs een relatie $\mathcal{R}_{\mathcal{A}}$ op de structuren (Definitie 16). Deze relatie verbindt termen met hun subtermen en arrays met hun elementen. Een structuur wordt alleen als een geldige NDT-structuur beschouwd als deze relatie welgevormd is. Dit sluit effectief cycli uit waarbij een datatype-waarde indirect naar zichzelf verwijst via een array.

2.2. Beslissingsprocedure

Het artikel presenteert een beslissingsprocedure die het verzadigbaarheidsprobleem voor geneste datatypen reduceert tot de (naïve) combinatie van datatypen, arrays en ongeïnterpreteerde functies (EUF). De procedure werkt als volgt:

Signatuur Translatie: Een nieuwe signatuur $\Sigma_{\varphi}$ wordt geconstrueerd.
- Array-sorts worden gesplitst in twee componenten: een datatype-sort ( $\sigma^*$ ) gebruikt voor cycluscontrole en een array-sort ( $\sigma'$ ) gebruikt voor standaard array-redenering.
- Datatype-constructors worden gekopieerd om op de nieuwe sorts te opereren.
- Speciale constructors worden geïntroduceerd om arrays als eindige tuples te representeren, waarbij de elementen die worden geraadpleegd via de aanwezige indices in de invoerformule worden vastgelegd.
- Ongeïnterpreteerde functies ( $f_A, g_A$ ) worden toegevoegd om de array-sort-representaties ( $\sigma'$ ) te koppelen aan de datatype-sort-representaties ( $\sigma^*$ ).
Formule Translatie: De invoerformule $\varphi$ wordt getranslateerd naar $\text{trFormula}(\varphi)$ .
- Standaard literalen (bijv. $x = \text{select}(a, i)$ ) worden gemapt naar hun tegenhangers in de nieuwe signatuur.
- Lemmata: Cruciaal is dat de translatie wordt uitgebreid met een set lemma's ( $L(\varphi)$ ) die de correspondentie afdwingen tussen de array-operaties in de oorspronkelijke formule en de tuple-gebaseerde representatie in de nieuwe signatuur. Deze lemma's zorgen ervoor dat de "verborgen cycli" zichtbaar worden in de getranslateerde formule.
Oplossen: De resulterende formule $\text{trFormula}(\varphi)$ wordt gecontroleerd op verzadigbaarheid met behulp van bestaande SMT-solvers die in staat zijn tot de combinatie van datatypen, arrays en EUF (bijv. via de Nelson-Oppen methode).

2.3. Correctheid en Beslisbaarheid

Het paper bewijst dat de translatie verzadigbaarheid behoudt (Theorem 31) onder de aanname dat de datatype-theorie stabiel oneindig is met betrekking tot de gedeelde sorts. Bij consequent is de theorie van geneste datatypen beslisbaar (Theorem 32).

3. Belangrijkste Bijdragen

Het paper levert drie primaire bijdragen:

Theorie Definitie: De introductie van een precieze theorie van geneste datatypen die niet-standaard cyclische modellen voorkomt die ontstaan door de interactie tussen datatypen en arrays.
Beslissingsprocedure: Een reductie-gebaseerde beslissingsprocedure die problemen met geneste datatypen transformeert naar standaard theorie-combinaties uitgebreid met ongeïnterpreteerde functies.
Implementatie en Evaluatie: Een prototype-implementatie binnen de cvc5 SMT-solver en een empirische evaluatie die de effectiviteit van de aanpak aantoont.

4. Experimentele Resultaten

De auteurs evalueerden hun implementatie op twee benchmark-suites:

Synthetische Benchmarks: Formula's die systematisch zijn ontworpen om cycli van variërende groottes tussen datatypen en arrays te creëren.
- Op onvervulbare instanties (cycli aanwezig), loste cvc5 alle 500 benchmarks op, waarmee het Z3 overtrof (Z3 loste er gemiddeld 299,8 op, hoewel de tabel aangeeft dat Z3 minder totale instanties oploste).
- Op vervulbare instanties (cycli doorbroken), loste cvc5 25 van de 50 op, terwijl Z3 er slechts 1 oploste.
Real-World Benchmarks: Formula's afgeleid van de Move Prover verificatietool, die geneste datatypen gebruikt om persistente datastructuren in smart contracts te modelleren.
- Beide solvers losten alle Move Prover benchmarks snel op.
- cvc5 was vergelijkbaar met of iets sneller dan Z3 op vervulbare instanties.

5. Betekenis en Claims

Het paper claimt dat de voorgestelde theorie en beslissingsprocedure succesvol het probleem van niet-standaard modellen aanpakken in de combinatie van datatypen en arrays, een probleem dat bestaande solvers (zoals Z3) wellicht impliciet afhandelen maar zonder een precieze theoretische definitie of gegarandeerde correctheid met betrekking tot acycliciteit.

De auteurs stellen dat hun aanpak "veelbelovend" is, waarbij zij aantonen dat zij competitief zijn met bestaande oplossingen op real-world benchmarks en superieur op synthetische benchmarks die ontworpen zijn om cyclusdetectie te testen. Zij benadrukken dat het werk gemotiveerd is door de behoeften van de Move Prover, waar dergelijke geneste structuren veel voorkomen.

Het paper sluit bescheiden af met de opmerking dat, hoewel het huidige werk specifiek het geval van arrays oplost, het bredere probleem van ongedetecteerde cycli bestaat voor andere datastructuren (sequenties, sets, etc.). De auteurs suggereren dat hun oplossing voor arrays als basis kan dienen voor een meer algemene oplossing voor de problemen van naïeve theorie-combinaties. Toekomstig werk wordt geïdentificeerd als het uitbreiden van ondersteuning voor incrementeel oplossen en kwantoren.