Curry Howard Korrespondenz mit Predicate Logic?

7

Also versuche ich, mich um Curry-Howard zu kümmern. (Ich habe es mehrmals versucht, es ist einfach nicht gelierend / scheint zu abstrakt). Um etwas Konkretes anzugehen, arbeite ich an einigen Haskell-Tutorials, die von Wikipedia verlinkt sind, insbesondere von Tim Newsham . Es gibt auch eine nützliche Diskussion, wenn Newsham das Tutorial veröffentlicht.

(Aber ich werde die dataWrapper von Newsham und Piponi ignorieren und über die zugrunde liegenden Typen sprechen.) Wir haben Hilberts Axiomschema (ausgedrückt als S , K- Kombinatoren); wir haben Sätze als Typen; Implikation als Funktionspfeil; und Modus Ponens als Funktionsanwendung:

axK :: p -> q -> p
axK  = const
axS :: (p -> q -> r) -> (p -> q) -> p -> r
axS     f                g          x  = f x (g x)

modPons = ($);   infixl 0 `modPons`          -- infix Left, cp ($) is Right

Dann kann ich das Identitätsgesetz ableiten:

ident     = axS `modPons` axK `modPons` axK  -- (S K K)
-- ident :: p -> p                           -- inferred

Diese Typen als bloße Typevars zu haben, die lediglich Aussagen entsprechen, scheint eher einfallslos. Kann ich mehr vom Typsystem verwenden, um die Sätze tatsächlich zu konstruieren? Ich denke:

data      IsNat n  = IsNat !n                -- [Note **]

data      Z        = Z
axNatZ ::            IsNat Z
axNatZ             = IsNat Z

data      S n      = S !n
axNatS :: IsNat n -> IsNat (S n)
axNatS   (IsNat n) = IsNat (S n) 

twoIsNat = axNatS `modPons` (axNatS `modPons` axNatZ)
-- ===> IsNat (S (S Z))

[Anmerkung **] Ich verwende strenge Konstruktoren gemäß dem Diskussionsthread, um die Einführung von _ | _ zu vermeiden .

Wo:

  • IsNat ist ein Prädikat: einen Satz aus einem Begriff machen.
  • n ist eine Variable.
  • S ist eine Funktion, die aus einer Variablen einen Term macht.
  • Z ist eine Konstante (niladische Funktion).

Ich habe also eine eingebettete Prädikatenlogik (erster Ordnung) (?)

Ich schätze, dass meine Typen nicht sehr hygienisch sind; Ich könnte leicht einen Typevar-als-Satz mit einem Typevar-als-Begriff verwechseln. Vielleicht sollte ich das KindSystem verwenden, um sie zu trennen. OTOH, meine Axiome müssten spektakulär falsch sein, um zu einer Schlussfolgerung zu gelangen.

Ich habe nicht ausgedrückt:

  • universeller Quantifizierer: Es ist implizit für die freien Vars;
  • existentielle Quantität: In der Tat könnten Konstanten als skolemisierte Existentiale wirken;
  • Gleichheit der Begriffe: Ich habe wiederholte Typevars in Implikationen verwendet;
  • Beziehungen: Das scheint zu funktionieren, oder ist es Verwirrung? ...
    data          PlusNat n m l  = PlusNat !n !m !l

    axPlusNatZ :: IsNat m       -> PlusNat Z m m
    axPlusNatZ   (IsNat m)       = PlusNat Z m m

    axPlusNatS :: PlusNat n m l -> PlusNat (S n) m (S l)
    axPlusNatS   (PlusNat n m l) = PlusNat (S n) m (S l)

    plus123 = axPlusNatS `modPons`
              (axPlusNatZ `modPons`
               (axNatS `modPons` (axNatS `modPons` axNatZ)) ) 
    -- ===> PlusNat (S Z) (S (S Z)) (S (S (S Z)))

Das Schreiben der Axiome ist einfach, mit freundlicher Genehmigung von Wadlers Theorems for Free! . Die Beweise zu schreiben ist harte Arbeit. (Ich werde die modPonsFunktion fallen lassen und nur die Funktionsanwendung verwenden.)

Erreicht dies tatsächlich eine Logik? Oder ist es verrücktes Zeug? Soll ich aufhören, bevor ich meinem Gehirn mehr Schaden zufüge?

Sie sollten abhängige Typen benötigen, um FOPL in Curry-Howard auszudrücken. Aber ich scheine das nicht zu tun (?)

