Quali sono i più interessanti equivalenze derivanti dalla Curry-Howard Isomorfismo?

https://stackoverflow.com/questions/2969140

24-10-2019
|

Domanda

Sono venuto sulla Curry-Howard Isomorfismo relativamente tardi nella mia la programmazione della vita, e forse ciò contribuisce a mio essere totalmente affascinato da essa. Ciò implica che per ogni concetto di programmazione esiste un analogo precisa logica formale, e viceversa. Ecco un elenco di "base" di tali analogie, la parte superiore della mia testa:

program/definition        | proof
type/declaration          | proposition
inhabited type            | theorem/lemma
function                  | implication
function argument         | hypothesis/antecedent
function result           | conclusion/consequent
function application      | modus ponens
recursion                 | induction
identity function         | tautology
non-terminating function  | absurdity/contradiction
tuple                     | conjunction (and)
disjoint union            | disjunction (or)          -- corrected by Antal S-Z
parametric polymorphism   | universal quantification

Quindi, alla mia domanda:? Che cosa sono alcune delle implicazioni più interessanti / oscuri di questo isomorfismo Non sono un logico, quindi sono sicuro che ho solo scalfito la superficie con questa lista .

Per esempio, qui ci sono alcune nozioni di programmazione per il quale io sono a conoscenza di nomi concisi in logica:

currying                  | "((a & b) => c) iff (a => (b => c))"
scope                     | "known theory + hypotheses"

E qui ci sono alcuni concetti logici che non ho abbastanza appuntati verso il basso in termini di programmazione:

primitive type?           | axiom
set of valid programs?    | theory

Modifica:

Qui ci sono alcuni più equivalenze raccolti dalle risposte:

function composition      | syllogism                -- from Apocalisp
continuation-passing      | double negation          -- from camccann

Soluzione

Dal momento che esplicitamente chiesto per la maggior parte quelli interessanti e oscuri:

È possibile estendere C-H a molte logiche e formulazioni di logiche interessanti per ottenere davvero una vasta gamma di corrispondenze. Qui ho cercato di mettere a fuoco su alcuni dei più interessanti piuttosto che sulla oscuro, più un paio di quelli fondamentali, che non sono venuti ancora.

evaluation             | proof normalisation/cut-elimination
variable               | assumption
S K combinators        | axiomatic formulation of logic   
pattern matching       | left-sequent rules 
subtyping              | implicit entailment (not reflected in expressions)
intersection types     | implicit conjunction
union types            | implicit disjunction
open code              | temporal next
closed code            | necessity
effects                | possibility
reachable state        | possible world
monadic metalanguage   | lax logic
non-termination        | truth in an unobservable possible world
distributed programs   | modal logic S5/Hybrid logic
meta variables         | modal assumptions
explicit substitutions | contextual modal necessity
pi-calculus            | linear logic

EDIT: Un riferimento lo consiglierei a chiunque sia interessato a saperne di più sulle estensioni di C-H:

"Una Judgmental Ricostruzione di Modal Logic" http: //www.cs .cmu.edu / ~ fp / documenti / mscs00.pdf - questo è un ottimo punto di partenza perché parte da principi primi e la gran parte di essa si propone di essere accessibile ai non-logici / teorici lingua. (Io sono il secondo autore, però, quindi sono di parte).

Altri suggerimenti

Si sta infangando le cose un po 'per quanto riguarda nontermination. La falsità è rappresentato da tipi disabitate , che per definizione non può essere non fatale perché non c'è niente di quel tipo di valutare, in primo luogo.

Non terminazione rappresenta contraddizione - una logica incoerente. Una logica incoerente sarà ovviamente permetterà di dimostrare nulla , tra cui la falsità, però.

Ignorando incongruenze, sistemi di tipo generalmente corrispondono a un intuizionistico logica , e sono necessariamente costruttivista , il che significa che certi pezzi di logica classica non possono essere espresse direttamente, se non del tutto. D'altra parte questo è utile, perché se un tipo è una prova costruttiva valida, quindi un termine di quel tipo è un mezzo di costruzione di tutto ciò che hai dimostrato l'esistenza di .

