Was sind die interessantesten Äquivalenzen, die sich aus dem Curry-Howard-Isomorphismus ergeben?

https://stackoverflow.com/questions/2969140

24-10-2019
|

Frage

Ich stieß auf die Curry-Howard Isomorphismus Relativ spät in meinem Programmierleben, und vielleicht trägt dies dazu bei, dass ich völlig fasziniert ist. Dies impliziert, dass für jedes Programmierkonzept ein genaues Analogon in der formalen Logik vorhanden ist und umgekehrt. Hier ist eine "grundlegende" Liste solcher Analogien, von der Spitze meines Kopfes:

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

Also zu meiner Frage: Was sind einige der interessanteren/obskureren Implikationen dieses Isomorphismus? Ich bin kein Logiker, also bin ich sicher, dass ich mit dieser Liste nur die Oberfläche zerkratzt habe.

Zum Beispiel finden Sie hier einige Programmiervorstellungen, für die ich nicht kennzeichnende Namen in der Logik weiß:

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

Und hier sind einige logische Konzepte, die ich nicht ganz in Programmierbegriffen festgehalten habe:

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

Bearbeiten:

Hier sind einige weitere Äquivalenzen, die aus den Antworten gesammelt wurden:

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

Lösung

Da Sie ausdrücklich nach den interessantesten und dunkelsten gefragt haben:

Sie können CH auf viele interessante Logik und Logikformulierungen ausdehnen, um eine wirklich Vielzahl von Korrespondenzen zu erhalten. Hier habe ich versucht, mich auf einige der interessanteren und nicht auf die Dunkelheit zu konzentrieren, und einige grundlegende, die noch nicht aufgetaucht sind.

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

Bearbeiten: Eine Referenz, die ich jedem empfehlen würde, der mehr über Erweiterungen von CH erfahren möchte:

"Eine wertende Rekonstruktion der modalen Logik" http://www.cs.cmu.edu/~fp/papers/mscs00.pdf - Dies ist ein großartiger Ausgangspunkt, da es von den ersten Prinzipien beginnt und viel davon für Nicht-Logiker/Sprachtheoretiker zugänglich ist. (Ich bin der zweite Autor, also bin ich voreingenommen.)

Andere Tipps

Sie verderben die Dinge ein wenig in Bezug auf Nichtverschlüsse. Falschheit wird durch dargestellt unbewohnte Typen, was per Definition nicht nicht terminiert werden kann, da es überhaupt nichts von diesem Typ gibt, das man überhaupt bewerten kann.

Nicht termination repräsentiert Widerspruch-eine inkonsistente Logik. Eine inkonsistente Logik wird natürlich Erlauben Sie Ihnen, zu beweisen irgendetwas, einschließlich Falschheit.

Wenn Sie Inkonsistenzen ignorieren, entsprechen Typsysteme typischerweise einer intuitionistische Logik, und sind notwendig Konstruktivist, was bedeutet, dass bestimmte klassische Logikstücke, wenn überhaupt, nicht direkt ausgedrückt werden können. Andererseits ist dies nützlich, denn wenn ein Typ ein gültiger konstruktiver Beweis ist, ist ein Begriff dieses Typs a Mittel, um alles zu konstruieren, was Sie bewiesen haben, von der Existenz von.

Ein wichtiges Merkmal des konstruktivistischen Geschmacks ist das doppelte Negation ist nicht gleichbedeutend mit der Nichtannegung. Tatsächlich ist Negation in einem Typsystem selten ein primitiv not P wird P -> Falsity. Die doppelte Negation wäre daher eine Funktion mit Typ (P -> Falsity) -> Falsity, was eindeutig nicht gleichbedeutend mit etwas einfachem Typ ist P.

Es gibt jedoch eine interessante Wendung! In einer Sprache mit dem parametrischen Polymorphismus reichen Typvariablen über alle möglichen Typen, einschließlich unbewohnter, so ein vollständig polymorpher Typ wie z. ∀a. a ist in gewissem Sinne fast fälschlich. Was ist, wenn wir doppelt so viel Negation schreiben, indem wir Polymorphismus verwenden? Wir bekommen einen Typ, der so aussieht: ∀a. (P -> a) -> a. Ist das entspricht so etwas vom Typ P? Es ist wirklich, wenden Sie es lediglich auf die Identitätsfunktion an.

