Sind Universaltypen Untertypen oder Sonderfälle existenzieller Typen?

Ich möchte wissen , ob ein universell quantifizierte Typ : ist ein Untertyp oder Sonderfall einer existentiell quantifiziert Typ mit derselben Signatur: $T_a$

T_{a} = \forall X : {a \in X, f : X \to {T, F}}

$T_a = \forall X: \left\{ a\in X,f:X→\{T, F\} \right\}$

T_{e}

$T_e$

T_{e} = \exists X : {a \in X, f : X \to {T, F}}

$T_e = \exists X: \left\{ a\in X,f:X→\{T, F\} \right\}$

Ich würde "ja" sagen: Wenn etwas wahr ist "für alle X" ( für alle X ), dann muss es auch wahr sein "für einige X" ( ). Das heißt, eine Anweisung mit ' ' ist einfach eine eingeschränktere Version derselben Anweisung mit ' ': $\forall X$ $\exists X$ $\forall$ $\exists$

\forall X, P (X) \overset{?}{⟹} \exists X, P (X) .

$∀X, P(X) \overset?\implies ∃X, P(X).$

Irre ich mich irgendwo

Hintergrund: Warum frage ich das?

Ich studiere existenzielle Typen, um zu verstehen, warum und wie "abstrakte [Daten] Typen existenzielle Typen haben" . Ich kann dieses Konzept nicht allein aus der Theorie verstehen. Ich brauche auch konkrete Beispiele.

Leider sind gute Codebeispiele schwer zu finden, da die meisten Programmiersprachen existenzielle Typen nur eingeschränkt unterstützen. (Zum Beispiel die Platzhalter von Haskellforall oder Java? .) Auf der anderen Seite werden universell quantifizierte Typen von vielen neueren Sprachen über "Generics" unterstützt.

Was noch schlimmer ist, Generika scheinen auch leicht mit existenziellen Typen verwechselt zu werden, was es noch schwieriger macht, existenzielle von universellen Typen zu unterscheiden. Ich bin gespannt, warum diese Verwechslung so leicht vorkommt. Eine Antwort auf diese Frage könnte es erklären: Wenn universelle Typen in der Tat nur ein Sonderfall existenzieller Typen sind, ist es kein Wunder, dass generische Typen, z. B. Javas List<T>, so oder so interpretiert werden können.

logic type-theory typing Raphael
quelle

Was ist überhaupt der Unterschied zwischen universell und existentiell?

Mathematisch gesehen haben Sie recht: Wenn forall x. P(x)ja exists x. P(x). Ob Typsysteme dies bei der Typenprüfung berücksichtigen ... Ich habe keine Ahnung. +1 für eine interessante Frage.

@deinan: Wenn P (x) für kein x gilt , gilt certainlyxP (x) mit Sicherheit nicht. Was Sie wahrscheinlich gemeint haben, ist, wenn es kein x gibt, dh ∀x∀XP (x) impliziert nicht ∃x∈XP (x), wenn X = ∅ .

... und beachte, dass wenn diese ohne gesetzte Notation umgeschrieben werden, sie anders aussehen: ∀xx∀X⇒P (x) vs. ∃xx∈X & P (x) und ∃xx∈X⇒P (x) wird trivial von jedem x erfüllt, das nicht von X stammt .

Coole Frage. In Haskell ist es sicher richtig, dass ein Wert vom Typ (forall b. Show b => b) an eine Funktion übergeben werden kann, die a (forall b. B) verwendet, aber nicht umgekehrt, was die von Ihnen erwartete Substituierbarkeit impliziert eine subtypisierende Beziehung. Aber wenn Sie über Typen sprechen, sollten Sie natürlich das Typensystem erwähnen, das Sie betrachten, besonders wenn Sie eine formale Typalgebra für Ihre Semantik im Sinn haben ...

Antworten:

$\forall x:T, P(x)$ $\exists x:T,P(x)$ $T$