Una delle caratteristiche principali del sapore costruttivista è che doppia negazione non equivale a non-negazione. Infatti, negazione è raramente una primitiva in un sistema di tipo, così invece possiamo rappresentare come implicante falsità, per esempio, diventa not P P -> Falsity. Doppia negazione sarebbe quindi una funzione di tipo (P -> Falsity) -> Falsity, che chiaramente non è equivalente a qualcosa di appena tipo P.

Tuttavia, c'è una svolta interessante su questo! In una lingua con il polimorfismo parametrico, le variabili di tipo spaziano su tutti i tipi possibili, comprese quelle disabitate, quindi un tipo completamente polimorfico come ∀a. a è, in un certo senso, quasi-falso. Che importa se scriviamo doppio quasi-negazione utilizzando il polimorfismo? Otteniamo un tipo che assomiglia a questo: ∀a. (P -> a) -> a. È che equivale a qualcosa di tipo P? In effetti è , semplicemente applicare alla funzione identità.

Ma qual è il punto? Perché scrivere un tipo del genere? Ha media nulla in termini di programmazione? Ebbene, si può pensare ad esso come una funzione che ha già qualcosa di tipo P da qualche parte, e si ha bisogno di dare una funzione che prende P come argomento, con il tutto essendo polimorfa nel tipo di risultato finale. In un certo senso, rappresenta una sospesa calcolo , attendere il resto da fornire. In questo senso, questi calcoli sospese possono essere composti insieme, passati in giro, invocato, qualunque. Questo dovrebbe iniziare a suonare familiare ai fan di alcune lingue, come Scheme o Ruby - perché ciò vuol dire è che doppia negazione corrisponde a continuazione-passing style , ed in effetti il ??tipo ho dato sopra è esattamente la monade prosecuzione in Haskell.

Il grafico non è giusto; in molti casi hai confuso i tipi con i termini.

function type              implication
function                   proof of implication
function argument          proof of hypothesis
function result            proof of conclusion
function application RULE  modus ponens
recursion                  n/a [1]
structural induction       fold (foldr for lists)
mathematical induction     fold for naturals (data N = Z | S N)
identity function          proof of A -> A, for all A
non-terminating function   n/a [2]
tuple                      normal proof of conjunction
sum                        disjunction
n/a [3]                    first-order universal quantification
parametric polymorphism    second-order universal quantification
currying                   (A,B) -> C -||- A -> (B -> C), for all A,B,C
primitive type             axiom
types of typeable terms    theory
function composition       syllogism
substitution               cut rule
value                      normal proof

[1] La logica di un linguaggio funzionale Turing-completo è incoerente. Ricorsione ha corrispondenza teorie coerenti. In una teoria della dimostrazione logica incoerente / alienato che si potrebbe chiamare una regola che causa incoerenza / unsoundness.

[2] Di nuovo, questa è una conseguenza di completezza. Questa sarebbe una prova di un anti-teorema se la logica fosse coerente -. Quindi, non può esistere

[3] non esiste in linguaggi funzionali, dal momento che Elide primo ordine logico caratteristiche: tutto quantificazione e parametrizzazione viene fatto su formule. Se tu avessi le caratteristiche del primo ordine, non ci sarebbe una specie diversa da *, * -> *, ecc .; il tipo di elementi del dominio del discorso. Per esempio, in Father(X,Y) :- Parent(X,Y), Male(X), X e la gamma Y sul dominio del discorso (lo chiamano Dom), e Male :: Dom -> *.

function composition      | syllogism

Mi piace molto questa domanda. Non conosco un bel po ', ma ho un paio di cose (assistiti da l'articolo di Wikipedia , che ha alcuni tavoli puliti e quali stesso):

