La corrispondenza Curry-Howard

Logica
Informatica
Proofs-as-programs
Riferimenti bibliografici
La corrispondenza Curry-Howard
Flavio Zelazek
4 luglio 2009
Flavio Zelazek
La corrispondenza Curry-Howard
Logica
Informatica
Proofs-as-programs
Riferimenti bibliografici
Introduzione
La corrispondenza Curry-Howard e il paradigma
proofs-as-programs (o formulae-as-types) da essa originatosi
sono un importante esempio di transdisciplinarità, costituendo
un notevole caso di interazione “spontanea” (scoperta a
posteriori, non costruita ad hoc) tra due discipline scientifiche:
LOGICA
Teoria della dimostrazione
Deduzione naturale
Flavio Zelazek
INFORMATICA
Teoria dei tipi
λ-calcolo tipato
La corrispondenza Curry-Howard
Logica
Informatica
Proofs-as-programs
Riferimenti bibliografici
Introduzione
La corrispondenza Curry-Howard e il paradigma
proofs-as-programs (o formulae-as-types) da essa originatosi
sono un importante esempio di transdisciplinarità, costituendo
un notevole caso di interazione “spontanea” (scoperta a
posteriori, non costruita ad hoc) tra due discipline scientifiche:
LOGICA
Teoria della dimostrazione
Deduzione naturale
Flavio Zelazek
INFORMATICA
Teoria dei tipi
λ-calcolo tipato
La corrispondenza Curry-Howard
Logica
Informatica
Proofs-as-programs
Riferimenti bibliografici
Introduzione
La corrispondenza Curry-Howard e il paradigma
proofs-as-programs (o formulae-as-types) da essa originatosi
sono un importante esempio di transdisciplinarità, costituendo
un notevole caso di interazione “spontanea” (scoperta a
posteriori, non costruita ad hoc) tra due discipline scientifiche:
LOGICA
Teoria della dimostrazione
Deduzione naturale
Flavio Zelazek
INFORMATICA
Teoria dei tipi
λ-calcolo tipato
La corrispondenza Curry-Howard
Logica
Informatica
Proofs-as-programs
Riferimenti bibliografici
L’interpretazione funzionale della logica
La deduzione naturale
Contenuto
1
Logica
L’interpretazione funzionale della logica
La deduzione naturale
2
Informatica
Il λ-calcolo
I sistemi di tipi
3
Proofs-as-programs
Flavio Zelazek
La corrispondenza Curry-Howard
Logica
Informatica
Proofs-as-programs
Riferimenti bibliografici
L’interpretazione funzionale della logica
La deduzione naturale
Denotazione e senso
Due diverse concezioni del significato dei connettivi logici:
Realista (Tarski): il significato di un enunciato è dato dalle
sue condizioni di verità — l’enunciato A → B è vero
quando se è vero A allora è vero B, cioè quando A è falso
oppure B è vero (modelli – semantica – denotazione).
Costruttivista (Heyting): il significato di un enunciato è dato
dalle sue condizioni di asseribilità, cioè da cosa conta
come una sua dimostrazione — una dimostrazione di
A → B è una costruzione (ovvero, una funzione) che
trasforma ogni dimostrazione di A in una dimostrazione di
B (dimostrazioni – sintassi – senso).
Flavio Zelazek
La corrispondenza Curry-Howard
Logica
Informatica
Proofs-as-programs
Riferimenti bibliografici
L’interpretazione funzionale della logica
La deduzione naturale
Denotazione e senso
Due diverse concezioni del significato dei connettivi logici:
Realista (Tarski): il significato di un enunciato è dato dalle
sue condizioni di verità — l’enunciato A → B è vero
quando se è vero A allora è vero B, cioè quando A è falso
oppure B è vero (modelli – semantica – denotazione).
Costruttivista (Heyting): il significato di un enunciato è dato
dalle sue condizioni di asseribilità, cioè da cosa conta
come una sua dimostrazione — una dimostrazione di
A → B è una costruzione (ovvero, una funzione) che
trasforma ogni dimostrazione di A in una dimostrazione di
B (dimostrazioni – sintassi – senso).
Flavio Zelazek
La corrispondenza Curry-Howard
Logica
Informatica
Proofs-as-programs
Riferimenti bibliografici
L’interpretazione funzionale della logica
La deduzione naturale
Estensione ed intensione
Il concetto di funzione, a sua volta, può essere inteso in due
modi:
Estensionale: una funzione f da A a B va identificata col
suo grafo in senso insiemistico, cioè l’insieme di tutte le
coppie ordinate hx, y i dove x ∈ A e y = f (x) ∈ B.
Intensionale: una funzione f da A a B è una regola (una
procedura, un algoritmo, un programma) che prescrive una
computazione da effettuare per ottenere f (x) da x, cioè
che indica come trasformare un qualunque elemento di A
in un elemento di B.
Flavio Zelazek
La corrispondenza Curry-Howard
Logica
Informatica
Proofs-as-programs
Riferimenti bibliografici
L’interpretazione funzionale della logica
La deduzione naturale
Estensione ed intensione
Il concetto di funzione, a sua volta, può essere inteso in due
modi:
Estensionale: una funzione f da A a B va identificata col
suo grafo in senso insiemistico, cioè l’insieme di tutte le
coppie ordinate hx, y i dove x ∈ A e y = f (x) ∈ B.
Intensionale: una funzione f da A a B è una regola (una
procedura, un algoritmo, un programma) che prescrive una
computazione da effettuare per ottenere f (x) da x, cioè
che indica come trasformare un qualunque elemento di A
in un elemento di B.
Flavio Zelazek
La corrispondenza Curry-Howard
Logica
Informatica
Proofs-as-programs
Riferimenti bibliografici
L’interpretazione funzionale della logica
La deduzione naturale
La deduzione naturale
L’oggetto di studio della deduzione naturale (e del calcolo dei
sequenti) sono le dimostrazioni – e non solo la dimostrabilità.
Nella deduzione naturale la regola di introduzione per un
connettivo ne definisce il significato, mostrando quali sono le
condizioni di asseribilità di un enunciato che ha quel connettivo
come connettivo principale.
La deduzione naturale è dunque il tipo si sistema logico
maggiormente connesso con l’interpretazione funzionale della
logica, su cui si basa la corrispondenza Curry-Howard.
Flavio Zelazek
La corrispondenza Curry-Howard
Logica
Informatica
Proofs-as-programs
Riferimenti bibliografici
L’interpretazione funzionale della logica
La deduzione naturale
Il sistema NJ→
Il sistema di deduzione naturale NJ→ è dato dalle seguenti
regole di inferenza:
x
Ax
..
.
B
A→B
→I
A→B
B
A
→E
Le dimostrazioni sono costruite a partire da assunzioni
(etichettate dalle variabili x, y , z, . . . ) utilizzando le regole
→I e →E.
In un’applicazione della regola →I, tutte le assunzioni della
forma A etichettate dalla variabile x vengono scaricate: la
conclusione non dipende più da esse.
Flavio Zelazek
La corrispondenza Curry-Howard
Logica
Informatica
Proofs-as-programs
Riferimenti bibliografici
L’interpretazione funzionale della logica
La deduzione naturale
Il sistema NJ→
S
x :A−A
A SS
Γ, x : A − B
→I
Γ−A→B
Γ−A→B
∆ − A →E
Γ, ∆ − B
Γ−B
W
Γ, x : A − B
Γ, x : A, y : A − B
C
Γ, z : A − B
Figura: Deduzione naturale “in stile sequente”
Flavio Zelazek
La corrispondenza Curry-Howard
Logica
Informatica
Proofs-as-programs
Riferimenti bibliografici
L’interpretazione funzionale della logica
La deduzione naturale
Normalizzazione
La normalizzazione è la procedura che elimina certe
“deviazioni” nelle dimostrazioni. Tali “deviazioni” consistono in
applicazioni ridondanti di regole: tipicamente, l’introduzione di
un connettivo seguita immediatamente da un’eliminazione di
quello stesso connettivo.
Le dimostrazioni normali hanno tutte la stessa forma (sono
scomponibili in una parte analitica e in un a parte sintetica) e
godono di importanti proprietà, tra cui la proprietà della
sottoformula.
Flavio Zelazek
La corrispondenza Curry-Howard
Logica
Informatica
Proofs-as-programs
Riferimenti bibliografici
L’interpretazione funzionale della logica
La deduzione naturale
Regole di conversione
Una dimostrazione viene ridotta in forma normale mediante la
ripetuta applicazione di certe regole di riscrittura, dette regole
di conversione. Nel caso di NJ→ abbiamo quest’unica regola:
→-conv:
D1
A
Ax
D2
B
x
→I
A → B →E
B
;
D1
A
D2
B
(la sottodimostrazione D1 viene sostituita al posto di ognuna
delle 0 o più occorrenze di A etichettate con x)
Flavio Zelazek
La corrispondenza Curry-Howard
Logica
Informatica
Proofs-as-programs
Riferimenti bibliografici
Il λ-calcolo
I sistemi di tipi
Contenuto
1
Logica
L’interpretazione funzionale della logica
La deduzione naturale
2
Informatica
Il λ-calcolo
I sistemi di tipi
3
Proofs-as-programs
Flavio Zelazek
La corrispondenza Curry-Howard
Logica
Informatica
Proofs-as-programs
Riferimenti bibliografici
Il λ-calcolo
I sistemi di tipi
Il λ-calcolo
Il λ-calcolo, nato come teoria generale delle funzioni, oggi è
uno dei principali modelli di calcolo (insieme alla teoria della
ricorsività e alle macchine di Turing), ovvero quegli insiemi di
metodologie, modelli e teorie formali attraverso cui viene
spiegato ed analizzato il concetto generale di computazione.
Inoltre, grazie al suo misto di potenza espressiva e semplicità
sintattica, esso funge da linguaggio paradigmatico di
programmazione (soprattutto nel caso dei linguaggi di
programmazione funzionale).
Flavio Zelazek
La corrispondenza Curry-Howard
Logica
Informatica
Proofs-as-programs
Riferimenti bibliografici
Il λ-calcolo
I sistemi di tipi
La λ-notazione
Gli oggetti studiati dal λ-calcolo sono i λ-termini, costruiti a
partire da variabili mediante le seguenti operazioni:
Astrazione: a partire dal termine t si può formare il termine
λx. t astraendo dalla variabile x (di cui t contiene 0
o più occorrenze). Il termine λx. t rappresenta la
funzione che, per ogni x, applicata a x dà come
risultato t.
Applicazione: a partire dai termini t e s si può formare il
termine ts. Il termine ts rappresenta l’applicazione
della funzione t all’argomento s.
Flavio Zelazek
La corrispondenza Curry-Howard
Logica
Informatica
Proofs-as-programs
Riferimenti bibliografici
Il λ-calcolo
I sistemi di tipi
La β-riduzione
La computazione (o β-riduzione) di un λ-termine ha luogo
applicando ripetutamente ai suoi sottotermini della forma
(λx. t)s (chiamati redex, ossia “espressioni riducibili”) la
seguente regola di riscrittura, detta regola di β-conversione:
(λx. t)s t[s/x]
Un “passo di computazione” dunque consiste semplicemente
nella sostituzione dell’argomento s al posto della variabile x nel
corpo della funzione λx. t (cioè in t).
Flavio Zelazek
La corrispondenza Curry-Howard
Logica
Informatica
Proofs-as-programs
Riferimenti bibliografici
Il λ-calcolo
I sistemi di tipi
Programmare col λ-calcolo
Per ogni n ∈ N, il numerale di Church n che rappresenta n è
definito così:
n ≡ λx. λy . x n y
(t n s denota l’applicazione di t a s iterata n volte).
La funzione (il programma) che calcola il successore di un
numerale di Church è definita così:
succ ≡ λn. λx. λy . x(nxy )
Un esempio di computazione:
succ 1 ≡ succ λw. λz. wz
λx. λy . x((λw. λz. wz)xy )
λx. λy . x((λz. xz)y )
λx. λy . x(xy ) ≡ 2
Flavio Zelazek
La corrispondenza Curry-Howard
Logica
Informatica
Proofs-as-programs
Riferimenti bibliografici
Il λ-calcolo
I sistemi di tipi
Tipi di dati
Un tipo di dati è una classe di dati che hanno lo stesso
“comportamento computazionale”. Per esempio, Int è il tipo
degli interi, e Bool è il tipo dei booleani.
Se A e B sono tipi, il tipo funzione A → B rappresenta lo spazio
delle funzioni da A a B. Così, Int → Bool è il tipo di un
programma che prende come input un intero e dà come output
un booleano (per esempio il programma che calcola se un
numero è primo oppure no).
Il tipo di un programma ne costituisce dunque la specifica in un
senso molto basilare. Questa permette di farlo interagire con
altri programmi in modo coerente a prescindere dalla
conoscenza del suo contenuto (il programma è un modulo, e il
suo tipo è l’interfaccia del modulo).
Flavio Zelazek
La corrispondenza Curry-Howard
Logica
Informatica
Proofs-as-programs
Riferimenti bibliografici
Il λ-calcolo
I sistemi di tipi
Il type-checking
Un sistema di tipi è una classificazione delle espressioni di un
linguaggio di programmazione in base a tipi di dati, la quale
serve a garantire che durante l’esecuzione di un programma
non si verifichino certi errori di natura molto basilare, gli errori di
tipo. Essi avvengono quando si fanno interagire due programmi
con tipi incompatibili (per esempio quando si usa l’output di un
programma di tipo Int → Bool come input di un programma di
tipo Int → Int).
Questo obiettivo è conseguito definendo delle regole di
type-checking, che servono a calcolare i tipi delle espressioni
che occorrono in un programma e a verificare che non ci siano
delle discordanze tra essi.
Flavio Zelazek
La corrispondenza Curry-Howard
Logica
Informatica
Proofs-as-programs
Riferimenti bibliografici
Il λ-calcolo
I sistemi di tipi
Il λ-calcolo tipato
È possibile arricchire il λ-calcolo con un sistema di tipi,
ottenendo il λ-calcolo tipato, in cui a ciascun λ-termine viene
associato un tipo (scelto tra i tipi atomici e quelli formati a
partire da questi mediante i costruttori di tipo, ad es. →).
Un giudizio di tipo è un’espressione della forma
x1 : A1 , . . . , xn : An I t : B
Il suo significato è che, assumendo che le variabili x1 , . . . , xn
(che eventualmente occorrono libere in t) siano rispettivamente
di tipo A1 , . . . , An , il λ-termine t è di tipo B.
Una derivazione di tipo è una derivazione costruita mediante le
regole di type-checking; essa corrisponde alla costruzione del
λ-termine con cui si conclude, e all’assegnazione a questo di
un tipo conformemente con esse.
Flavio Zelazek
La corrispondenza Curry-Howard
Logica
Informatica
Proofs-as-programs
Riferimenti bibliografici
Il λ-calcolo
I sistemi di tipi
Il λ-calcolo tipato semplice λβ →
x :AIx :A
VAR
Γ, x : A I t : B
A BS
Γ I λx. t : A → B
ΓIt :A→B
∆Is:A
A PP
Γ, ∆ I ts : B
ΓIt :B
E NV-W
Γ, x : A I t : B
Γ, x : A, y : A I t : B
E NV-C
Γ, z : A I t[z/x, z/y ] : B
Figura: Regole di type-checking per λβ →
Flavio Zelazek
La corrispondenza Curry-Howard
Logica
Informatica
Proofs-as-programs
Riferimenti bibliografici
Il λ-calcolo
I sistemi di tipi
La β-riduzione in λβ →
La β-riduzione nel λ-calcolo tipato semplice è sostanzialmente
immutata; ma ora può esser meglio analizzata come
trasformazione delle derivazioni di tipo:
β-conv:
Γ, x : A
D1
t :B
A BS
λx. t : A → B
(λx. t)s : B
∆
D2
s:A
A PP
Γ, ∆
D1 [D2 /x]
t[s/x] : B
(la notazione D1 [D2 /x] rappresenta la derivazione D1 in cui
tutte le (eventuali) assunzioni etichettate con x sono state
sostituite dalla derivazione D2 avente conclusione s : A)
Flavio Zelazek
La corrispondenza Curry-Howard
Logica
Informatica
Proofs-as-programs
Riferimenti bibliografici
Contenuto
1
Logica
L’interpretazione funzionale della logica
La deduzione naturale
2
Informatica
Il λ-calcolo
I sistemi di tipi
3
Proofs-as-programs
Flavio Zelazek
La corrispondenza Curry-Howard
Logica
Informatica
Proofs-as-programs
Riferimenti bibliografici
Nascita della corrispondenza Curry-Howard
La corrispondenza Curry-Howard si articola, sia
concettualmente che storicamente, nei seguenti quattro punti:
1
Interpretazione funzionale della logica, o interpretazione
BHK (Brouwer-Heyting-Kolmogorov).
2
Corrispondenza tra formule e tipi (logica combinatoria di
Curry; “interpretazione Dialectica” di Gödel).
3
Corrispondenza tra eliminazione del taglio
(normalizzazione) e β-riduzione (Tait).
4
Corrispondenza tra dimostrazioni e λ-termini (Howard).
La corrispondenza che sussiste non solo tra dimostrazioni e
λ-termini, ma anche tra le operazioni che si possono svolgere
su di essi (normalizzazione e β-riduzione), permette di
individuare un vero e proprio isomorfismo:
Flavio Zelazek
La corrispondenza Curry-Howard
Logica
Informatica
Proofs-as-programs
Riferimenti bibliografici
Nascita della corrispondenza Curry-Howard
La corrispondenza Curry-Howard si articola, sia
concettualmente che storicamente, nei seguenti quattro punti:
1
Interpretazione funzionale della logica, o interpretazione
BHK (Brouwer-Heyting-Kolmogorov).
2
Corrispondenza tra formule e tipi (logica combinatoria di
Curry; “interpretazione Dialectica” di Gödel).
3
Corrispondenza tra eliminazione del taglio
(normalizzazione) e β-riduzione (Tait).
4
Corrispondenza tra dimostrazioni e λ-termini (Howard).
La corrispondenza che sussiste non solo tra dimostrazioni e
λ-termini, ma anche tra le operazioni che si possono svolgere
su di essi (normalizzazione e β-riduzione), permette di
individuare un vero e proprio isomorfismo:
Flavio Zelazek
La corrispondenza Curry-Howard
Logica
Informatica
Proofs-as-programs
Riferimenti bibliografici
Nascita della corrispondenza Curry-Howard
La corrispondenza Curry-Howard si articola, sia
concettualmente che storicamente, nei seguenti quattro punti:
1
Interpretazione funzionale della logica, o interpretazione
BHK (Brouwer-Heyting-Kolmogorov).
2
Corrispondenza tra formule e tipi (logica combinatoria di
Curry; “interpretazione Dialectica” di Gödel).
3
Corrispondenza tra eliminazione del taglio
(normalizzazione) e β-riduzione (Tait).
4
Corrispondenza tra dimostrazioni e λ-termini (Howard).
La corrispondenza che sussiste non solo tra dimostrazioni e
λ-termini, ma anche tra le operazioni che si possono svolgere
su di essi (normalizzazione e β-riduzione), permette di
individuare un vero e proprio isomorfismo:
Flavio Zelazek
La corrispondenza Curry-Howard
Logica
Informatica
Proofs-as-programs
Riferimenti bibliografici
Nascita della corrispondenza Curry-Howard
La corrispondenza Curry-Howard si articola, sia
concettualmente che storicamente, nei seguenti quattro punti:
1
Interpretazione funzionale della logica, o interpretazione
BHK (Brouwer-Heyting-Kolmogorov).
2
Corrispondenza tra formule e tipi (logica combinatoria di
Curry; “interpretazione Dialectica” di Gödel).
3
Corrispondenza tra eliminazione del taglio
(normalizzazione) e β-riduzione (Tait).
4
Corrispondenza tra dimostrazioni e λ-termini (Howard).
La corrispondenza che sussiste non solo tra dimostrazioni e
λ-termini, ma anche tra le operazioni che si possono svolgere
su di essi (normalizzazione e β-riduzione), permette di
individuare un vero e proprio isomorfismo:
Flavio Zelazek
La corrispondenza Curry-Howard
Logica
Informatica
Proofs-as-programs
Riferimenti bibliografici
Nascita della corrispondenza Curry-Howard
La corrispondenza Curry-Howard si articola, sia
concettualmente che storicamente, nei seguenti quattro punti:
1
Interpretazione funzionale della logica, o interpretazione
BHK (Brouwer-Heyting-Kolmogorov).
2
Corrispondenza tra formule e tipi (logica combinatoria di
Curry; “interpretazione Dialectica” di Gödel).
3
Corrispondenza tra eliminazione del taglio
(normalizzazione) e β-riduzione (Tait).
4
Corrispondenza tra dimostrazioni e λ-termini (Howard).
La corrispondenza che sussiste non solo tra dimostrazioni e
λ-termini, ma anche tra le operazioni che si possono svolgere
su di essi (normalizzazione e β-riduzione), permette di
individuare un vero e proprio isomorfismo:
Flavio Zelazek
La corrispondenza Curry-Howard
Logica
Informatica
Proofs-as-programs
Riferimenti bibliografici
Nascita della corrispondenza Curry-Howard
La corrispondenza Curry-Howard si articola, sia
concettualmente che storicamente, nei seguenti quattro punti:
1
Interpretazione funzionale della logica, o interpretazione
BHK (Brouwer-Heyting-Kolmogorov).
2
Corrispondenza tra formule e tipi (logica combinatoria di
Curry; “interpretazione Dialectica” di Gödel).
3
Corrispondenza tra eliminazione del taglio
(normalizzazione) e β-riduzione (Tait).
4
Corrispondenza tra dimostrazioni e λ-termini (Howard).
La corrispondenza che sussiste non solo tra dimostrazioni e
λ-termini, ma anche tra le operazioni che si possono svolgere
su di essi (normalizzazione e β-riduzione), permette di
individuare un vero e proprio isomorfismo:
Flavio Zelazek
La corrispondenza Curry-Howard
Logica
Informatica
Proofs-as-programs
Riferimenti bibliografici
L’isomorfismo Curry-Howard
DEDUZIONE NATURALE
formule
dimostrazioni
normalizzazione
Flavio Zelazek
λ-CALCOLO TIPATO
tipi
λ-termini
β-riduzione
La corrispondenza Curry-Howard
Logica
Informatica
Proofs-as-programs
Riferimenti bibliografici
L’isomorfismo Curry-Howard
DEDUZIONE NATURALE
formule
dimostrazioni
normalizzazione
Flavio Zelazek
λ-CALCOLO TIPATO
tipi
λ-termini
β-riduzione
La corrispondenza Curry-Howard
Logica
Informatica
Proofs-as-programs
Riferimenti bibliografici
L’isomorfismo Curry-Howard
DEDUZIONE NATURALE
formule
dimostrazioni
normalizzazione
Flavio Zelazek
λ-CALCOLO TIPATO
tipi
λ-termini
β-riduzione
La corrispondenza Curry-Howard
Logica
Informatica
Proofs-as-programs
Riferimenti bibliografici
L’isomorfismo Curry-Howard
DEDUZIONE NATURALE
formule
dimostrazioni
normalizzazione
Flavio Zelazek
λ-CALCOLO TIPATO
tipi
λ-termini
β-riduzione
La corrispondenza Curry-Howard
Logica
Informatica
Proofs-as-programs
Riferimenti bibliografici
La decorazione: dalle regole di NJ→ . . .
x :A−
Γ, x : A − B
→I
Γ−
A→B
A
Γ−
A SS
A→B
Γ, ∆ −
∆−
B
Γ, x : A, y : A −
Γ, z : A −
Γ− B
W
Γ, x : A − B
Figura: Il sistema NJ→
S
Flavio Zelazek
La corrispondenza Curry-Howard
A
B
B
→E
C
Logica
Informatica
Proofs-as-programs
Riferimenti bibliografici
. . . alle regole di type-checking per λβ →
x :A−x :A
A SS
Γ, x : A − t : B
→I
Γ − λx. t : A → B
Γ−t :A→B
∆−s:A
→E
Γ, ∆ − ts : B
Γ−t :B
W
Γ, x : A − t : B
Γ, x : A, y : A − t : B
C
Γ, z : A − t[z/x, z/y ] : B
Figura: Sistema di assegnazione di termini per NJ→
S
Flavio Zelazek
La corrispondenza Curry-Howard
Logica
Informatica
Proofs-as-programs
Riferimenti bibliografici
Curry-Howard: importanza pratica
Il paradigma proofs-as-programs permette una fruttuosa interazione
tra logica e informatica (teorica), consistente nello “scambio” di
risultati e metodi tra le due discipline:
Sul versante della logica, ha fatto sì che essa venisse studiata
sempre di più con gli strumenti della semantica denotazionale e
della teoria delle categorie. In particolare, la semantica
denotazionale (la quale modellizza il concetto di dimostrazione e
non solo quello di dimostrabilità) è alla base della nascita della
logica lineare.
Sul versante dell’informatica, ha comportato un maggior rigore
nella progettazione dei linguaggi di programmazione, dovuto al
fatto che questa è sempre più “guidata” da un sistema logico
sottostante. Inoltre, alcune tra le proprietà fondamentali dei
linguaggi di programmazione (per esempio, la loro complessità
computazionale) possono essere studiate come proprietà dei
sistemi logici corrispondenti.
Flavio Zelazek
La corrispondenza Curry-Howard
Logica
Informatica
Proofs-as-programs
Riferimenti bibliografici
Curry-Howard: importanza pratica
Il paradigma proofs-as-programs permette una fruttuosa interazione
tra logica e informatica (teorica), consistente nello “scambio” di
risultati e metodi tra le due discipline:
Sul versante della logica, ha fatto sì che essa venisse studiata
sempre di più con gli strumenti della semantica denotazionale e
della teoria delle categorie. In particolare, la semantica
denotazionale (la quale modellizza il concetto di dimostrazione e
non solo quello di dimostrabilità) è alla base della nascita della
logica lineare.
Sul versante dell’informatica, ha comportato un maggior rigore
nella progettazione dei linguaggi di programmazione, dovuto al
fatto che questa è sempre più “guidata” da un sistema logico
sottostante. Inoltre, alcune tra le proprietà fondamentali dei
linguaggi di programmazione (per esempio, la loro complessità
computazionale) possono essere studiate come proprietà dei
sistemi logici corrispondenti.
Flavio Zelazek
La corrispondenza Curry-Howard
Logica
Informatica
Proofs-as-programs
Riferimenti bibliografici
Curry-Howard: importanza pratica
Il paradigma proofs-as-programs permette una fruttuosa interazione
tra logica e informatica (teorica), consistente nello “scambio” di
risultati e metodi tra le due discipline:
Sul versante della logica, ha fatto sì che essa venisse studiata
sempre di più con gli strumenti della semantica denotazionale e
della teoria delle categorie. In particolare, la semantica
denotazionale (la quale modellizza il concetto di dimostrazione e
non solo quello di dimostrabilità) è alla base della nascita della
logica lineare.
Sul versante dell’informatica, ha comportato un maggior rigore
nella progettazione dei linguaggi di programmazione, dovuto al
fatto che questa è sempre più “guidata” da un sistema logico
sottostante. Inoltre, alcune tra le proprietà fondamentali dei
linguaggi di programmazione (per esempio, la loro complessità
computazionale) possono essere studiate come proprietà dei
sistemi logici corrispondenti.
Flavio Zelazek
La corrispondenza Curry-Howard
Logica
Informatica
Proofs-as-programs
Riferimenti bibliografici
Curry-Howard: rilevanza filosofica
1
I sistemi logici a bassa complessità (tra cui principalmente le
logiche leggere, tutte basate sulla logica lineare) permettono di
dare una caratterizzazione puramente logica, attraverso la
corrispondenza Curry-Howard, di alcune classi di complessità –
tra cui la classe P dei problemi algoritmici risolvibili in tempo
polinomiale (ovvero in modo efficiente). . .
2
. . . La nostra via via maggiore comprensione della classe P ci
avvicina alla soluzione di uno dei più affascinanti “problemi del
?
millennio”, il problema P = NP. . .
3
. . . La soluzione di questo problema è strettamente collegata alla
realizzabilità di una versione limitata del programma di Hilbert
(cfr. lettera di Gödel a Von Neumann, 1956).
Flavio Zelazek
La corrispondenza Curry-Howard
Logica
Informatica
Proofs-as-programs
Riferimenti bibliografici
Curry-Howard: rilevanza filosofica
1
I sistemi logici a bassa complessità (tra cui principalmente le
logiche leggere, tutte basate sulla logica lineare) permettono di
dare una caratterizzazione puramente logica, attraverso la
corrispondenza Curry-Howard, di alcune classi di complessità –
tra cui la classe P dei problemi algoritmici risolvibili in tempo
polinomiale (ovvero in modo efficiente). . .
2
. . . La nostra via via maggiore comprensione della classe P ci
avvicina alla soluzione di uno dei più affascinanti “problemi del
?
millennio”, il problema P = NP. . .
3
. . . La soluzione di questo problema è strettamente collegata alla
realizzabilità di una versione limitata del programma di Hilbert
(cfr. lettera di Gödel a Von Neumann, 1956).
Flavio Zelazek
La corrispondenza Curry-Howard
Logica
Informatica
Proofs-as-programs
Riferimenti bibliografici
Curry-Howard: rilevanza filosofica
1
I sistemi logici a bassa complessità (tra cui principalmente le
logiche leggere, tutte basate sulla logica lineare) permettono di
dare una caratterizzazione puramente logica, attraverso la
corrispondenza Curry-Howard, di alcune classi di complessità –
tra cui la classe P dei problemi algoritmici risolvibili in tempo
polinomiale (ovvero in modo efficiente). . .
2
. . . La nostra via via maggiore comprensione della classe P ci
avvicina alla soluzione di uno dei più affascinanti “problemi del
?
millennio”, il problema P = NP. . .
3
. . . La soluzione di questo problema è strettamente collegata alla
realizzabilità di una versione limitata del programma di Hilbert
(cfr. lettera di Gödel a Von Neumann, 1956).
Flavio Zelazek
La corrispondenza Curry-Howard
Logica
Informatica
Proofs-as-programs
Riferimenti bibliografici
Bibliografia
[1] Jean Gallier. Constructive logics Part I: A tutorial on proof
systems and typed -calculi. Theoretical Computer Science,
110:249–339, 1993.
[2] Jean-Yves Girard, Paul Taylor, e Yves Lafont. Proofs and types.
Cambridge University Press, 1989.
[3] Benjamin C. Pierce. Types and Programming Languages. The
MIT Press, 2002.
[4] Steven Rudich. Complexity Theory: From Gödel to Feynman. In
Computational Complexity. A cura di Steven Rudich e Avi
Wigderson. American Mathematical Society, 2004.
[5] Philip Wadler. Proofs are Programs: 19th Century Logic and 21st
Century Computing. Reperibile su
http://homepages.inf.ed.ac.uk/wadler/, 2000.
Flavio Zelazek
La corrispondenza Curry-Howard