💻 computer science

Cyclic Proofs in Hoare Logic and its Reverse

Il paper esamina le relazioni tra sistemi di prova assiomatici e ciclici per la logica di Hoare e la sua versione duale (reverse Hoare logic), dimostrando che le versioni cicliche, che sostituiscono invarianti e misure di terminazione con regole di srotolamento e condizioni di correttezza globale, sono sia corrette che relativamente complete.

Autori originali: James Brotherston, Quang Loc Le, Gauri Desai, Yukihiro Oda

Pubblicato 2026-03-03

📖 5 min di lettura🧠 Approfondimento

CC BY 4.0

Autori originali: James Brotherston, Quang Loc Le, Gauri Desai, Yukihiro Oda

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 dover spiegare a un amico come funziona un programma informatico, ma invece di guardare il codice riga per riga, vuoi essere sicuro al 100% che funzioni come previsto. Questo è il cuore della Logica di Hoare, un metodo matematico usato per "provare" che i software non abbiano bug.

Questo articolo scientifico è come una mappa che collega quattro modi diversi di fare questa verifica, mostrando che in realtà sono tutti collegati tra loro come pezzi di un unico puzzle.

Ecco una spiegazione semplice, usando metafore quotidiane:

1. I Due Mondi: "Non deve andare storto" vs "Deve succedere"

Immagina di avere un'automobile (il tuo programma).

