💻 computer science

Nominal Type Theory by Nullary Internal Parametricity

Dit artikel presenteert een nieuw type-theoretisch raamwerk gebaseerd op Nullary Internally Parametric Type Theory en een specifiek naam-inductieprincipe dat de schone typeringsregels van universele naamabstrakties succesvol verenigt met de krachtige patroonmatchingcapaciteiten van existentiële abstrakties, waardoor een goed-gedragend nominaal raamwerk wordt gevestigd voor het representeren van syntaxis met binders.

Oorspronkelijke auteurs: Antoine Van Muylder, Andreas Nuyts, Dominique Devriese

Gepubliceerd 2026-05-25

📖 5 min leestijd🧠 Diepgaand

CC BY 4.0

Oorspronkelijke auteurs: Antoine Van Muylder, Andreas Nuyts, Dominique Devriese

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 probeert een computerprogramma te schrijven dat de regels van een taal begrijpt, zoals een programmeertaal of een logische puzzel. Een grote hoofdpijn in dit veld is het omgaan met variabelen (zoals x of y) die "gebonden" zijn binnen specifieke scopes, zoals binnen een functie of een lus.

In de traditionele informatica is het hanteren van deze variabelen rommelig. Je moet je voortdurend zorgen maken over "alfa-equivalentie" (is x hetzelfde als y als ik het gewoon hernoem?) en "variabele opname" (heb ik per ongeluk de verkeerde x gegrepen?).

Dit artikel introduceert een nieuwe, schonere manier om deze variabelen te hanteren met behulp van een concept genaamd Nominaal Type-theorie, gebouwd op een fundament genaamd Nulstellige Interne Parametriciteit. Hier is de uitleg met eenvoudige analogieën:

1. Het Probleem: Het "Naamplaatje"-Dilemma

Stel je voor dat je een feestje organiseert. Je hebt een lijst met gasten (variabelen).

De Oude Manier (Existentieel): Je behandelt een gast als een specifiek paar: "Hier is een naamplaatje, en hier is de persoon die het draagt." Dit is geweldig omdat je naar het plaatje kunt kijken en zeggen: "Ah, dat is Bob!" (Patroonmatching). Maar de regels voor het beheren van deze plaatjes zijn ongelooflijk ingewikkeld en bureaucratisch.
De Alternatieve Manier (Universeel): Je behandelt een gast als een "functie" die alleen werkt als je hen een vers, ongebruikt naamplaatje geeft. Dit is zeer schoon en eenvoudig te beheren, maar je verliest de mogelijkheid om naar het plaatje te kijken en te zeggen: "Dat is Bob!" Je kunt patronen niet gemakkelijk matchen.

Lange tijd moesten onderzoekers kiezen tussen de rommelige maar flexibele manier of de schone maar starre manier.

2. De Oplossing: De "Magische Doos" (Nulstellige Parametriciteit)

De auteurs stellen een nieuw systeem voor dat het beste van twee werelden combineert. Ze gebruiken een wiskundig hulpmiddel genaamd Parametriciteit.

Denk aan Parametriciteit als een "Magische Doos" die controleert of je code eerlijk is.

Binair Parametriciteit (De Standaard): Normaal gesproken controleert deze doos of je code zich op dezelfde manier gedraagt voor twee verschillende invoerwaarden.
Nulstellige Parametriciteit (De Nieuwe Truc): De auteurs realiseerden zich dat als je deze doos verkleint tot nul invoerwaarden (Nulstellig), het een perfect hulpmiddel wordt voor het hanteren van namen.

In dit nieuwe systeem is een "naam" niet zomaar een label; het is een speciaal soort "brug" of "pad" dat dingen met elkaar verbindt. Het systeem behandelt namen als affiene functies — denk aan ze als een "generator voor verse namen" die garandeert dat je een naam gebruikt die in die specifieke context nog niet eerder is gebruikt.

3. De Belangrijkste Innovatie: "Naam-Inductie"

Het artikel introduceert een speciale regel genaamd Naam-Inductie.

Stel je voor dat je een mysteriedoos hebt met daarin een naam. Je wilt weten wat erin zit. De regel "Naam-Inductie" zegt dat er slechts twee mogelijkheden zijn:

Het Identiteitsgeval: De naam binnenin is precies de "huidige" naam die je vasthoudt (zoals in een spiegel kijken).
Het Verse Geval: De naam binnenin is volledig nieuw en is in deze context nog nooit gezien.

Deze eenvoudige "of-of"-controle stelt de computer in staat om iets te doen wat het voorheen niet gemakkelijk kon: Nominaal Patroonmatching. Het kan nu naar een complexe structuur kijken, bijvoorbeeld "Hier is een functie die een naam accepteert", en deze veilig ontleden om te zien wat erin zit, net zoals de rommelige "Oude Manier" dat toeliet, maar dan met de schone regels van de "Alternatieve Manier".

4. Hoe Het in de Praktijk Werkt

De auteurs tonen aan dat ze, door deze "Nulstellige" aanpak te gebruiken, alle functies van eerdere, complexe systemen (zoals FreshML) kunnen herbouwen zonder de rommelige regels.