Credo che tipi della somma / sindacali ( per es. data Either a b = Left a | Right b) sono equivalenti a inclusiva disgiunzione. E, se non sto molto bene conosco Curry-Howard, credo che questo lo dimostra. Si consideri la seguente funzione:
```
andImpliesOr :: (a,b) -> Either a b
andImpliesOr (a,_) = Left a
```
Se ho capito le cose correttamente, il tipo dice che ( a ? b ) ? ( a ? b ) e la definizione dice che questo è vero, dove ? è o inclusiva o esclusiva o, a seconda di quale Either rappresenta. Hai Either rappresentanza esclusiva o, ?; tuttavia, ( a ? b ) ? ( a ? b ). Per esempio, ? ? ? = ?, ma ? ? ? = ?, e ? ? ?. In altre parole, se entrambi un e b sono vere, allora l'ipotesi è vera ma la conclusione è falsa, e quindi questa implicazione deve essere falsa. Tuttavia, chiaramente, ( a ? b ) ? ( a ? b ), dal momento che se entrambi a e b sono vere, allora almeno una è vera. Così, se i sindacati discriminati sono una qualche forma di separazione, devono essere la varietà compreso. Credo che questo vale come prova, ma sento più che libero di disabuse me di questo concetto.
Allo stesso modo, le definizioni di per tautologia e l'assurdo come la funzione identità e funzioni non fatale, rispettivamente, sono un po 'fuori. Il vero formula è rappresentato dalla tipo di unità , che è del tipo che ha un solo elemento (data ⊤ = ⊤; () spesso farro e / o Unit in linguaggi funzionali). Questo ha senso: da quel tipo è garantito per essere abitata, e dal momento che c'è una sola possibile abitante, deve essere vero. La funzione di identità solo rappresenta il particolare tautologia che a ? a .

Il tuo commento su funzioni non terminanti è, a seconda di cosa esattamente si intende, più fuori. funzioni di Curry-Howard sul sistema tipo, ma non di terminazione non è codificato lì. Secondo Wikipedia , si tratta di non-terminazione è un problema, come l'aggiunta produce incoerente logiche ( es , posso definire wrong :: a -> b da wrong x = wrong x, e quindi “dimostrare” che un ? b per ogni un e b ). Se questo è ciò che si intende per “assurdità”, allora sei esattamente corretto. Se invece si intende la dichiarazione falsa, allora ciò che si vuole invece è qualsiasi tipo disabitata, per es. qualcosa di definito da data ⊥, cioè un tipo di dati senza alcun modo per costruirlo. Questo assicura che non ha valori affatto, e quindi deve essere disabitata, che è equivalente a falso. Penso che probabilmente si potrebbe usare anche a -> b, dal momento che se proibiamo non fatale funzioni, allora questo è anche disabitata, ma non sono sicuro al 100%.
Wikipedia dice che gli assiomi sono codificati in due modi diversi, a seconda da come si interpreta Curry-Howard: sia nei combinatori o nelle variabili. Credo che i mezzi vista combinatore che le funzioni primitive c'è dato codificare le cose che possiamo dire di default (simile al modo in cui modus ponens è un assioma perché un'applicazione funzione primitiva). E io che che la vista variabile può in realtà significare la stessa cosa-combinatori, dopo tutto, sono variabili globali, che sono solo particolari funzioni. Per quanto riguarda i tipi primitivi: se sto pensando a questo correttamente, allora penso che i tipi primitivi sono i soggetti-oggetti primitiviche stiamo cercando di dimostrare le cose circa.
Secondo la mia logica e la classe semantica, il fatto che ( a ? b ) ? c = un ? ( b ? c ) (e anche che b ? ( a ? c )) si chiama la legge di equivalenza esportazione, almeno in prove deduzione naturale. Non ho notato nel momento in cui è stato appena strigliando-vorrei avere, perché che figata!
Mentre ora abbiamo un modo per rappresentare inclusiva disgiunzione, non abbiamo un modo per rappresentare la varietà esclusiva. Dovremmo essere in grado di utilizzare la definizione di disgiunzione esclusiva a rappresentarlo: a ? b = ( a ? b ) ? ¬ ( a ? b ). Non so come la negazione di scrittura, ma so che ¬ p = p ? ?, ed entrambi implicazione e la falsità sono facili. Dovremmo quindi in grado di rappresentare disgiunzione esclusiva da:
```
data ⊥
data Xor a b = Xor (Either a b) ((a,b) -> ⊥)
```
Questo definisce ⊥ essere il tipo vuota senza valori, che corrisponde alla falsità; Xor viene quindi definito in modo da contenere sia ( e ) Either un un o b ( o ) e una funzione ( implicazione ) da (a, b) ( e ) per il tipo di fondo ( false ). Tuttavia, non ho idea di che cosa questo mezzi . ( Modifica 1: Ora io, vedo il paragrafo successivo) Dal momento che ci sono valori di tipo (a,b) -> ⊥ (ci sono?), non riesco a capire che cosa questo significherebbe in un programma. Qualcuno sa un modo migliore di pensare sia questa definizione o di un altro ( Modifica 1:? Sì, camccann .)

