Universelle und existenzielle Typen

Ich versuche, mich mit den Konzepten universeller und existenzieller Typen zu beschäftigen, aber überall, wo ich hinschaue, sehe ich entweder logische oder operative Intuitionen (oder Implementierungen) (z. B. TAPL-Buch von B. Pierce), was gut ist , aber ich würde gerne die Definitionen sehen (wo wir sie als Mengen betrachten) - und daraus Ableitungen einiger Gesetze sowie Rechtfertigungen für unsere Intuitionen.

Da ich diese Definitionen nicht finden kann, habe ich mich dazu entschlossen, dies selbst zu tun, und ich denke, dass dies vernünftig sein kann:

\forall x . T \overset{d e f}{:=} ⋂_{S - t y p e} T [x := S]

$\forall x.T \overset{def}{:=} \bigcap_{S - type} T[x := S]$

\exists x . T \overset{d e f}{:=} ⋃_{S - t y p e} T [x := S]

$\exists x.T \overset{def}{:=} \bigcup_{S - type} T[x := S]$

Aber in dem oben erwähnten TAPL-Buch erhalten wir diese Definition (obwohl ich es eine Identität nennen würde)

\exists x . T \overset{d e f}{:=} \forall y . (\forall x . T \to y) \to y (*)

$\exists x.T \overset{def}{:=} \forall y. (\forall x. T \rightarrow y) \rightarrow y \quad (*)$

Ich habe zwei Probleme damit:

Auf der LHS von würde ich erwarten, dass die einzige freie Variable von (denn wie kann man einen Typ "noch nicht erstellt" mit einigen darin baumelnden freien Variablen anzeigen?), Aber auf der RHS scheint es so kann einen Einfluss auf , daher ist es besser, eine freie Variable in . Daher kann LHS nicht gleich RHS sein, da sich die Mengen der freien Variablen von auf beiden Seiten unterscheiden, oder? $(*)$ $x$ $T$ $y$ $T$ $T$ $T$
Selbst wenn ich die Bedenken an Punkt 1 außer Acht lasse. - Ich habe versucht, RHS mithilfe meiner Definitionen neu zu schreiben und zu prüfen, ob ich meine Definition des existenziellen Typs erhalten kann, aber ich bin festgefahren: $R H S = ⋂_{S} (\forall x . T \to y) [y := S] \to S = ⋂_{S} (⋂_{R} T [x := R, y := S] \to S) \to S$ $RHS = \bigcap_{S} (\forall x.T \rightarrow y)[y := S] \rightarrow S = \bigcap_{S} \left(\bigcap_{R} T[x := R, y := S] \rightarrow S\right) \rightarrow S$

Es ähnelt nicht einmal im entferntesten meiner Definition. Ist es möglich, die Formel, zu der ich gekommen bin, zu vereinfachen? Intuitiv, weil es Funktionstypen gibt, wird es wahrscheinlich nie meiner Definition entsprechen. Aber wenn sie nicht gleich sind - sind sie zumindest in gewissem Sinne "isomorph"? Wenn nicht - was ist "schief gelaufen"?

lo.logic type-theory type-systems set-theory umständlich
quelle

Ihre Gleichung (*) enthält einen Tippfehler: Sie sollte und nicht .

\forall Y

$\forall Y$

\forall y

$\forall y$

Cody

Auch in Ihrer letzten Gleichung: erscheint möglicherweise nicht in !

y

$y$

T

$T$

Cody

Antworten:

Die Mengenlehre schadet Ihnen hier und je früher Sie sich davon befreien, desto besser wird es für Ihr Verständnis der Informatik.

Vergessen Sie die Kreuzungen und Gewerkschaften. Die Leute kommen auf die Idee, dass und wie und , was die polnische Schule vor langer Zeit mit Booleschen Algebren gemacht hat, aber es ist wirklich nicht der richtige Weg (definitiv nicht im Computer) Wissenschaft). $\forall$ $\exists$ $\bigcap$ $\bigcup$