Namen Wisselen: Je kunt twee namen veilig met elkaar verwisselen.
Lokale Scope: Je kunt een "privé"-naam maken die alleen bestaat binnen een specifiek blok code en verdwijnt wanneer je het verlaat.
Patroonmatching: Je kunt code schrijven die zegt: "Als ik een functie zie die een naam accepteert, laten we kijken wat het doet," en het systeem behandelt automatisch de veiligheidscontroles voor je.

5. Het "HOAS"-Voorbeeld (Het Grootse Finale)

Om te bewijzen dat hun systeem werkt, bouwden de auteurs een brug tussen twee verschillende manieren om de "Ongetypeerde Lambda-calculus" (een fundamentele taal van computing) weer te geven.

De ene manier gebruikt "De Bruijn-indexen" (tellen met nummers om variabelen bij te houden, zoals "de 3e variabele").
De andere gebruikt "Higher-Order Abstract Syntax" (het gebruik van de eigen functies van de gasttaal om variabelen weer te geven).

Ze toonden aan dat hun nieuwe systeem perfect kon vertalen tussen deze twee werelden. Ze gebruikten een concept genaamd Synthetische Kripke-Parametriciteit, wat een chique manier is om te zeggen dat ze de "Nulstellige" regels gebruikten om een complex, meerlagig logisch model te simuleren dat normaal gesproken een veel zwaardere wiskundige opstelling vereist.

Samenvatting

Kortom, dit artikel zegt: "We hebben een manier gevonden om het hanteren van variabele namen in computertalen net zo makkelijk te maken als tellen, maar net zo krachtig als het kijken naar specifieke namen, door een complexe wiskundige 'eerlijkheidscontrole' te verkleinen tot nul dimensies."

Ze hebben geen nieuwe programmeertaal uitgevonden om aan consumenten te verkopen; ze hebben een nieuwe wiskundige fundament uitgevonden die het voor informatici gemakkelijker maakt om tools te bouwen die redeneren over code, zodat we bij het manipuleren van variabelen niet per ongeluk de regels van de logica breken.

Technische Samenvatting: Nominale Type-theorie door Nullaire Interne Parametriciteit

Probleemstelling
Het formaliseren van de syntaxis van talen met binders (bijvoorbeeld de lambda-calculus) vereist het hanteren van $\alpha$ -equivalentie, naamabstractie en versheid. Nominale kaders adresseren dit met behulp van typen voor "naamabstractie" (aangeduid als $\@N \multimap -$ ). Echter, bestaande benaderingen staan voor een afweging:

Existentiële Presentatie: Behandelt abstracties als naam-term paren $\langle x, a \rangle$ . Dit ondersteunt handzame "nominale patroonmatching" (deconstrueren van binders) maar lijdt onder lastige type-regels die complexe versheidspropagatie vereisen.
Universele Presentatie: Behandelt abstracties als functies die verse namen consumeren (affiene functies). Dit biedt schone inferentieregels maar lijkt het vermogen te missen om nominale patroonmatching uit te voeren.

Huidige nominale kaders vertrouwen vaak op externe semantiek (bijvoorbeeld nominale verzamelingen) of complexe interne mechanismen om deze kloof te overbruggen. Het artikel zoekt een fundament dat de schone regels van de universele presentatie verenigt met de patroonmatching-capaciteiten van de existentiële, volledig binnen een type-theoretische setting.

Methodologie
De auteurs stellen Parametrische Nominale Type-theorie (PNTT) voor, een afhankelijke type-theorie gebaseerd op Nullaire Interne Parametrische Type-theorie (nullaire PTT). Deze benadering past de binaire intern parametrische type-theorie van Cavallo en Harper (CH) aan door de ariteit van parametriciteit te reduceren van 2 naar 0.

De kernmethodologie omvat:

Nullaire Bruggen: Het vervangen van de standaard binaire pad-/bruggentypen door nullaire bruggen. Een nullaire brug $q : \text{Bridge } A \dots$ wordt behandeld als een affiene functie vanuit een bruginterval $\@N$ . Deze bruggen vertegenwoordigen "verse" variabelen.
Structuurabstractieprincipe (SAP): De theorie internaliseert parametriciteit via het SAP, dat equivalenties vaststelt tussen een type $K$ en zijn "bruggentype" $\@N \multimap K$ . Cruciaal stelt het SAP dat de bruggentypevormer commuteert met alle andere typevormers.
Naaminductie: Het bruginterval $\@N$ wordt uitgebreid tot een eerste-klassen type van namen, $\text{Nm}$ . Een nieuw eliminator, naaminductie ( $\text{ind}_{\text{Nm}}$ ), wordt geïntroduceerd. Dit maakt casusanalyse op een naam $n$ mogelijk: ofwel is $n$ de specifieke affiene variabele $x$ die momenteel in scope is, ofwel is $x$ vers in $n$ .
Nominale Datatypen: Standaard nominale datatypen (zoals de syntaxis van de ongetypeerde lambda-calculus) worden gedefinieerd met constructoren die namen als argumenten kunnen nemen.