Logica di Hoare (Il mondo della sicurezza): Qui ci chiediamo: "Se parto da casa con il serbatoio pieno (precondizione), arriverò a destinazione senza incidenti (postcondizione)?"
- Parziale: Ci assicuriamo solo che se l'auto si ferma, sia al posto giusto. Non ci importa se l'auto rimane in panne per sempre (non finisce mai).
- Totale: Ci assicuriamo che l'auto arrivi a destinazione e che non rimanga mai bloccata in un traffico infinito. Deve finire il viaggio.
Logica di Hoare Inversa (Il mondo della caccia al bug): Qui ci chiediamo il contrario: "Esiste un modo per guidare l'auto in modo che finisca esattamente nel parcheggio sbagliato (o in un bug)?"
- Se riusciamo a dimostrare che è impossibile finire in quel parcheggio, allora il bug non esiste.
- Inversa Parziale: Ci chiediamo se possiamo finire nel parcheggio sbagliato (anche se il viaggio dura un'eternità).
- Inversa Totale: Ci chiediamo se possiamo finire nel parcheggio sbagliato in un tempo finito.

2. Il Problema: Trovare la "Ricetta" Perfetta

Nella logica classica (quella "assiomatica"), per dimostrare che un programma funziona (specialmente se ha un ciclo, come un while che ripete un'azione), devi inventare una "Ricetta Magica" (chiamata invariante).

Devi scrivere una regola che sia vera prima del ciclo, vera durante ogni giro del ciclo e vera alla fine.
Per la versione "Totale", devi anche inventare un "Contatore di Energia" (misura di terminazione) che diminuisce ad ogni giro, per provare che il ciclo non durerà per sempre.

Il problema? Trovare queste ricette è difficilissimo per i computer e spesso anche per gli umani. È come chiedere a qualcuno di inventare una ricetta perfetta per un piatto che non ha mai cucinato prima.

3. La Soluzione: I "Cicli" (Cyclic Proofs)

Gli autori del paper propongono un approccio diverso, chiamato Proofs Ciclici (Dimostrazioni Cicliche).
Invece di cercare la ricetta perfetta da scrivere tutto in una volta, lasciamo che la dimostrazione si "srotoli" da sola, come un nastro magnetico.

Come funziona: Invece di scrivere "Fai questo ciclo 100 volte", la dimostrazione dice: "Fai un giro, poi guarda di nuovo la stessa regola, fai un altro giro, e così via".
Il trucco: Per evitare che la dimostrazione diventi un cerchio vizioso senza senso (un paradosso), usiamo due "regole di sicurezza" globali:
1. Per la sicurezza (Parziale): Se il cerchio è infinito, deve esserci sempre un'azione che cambia qualcosa (il programma non può stare fermo per sempre). È come dire: "Se giri in tondo, devi comunque avanzare".
2. Per la fine (Totale): Se il cerchio è infinito, deve esserci una "scala" che scende sempre più in basso (il contatore di energia diminuisce). Non puoi scendere all'infinito, quindi prima o poi devi fermarti.

4. La Grande Scoperta: Specchi e Riflessi

La parte più affascinante del paper è che gli autori hanno scoperto che questi quattro mondi (Hoare Parziale/Totale e Inversa Parziale/Totale) sono collegati da specchi perfetti.

Il Simmetria: La logica che ti dice "Non deve andare storto" (Hoare) e quella che ti dice "Deve succedere un bug" (Inversa) sono come due facce della stessa medaglia.
La Traduzione: Gli autori hanno mostrato che puoi prendere una dimostrazione classica (quella difficile con le ricette magiche) e trasformarla automaticamente in una dimostrazione ciclica (quella più fluida con i cerchi). È come prendere un libro di testo rigido e trasformarlo in un'animazione interattiva che si ripete, ma che mantiene la stessa verità.

In Sintesi

Immagina di dover controllare che un ascensore funzioni.

Metodo Vecchio: Devi scrivere un manuale di 100 pagine che spiega esattamente cosa succede in ogni scenario possibile, inventando regole complesse per ogni piano.
Metodo Nuovo (Ciclico): Disegni un diagramma che mostra: "Se l'ascensore è al piano 1, va al 2. Se è al 2, torna al 1". Poi aggiungi un timbro di sicurezza che dice: "Ok, questo ciclo è sicuro perché ogni volta che scendi, l'energia della batteria diminuisce, quindi prima o poi si ferma".

Perché è importante?
Questo lavoro non inventa una nuova magia, ma organizza le vecchie magie in un unico sistema coerente. Dimostra che i metodi per trovare i bug (logica inversa) e i metodi per garantire la sicurezza (logica classica) sono due facce della stessa medaglia e che possiamo usare le stesse tecniche "cicliche" per entrambi. Questo apre la strada a computer più intelligenti che possono trovare bug o provare la sicurezza dei software in modo più automatico e meno faticoso per gli umani.

1. Il Problema

La logica di Hoare è il quadro formale standard per specificare e ragionare sulla correttezza dei programmi, utilizzando triple $\{P\} C \{Q\}$ . Tradizionalmente, i sistemi di prova assiomatici per la correttezza parziale e totale richiedono l'invenzione esplicita di invarianti di ciclo (per la correttezza parziale) e misure di terminazione ben fondate (per la correttezza totale). Questo processo è spesso difficile da automatizzare e costituisce un ostacolo significativo per la ricerca automatica di prove.

Parallelamente, è emersa la Logica di Hoare Inversa (o Reverse Hoare Logic, RHL), che studia la presenza di comportamenti specifici (reachability) piuttosto che la loro assenza. Esistono versioni parziali e totali anche per la RHL (e la sua estensione, la "Incorrectness Logic").

Il problema affrontato dal paper è duplice:

Come formulare sistemi di prova basati su prove cicliche (cyclic proofs) per le versioni parziale e totale sia della Logica di Hoare standard che della sua duale, la Logica di Hoare Inversa?
Come dimostrare che questi sistemi ciclici sono corretti (sound) e relativamente completi, e quali sono le relazioni simmetriche tra le condizioni di correttezza dei sistemi parziali e totali in entrambi i contesti?

2. Metodologia

Gli autori adottano un approccio basato sulla teoria della dimostrazione, confrontando sistemi assiomatici tradizionali con sistemi basati su alberi di derivazione non ben fondati (non-wellfounded).

Linguaggio e Semantica: Viene definito un semplice linguaggio di programmazione while con semantica operazionale a piccoli passi. Vengono definite le nozioni di validità semantica per:
- PHL/THL: Logica di Hoare Parziale/Totale.
- PRHL/TRHL: Logica di Hoare Inversa Parziale/Totale.
Sistemi Assiomatici: Vengono presentati i sistemi di prova standard (Fig. 3 e Fig. 4) che utilizzano regole con invarianti espliciti e misure di terminazione.
Sistemi Ciclici: Viene introdotto un sistema unificato di prove cicliche (Fig. 5 e Fig. 6) basato su:
- Stile di continuazione: Le regole sono formulate come $\{P\} C; C' \{Q\}$ , permettendo di "unroll" (srotolare) i cicli una volta alla volta.
- Backlinks: I fogli di prova aperti (bud) sono collegati a nodi interni (companion) con la stessa giunzione, formando cicli.
- Condizioni di Correttezza Globali:
  - Per la correttezza parziale (PHL e PRHL): Ogni percorso infinito nella pre-prova deve contenere infinite applicazioni di regole di esecuzione simbolica. Questo garantisce che un eventuale controesempio implicherebbe un'esecuzione infinita del programma, contraddicendo l'ipotesi di un controesempio finito.
  - Per la correttezza totale (THL e TRHL): Ogni percorso infinito deve contenere una traccia infinita di valori ben fondati che decrescono (progresso). Questo garantisce che un eventuale controesempio implicherebbe una catena discendente infinita di numeri naturali, che è impossibile.
Dimostrazioni: La correttezza (soundness) è dimostrata per assurdo costruendo percorsi infiniti che violano le condizioni di correttezza globale. La completezza relativa è dimostrata fornendo una traduzione esplicita dalle prove assiomatiche standard alle prove cicliche (Lemma 4.8 e 5.6).

3. Contributi Chiave

Formulazione Unificata: Gli autori presentano sistemi di prova ciclici coerenti per quattro logiche distinte: PHL, THL, PRHL e TRHL.
Dualità Semantica e Sintattica: Viene evidenziata una profonda simmetria:
- PHL e PRHL condividono condizioni di correttezza ciclica essenzialmente coinduttive (basate sull'infinità delle esecuzioni).
- THL e TRHL condividono condizioni di correttezza ciclica essenzialmente induttive (basate sulla decrescita di misure ben fondate).
- Viene mostrato che PHL e TRHL sono duali semantici, così come THL e PRHL.
Nuova Logica (PRHL): Viene introdotta e formalizzata la versione parziale della Logica di Hoare Inversa (PRHL), che sembra essere meno conosciuta o addirittura nuova rispetto alle tassonomie esistenti, definendola come il duale semantico della correttezza totale.
Trasformazione di Prove: Viene dimostrato che ogni prova assiomatica standard può essere trasformata in una prova ciclica valida, eliminando la necessità di inventare invarianti e misure di terminazione espliciti nella prova stessa (questi sono "nascosti" nella struttura ciclica e nella condizione di progresso).

4. Risultati

Correttezza (Soundness): È stato dimostrato che se una tripla è dimostrabile nel sistema ciclico (PHL, THL, PRHL o TRHL), allora è semanticamente valida. La dimostrazione si basa sul fatto che la violazione della validità porterebbe alla costruzione di un percorso infinito che viola la condizione globale di correttezza (es. una catena discendente infinita o un'esecuzione finita che non soddisfa la postcondizione).
Completezza Relativa: È stato dimostrato che se una tripla è valida semanticamente, allora è dimostrabile nel sistema ciclico. Questo segue dalla possibilità di tradurre qualsiasi prova assiomatica esistente in una prova ciclica.
Equivalenza dei Sistemi: I sistemi ciclici sono stati provati equivalenti ai loro corrispettivi assiomatici in termini di potere dimostrativo, ma offrono una struttura più adatta all'automazione poiché rimuovono il bisogno di quantificazione esistenziale sugli invarianti.

5. Significato

Questo lavoro ha un significato teorico e pratico rilevante:

Chiarezza Teorica: Mette in luce le relazioni profonde e spesso nascoste tra logica di Hoare standard e logica inversa, mostrando come le loro strutture di prova siano speculari.
Automazione: Le prove cicliche sono un paradigma promettente per l'automazione della verifica dei programmi. Eliminando la necessità di fornire invarianti di ciclo e misure di terminazione come input dell'utente (richiesto nei sistemi assiomatici tradizionali), si apre la strada a strumenti di verifica più potenti e automatizzati.
Fondamenti per Incorrectness Logic: Poiché la "Incorrectness Logic" (usata per la rilevazione automatica di bug) è un'estensione della Logica di Hoare Inversa, l'introduzione di prove cicliche per PRHL e TRHL fornisce basi solide per estendere queste tecniche alla ricerca automatica di bug, permettendo di ragionare sulla presenza di errori senza dover specificare manualmente invarianti complessi.
Unificazione: Il paper dimostra che le differenze tra correttezza parziale e totale, e tra logica diretta e inversa, possono essere gestite da un'unica infrastruttura di prova ciclica, variando solo la condizione di correttezza globale applicata ai percorsi infiniti.

In sintesi, il paper non introduce necessariamente nuove regole logiche fondamentali, ma offre una sintesi e una formalizzazione unificata che chiarisce le relazioni proof-theoretiche tra queste logiche, proponendo un approccio ciclico che è sia teoricamente elegante che potenzialmente più amichevole per l'implementazione di tool di verifica automatica.