$(\forall x:T, P(x)) ⇒ (\exists x:T, P(x))$ $T_a$ $T_e$

$T_a = ∀X.\{a: X, f: X\rightarrow\mathsf{bool}\}$ $A$ $A(M)$ $M:X$ $M_1$ $M_2$ $X$ $A(M_1)$ $A(M_2)$ $T_a$

$T_e = \exists X.\{a: X, f: X\rightarrow\mathsf{bool}\}$ $B$ $T_e$ $N: X$ $\pi_1(B) = N$ $\pi_2(B) = \{a:N, f:N\rightarrow\mathsf{bool}\}$ $N$

Lassen Sie sich nicht von Haskells irreführen forall: Trotz seines Namens handelt es sich um eine Art existenziellen Quantifikator.

Für den Hintergrund empfehle ich dringend Typen und Programmiersprachen (Kapitel 23 und 24 behandeln universelle Typen bzw. existenzielle Typen). Es bietet nützliche Hintergrundinformationen zum Verständnis von Forschungsartikeln.

Gilles 'SO - hör auf böse zu sein'
quelle

Ein kleiner und ziemlich später Streitpunkt - Haskells forallist in der Tat ein universeller Quantifizierer im ursprünglichen Kontext der impliziten Quantifizierung, die er explizit macht, nämlich die Betrachtung polymorpher Typen "von außen" für Definitionen auf oberster Ebene. Im "Inneren" einer solchen Definition sind polymorphe Typen bei der Manipulation von Argumenten tatsächlich existenziell. Jede Typvariable ist an einen Typ gebunden, aber wir wissen (und können) nicht, was dieser Typ ist. Meines Wissens unterstützt keine Haskell-Implementierung echte (rohe, übergeordnete) existenzielle Typen, und mir ist nicht klar, welchem Zweck dies überhaupt dienen würde.

CA McCann

Die existenziellen Typen, die von GHC unterstützt werden, sind Typen, die (direkt oder indirekt) universelle Quantifizierer haben, die, von "außen" gesehen, in entgegengesetzter Position auftreten. Dies verwendet ungefähr die gleiche Dualität wie die logische Negation. Um solche existenziellen Typen auf oberster Ebene zu haben, müssen sie doppelt kontravariant sein und eine CPS-ähnliche Codierung verwenden (dies ist die Äquivalenz, die Uday Reddy angibt). Es ist zu beachten, dass existenzielle Quantifizierer in der Intuitionistik aus ähnlichen Gründen ähnliche Nachteile aufweisen.

CA McCann

$\forall X.\, P(X)$ $\exists X.\, P(X)$

$\forall X.\, (X \times (X \to Bool))$ $X$ $\exists X.\, (X \times (X \to Bool))$

 f (p: \forall X. (X * (X -> Bool))) = PACK X = Bool WITH p[Bool]

Der Artikel, den Sie für existenzielle Typen erwähnen, ist ein bisschen theoretisch. Ein weiterer Tutorial-Artikel ist der Artikel von Cardelli und Wegner: Zum Verständnis von Typen, Datenabstraktion und Polymorphismus . In den meisten fortgeschrittenen Lehrbüchern über Programmiersprachen würden auch existenzielle Typen erörtert. Ein gutes Buch zum Nachschlagen wäre Mitchells Grundlagen der Programmiersprachen .

Sie haben Recht, dass die meisten Programmiersprachen nicht explizit existenzielle Typen haben. Viele haben jedoch abstrakte Typen (oder einen anderen Namen wie "Pakete" oder "Module"). Sie können also Werte existenzieller Typen ausdrücken , obwohl sie solche Werte nicht als erstklassige Entitäten behandeln.

$\exists X.\, P(X)$ $\forall Y.\, (\forall X.\, P(X) \rightarrow Y) \to Y$ $\forall$

Uday Reddy
quelle