Modifica 1: Grazie a di camccann risposta (più in particolare, i commenti che ha lasciato su di esso a darmi una mano), mi sembra di vedere che cosa sta succedendo qui. Per costruire un valore di tipo Xor a b, è necessario fornire due cose. In primo luogo, una testimonianza dell'esistenza di un elemento di una a o b come primo argomento; cioè un Left a o un Right b. E in secondo luogo, una prova che non ci sono elementi di entrambi i tipi a e b, in altre parole, una prova che (a,b) è disabitata, come secondo argomento. Dal momento che sarà solo in grado di scrivere una funzione da (a,b) -> ⊥ se (a,b) è disabitata, che cosa significa per che per essere il caso? Ciò significherebbe che una parte di un oggetto di tipo (a,b) non potrebbe essere costruito; in altre parole, che almeno uno, e possibilmente entrambi, di a e b sono disabitata pure! In questo caso, se stiamo pensando di pattern matching, non si poteva forse pattern-partita su tale tupla: supponendo che b è disabitata, cosa faremmo scrivere che potrebbe corrispondere alla seconda parte di tale tupla? Quindi, non possiamo pattern match contro di essa, che può aiutare a capire perché questo lo rende disabitata. Ora, l'unico modo per avere una funzione totale che non prende argomenti (come questo obbligo, dal momento che (a,b) è disabitata) è per il risultato sia di un tipo disabitata troppo se pensiamo a questo da un punto di vista pattern-matching , questo significa che, anche se la funzione non ha casi, non c'è possibile corpo potrebbe avere sia, e quindi su OK di tutto.

Un sacco di questo mi sta pensando ad alta voce / dimostrando (si spera) le cose al volo, ma spero che sia utile. Consiglio vivamente laarticolo di Wikipedia ; Non ho letto attraverso di essa in qualsiasi tipo di dettagli, ma le sue tavole sono davvero un bel riassunto, ed è molto accurata.

Ecco un po 'oscura quello che mi sorprende non è stato portato in precedenza:. "Classici" funzionali corrisponde programmazione reattivi a logica temporale

Naturalmente, se non sei un filosofo, matematico programmatore funzionale, ossessivo, questo probabilmente porta in primo piano alcune domande più.

Quindi, prima di tutto: che cosa è la programmazione funzionale reattivo? E 'un modo dichiarativo di lavorare con valori che variano nel tempo . Ciò è utile per scrivere cose come interfacce utente perché gli ingressi provenienti dall'utente sono valori che variano nel tempo. "Classica" FRP ha due tipi di dati di base: eventi e comportamenti.

Eventi rappresentano valori che esistono solo in tempi discreti. Combinazioni di tasti sono un grande esempio: si può pensare degli input dalla tastiera come un personaggio in un dato momento. Ogni pressione di tasto è quindi solo una coppia con il carattere della chiave e il tempo è stato premuto.

I comportamenti sono valori che esistono sempre, ma possono essere cambiando continuamente. La posizione del mouse è un grande esempio: è solo un comportamento di coordinate x, y. Dopo tutto, il mouse sempre ha una posizione e, concettualmente, questa posizione cambi continua come si sposta il mouse. Dopo tutto, spostando il mouse è una singola azione protratta, non un gruppo di passi discreti.