Sie möchten diese als Sets betrachten. Ok, aber dann müssen wir Größenprobleme ignorieren und so tun, als gäbe es eine Menge aller Mengen. (Es ist möglich, die Größenprobleme zu beheben, indem Sie an eine andere Kategorie übergeben.) Der Typ ist wirklich wie das kartesische Produkt Das heißt, ein Element von ist eine Funktion von Mengen zu Mengen: Für jede Menge gibt es ein Element vom Typ . Zum Beispiel ist ein Element von eine Funktion die eine Menge annimmt $\forall x . T$

\forall X . T : = \prod_{S : S e t} T [X \mapsto S] .

$\forall X . T \mathrel{{:}{=}} \prod_{S : \mathsf{Set}} T[X \mapsto S].$

\forall X . T

$\forall X . T$

f

$f$

S

$S$

f (S)

$f(S)$

T [x \mapsto S]

$T[x \mapsto S]$

\forall X . (X \to X) \to (X \to X)

$\forall X. (X \to X) \to (X \to X)$

f

$f$

S

$S$ und gibt eine Funktion vom Typ . Hier sind einige solcher Funktionen: Wir erhalten also eine für jede natürliche Zahl, und es ist schwierig, sich andere Beispiele vorzustellen . (Übung: Google "Kirchencodierung natürlicher Zahlen".)

(S \to S) \to (S \to S)

$(S \to S) \to (S \to S)$

\begin{aligned} f_{0} (S) (g) (x) & : = x \\ f_{1} (S) (g) (x) & : = g (x) \\ f_{2} (S) (g) (x) & : = g (g (x)) \\ f_{3} (S) (g) (x) & : = g (g (g (x))) \end{aligned}

$\begin{align*} f_0(S)(g)(x) &\mathrel{{:}{=}} x \\ f_1(S)(g)(x) &\mathrel{{:}{=}} g(x) \\ f_2(S)(g)(x) &\mathrel{{:}{=}} g(g(x)) \\ f_3(S)(g)(x) &\mathrel{{:}{=}} g(g(g(x))) \end{align*}$

Als nächstes betrachten wir die existenziellen Typen. Zunächst wird die richtige Codierung hinsichtlich ist wobei die Variable nicht in erscheint ! (Dies sollte in Pierces TAPL erwähnt werden.) Bevor wir uns diese Codierung ansehen, lassen Sie uns tun direkt in Mengen. Diesmal ist es ein Nebenprodukt: Ein Element von ist ein Paar wobei eine Menge und ein Element von ist $\exists$ $\forall$

\exists X . T : = \forall Y . (\forall X . (T \to Y)) \to Y

$\exists X . T \mathrel{{:}{=}} \forall Y . (\forall X . (T \to Y)) \to Y$ $Y$ $T$

\exists X . T

$\exists X . T$

\exists X . T : = \underset{S : S e t}{∐} T [X \mapsto S] .

$\exists X . T \mathrel{{:}{=}} \coprod_{S : \mathsf{Set}} T[X \mapsto S].$

\exists X . T

$\exists X . T$

(S, a)

$(S, a)$

S

$S$

a

$a$

T [X \mapsto S]

$T[X \mapsto S]$ . Ein Beispiel wäre der Typ , deren Elemente Paare wobei eine Menge ist und eine binäre Operation ist. Dies ist auch als Magma bekannt . Wenn Sie etwas schicker werden, können Sie bekannte Strukturen wie Gruppen und Ringe ausdrücken (Sie müssen zuerst die Identitätstypen erfinden ).

\exists X . (X \times X \to X)

$\exists X . (X \times X \to X)$

(S, m)

$(S, m)$

S

$S$

m : S \times S \to S

$m : S \times S \to S$

Lassen Sie uns sehen, wie die Codierung von in Bezug auf funktioniert. Es ist falsch zu erwarten, dass wir eine Gleichheit zwischen und (NB: ist frisch) - nur die Mengenlehre würde den Menschen solche Erwartungen geben. Wir sollten erwarten, dass die beiden isomorph sind . Die Aufgabe besteht also darin, eine Bijektion zwischen und Dies ist eine Übung in $\exists$ $\forall$ $\exists X. T$ $\forall Y . (\forall X . (T \to Y)) \to Y$ $Y$