AntC
quelle
1
Das Problem bei Ihrem Ansatz ist, IsNatdass Sie keinen Satz aus einem Begriff machen, sondern einen Satz aus einem Satz .
Derek Elkins verließ SE
Danke @DerekElkins, ich denke du meinst, das Argument IsNatist nur ein Typ, also muss es ein Vorschlag sein. OK, ebenso IsNat nist es nur ein Typ, also muss es ein Satz sein. Ich muss 'auf meiner Ehre' sein, um nicht nin das Proposition-Land entkommen zu lassen / als Argument für einen logischen Zusammenhang erscheinen zu lassen (weshalb ich über Typhygiene gesprochen habe). Wären Sie glücklicher, wenn ich die Kirchencodierung für Nats verwenden würde? Ich glaube, ich erweitere λ-calc nur mit Konstruktoren auf
Typebene
PS Vielleicht n ist ein Satz : es sagt : ‚Ich bin bewohnt‘. Was nicht mehr ist, als jeder Typevar unter CH sagt. IsNat nsagt / bezeugt: Außerdem ist der Einwohner von neiner bestimmten Art, auch bekannt als "Art" in der Logik. Dann gehe ich über einfach eingegebene λ-calc (?)
AntC
1
Ich denke nicht, dass das Erlernen des Curry-Howard-Isomorphismus durch Herumspielen mit arkanen Programmiersprachen der richtige Ansatz ist. Es wird nicht zu einem wirklichen Verständnis des Prinzips führen.
Miles Rout
1
Wenn Sie die Texte nicht verstehen, sollten Sie lernen, was Sie brauchen, um die Texte zu verstehen. Haskell ist nicht eines dieser Dinge.
Miles Rout

Antworten:

3

Um zu erklären, warum ich mich mit Newshams und (besonders) Piponis dataWrappern unwohl fühle ... (Dies wird mehr eine Frage als eine Antwort sein, aber vielleicht hilft es zu erklären, was mit meinem falsch ist IsNat, obwohl es Newsham sehr ähnlich zu sein scheint. )

Piponi Seite 17 hat:

data Proposition = Proposition :-> Proposition
                  | Symbol String
                  | False deriving Eq

data Proof = MP Proof Proof
     | Axiom String Proposition deriving Eq

Ich sehe hier keine Typen. Wenn Sie einen Datenkonstruktor buchstabieren, :->funktioniert er nicht als Funktionspfeil. Wenn Sie einen Datenkonstruktor MP(für Modus Ponens) buchstabieren , funktioniert er nicht als Anwendung. Es gibt einen 'intelligenten Konstruktor'-Operator (@@)für MP, der jedoch keine Funktion anwendet: Er führt lediglich einen Mustervergleich für den :->Konstruktor durch.

Newsham hat (ich beginne mit dem Implikationsabschnitt / Modus Ponens):

data Prop p = Prop p

data p :=> q = Imp (Prop p -> Prop q)

impInj :: (Prop p -> Prop q) -> Prop (p :=> q)
impInj p2q = Prop (Imp p2q)

impElim :: Prop p -> Prop (p :=> q) -> Prop q
impElim p (Prop (Imp p2q)) = p2q p

Das sieht eher so aus: Wir haben Typen, Funktionspfeile, Funktionsanwendungen in impElim. Der Typkonstruktor Impmit seinen Injektions- und Eliminierungsregeln spiegelt die Beweisbaumstrukturen in den Lectures on Curry-Howard-Isomorphismus wider . Aber ich bin nervös: Warum braucht Impman einen Typkonstruktor und einen Datenkonstruktor? Auch hier macht die Rechtschreibung as :=>keinen Funktionspfeil. Warum all diese PropKonstruktoren zum Ein- und Auspacken ? Warum nicht einfach Prop (p -> q)?

Wenn ich mir also den Abschnitt "Konjunktion" anschaue (der eigentlich an erster Stelle steht):

data p :/\ q = And (Prop p) (Prop q)

andInj :: Prop p -> Prop q -> Prop (p :/\ q)
andInj p q = Prop (And p q)

andElimL :: Prop (p :/\ q) -> Prop p
andElimL (Prop (And p q)) = p

andElimR :: Prop (p :/\ q) -> Prop q
andElimR (Prop (And p q)) = q

Diese ElimFunktionen verwenden keine Funktionsanwendung. Sie stimmen lediglich mit den Konstruktoren überein. Es gibt keine implizite Struktur für die Konjunktion: Wir verlassen uns ausschließlich darauf, dass der 'Programmierer' nur die andInjRegel verwendet hat, um einen Typ zu erstellen (p :/\ q).

Wenn Newsham zur Kommutativität der Konjunktion kommt:

commuteAnd :: Prop (p :/\ q) -> Prop (q :/\ p)
commuteAnd pq = andInj (andElimR pq) (andElimL pq)

Und behauptet

Beachten Sie, dass unser Haskell-Proof keinen Verweis auf die interne Struktur des Datentyps (: / \) enthielt. Nachdem wir unsere Regeln "andInj", "andElimR" und "andElimL" definiert und bewiesen haben, sollten wir nie wieder einen Blick in die Implementierung des Datentyps (: / \) werfen müssen.