E che cosa è logica temporale? abbastanza giustamente, è un insieme di regole logiche per trattare con proposizioni quantificati nel corso del tempo. In sostanza, si estende normale logica del primo ordine con due quantificatori: ? e ?. Il primo mezzo "sempre": leggere ? f come "f tiene sempre". Il secondo è "casualmente": ? f significa che "f è destinata a contenere". Si tratta di un particolare tipo di modale logica . Le due leggi di seguito si riferiscono i quantificatori:

□φ ⇔ ¬◇¬φ
◇φ ⇔ ¬□¬φ

Così ? e ? sono dual gli uni agli altri nello stesso modo come ? e ?.

Questi due quantificatori corrispondono ai due tipi di FRP. In particolare, ? corrisponde a comportamenti ed ? corrisponde agli eventi. Se pensiamo a come questi tipi sono abitate, questo dovrebbe dare un senso: un comportamento è abitata a tutti tempo possibile, mentre un evento si verifica solo una volta.

In relazione al rapporto tra continuazioni e doppia negazione, il tipo di chiamata / cc è la legge di Peirce http://en.wikipedia.org/wiki/Call-with-current-continuation

C-H viene normalmente indicato come corrispondenza tra logica e programmi intuizionista. Tuttavia, se si aggiunge il (callCC) operatore di call-con-corrente di continuazione (il cui tipo corrisponde alla legge di Peirce), si ottiene una corrispondenza tra logica classica e programmi con callCC.

Anche se non è un isomorfismo semplice, questa discussione costruttiva LEM è molto risultato interessante. In particolare, nella sezione conclusione, Oleg Kiselyov illustra come l'uso di monadi arrivare all'eliminazione doppio negazione in una logica costruttiva è analogo a distinguere proposizioni computazionalmente decidibili (LEM per cui è valida in un contesto costruttivo) da tutte le proposizioni. L'idea che le monadi di cattura gli effetti di calcolo è un vecchio, ma questa istanza della Curry -. Howard isomorfismo aiuta metterlo in prospettiva e aiuta a ottenere a ciò che doppia negazione davvero "significa"

Supporto continuazioni di prima classe ti permette di esprimere $ P \ lor \ neg P $. Il trucco si basa sul fatto che non chiamare il proseguimento e uscire con qualche espressione equivale a chiamare la continuazione con la stessa espressione.

Per visualizzare maggiori dettagli si veda: http://www.cs.cmu.edu/~rwh/courses/logic/www-old/handouts/callcc.pdf

2-continuation           | Sheffer stoke
n-continuation language  | Existential graph
Recursion                | Mathematical Induction

Una cosa che è importante, ma non hanno ancora in fase di studio è il rapporto di 2-continuazione (continuazioni che prende 2 parametri) e Sheffer ictus . Nella logica classica, Sheffer ictus può formare un sistema completo logica di per sé (più alcuni concetti non operatore). Il che significa che il and familiare, or, not può essere implementato utilizzando solo lo stoke Sheffer o nand.

Questo è un fatto importante di questo tipo programmazione corrispondenza perché richiede che un singolo tipo combinatore può essere usato per formare tutti gli altri tipi.

La firma tipo di un 2-continuazione è (a,b) -> Void. Da questa implementazione possiamo definire 1 di continuazione (continuazioni normali) come (a,a) -> Void, tipo di prodotto come ((a,b)->Void,(a,b)->Void)->Void, tipo somma come ((a,a)->Void,(b,b)->Void)->Void. Questo ci dà un impressionante del suo potere di espressività.

Se scaviamo più, scopriremo che Blocco è esistenziale grafico è equivalente a un lingua con l'unico tipo di dati è n-continuazione, ma non ho visto tutte le lingue esistenti è in questa forma. Così inventare uno potrebbe essere interessante, credo.

Autorizzato sotto: CC-BY-SA insieme a attribuzione

Non affiliato a StackOverflow