A : = \underset{S : S e t}{∐} T [X \mapsto S]

$A \mathrel{{:}{=}} \coprod_{S : \mathsf{Set}} T[X \mapsto S]$

B : = \prod_{R : S e t} (\prod_{S : S e t} (T [X \mapsto S] \to R)) \to R .

$B \mathrel{{:}{=}} \prod_{R : \mathsf{Set}} \left(\prod_{S : \mathsf{Set}} (T[X \mapsto S] \to R) \right) \to R.$

λ

$\lambda$ -Infinitesimalrechnung. In einer Richtung haben wir die Karte definiert als und in der anderen eine Karte definiert durch (Die Notation bedeutet die Funktion .) Nun können wir prüfen, ob und invers zueinander sind. Eine Richtung ist einfach: Die andere Richtung sieht folgendermaßen aus:

f : A \to B

$f : A \to B$

f (S, a) (R) (h) : = h (S) (a)

$f(S,a)(R)(h) \mathrel{{:}{=}} h(S)(a)$

g : B \to A

$g : B \to A$

g (ϕ) : = ϕ (A) (λ S . λ a . (S, a)) .

$g(\phi) \mathrel{{:}{=}} \phi(A)(\lambda S . \lambda a . (S, a)).$

λ S . λ a . (S, a)

$\lambda S . \lambda a . (S, a)$

S \mapsto a \mapsto (S, a)

$S \mapsto a \mapsto (S, a)$

f

$f$

g

$g$

g (f (S, a)) = f (S, a) (A) (λ S^{'} . λ a^{'} . (S^{'}, a^{'})) = (λ S^{'} . λ a^{'} . (S^{'}, a^{'}) (S) (a) = (S, a) .

$g(f(S,a)) = f(S,a)(A)(\lambda S' . \lambda a' . (S', a')) = (\lambda S' . \lambda a' . (S', a')(S)(a) = (S, a).$

f (g (ϕ)) (R) (h) = h (π_{1} (g (ϕ)) (π_{2} (g (ϕ))) .

$f(g(\phi))(R)(h) = h(\pi_1(g(\phi))(\pi_2(g(\phi))).$ Wir könnten noch ein bisschen weiter machen, indem wir in umschreiben , aber dann würden wir stecken bleiben!

g (ϕ)

$g(\phi)$

ϕ (A) (λ S . λ a . (S, a))

$\phi(A)(\lambda S . \lambda a . (S, a))$

Es stellt sich heraus , dass in der Mengenlehre die Codierung in Bezug auf funktioniert nicht. Es funktioniert jedoch auch in anderen Setups, in denen Typen keine Sets sind. Sie können sich beispielsweise davon überzeugen, dass in der Logik die Anweisungen entspricht wobei über alle Sätze (Wahrheitswerte, logische Aussagen) reicht. Auch hier sollte die Variable in nicht vorkommen . $\exists$ $\forall$

\exists x . ϕ (x)

$\exists x . \phi(x)$

\forall P : P r o p . (\forall x . (ϕ (x) \Rightarrow P)) \Rightarrow P,

$\forall{P : \mathsf{Prop}} . (\forall x . (\phi(x) \Rightarrow P)) \Rightarrow P,$

P

$P$

P

$P$

ϕ

$\phi$

Andrej Bauer
quelle

Andrej, du bist blitzschnell!

Cody

Das ist aufschlussreich, danke! Aber ich habe immer noch Fragen :) 1) Verstehe ich richtig, dass das von Ihnen vorgestellte Setup immer noch satztheoretisch ist (aber nicht so naiv wie meins) und deshalb nicht gilt und wir keine Hoffnung haben, es angemessen zu finden und ? 2) Ich verstehe, dass diese Aussagen in der Logik äquivalent sind, aber es scheint mir, dass sie ein bisschen von der Typentheorie abweichen (na ja, denn wo sind die Typen? :)). Was wäre also die Einstellung des Typsystems, in dem gilt? 3) Wenn ich eine Sprache implementiere, die auf Lambda-Kalkül basiert - sollte ich vorsichtig sein, wenn ich ?