Aber was ist der Punkt? Warum einen solchen Typ schreiben? Macht es bedeuten Irgendwas in Programmierbegriffen? Nun, Sie können es als eine Funktion betrachten, die bereits etwas vom Typ hat P irgendwo und braucht Sie, um ihm eine Funktion zu geben, die dauert P Als Argument, wobei das Ganze im Endergebnis -Typ polymorph ist. In gewissem Sinne repräsentiert es a Suspendierte Berechnung, Warten auf den Rest, der zur Verfügung gestellt wird. In diesem Sinne können diese suspendierten Berechnungen zusammen komponiert, weitergegeben, aufgerufen, was auch immer. Dies sollte Fans einiger Sprachen, wie Schema oder Rubin, vertraut sein-weil es das bedeutet, ist das Die Doppelnegation entspricht Fortsetzungsstil, und in der Tat ist der Typ, den ich oben gegeben hat, genau die Fortsetzungsmonade in Haskell.

Ihr Diagramm ist nicht ganz richtig; In vielen Fällen haben Sie Typen mit Bedingungen verwirrt.

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] Die Logik für eine Turing-Complete-Funktionssprache ist inkonsistent. Rekursion hat keine Korrespondenz in konsistenten Theorien. In einer inkonsistenten Logik-/unklar Beweistheorie können Sie es als Regel bezeichnen, die Inkonsistenz/Unversehrtheit verursacht.

2] Dies ist wiederum eine Folge der Vollständigkeit. Dies wäre ein Beweis für ein Anti-Theorem, wenn die Logik konsistent wäre-daher kann sie nicht existieren.

3] existiert nicht in funktionalen Sprachen, da sie logische Merkmale erster Ordnung elidieren: Alle Quantifizierungen und Parametrisierung erfolgen über Formeln. Wenn Sie Funktionen erster Ordnung hätten, gäbe es eine andere Art als *, * -> *, etc.; Die Art von Elementen des Diskurses. Zum Beispiel in Father(X,Y) :- Parent(X,Y), Male(X), X und Y Reichweite über den Diskursbereich (nennen Sie es Dom), und Male :: Dom -> *.

function composition      | syllogism

Ich mag diese Frage wirklich. Ich weiß nicht viel, aber ich habe ein paar Dinge (unterstützt von Der Wikipedia -Artikel, der einige ordentliche Tische und dergleichen selbst hat):

