💻 computer science

Definitional Inversion, Without Normalisation

Questo articolo introduce una nuova tecnica di dimostrazione basata sulla teoria dei domini che stabilisce proprietà di inversione definizionale per i sistemi di tipi dipendenti senza fare affidamento sulla normalizzazione, consentendo così l'analisi metateoretica di sistemi non normalizzanti come Idris e Lean, nonché di quelli con type-in-type.

Autori originali: Mario Carneiro, Thierry Coquand, Adrien Frabetti Mathieu, Meven Lennon-Bertrand, Paul-André Melliès, Stephanie Weirich

Pubblicato 2026-07-16

📖 6 min di lettura🧠 Approfondimento

CC BY 4.0

Autori originali: Mario Carneiro, Thierry Coquand, Adrien Frabetti Mathieu, Meven Lennon-Bertrand, Paul-André Melliès, Stephanie Weirich

Articolo originale sotto licenza CC BY 4.0 (http://creativecommons.org/licenses/by/4.0/). ✨ Questa è una spiegazione generata dall'IA dell'articolo qui sotto. Non è stata scritta né approvata dagli autori. Per precisione tecnica, consulta l'articolo originale. Leggi il disclaimer completo

Immagina di costruire una biblioteca magica e immensa dove ogni libro è una dimostrazione matematica e gli scaffali stessi sono fatti di logica. Questo è il mondo dei sistemi di tipi dipendenti, il motore segreto dietro gli moderni assistenti alla dimostrazione come Lean e i linguaggi di programmazione come Idris. In questo mondo, le regole sono incredibilmente rigide: se provi a mettere un "gatto" su uno scaffale etichettato "numeri", il sistema di sicurezza della biblioteca (il controllore di tipi) dovrebbe urlare immediatamente "Errore!" e fermarti. Questa sicurezza si basa su un concetto chiamato uguaglianza definizionale, che è il modo in cui la biblioteca decide se due cose sono essenzialmente la stessa cosa. Per esempio, un "quadrato" è solo un "rettangolo con lati uguali"? Se il sistema dice di sì, li tratta come identici.

Tuttavia, controllare queste regole è complicato. Tradizionalmente, per dimostrare che la biblioteca fosse sicura, i matematici dovevano mostrare che ogni singolo libro potesse essere semplificato fino alla sua forma più semplice e basilare (un processo chiamato normalizzazione). Ma molte librerie moderne e potenti sono progettate per essere infinite o autoreferenziali, il che significa che non possono essere semplificate fino a un punto finale. È come cercare di appiattire un frattale: continuerai a trovare nuovi dettagli. Per molto tempo, se un sistema non poteva essere semplificato, non potevamo dimostrarne la sicurezza. Questo articolo introduce un nuovo modo per controllare la sicurezza della biblioteca senza dover prima appiattire il frattale.

L'enigma infinito e lo specchio magico

Pensa a un sistema di tipi dipendenti come a un gigantesco puzzle che si controlla da solo. I pezzi sono i tipi (come "numeri" o "funzioni") e l'obiettivo è assicurarsi che, quando si incastrano due pezzi, questi si adattino perfettamente. La regola più critica in questo puzzle è l'inversione definizionale. È la logica che dice: "Se due strutture complesse sembrano uguali, anche le loro parti devono essere uguali". Per esempio, se hai due tipi di funzione che sono identici, l'articolo dimostra che anche i loro tipi di input e di output devono essere identici. Questo è fondamentale perché permette al computer di scomporre in sicurezza il codice complesso in pezzi più piccoli senza confondersi.

Per decenni, l'unico modo per provare che questi pezzi si incastrassero era usare un metodo chiamato confluenza (controllare se diversi percorsi di semplificazione portano allo stesso risultato) o relazioni logiche (un modo complesso per confrontare come i termini si comportano). Ma questi vecchi strumenti si sono scontrati con un muro. La confluenza crolla quando si aggiungono certe regole "estensionali" (come le leggi $\eta$ , che dicono che una funzione è definita interamente da ciò che fa, non da come è scritta). Le relazioni logiche richiedono solitamente che il sistema sia "normalizzante" (capace di fermare la semplificazione), il che esclude molti linguaggi di programmazione reali e potenti che permettono loop infiniti o tipi autoreferenziali.

Il nuovo approccio: Una mappa di possibilità

Gli autori, un team di scienziati dell'informatica e matematici, propongono una nuova strategia basata sulla teoria dei domini. Inve al di tentare di forzare i pezzi del puzzle a semplificarsi in un'unica forma finale, costruiscono una mappa di tutti i comportamenti possibili.

Immagina di cercare di identificare una creatura misteriosa in una foresta buia.

Il vecchio modo: Aspetti che la creatura smetta di muoversi e riveli la sua vera forma finale. Se la creatura non smette mai di muoversi (perché è un loop infinito), non puoi identificarla e la foresta è insicura.
Il nuovo modo: Non aspetti che la creatura si fermi. Invece, osservi le sue impronte. Noti che lascia un'impronta del "piede sinistro", poi un'impronta del "piede destro", poi di nuovo del "piede sinistro". Anche se la creatura non smette mai di camminare, puoi comunque dedurre la sua forma guardando il modello dei suoi passi.

Nel linguaggio dell'articolo, queste "impronte" sono chiamate elementi compatti o osservazioni finite. Gli autori costruiscono un "dominio" matematico (uno spazio strutturato) dove ogni tipo è rappresentato non da una risposta finale, ma dall'insieme di tutte le cose finite che possiamo osservare di esso. Usano una tecnica chiamata proiettori finiti per tagliare questo dominio in parti gestibili.

Cosa hanno scoperto

Usando questo metodo delle "impronte", il team è riuscito a dimostrare che l'inversione definizionale è vera anche in sistemi che:

Non si fermano mai nella semplificazione (non normalizzanti), come quelli con una regola "type-in-type" (dove un tipo può contenere se stesso).
Includono leggi $\eta$ , che sono regole complicate che rendono le funzioni e le coppie più intuitive ma che rompono i metodi di dimostrazione tradizionali.

Hanno dimostrato questo su una piccola versione "core" di una teoria dei tipi chiamata MLTT $\eta$ (Teoria dei tipi di Martin-Löf con leggi $\eta$ ). Hanno dimostrato che anche in questo sistema caotico e potenzialmente infinito, se due tipi sono uguali, anche i loro componenti devono essere uguali. Questo è un grande passo avanti perché dimostra che la "rete di sicurezza" del sistema di tipi funziona anche quando il sistema è permesso di essere disordinato e infinito.

Perché è importante

Gli autori non hanno solo risolto un puzzle per un piccolo sistema di prova; hanno dimostrato che il loro metodo è robusto. Hanno esteso la loro dimostrazione per includere:

Somme dipendenti (coppie di dati).
Tipi unitari (un tipo con un solo valore).
Combinatori di punto fisso (strumenti che permettono la ricorsione infinita).
Numeri naturali con pattern matching.
Tipi di identità (dimostrare che due cose sono uguali).
Proposizioni con irrilevanza della prova (dove il contenuto di una prova non conta, conta solo che essa esista).

Hanno persino costruito un modello per un "universo di proposizioni strette", mostrando che la loro tecnica può gestire le caratteristiche complesse presenti in strumenti del mondo reale come Lean, Agda e Rocq.

I limiti e il futuro

L'articolo è molto chiaro su ciò che non fa. Non dimostra che questi sistemi siano "normalizzanti" (ovvero che si fermino sempre). Anzi, lavora esplicitamente per sistemi che non si fermano. Inoltre, non risolve il problema dei "neutri" (variabili che non sono ancora state riempite) nello stesso modo in cui risolve quello per i termini chiusi, sebbene accenni a come ciò potrebbe essere fatto in futuro.

Gli autori hanno già trasformato le loro dimostrazioni matematiche in codice, verificandole tre volte in tre diversi assistenti alla dimostrazione (Agda, Lean e Rocq). Ciò suggerisce che il loro metodo non è solo un'idea teorica, ma uno strumento pratico.

Il punto fondamentale

Questo articolo è come consegnare ai costruttori della biblioteca magica un nuovo paio di occhiali. Prima, potevano controllare la sicurezza della biblioteca solo se i libri erano statici e finiti. Ora, possono controllare la sicurezza di libri che sono ancora in fase di scrittura, o libri che si riferiscono a se stessi per sempre. Concentrandosi sul comportamento osservabile (le impronte) piuttosto che sulla destinazione finale (l'arresto), hanno aperto la porta alla verifica dei sistemi di tipi più potenti, complessi e potenzialmente infiniti che possiamo immaginare. Questo apre la strada a "Lean4Lean" e "MetaRocq"—progetti in cui gli assistenti alla dimostrazione verificano il proprio codice—rendendo gli strumenti che usiamo per costruire la matematica e il software ancora più affidabili.

Sintesi Tecnica: Inversione Definizione, Senza Normalizzazione

Problema
I sistemi di tipi dipendenti costituiscono la base di assistenti alla dimostrazione critici (Agda, Lean, Rocq) e di linguaggi di programmazione (Idris, Haskell dipendente). Stabilire le loro proprietà metateoriche, in particolare i principi di inversione definizionale (iniettività e assenza di confusione dei costruttori di tipi), è essenziale per dimostrare la correttezza, l'unicità dei tipi e la verifica del kernel. Tuttavia, gli strumenti metateorici esistenti affrontano gravi limitazioni:

Approcci basati sulla confluenza: faticano con le moderne caratteristiche come le leggi $\eta$ . Sebbene la confluenza funzioni per la $\beta$ -riduzione, mescolare la confluenza con la conversione tipizzata e le leggi $\eta$ (ad esempio per funzioni o coppie) spesso porta a sistemi non confluenti o richiede presentazioni complesse e non standard.
Approcci basati sulla normalizzazione (Relazioni Logiche): Le relazioni logiche tradizionali si basano sull'esistenza di forme normali. Esse falliscono per le teorie dei tipi non normalizzanti (comuni nella pratica, ad esempio quelle che utilizzano Type:Type o combinatori di punto fisso). Inoltre, dimostrare la normalizzazione richiede una logica ambiente più forte della logica oggetto (spesso coinvolgendo l'induzione-ricorsione o l'impredicatività), il che rende impossibile studiare la metateoria dei proof assistant all'interno di se stessi (ad esempio Lean4Lean, MetaRocq).

Il documento affronta il caso specifico di MLTT $\eta$ , una variante della teoria dei tipi di Martin-Löf con prodotti dipendenti, equazioni $\beta$ e $\eta$ , e un universo Type:Type. Questo sistema sfida la confluenza (a causa di $\eta$ ) e la normalizzazione (a causa di Type:Type), lasciando le sue proprietà di inversione definizionale non dimostrate.

Metodologia
Gli autori propongono una nuova tecnica di dimostrazione basata sulla teoria dei domini, specificamente utilizzando proiezioni finitarie. L'intuizione centrale è quella di interpretare i tipi non tramite le loro forme normali (che potrebbero non esistere), ma tramite il loro "comportamento osservabile" attraverso elementi compatti in un dominio di Scott.

Costruzione del Dominio: Gli autori costruiscono un dominio $D$ $D$ come la soluzione di un'equazione di dominio ricorsiva che rappresenta i costruttori di tipi ( $\Pi$ $Π$ , $\mathcal{U}$ $U$ , ecc.). Il dominio è costruito come il limite di una sequenza crescente di approssimazioni finite ( $C_n$ $C_{n}$ ), dove gli elementi sono compatti (rappresentano osservazioni finite).
- Crucialmente, il modello identifica $\bot$ con $\lambda x.\bot$ per soddisfare le leggi $\eta$ per le funzioni, mantenendo al contempo i costruttori $\Pi$ distinti da $\mathcal{U}$ per garantire la disgiunzione.
Tipizzazione Semantica: Una relazione di tipizzazione semantica è definita sugli elementi compatti del dominio. Questa relazione è formulata utilizzando proiettori finiti (mappe continue $p: D \to D$ tali che $p(\alpha) \le \alpha$ e $p(p(\alpha)) = p(\alpha)$ ). Un tipo è interpretato come un proiettore finito, e un termine è correlato a un tipo se la sua denotazione è un punto fisso di quel proiettore.
Relazione Logica: Una relazione logica è definita sui termini sintattici e sulle testimonianze semantiche (elementi compatti). A differenza delle relazioni logiche tradizionali che ricorsono sulle forme normali dei tipi, questa relazione ricorre sullo stadio $n$ $n$ degli elementi compatti e sulla struttura della testimonianza semantica.
- La relazione gestisce i termini aperti interpretando i termini neutri come $\bot$ , evitando la complessità della quantificazione di tipo Kripke pur supportando comunque l'inversione in contesti aperti.
- La relazione è definita fino alla riduzione head, incorporando direttamente le regole $\beta$ e $\eta$ nella struttura della relazione logica.
Adeguatezza: Gli autori dimostrano un teorema di adeguatezza: se due termini sono definizionalmente uguali nella sintassi, essi sono correlati nella relazione logica. Ciò consente di derivare proprietà sintattiche (come l'iniettività) dalle proprietà semantiche (disgiunzione degli elementi del dominio).

Contributi Chiave

Nuova Tecnica di Dimostrazione: Un metodo basato sulla teoria dei domini per dimostrare l'inversione definizionale (iniettività e assenza di confusione) senza fare affidamento su normalizzazione o confluenza.
Gestione di $\eta$ e Non-Normalizzazione: La tecnica dimostra con successo l'iniettività per sistemi con leggi $\eta$ e Type:Type (o combinatori di punto fisso), una combinazione precedentemente intrattabile per i metodi standard.
Logica Ambiente Debole: La dimostrazione si basa solo sull'induzione di base sui numeri naturali, evitando principi logici forti (come l'induzione-ricorsione) richiesti per le dimostrazioni di normalizzazione. Ciò la rende adatta a progetti di auto-verifica (ad esempio, dimostrare le proprietà di Lean all'interno di Lean).
Estendibilità: La tecnica è dimostrata su MLTT $\eta$ e si mostra scalabile a teorie più ricche che includono:
- Somme dipendenti ( $\Sigma$ ) e tipo Unit ($1$) con leggi $\eta$ .
- Ricorsione generale tramite un combinatore di punto fisso ( $Y$ ).
- Numeri naturali ( $\mathbb{N}$ ) con pattern matching.
- Tipi di identità rilevanti per la prova ($Id$) con trasporto.
- Un universo di proposizioni strette ($Prop$) con irrelevanza della prova definizionale.
Meccanizzazione: I risultati sono meccanizzati in Agda, Lean e Rocq, coprendo le varie estensioni elencate sopra.

Risultati

Iniettività di $\Pi$ : Il documento dimostra che se $\Pi x:A.B \equiv \Pi x:A'.B'$ , allora $A \equiv A'$ e $B \equiv B'$ .
Disgiunzione: I costruttori di tipi sono disgiunti (ad esempio, $\Pi x:A.B \not\equiv \mathcal{U}$ ).
Soggetto Riduzione e Progress: Come conseguenze dei principi di inversione, gli autori derivano i teoremi di progress e preservation, stabilendo la correttezza del linguaggio come linguaggio di programmazione.
Fallimento di UIP: Il modello dimostra che l'Unicità delle Prove di Identità (UIP/regola-K) non è derivabile in questo sistema, poiché il modello di dominio distingue tra diverse prove di identità.

Significatività
Il documento sostiene di colmare un "punto cieco" nella metateoria dei sistemi di tipi dipendenti. Scollegando l'inversione definizionale dalla normalizzazione, la tecnica permette lo studio rigoroso di sistemi non normalizzanti e di sistemi con ricche teorie equazionali (come $\eta$ ) che sono prevalenti nei moderni assistenti alla dimostrazione e nei linguaggi di programmazione.

Gli autori posizionano questo lavoro come un passo fondamentale per progetti come Lean4Lean e MetaRocq, che mirano a verificare la metateoria dei proof assistant all'interno di se stessi. Poiché questi progetti non possono assumere la normalizzazione della logica oggetto (a causa del secondo teorema di incompletezza di Gödel), questo approccio basato sulla teoria dei domini offre una via percorribile per verificare i kernel e garantire la correttezza degli algoritmi di type-checking senza richiedere una logica ambiente più forte. Gli autori suggeriscono inoltre potenziali applicazioni per i linguaggi di programmazione tipizzati dipendentemente che utilizzano caratteristiche non terminanti o la tipizzazione graduale, dove la metateoria tradizionale basata sulla terminazione fallisce.