(*)

$(*)$

f

$f$

g

$g$

(*)

$(*)$

(*)

$(*)$

umständlich

Richtig: Das satztheoretische "Modell" (es ist kein Modell, weil wir so tun, als könnten wir kartesische Produkte herstellen, die von allen Mengen indiziert werden ) verletzt die Kodierung von in Bezug auf . Die Typentheorie validiert ebenfalls nicht die Codierung. Stattdessen erhalten Sie einen Rückzug (verwenden Sie einfach das gleiche und oben für die Typentheorie), aber keinen Isomorphismus. Um einen Isomorphismus zu erhalten, benötigen Sie etwas Besonderes. Beispielsweise stellt die Parametrizität sicher, dass sich alle Elemente des kartesischen Produkts gut verhalten, und stellt den Isomorphismus wieder her.

\exists

$\exists$

\forall

$\forall$

f

$f$

g

$g$

Andrej Bauer

@AndrejBauer ist das zugrunde liegende System nicht aussagekräftig? Und im Falle einer positiven Antwort gilt der Isomorphismus für prädikative Systeme?

Giorgio Mossa

@GiorgioMossa: Welches System? Fragen Sie sich, ob man Unbestimmtheit braucht, um die Gültigkeit der Kodierung von exist in Bezug auf festzustellen ? Nein, Parametrizität ist ausreichend, obwohl manchmal Impredikativität hilft (zum Beispiel, wenn wir mit ni a topos ausdrücken ).

\exists

$\exists$

\forall

$\forall$

\exists

$\exists$

\forall

$\forall$

Andrej Bauer

Zu Frage 1): Die Variable darf nicht in erscheinen , sondern muss nicht eingeschränkt werden. Wenn Sie hoffen möchten, dass die lhs gleich den rhs sind, sollten Sie auf jeder Seite die gleiche Anzahl freier Variablen haben, was unmöglich ist, wenn in erfasst wird . Die Intuition ist, dass gleich der unendlichen Konjunktion sein sollte für jeden möglichen Typ . In der Tat ist es nicht schwer, für einen bestimmten Typ zu zeigen, dass $Y$ $Y$ $Y$ $T$ $\exists T$

((\forall x . T \to U_{0}) \to U_{0}) \land ((\forall x . T \to U_{1}) \to U_{1}) \land \dots

$((\forall x. T\rightarrow U_0)\rightarrow U_0)\wedge((\forall x. T\rightarrow U_1)\rightarrow U_1)\wedge\ldots$

U_{i}

$U_i$

U

$U$

\exists x . T \to ((\forall x . T \to U) \to U)

$\exists x.T \rightarrow ((\forall x. T\rightarrow U)\rightarrow U)$

In Worten:

Der Beweis, dass, wenn es ein (beliebiges) so dass gilt, gilt, ist dasselbe wie der Beweis, dass für jedes , wenn gilt, . $x$ $T(x)$ $U$ $x$ $T(x)$ $U$

Beachten Sie, dass selbst nicht von abhängen darf . $U$ $x$

Die Intuition hinter der Gleichheit ist, dass diese Tatsache für jedes mögliche $U$ ausreicht, um den existenziellen Quantifizierer zu charakterisieren.

Für 2) ist die satztheoretische Intuition hier leider etwas schwierig. Es ist nicht naiv möglich, Typen als Mengen von Elementen und Pfeilen als satztheoretische Funktionen zwischen ihnen zu betrachten. Wenn jedoch eine Kreuzung nicht leer ist, sollte intuitiv nicht leer sein. In Ihrem Fall ergibt dies $\bigcap_S A(S)$ $A(\varnothing)$