Belangrijkste Bijdragen

Herstel van Nominale Patroonmatching: Het artikel demonstreert dat nominale patroonmatching, typisch geassocieerd met existentiële abstracties, kan worden hersteld in de universele setting. Door het SAP toe te passen op een nominaal datatype $D$ , wordt het bruggentype $\@N \multimap D$ getoond equivalent te zijn aan een "parametrische vertaling" $D_1$ (bijvoorbeeld $Ltm_1$ ). $D_1$ bevat expliciete "gat"-constructoren. Patroonmatching op een binder in $D$ wordt aldus gereduceerd tot inductie op $D_1$ , waarbij het "gat"-geval overeenkomt met de gebonden variabele.
Gefuseerde Primitieven: De auteurs tonen aan dat PNTT op natuurlijke wijze ondersteuning biedt voor:
- Universele Naamabstractie: Via nullaire bruggentypen.
- Typale Versheid: Via $\text{Gel}$ -typen, die termen classificeren waarbij een specifieke naam vers is.
- Existentiële Abstractie: Afgeleid niet-primitief via het SAP en versheidstypen.
- Naamverwisseling en Lokale Scope: Geïmplementeerd met behulp van affiene functies en de $\nu$ -binder (geïmplementeerd als $\text{ung}(\lambda x. t)$ ).
Synthetische Kripke-Parametriciteit: Het artikel verbindt nullaire parametriciteit met binaire Kripke-parametriciteit. Door nullaire parametriciteit (voor nominale redenering) te combineren met een standaard binair parametriciteitsaxioma, emuleren de auteurs Kripke-modellen. Dit wordt aangetoond door het bewijs van de equivalentie tussen de De Bruijn-syntaxis van de ongetypeerde lambda-calculus en zijn HOAS-encoding (Higher-Order Abstract Syntax).
Structuurabstractieprincipe (SAP) op Namen: Een specifiek bewijs wordt geleverd dat aantoont dat $\@N \multimap \text{Nm} \simeq 1 + \text{Nm}$ . Deze equivalentie is centraal voor het principe van naaminductie en het herstel van patroonmatching.

Resultaten

Theoretische Soundheid: De auteurs leveren een semantisch model voor PNTT in de voorplaat-categorie $\text{Psh}(\square_2 \times \square_0)$ , waarbij $\square_0$ de categorie is van eindige ordinalen en injecties (de basis van de Schanuel-topos). Dit bevestigt de consistentie van het systeem.
Implementatiehaalbaarheid: Het artikel betoogt dat, aangezien de binaire CH-theorie is geïmplementeerd in Cubical Agda, het implementeren van PNTT (essentieel nullaire CH + naaminductie) haalbaar is.
Casestudies:
- $\pi$ -calculus Substitutie: De auteurs definiëren een substitutiefunctie voor $\pi$ -calculus-processen door te matchen op bindingpatronen, wat de bruikbaarheid van de SAP-gebaseerde aanpak demonstreert.
- HOAS Adequaatheid: Een bewijs wordt geschetst (teruggrijpend op een extern binair parametriciteitsaxioma) dat aantoont dat de nominale syntaxis van de lambda-calculus equivalent is aan zijn HOAS-encoding, wat de resultaten van Atkey's Kripke-parametriciteit nabootst.

Beteekenis en Beweringen
Het artikel claimt een "legitiem nominaal kader" te bieden dat de historische spanning tussen existentiële en universele naamabstracties oplost.

Unificatie: Het verenigt de schone inferentieregels van universele abstractie met de praktische patroonmatching-capaciteiten van existentiële abstractie zonder externe metatheorie te vereisen.
Internalisatie: In tegenstelling tot eerdere benaderingen waarbij parametriciteit een metatheoretische eigenschap is, internaliseert PNTT parametriciteit via het SAP, waardoor parametriciteitsresultaten binnen de theorie kunnen worden bewezen.
Nieuwheid: De auteurs stellen dat zij de eersten zijn die expliciet en actief gebruik maken van nullaire parametriciteit als fundament voor nominale type-theorie.
Bescheidenheid: Het artikel erkent beperkingen. De SAP-bewijzen voor complexe termen zijn "onhandig" en vereisen momenteel handmatige reproductie van termstructuren. De auteurs suggereren dat toekomstig werk zou kunnen bestaan uit het automatiseren van SAP-bewijsconstructie of het overstappen naar een "observationele" versie van PNTT (zoals in de Narya bewijsassistent) om de noodzaak van expliciete SAP-bewijzen te vermijden. Zij merken ook op dat volledige FreshMLTT naamverwisselingsregels (commuterend met substitutie) nog niet volledig worden opgevangen zonder ad-hoc beperkingen.

Samenvattend vestigt het artikel nullaire interne parametriciteit als een robuust fundament voor nominale type-theorie, en biedt het een principieel manier om binders, versheid en patroonmatching te hanteren binnen één coherent type-theoretisch systeem.