Ich denke, dass Sumentypen/Gewerkschaftstypen (z.B data Either a b = Left a | Right b) sind gleichbedeutend zu inklusiv disjunktion. Und obwohl ich Curry-Howard nicht sehr gut vertraut bin, zeigt ich es. Betrachten Sie die folgende Funktion:
```
andImpliesOr :: (a,b) -> Either a b
andImpliesOr (a,_) = Left a
```
Wenn ich die Dinge richtig verstehe, sagt der Typ das ((a ∧ b) → (a ★ b) und die Definition besagt, dass dies wahr ist, wo ★ entweder inklusiv oder exklusiv oder je nachdem, was auch immer Either repräsentiert. Du hast Either Exklusive oder, ⊕; jedoch, (a ∧ b) ↛ (a ⊕ b). Zum Beispiel ⊤ ∧ ⊤ ≡ ⊤ ⊤ ⊤ ⊕ ⊥ ≡ ⊥ und ⊤ ↛ ⊥ ⊥ ⊥ ⊤ ⊕ ⊥ ⊥ ⊥ ⊥ ⊤ ⊥ ⊤ ⊕ ⊥ ⊥ ⊥ ⊥ ⊤ ⊤ ⊤ ⊤ ⊕ ⊥ ⊥ ⊥ ⊥ ⊤ ⊤ ⊤ ⊤ ⊤ ⊕ ⊥ ⊥ ⊥ ∧ ⊤ ⊤ ⊤ ⊤ ⊤ ⊕ ⊥ ⊥ ⊥ ⊥ ⊤ ⊤ ⊤ ⊕ ⊥ ⊥ ⊥ ⊥ ⊤ ⊤ ⊤ ⊥ ⊥ ⊥ ⊥ ⊥ ⊤ ⊤ ⊥ ⊥ ⊥ ⊥ ⊥ ⊥ ⊥ ⊥ ⊥ ⊥ ⊥ ⊥ ⊕ ⊥ ⊥ ⊥ ⊥ ⊥ ⊥ ⊥ ⊥ ⊥ ⊥ ⊥ ⊥ ⊕ ⊕ Mit anderen Worten, wenn beides a und b sind wahr, dann ist die Hypothese wahr, aber die Schlussfolgerung ist falsch, und daher muss diese Implikation falsch sein. Es ist jedoch klar (klar (a ∧ b) → (a ∨ b), da wenn beides a und b sind wahr, dann ist mindestens einer wahr. Wenn diskriminierte Gewerkschaften eine Form der Disjunktion sind, müssen sie die inklusive Sorte sein. Ich denke, das gilt als Beweis, aber ich fühle mich mehr als frei, mich von diesem Begriff zu entlasten.
In ähnlicher Weise sind Ihre Definitionen für Tautologie und Absurdität als Identitätsfunktion bzw. nicht terminierende Funktionen ein wenig ab. Die wahre Formel wird durch die dargestellt Gerätetyp, was ist der Typ, der nur ein Element hat (data ⊤ = ⊤; oft geschrieben () und/oder Unit in funktionalen Programmiersprachen). Das macht Sinn: Da dieser Typ ist garantiert Um bewohnt zu werden, und da es nur einen möglichen Bewohner gibt, muss es wahr sein. Die Identitätsfunktion repräsentiert nur die besondere Tautologie, die a → a.

Ihr Kommentar zu nicht terminierenden Funktionen ist, je nachdem, was Sie genau gemeint haben, mehr nicht. Curry-Howard funktioniert auf dem Typ-System, aber dort wird nicht termination codiert. Entsprechend Wikipedia, Der Umgang mit Nicht-Termination ist ein Problem, da das Hinzufügen inkonsistente Logik erzeugt (z.B, Ich kann definieren wrong :: a -> b durch wrong x = wrong x, und so „beweisen“ das a → b für jeden a und b). Wenn Sie dies unter „Absurdität“ gemeint haben, sind Sie genau richtig. Wenn Sie stattdessen die falsche Aussage gemeint haben, ist das, was Sie stattdessen wollen, ein unbewohntem Typ. z.B etwas definiert von data ⊥- Das heißt, ein Datentyp ohne Möglichkeit, ihn zu konstruieren. Dies stellt sicher, dass es überhaupt keine Werte gibt, und daher muss es unbewohnt sein, was dem falschen entspricht. Ich denke, Sie könnten wahrscheinlich auch verwenden a -> b, Da wir nicht terminierende Funktionen verbieten, ist dies auch unbewohnt, aber ich bin mir nicht zu 100% sicher.
Wikipedia sagt, dass Axiome auf zwei verschiedene Arten codiert werden, je nachdem, wie Sie Curry-Howard interpretieren: entweder in den Kombinatoren oder in den Variablen. Ich denke, die Kombinatoransicht bedeutet, dass die primitiven Funktionen, die wir für die Dinge erhalten, die wir standardmäßig sagen können (ähnlich wie bei den Modus -Ponens ein Axiom ist, weil die Funktionsanwendung primitiv ist). Und ich denken Dass die variable Ansicht tatsächlich dasselbe bedeuten kann - Kombinatoren sind schließlich nur globale Variablen, die bestimmte Funktionen sind. Was primitive Typen betrifft: Wenn ich richtig darüber nachdenke, dann denke ich, dass primitive Typen die Entitäten sind - die primitiven Objekte, über die wir versuchen, Dinge zu beweisen.
Nach meiner Logik- und Semantikklasse die Tatsache, dass ((a ∧ b) → c ≡ a → (b → c) (und auch das b → (a → c)) wird zumindest in natürlichen Abzugsnachweisen als Export -Äquivalenzgesetz bezeichnet. Ich habe damals nicht bemerkt, dass es nur Currying war - ich wünschte, ich hätte es, weil das cool ist!
Während wir jetzt eine Möglichkeit haben, darzustellen inklusiv In Disjunktion haben wir keine Möglichkeit, die exklusive Sorte darzustellen. Wir sollten in der Lage sein, die Definition einer ausschließlichen Disjunktion zu verwenden, um sie darzustellen: a ⊕ b ≡ (a ∨ b) ∧ ¬(a ∧ b). Ich weiß nicht, wie ich Negation schreiben soll, aber ich weiß, dass ¬p ≡ p→ ⊥ und sowohl die Implikation als auch die Unwahrheit sind einfach. Wir sollten daher in der Lage sein, eine exklusive Disjunktion darzustellen durch:
```
data ⊥
data Xor a b = Xor (Either a b) ((a,b) -> ⊥)
```
Dies definiert ⊥ Um den leeren Typ ohne Werte zu sein, was der Falschheit entspricht; Xor wird dann definiert, um beide zu enthalten (und) Either ein a oder ein b (oder) und eine Funktion (Implikation) aus (a, b) (und) zum unteren Typ (FALSCH). ~~Ich habe jedoch keine Ahnung, was das ist meint.~~ (Bearbeiten 1: Jetzt tue ich den nächsten Absatz!) Da gibt es keine Werte vom Typ (a,b) -> ⊥ (Gibt es da?), Ich kann nicht ergründen, was dies in einem Programm bedeuten würde. Kennt jemand einen besseren Weg, um entweder über diese oder eine andere Definition nachzudenken? (Bearbeiten 1: Ja, Camccann.)

Bearbeiten 1: Dank an Camccanns Antwort (Insbesondere die Kommentare, die er dazu hinterlassen hat, um mir zu helfen), denke ich, ich sehe, was hier los ist. Einen Wert des Typs zu konstruieren Xor a b, Sie müssen zwei Dinge bereitstellen. Erstens ein Zeuge der Existenz eines Elements von beiden a oder b als erstes Argument; das ist ein Left a oder ein Right b. Und zweitens ein Beweis dafür, dass es keine Elemente beider Typen gibt a und b- andere Worte, ein Beweis dafür (a,b) ist unbewohnt - als zweites Argument. Da Sie nur eine Funktion schreiben können (a,b) -> ⊥ wenn (a,b) Ist unbewohnt, was bedeutet es, dass dies der Fall ist? Das würde bedeuten, dass ein Teil eines Objekts vom Typ (a,b) konnte nicht konstruiert werden; mit anderen Worten, dass mindestens eins und möglicherweise beides von a und b sind auch unbewohnt! In diesem Fall könnten Sie, wenn wir über ein Muster-Matching nachdenken, unmöglich Muster für ein solches Tupel: Angenommen, das b Ist unbewohnt, was würden wir schreiben, die mit dem zweiten Teil dieses Tupels übereinstimmen könnten? Daher können wir nicht übereinstimmen, was Ihnen helfen kann, zu sehen, warum dies es unbewohnt macht. Nun die einzige Möglichkeit, eine Gesamtfunktion zu haben, die keine Argumente nimmt (wie dieses muss, seitdem (a,b) ist unbewohnt) bedeutet auch, dass das Ergebnis auch unbewohnt ist-wenn wir aus einer Sicht des Muster-Matching darüber nachdenken, bedeutet dies, dass die Funktion zwar keine Fälle hat, es keine Möglichkeit gibt Karosserie Es könnte entweder sein und so ist alles in Ordnung.

Vieles davon denke ich laut nach (hoffentlich) Dinge im Fluge, aber ich hoffe, es ist nützlich. Ich empfehle wirklich Der Wikipedia -Artikel; Ich habe es nicht im Detail gelesen, aber seine Tische sind eine wirklich schöne Zusammenfassung und es ist sehr gründlich.

Hier ist eine etwas dunkle, von der ich überrascht bin, dass ich nicht früher angesprochen wurde: "klassische" funktionelle reaktive Programmierung entspricht der zeitlichen Logik.

Wenn Sie nicht ein Philosoph, Mathematiker oder obsessive funktionale Programmierer sind, wirft dies wahrscheinlich einige weitere Fragen auf.

Also, zunächst: Was ist funktionale reaktive Programmierung? Es ist eine deklarative Art zu arbeiten zeitlich variierende Werte. Dies ist nützlich, um Dinge wie Benutzeroberflächen zu schreiben, da Eingaben vom Benutzer Werte sind, die im Laufe der Zeit variieren. "Klassische" FRP hat zwei grundlegende Datentypen: Ereignisse und Verhaltensweisen.

Ereignisse repräsentieren Werte, die nur zu diskreten Zeiten existieren. Tastenanschläge sind ein gutes Beispiel: Sie können sich die Eingaben von der Tastatur zu einem bestimmten Zeitpunkt als Zeichen vorstellen. Jeder Tastendress ist dann nur ein Paar mit dem Charakter der Taste und der Zeit, in der sie gedrückt wurde.

Verhaltensweisen sind Werte, die ständig existieren, sich aber kontinuierlich ändern können. Die Mausposition ist ein gutes Beispiel: Sie ist nur ein Verhalten von X-, Y -Koordinaten. Immerhin die Maus stets hat eine Position und konzeptionell ändert sich diese Position ständig Während Sie die Maus bewegen. Schließlich ist das Bewegen der Maus eine einzelne langwierige Aktion, nicht eine Reihe diskreter Schritte.

Und was ist zeitliche Logik? Angemessen sind es eine Reihe logischer Regeln für den Umgang mit Vorschlägen im Laufe der Zeit. Im Wesentlichen erweitert es die normale Logik erster Ordnung mit zwei Quantifizierern: □ und ◇. Das erste bedeutet "immer": Lesen Sie □ φ als "φ hält immer". Der zweite ist "irgendwann": ◇ φ bedeutet, dass "φ irgendwann hält". Dies ist eine bestimmte Art von Modale Logik. Die folgenden beiden Gesetze beziehen die Quantifizierer:

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

So sind □ und ◇ so doppelt zueinander wie ∀ und ∃.

Diese beiden Quantifizierer entsprechen den beiden Typen in FRP. Insbesondere □ entspricht Verhaltensweisen und ◇ entspricht Ereignissen. Wenn wir darüber nachdenken, wie diese Typen bewohnt sind, sollte dies sinnvoll sein: Ein Verhalten ist bewohnt bei jeder Mögliche Zeit, während ein Ereignis nur einmal stattfindet.

In Bezug auf die Beziehung zwischen Kontinuationen und doppelter Negation ist die Art des Anrufs/CC Peirce's Gesetz http://en.wikipedia.org/wiki/call-with-current-continuation

CH wird normalerweise als Korrespondenz zwischen intuitionistischer Logik und Programmen angegeben. Wenn wir jedoch den CALLCC-Operator (Call-with-Stromkontinuation) hinzufügen (dessen Typ dem Gesetz von Peirce entspricht), erhalten wir eine Korrespondenz zwischen klassische Logik und Programme mit CALLCC.

Obwohl es kein einfacher Isomorphismus ist, Diese Diskussion über konstruktive Lem ist ein sehr interessantes Ergebnis. Insbesondere im Schlussfolgerung-Abschnitt erörtert Oleg Kiselyov, wie die Verwendung von Monaden zur Unterscheidung von rechnerisch-leglierbaren Aussagen (für die LEM in einer konstruktiven Einstellung gültig ist) von allen Propositionen analog ist, um rechnerische Aussagen zu unterscheiden. Die Vorstellung, dass Monaden Berechnungseffekte erfassen, ist eine alte, aber diese Instanz des Curry-wie Isomorphismus, hilft es in die richtige Perspektive und hilft, das zu erreichen, was die Doppelbeschaffung wirklich "bedeutet".

Erstklasse-Kontinuationsunterstützung ermöglicht es Ihnen, $ p lor neg $ auszudrücken. Der Trick beruht auf der Tatsache, dass das Nichtanruf der Fortsetzung und Verlassen des Ausdrucks gleichbedeutend mit dem Aufruf der Fortsetzung mit demselben Ausdruck ist.

Für eine detailliertere Ansicht finden Sie bitte: http://www.cs.cmu.edu/~rwh/courses/logic/www-alte/handouts/callcc.pdf

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

Eine Sache, die wichtig, aber noch nicht untersucht wurde Sheffer Schlaganfall. In der klassischen Logik kann Sheffer Stroke ein vollständiges Logiksystem für sich bilden (plus einige Nichtoperatorkonzepte). Was bedeutet das Vertraute and, or, not kann nur mit Sheffer Stoke oder implementiert werden nand.

Dies ist eine wichtige Tatsache seiner Korrespondenz des Programmieryps, da ein einzelner Typ -Kombinator zur Bildung aller anderen Typen verwendet werden kann.

Die Typ Signatur einer 2-in-Intensiva ist (a,b) -> Void. Durch diese Implementierung können wir 1 Inkontinuierung (normale Kontinuationen) als definieren (a,a) -> void, Produkttyp als ((a,b)->Void,(a,b)->Void)->Void, Sumentyp als ((a,a)->Void,(b,b)->Void)->Void. Dies gibt uns eine beeindruckende Ausdruckskraft.

Wenn wir weiter graben, werden wir das dieses Stücks herausfinden Existenzielle Grafik entspricht einer Sprache mit dem einzigen Datentyp ist die N-Einbindung, aber ich habe nicht gesehen, dass vorhandene Sprachen in diesem Formular vorhanden sind. Das Erfinden eines könnte also interessant sein, denke ich.

Lizenziert unter: CC-BY-SA mit Zuschreibung

Nicht verbunden mit StackOverflow