(⋂_{R} (T [x := R] \to \emptyset)) \to \emptyset

$\left(\bigcap_R \left(T[x:=R]\rightarrow \varnothing\right)\right)\rightarrow\varnothing$

(Beachten Sie die Klammern), die nicht leer sein dürfen. Der einzige Weg dafür ist, dass es ein so dass leer ist, was bedeutet, dass nicht leer sein muss. $R$ $T[x:=R]\rightarrow \varnothing$ $T[x:=R]$

Cody
quelle

Nein! Keine unendliche Konjunktion. Es ist ein unendliches Produkt . Die Konjunktion vergisst, was bei jedem Typ und das ist böse. (Lassen Sie uns nicht jemand sagen , dass in den Realisierbarkeit Modelle von System F die Allquantor ist Kreuzung.)

U_{i}

$U_i$

Andrej Bauer

@AndrejBauer: Das ist fair, obwohl es manchmal nützlich ist, Informationen zu vergessen ... meine Intuition basiert teilweise auf der Eliminierungsregel von .

\exists

$\exists$

Cody

Sie können Informationen nur unter geeigneten Umständen vergessen, die garantieren, dass Sie trotzdem damit durchkommen. Zum Beispiel können wir in den Realisierbarkeitsmodellen, in denen tatsächlich ist, Informationen aufgrund der erstaunlichen Einheitlichkeit der Realisierer vergessen. Wenn Sie Informationen vergessen, wenn Sie dies nicht tun sollten, machen Sie die Gesetze einfach ungültig.

\forall

$\forall$

⋂

$\bigcap$

Andrej Bauer

Ich schlage vor, die operative Intuition nicht aufzugeben. Operativ ist primär, alle Semantiken werden abgeleitet und sind nur Beweisverfahren für die operative Semantik. Die Schlüsselideen sind wie folgt.

Ein Programm verwendet eine Variable universell-polymorph , vorausgesetzt, macht nichts mit , was Kenntnisse über den Typ von erfordert . Zum Beispiel könnten im Kalkül die folgenden Operationen polymorph sein (ob sie sind oder nicht, hängt von der genauen Sprachsemantik ab). $P$ $x$ $P$ $x$ $x$ $\lambda$

Weiterleitung, zB , $\lambda x.x.$
Neuordnung, zB . $\lambda (x,y,z). (z,x, y)$
Duplizieren, zB . $\lambda x.(x,x)$
fallen lassen, zB . $\lambda x.7$

Der existenzielle Polymophismus ist nun das exakte Dual des universellen Polymorphismus: Ein Programm verwendet eine Variable existenziell-polymophial , wenn nur für Kontexte bereitstellt , die keine Kenntnis des Typs von erfordern . Mit anderen Worten, liefert nur für Kontexte, die universell-polymorph verwenden. $P$ $x$ $P$ $x$ $x$ $P$ $x$ $x$

Meiner Meinung nach wird diese schöne Symmetrie verdeckt, wenn man über universellen / existenziellen Polymorphismus im Kalkül nachdenkt. Der Grund ist die starke Abhängigkeit vom Funktionsraumoperator, der leider kein Dualisierungsoperator ist, sondern etwas Komplizierteres (Kovariante in einem Argument, Kontravariante im anderen). $\lambda$

Martin Berger
quelle

Eine interessante Sichtweise (obwohl ich es nicht ganz verstehe :)). Die Idee ist dann zu prüfen, ob Gesetze, die in einer solchen allgemeinen Ansicht abgeleitet wurden, in konkreten Einstellungen von Typsystemen gelten. Und wo finde ich einen Einführungstext dazu?

umständlich

@socumbersome Die meisten vorhandenen Implementierungen des Polymorphismus verstehen das nicht ganz richtig. In der Tat wird die existenzielle Quantifizierung selten direkt implementiert. Ich fürchte, es gibt keinen Einführungstext, der die Dualität beschreibt. Wir haben es hier erklärt, aber es ist für ein spezialisiertes Publikum geschrieben.

Martin Berger