Les types universels sont-ils un sous-type ou un cas spécial de types existentiels?

Je voudrais savoir si un type universellement quantifié : est un sous-type, ou cas particulier, de type existentiellement quantifié avec la même signature: $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\}$

Je dirais "oui": si quelque chose est vrai "pour tous les X" ( pour tous les X ), alors cela doit aussi être vrai "pour certains X" ( ). Autrement dit, une instruction avec « » est simplement une version plus restreinte de la même instruction avec « »: $\forall X$ $\exists X$ $\forall$ $\exists$

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

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

Ai-je tort quelque part?

Contexte: pourquoi est-ce que je demande cela?

J'étudie les types existentiels afin de comprendre pourquoi et comment les "types [de données] abstraits ont un type existentiel" . Je ne peux pas avoir une bonne compréhension de ce concept par la seule théorie; J'ai aussi besoin d'exemples concrets.

Malheureusement, il est difficile de trouver de bons exemples de code car la plupart des langages de programmation ne prennent en charge que peu de types existentiels. (Par exemple, les caractères génériques de Haskellforall ou Java? .) D'un autre côté, les types universellement quantifiés sont pris en charge par de nombreux langages récents via des "génériques".

Pire encore, les génériques semblent facilement se mélanger avec les types existentiels , ce qui rend encore plus difficile de distinguer les types existentiels des types universels. Je suis curieux de savoir pourquoi cette confusion se produit si facilement. Une réponse à cette question pourrait l'expliquer: si les types universels ne sont en effet qu'un cas particulier de types existentiels, il n'est pas étonnant que les types génériques, par exemple Java List<T>, puissent être interprétés dans un sens ou dans l'autre.

logic type-theory typing Raphael
la source

Quelle est même la différence entre l'universel et l'existentiel?

Mathématiquement parlant, vous avez raison: Si forall x. P(x)alors exists x. P(x). Si les systèmes de types en tiennent compte lors de la vérification des types ... Je n'en ai aucune idée. +1 pour une question intéressante.

@deinan: Si P (x) ne vaut pour aucun x , alors certainement ∀xP (x) ne l'est pas. Ce que vous vouliez probablement dire, quand il n'y a pas de x , c'est-à-dire que ∀x∈XP (x) n'implique pas ∃x∈XP (x) si X = ∅ .

... Et notez que si ceux-ci sont réécrits sans notation d'ensemble, ils seront différents: ∀xx∈X⇒P (x) vs vs.xx∈X & P (x) et que ∃xx∈X⇒P (x) sera satisfaite trivialement par tout x pas de X .

Cool question. Dans Haskell, il est certainement vrai qu'une valeur de type (forall b. Show b => b) peut être passée à une fonction qui prend a (forall b. B), mais pas l'inverse, ce qui implique la substituabilité que vous attendez de une relation de sous-typage. Mais bien sûr, lorsque vous parlez de types, vous devez mentionner le système de types que vous regardez, en particulier si vous avez une algèbre de type formelle à l'esprit pour votre sémantique ...

Réponses:

D'abord, d'un point de vue mathématique, n'implique pas . L'implication est valable si et seulement si n'est pas vide. Cependant, dans les langages de programmation, il est rare de traiter des types vides (bien que cela se produise). $\forall x:T, P(x)$ $\exists x:T,P(x)$ $T$

Toujours d'un point de vue mathématique, même lorsque , les deux ne sont pas les mêmes. Si vous donnez aux types une sémantique définie, alors est un sur-ensemble de , pas le même type. (En fait, ce n'est pas un sur-ensemble; il est presque isomorphe à un sur-ensemble.) $(\forall x:T, P(x)) ⇒ (\exists x:T, P(x))$ $T_a$ $T_e$

Rapprochez-vous de la théorie du langage de programmation et voyons ce que ces types signifient réellement. est un type universel: si vous avez une valeur de ce type, vous pouvez construire pour tout . En particulier, si vous avez et de type , vous pouvez construire $T_a = ∀X.\{a: X, f: X\rightarrow\mathsf{bool}\}$ $A$ $A(M)$ $M:X$ $M_1$ $M_2$ $X$ et . En substance (et éventuellement en vigueur, selon la langue) est une fonction des types aux termes. En tant que tel, le type universel fournit uneparamétrisation detype: une valeur valable pour tous les types. Les types universels sont au cœur dupolymorphisme. $A(M_1)$ $A(M_2)$ $T_a$

Le type existentielle est une bête bien différente. Étant donné une valeur de type , il n'y a qu'un seul terme tel que , et pour ce terme $T_e = \exists X.\{a: X, f: X\rightarrow\mathsf{bool}\}$ $B$ $T_e$ $N: X$ $\pi_1(B) = N$ . Le type existentiel fournit un moyen de masquer la nature de ; il dit: «Il existe un type! Mais je ne vous dirai pas quoi! ». En tant que tel, le type existentiel fournit uneabstraction detype: une valeur cachée spécifique. Les types existentiels sont au cœur dessystèmesdemodules. $\pi_2(B) = \{a:N, f:N\rightarrow\mathsf{bool}\}$ $N$

Ne vous laissez pas induire en erreur par Haskell forall: malgré son nom, c'est une forme de quantificateur existentiel.

Pour le fond, je recommande fortement les types et les langages de programmation (les chapitres 23 et 24 traitent respectivement des types universels et des types existentiels). Il fournira un contexte utile pour comprendre les articles de recherche.

Gilles 'SO- arrête d'être méchant'
la source

Un petit reproche mineur et assez tardif - celui de Haskell forallest en effet un quantificateur universel dans le contexte original de la quantification implicite qu'il rend explicite, à savoir la visualisation des types polymorphes "de l'extérieur" pour les définitions de haut niveau. A "l'intérieur" d'une telle définition, lors de la manipulation d'arguments, les types polymorphes sont effectivement existentiels; chaque variable de type est liée à un certain type, mais nous ne savons pas (et ne pouvons pas) savoir ce qu'est ce type. À ma connaissance, aucune implémentation Haskell ne prend en charge les vrais types existentiels (bruts, de niveau supérieur), et je ne sais pas à quoi cela pourrait même servir.

CA McCann

Les types existentiels supportés par GHC sont des types qui (directement ou indirectement) ont des quantificateurs universels qui, vus de "l'extérieur", se produisent en position contravariante. Cela utilise à peu près la même dualité que celle de la négation logique, donc pour avoir de tels types existentiels au niveau supérieur, ils doivent être doublement contravariants, en utilisant un codage de type CPS (c'est l'équivalence qu'Uday Reddy donne). Notez que les quantificateurs existentiels dans l'intuitionnisme présentent des inconvénients similaires pour des raisons similaires.

CA McCann

Votre intuition que doit être intégrables dans $\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]

L'article que vous mentionnez pour les types existentiels est un peu théorique. Un article plus didacticiel est l'article de Cardelli et Wegner: sur la compréhension des types, l'abstraction des données et le polymorphisme . La plupart des manuels avancés sur les langages de programmation auraient également une discussion sur les types existentiels. Un bon livre à rechercher serait les fondations de Mitchell des langages de programmation .

Vous avez raison de dire que la plupart des langages de programmation n'ont pas explicitement de types existentiels. Cependant, beaucoup ont des types abstraits (ou sous un autre nom tel que "packages" ou "modules"). Ainsi, ils sont capables d' exprimer des valeurs de types existentiels, même s'ils ne traitent pas ces valeurs comme des entités de première classe.

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

Uday Reddy
la source