Una domanda sulla logica e la corrispondenza di Curry-Howard

Question

La prego di spiegare che cosa è la connessione fondamentale tra i fondamenti della programmazione logica e il fenomeno di somiglianza sintattica tra i sistemi di tipo e logica convenzionale?

Answer 1

La corrispondenza di Curry-Howard non si tratta di programmazione logica, ma programmazione funzionale. Il meccanico fondamentale di Prolog è giustificato in teoria della dimostrazione da John Robinson risoluzione tecnica , che mostra come sia possibile verificare se formule logiche espresse clausole di Horn sono satisfiable , vale a dire, se è possibile trovare i termini per substitue per le loro variabili logiche che li rendono vere.

Così programmazione logica è di circa specifica programmi come formule logiche, e il calcolo del programma è una qualche forma di inferenza prove, in Prolog reolution, come ho detto. Al contrario gli spettacoli corrispondenza di Curry-Howard come prove in un formulasition speciale di logica, chiamato deduzione naturale , conforme a programmi nel lambda calcolo, con il tipo di programma corrispondente alla formula che la prova dimostra; calcolo nei corrisponde lambda calcolo ad un fenomeno importante nella teoria della dimostrazione chiamato normalizzazione, che trasforma prove in nuove prove più dirette. Così programmazione logica e corrispondono programmazione funzionale a diversi livelli in queste logiche:. Programmi logici corrispondono formule di una logica, mentre i programmi funzionali corrispondono prove di formule

C'è un'altra differenza: le logiche utilizzate sono generalmente diversi. programmazione logica generalmente usa logiche più semplici - come ho detto, Prolog è fondato su clausole di Horn, che sono una classe molto limitato di formule in cui non possono essere annidati implicazioni, e non ci sono disgiunzioni, anche se Prolog recupera tutta la forza della logica classica utilizzando la regola taglio. Al contrario, i linguaggi di programmazione funzionali come Haskell fanno largo uso di programmi i cui tipi avere implicazioni nidificati, e sono decorati da tutti i tipi di forme di polimorfismo. Essi si basano sulla logica intuizionistica, una classe di logiche che proibisce uso del principio del terzo escluso, quale meccanismo di calcolo di Robinson si riferiscono.

Alcuni altri punti:

1. E 'possibile la programmazione logica di base su logiche più sofisticato di clausole di Horn; per esempio, Lambda-prolog è basato sulla logica intuizionistica, con un meccanismo di calcolo diverso rispetto alla risoluzione.
2. Dale Miller ha chiamato il paradigma a prova di teoria dietro logica di programmazione di ricerca come prova di programmazione metafora, per contrasto con il prove i programmi metafora che viene usato un altro termine per la corrispondenza di Curry-Howard.

Answer 2

programmazione logica è fondamentalmente circa obiettivo diretto la ricerca per le prove. Il rapporto strutturale tra le lingue digitati e logica generalmente comporta linguaggi funzionali, anche se a volte imperativo e altre lingue - ma non la logica di programmazione direttamente lingue. Questo rapporto si riferisce prove ai programmi.

Quindi, cerca la prova di programmazione logica può essere usato per trovare le prove che vengono poi interpretati come programmi funzionali. Questo sembra essere il rapporto più diretto tra i due (come lei ha chiesto).

Imprese interi programmi in questo modo non è pratico, ma può essere utile per il riempimento in noiosi dettagli nei programmi, e ci sono alcuni esempi importanti di questo in pratica. Un esempio di base di questo è sottotipaggio strutturale - che corrisponde al riempimento in pochi passi prova tramite una semplice prova implicazione. Un esempio molto più sofisticato è il sistema di tipo di classe di Haskell, che comporta un particolare tipo di obiettivo diretto di ricerca -. Nell'estremo si tratta di una forma di Turing-complete di programmazione logica al momento della compilazione