Eine Frage, über Logik und die Curry-Howard Korrespondenz

Question

Könnten Sie mir bitte erklären, was die grundlegende Verbindung zwischen den Grundlagen der logischen Programmierung und das Phänomen der syntaktischen Ähnlichkeit zwischen Typ-Systemen und herkömmlichen Logik?

Answer 1

Der Curry-Howard Korrespondenz geht es nicht um Logik-Programmierung, aber funktionale Programmierung. Die grundlegende Mechanik des Prologs wird in Beweistheorie von John Robinson gerechtfertigt Auflösungstechnik , die zeigt, wie es möglich ist, zu überprüfen, ob logische Formeln ausgedrückt als Horn-Klauseln sind erfüllbar , das heißt, ob Sie Begriffe substitue für ihre logischen Variablen finden können, die sie wahr zu machen.

So Logikprogrammierung ist über Programme als logische Formeln spezifizieren, und die Berechnung des Programms ist eine Form der Beweis Folgerung, in Prolog reolution, wie ich gesagt habe. Im Gegensatz dazu der Curry-Howard Korrespondenz zeigt, wie Beweise in einem speziellen formulasition der Logik, natürlichen Abzug genannt, entsprechen die Programme in dem Lambda-Kalkül, mit der Art des Programms entsprechend die Formel, dass der Nachweis nachweist; Berechnung in dem Lambda-Kalkül entspricht ein wichtiges Phänomen in Beweistheorie Normalisierung genannt, die Beweise in neue, direkterer Proofs umwandelt. So Logikprogrammierung und funktionale Programmierung entsprechen verschiedenen Ebenen in diesen Logiken. Logikprogramme entsprechen Formeln einer Logik, während funktionale Programme Beweise Formeln entsprechen

Es gibt einen weiteren Unterschied: die verwendeten Logiken im Allgemeinen unterschiedlich sind. Logikprogrammierung verwendet in der Regel einfache Logik - wie gesagt, Prolog auf Horn-Klauseln begründet, welche eine stark eingeschränkte Klasse von Formeln in denen Auswirkungen können nicht verschachtelt werden, und es gibt keine Abtrennungen, obwohl Prolog die volle Stärke der klassischen Logik erholt ich die Schnittregel. Im Gegensatz dazu funktionalen Programmiersprachen wie Haskell machen starken Gebrauch von Programmen, deren Typen haben verschachtelte Implikationen, und werden von allen Arten von Formen des Polymorphismus eingerichtet. Sie sind auch auf intuitionismus, eine Klasse von Logik zugrunde, dass verbietet das Prinzip des ausgeschlossenen Dritten verwendet werden, die Robinsons Rechenmechanismus, der auf basiert.

Einige andere Punkte:

1. Es ist möglich, Basislogikprogrammierung auf komplexere Logik als Horn-Klauseln; beispielsweise Lambda-prolog auf intuitionismus basiert, mit einem anderen Berechnungsmechanismus als Auflösung.
2. Dale Miller hat den Beweis theoretische Paradigma hinter Logik genannt Programmierung der Beweissuche als Programmierung Metapher, um den Kontrast mit dem Beweise als Programme Metapher, die ein anderer Begriff verwendet wird, für die Curry-Howard Korrespondenz.

Answer 2

Logikprogrammierung ist grundsätzlich über zielgerichtete Suche nach Beweisen. Die strukturelle Beziehung zwischen typisierten Sprachen und Logik beinhaltet im allgemeinen funktionalen Sprachen, wenn auch manchmal zwingend notwendig und anderen Sprachen - aber nicht Logik Sprachen direkt programmieren. Diese Beziehung bezieht sich Beweise für Programme.

kann also Suchlogik Programmierung Beweis verwendet werden, Beweise zu finden, die dann als funktionale Programme interpretiert. Dies scheint die direkte Beziehung zwischen den beiden zu sein (wie Sie gefragt).

Gebäude ganze Programme auf diese Weise nicht praktikabel ist, aber es kann zum Ausfüllen ermüdend Details in den Programmen, und es gibt einige wichtige Beispiele hierfür in der Praxis nützlich sein. Ein einfaches Beispiel hierfür ist strukturelle Subtypisierung - entspricht, in wenigen Schritten Nachweis über einen einfachen entailment Nachweis füllen. Eine viel anspruchsvolleres Beispiel ist die Art Klassensystem von Haskell, die eine bestimmte Art von Ziel gerichtet Suche beinhaltet -. Im Extrem dies eine Turing-complete Form von Logik-Programmierung bei der Kompilierung beinhaltet