Ich bin einfach anderer Meinung:

  • Die Signatur für commuteAnd hängt von der internen Struktur des :/\Typkonstruktors ab.
  • Obwohl die Funktionsdefinition sieht lediglich Funktionsanwendung mag in der Tat die andElims tun „Peek“ in die Struktur.

Ich würde erwarten, dass wir die Kommutativität der Konjunktion anhand ihrer Definition beweisen können, ohne ein Axiom zu benötigen, um dies zu sagen (?)

OK, wenn ich so puristisch bin, was erwarte ich dann? Diese Konjunktion basiert auf der Kodierung der Kirche für Paare:

type Conj p q r = Prop ((p -> q -> r) -> r)     -- not right, see later

andInj :: Prop p -> Prop q -> Conj p q r
andInj (Prop p) (Prop q) = Prop (\elim -> elim p q)

andElimL :: Conj p q p -> Prop p
andElimL (Prop conj) = Prop (conj axK)    -- axK is `const`

Jetzt kann ich commuteAndmit der 'richtigen' Funktionsanwendung schreiben :

--  commuteAnd :: (Conj p q r) -> (Conj q p r)
commuteAnd pq = andInj (andElimR pq) (andElimL pq)

Diese Funktionsdefinition ist dieselbe wie die von Newsham. Aber ich habe die Signatur auskommentiert, weil der abgeleitete Typ von GHC nicht allgemein genug ist. Es will Prop ((p -> p -> p) -> p) -> ((p -> p -> p) -> p). Welches ist nur eine ausgefallene Variation des Identitätsgesetzes.

Bearbeiten: (Nach @DerekElkins erstem Kommentar hier.) Verschrotte alles:

Ich bin in tiefem (und trübem) Wasser gelandet. Ich denke, mein Typ für Conjmuss polymorpher sein, möglicherweise Impredicative. Ich habe mich über den Versuch lustig gemacht, einen Typ mit höherem Rang zu vergeben:

type Conj p q = Prop (forall r.((p -> q -> r) -> r))

Aber GHC spielt nicht. (Und die Unterstützung für Impredicative Polymorphism ist "schuppig".) Und eine forallsolche quantifizierte Sache sieht verdächtig aus wie die Definition für Falsch / unbewohnt, die ich erwartet hatte.

Ich brauche einen höherrangigen Typ, aber keinen Impredicative. Und nicht auf den Typ für, Conjsondern fürcommuteAnd

commuteAnd :: (forall r. Conj p q r) -> (Conj q p r')
-- (same function for `commuteAnd` as above)

OK. Ich kann gerne ad infinitum Argumente austauschen.

[Ende der Bearbeitung]

Meine Frage: Wenn es legitim ist, was Newsham mit Verschachtelungskonstruktoren und Mustervergleich überall macht, was ist dann nicht legitim an meinem IsNatund Mustervergleich?

AntC
quelle
1
Wie Piponi feststellt, sind die Typen Propositionund Proofkeine Beispiele für die Curry-Howard-Korrespondenz in Aktion. Diese bilden lediglich ein einfaches Proof-System im LCF-Stil. Die Curry-Howard-Korrespondenz wird durch die compileFunktion (obwohl der größte Teil der Arbeit von (^)und erledigt wird show) bestätigt, die diese Propositions und Proofs in Haskell-Code umwandelt. Was Newshams Code betrifft, machen die Wrapper (:=>)im Wesentlichen keinen Unterschied (->). Er fügt sie nur hinzu (wie er ausdrücklich angibt), damit er später eine andere, nicht triviale Implementierung austauschen kann.
Derek Elkins verließ SE
Vielen Dank. Für Neasham wollte ich mich an die Intuitionistische Logik halten, nicht an die Klassik. Also ignorierte ich die Fortsetzungen / Monaden. Wollen Sie damit sagen, dass seine Def'ns nicht für Intuitionistic funktionieren? Ja (:=>)ist implementiert als (->). Ein Modell / eine Simulation einer Logik erfordert jedoch eine Validierung des Interpreters (?). Warum kann ich nicht direkt in Haskell ausdrücken (->)?
AntC
Ähnliche Bemerkungen zu Piponi: Er stellt vor (^), sich mit Klassik zu befassen. OK, ich werde versuchen show, Haskell-Code zu generieren und zu sehen, wie sich das unterscheidet. (Ich werde auch versuchen herauszufinden, wie er sich vorstellt Integer.) Ich versuche, ein Minimum an Haskell-Maschinen zu verwenden, aus Angst, ich werde _|_irgendwo etwas einführen und "Programme sind Beweise" untergraben.
AntC