Qu'est-ce qu'un type existentiel?

https://stackoverflow.com/questions/292274

08-07-2019
|

Question

J'ai lu l'article Wikipedia Types existentiels . J'ai compris qu'ils s'appellent des types existentiels à cause de l'opérateur existentiel (& # 8707;). Je ne suis toutefois pas sûr de savoir à quoi ça sert. Quelle est la différence entre

T = ∃X { X a; int f(X); }

T = ∀x { X a; int f(X); }

La solution

Lorsque quelqu'un définit un type universel ∀X, il dit: Vous pouvez brancher le type de votre choix, je n'ai pas besoin de connaître le type pour faire mon travail, je ne ferai que renvoyer de manière opaque comme X .

Lorsque quelqu'un définit un type existentiel ∃X, il dit: j'utiliserai le type que je veux ici; vous ne saurez rien sur le type, vous ne pouvez donc vous y référer que de manière opaque: copy .

Les types universels vous permettent d’écrire des choses comme:

void copy<T>(List<T> source, List<T> dest) {
   ...
}

La fonction T n'a aucune idée de ce que runAllCompilers sera réellement, mais elle n'en a pas besoin.

Les types existentiels vous permettraient d’écrire des choses comme:

interface VirtualMachine<B> {
   B compile(String source);
   void run(B bytecode);
}

// Now, if you had a list of VMs you wanted to run on the same input:
void runAllCompilers(List<∃B:VirtualMachine<B>> vms, String source) {
   for (∃B:VirtualMachine<B> vm : vms) {
      B bytecode = vm.compile(source);
      vm.run(bytecode);
   }
}

Chaque implémentation de machine virtuelle dans la liste peut avoir un type de bytecode différent. La fonction VirtualMachine.compile n'a aucune idée de ce que le type de code intermédiaire est, mais elle n'en a pas besoin; il ne fait que relayer le bytecode de VirtualMachine.run à List<?>.

Les caractères génériques de type Java (ex: VMWrapper) sont une forme très limitée de types existentiels.

Mise à jour: Vous avez oublié de préciser que vous pouvez en quelque sorte simuler des types existentiels avec des types universels. Commencez par envelopper votre type universel pour masquer le paramètre type. Deuxièmement, invert control (cela échange efficacement la partie & "; Vous &" Et & "I &" Dans les définitions ci-dessus, qui constitue la principale différence entre existentials et universaux).

// A wrapper that hides the type parameter 'B'
interface VMWrapper {
   void unwrap(VMHandler handler);
}

// A callback (control inversion)
interface VMHandler {
   <B> void handle(VirtualMachine<B> vm);
}

Nous pouvons maintenant appeler VMHandler notre propre handle qui possède une fonction B universellement typée. L’effet net est le même, notre code doit traiter <=> comme opaque.

void runWithAll(List<VMWrapper> vms, final String input)
{
   for (VMWrapper vm : vms) {
      vm.unwrap(new VMHandler() {
         public <B> void handle(VirtualMachine<B> vm) {
            B bytecode = vm.compile(input);
            vm.run(bytecode);
         }
      });
   }
}

Un exemple d'implémentation de machine virtuelle:

class MyVM implements VirtualMachine<byte[]>, VMWrapper {
   public byte[] compile(String input) {
      return null; // TODO: somehow compile the input
   }
   public void run(byte[] bytecode) {
      // TODO: Somehow evaluate 'bytecode'
   }
   public void unwrap(VMHandler handler) {
      handler.handle(this);
   }
}

Autres conseils

Une valeur de un type existentiel comme ∃x. F(x) est un couple contenant du type x et une valeur du type F(x). Tandis qu'une valeur de type polymorphe comme ∀x. F(x) est une fonction qui prend un type F et produit une valeur de type T. Dans les deux cas, le type se ferme sur un constructeur de type X.

Notez que cette vue mélange les types et les valeurs. La preuve existentielle est un type et une valeur. La preuve universelle est une famille entière de valeurs indexées par type (ou un mappage de types en valeurs).

La différence entre les deux types que vous avez spécifiés est la suivante:

T = ∃X { X a; int f(X); }

Cela signifie qu'une valeur de type a:X contient un type appelé f:X->int, une valeur a et une fonction int. Un producteur de valeurs de type f peut choisir un type pour null et un consommateur ne peut rien connaître de n+1. Sauf qu'il existe un exemple appelé n et que cette valeur peut être transformée en <=> en la donnant à <=>. En d’autres termes, une valeur de type <=> sait comment produire un <=>. Eh bien, nous pourrions éliminer le type intermédiaire <=> et simplement dire:

T = int

L’universellement quantifié est un peu différent.

T = ∀X { X a; int f(X); }

Cela signifie qu’une valeur de type <=> peut être attribuée à n’importe quel type <=>. Elle produira une valeur <=> et une fonction <=> quel que soit <=> . En d'autres termes: un consommateur de valeurs de type <=> peut choisir n'importe quel type pour <=>. Et un producteur de valeurs de type <=> ne peut rien savoir de <=>, mais il doit être capable de produire une valeur <=> pour tout choix de <=>, et de pouvoir transformer un tel valeur dans un <=>.

Il est évident que mettre en œuvre ce type est impossible, car aucun programme ne peut produire une valeur de tous les types imaginables. Sauf si vous autorisez des absurdités telles que <=> ou les bas.

Etant donné qu'un existentiel est une paire, un argument existentiel peut être converti en un argument universel via currying .

(∃b. F(b)) -> Int

est identique à:

∀b. (F(b) -> Int)

Le premier est un existentiel rang-2 . Cela conduit à la propriété utile suivante:

Chaque type de rang existentiellement quantifié <=> est un type de rang quantifié universellement <=>.

Il existe un algorithme standard pour transformer les éléments existentiels en universaux, appelé Skolemization .

Je pense qu'il est logique d'expliquer les types existentiels en même temps que les types universels, car les deux concepts sont complémentaires, c'est-à-dire que l'un est & "opposé &"; de l'autre.

Je ne peux pas répondre à tous les détails concernant les types existentiels (comme donner une définition exacte, énumérer toutes les utilisations possibles, leur relation avec les types de données abstraits, etc.), car je ne connais tout simplement pas suffisamment pour cela. Je ne montrerai que (avec Java) ce que cet article de HaskellWiki déclare comme étant le effet principal des types existentiels:

Les types existentiels peuvent être utilisés à différentes fins. Mais ce qu’ils font , c’est «masquer» une variable de type du côté droit. Normalement, toute variable de type apparaissant à droite doit également apparaître à gauche [& # 8230;]

Exemple de configuration:

Le pseudo-code suivant n'est pas tout à fait valide en Java, même s'il serait assez facile de résoudre ce problème. En fait, c'est exactement ce que je vais faire dans cette réponse!

class Tree<α>
{
    α       value;
    Tree<α> left;
    Tree<α> right;
}

int height(Tree<α> t)
{
    return (t != null)  ?  1 + max( height(t.left), height(t.right) )
                        :  0;
}

Permettez-moi d’écrire brièvement ceci pour vous. Nous définissons & # 8230;

un type récursif Tree<α> qui représente un nœud dans une arborescence binaire. Chaque noeud stocke un value type & # 945; et contient des références à des sous-arbres facultatifs left et right du même type.
une fonction height qui renvoie la distance la plus éloignée d'un nœud feuille au nœud racine t.

Maintenant, convertissons le pseudo-code ci-dessus pour t.value en syntaxe Java appropriée! (Je continuerai d'omettre certains motifs habituels, comme les modificateurs d'orientation et d'objet.) Je vais vous montrer deux solutions possibles.

1. Solution de type universelle:

La solution la plus évidente consiste simplement à rendre ? générique en introduisant le paramètre de type & # 945; dans sa signature:

<α> int height(Tree<α> t)
{
    return (t != null)  ?  1 + max( height(t.left), height(t.right) )
                        :  0;
}

Cela vous permettrait de déclarer des variables et de créer des expressions de type & # 945; dans cette fonction, si vous le souhaitez. Mais ...

2. Solution de type existentielle:

Si vous regardez le corps de notre méthode, vous remarquerez que nous n’avons ni accès à, ni travaillé avec quoi que ce soit du type & # 945; ! Il n'y a pas d'expressions ayant ce type, ni de variables déclarées avec ce type ... alors pourquoi devons-nous rendre Object générique? Pourquoi ne pouvons-nous pas simplement oublier & # 945; ? En fin de compte, nous pouvons:

int height(Tree<?> t)
{
    return (t != null)  ?  1 + max( height(t.left), height(t.right) )
                        :  0;
}

Comme je l’ai écrit au tout début de cette réponse, les types existentiel et universel sont de nature complémentaire / double. Ainsi, si la solution de type universel devait rendre <=> plus générique, il fallait alors s'attendre à ce que les types existentiels aient l'effet inverse: le rendre moins générique, notamment en masquant / supprimer le paramètre de type & # 945; .

En conséquence, vous ne pouvez plus faire référence au type de <=> dans cette méthode ni manipuler les expressions de ce type, car aucun identifiant n’a été lié à celle-ci. (Le <=> le caractère générique est un jeton spécial et non un identifiant qui " capture " un type.) <=> est effectivement devenu opaque; peut-être que la seule chose que vous puissiez faire est de le transtyper en <=>.

Résumé:

===========================================================
                     |    universally       existentially
                     |  quantified type    quantified type
---------------------+-------------------------------------
 calling method      |                  
 needs to know       |        yes                no
 the type argument   |                 
---------------------+-------------------------------------
 called method       |                  
 can use / refer to  |        yes                no  
 the type argument   |                  
=====================+=====================================

Ce sont tous de bons exemples, mais j’ai choisi d’y répondre un peu différemment. Rappelez-vous des maths que & # 8704; x. P (x) signifie & Quot; pour tous les x, je peux prouver que P (x) & Quot; En d’autres termes, c’est une sorte de fonction, vous me donnez un x et j’ai une méthode pour vous le prouver.

En théorie des types, nous ne parlons pas de preuves, mais de types. Donc, dans cet espace, nous entendons & "; Quel que soit le type X que vous me donnez, je vais vous donner un type spécifique P &"; Maintenant, comme P ne donne pas beaucoup d’informations à P sur X, mis à part le fait qu’il s’agit d’un type, P ne peut pas en faire grand chose, mais il existe quelques exemples. P peut créer le type de & "; Toutes les paires du même type &" ;:: P<X> = Pair<X, X> = (X, X). Ou nous pouvons créer le type d'option: P<X> = Option<X> = X | Nil, où Nil est le type des pointeurs nuls. Nous pouvons en faire une liste: List<X> = (X, List<X>) | Nil. Notez que le dernier est récursif, les valeurs de List<X> sont des paires où le premier élément est un X et le deuxième élément est un ∃X.P<X> ou bien un pointeur nul.

Maintenant, en maths & # 8707; x. P (x) signifie & "Je peux prouver qu’il existe un x particulier tel que P (x) est vrai &"; Il peut y avoir beaucoup de tels x, mais pour le prouver, un suffit. Une autre façon d’y penser est qu’il doit exister un ensemble non vide de paires preuve-preuve-preuve {(x, P (x))}.

Traduit en théorie des types: un type de la famille P<X> est un type X et un type correspondant <=>. Remarquez qu'avant, nous avons donné X à P (si bien que nous sachions tout sur X mais très peu sur P), l'inverse est maintenant vrai. <=> ne promet de donner aucune information sur X, mais simplement qu'il y en a une et qu'il s'agit bien d'un type.

En quoi est-ce utile? Eh bien, P pourrait être un type ayant le moyen d’exposer son type interne X. Un exemple serait un objet masquant la représentation interne de son état X. Bien que nous n’ayons aucun moyen de le manipuler directement, nous pouvons en observer l’effet en: piquer sur P. Il pourrait y avoir de nombreuses implémentations de ce type, mais vous pouvez utiliser tous ces types, quel que soit le type choisi.

Un type existentiel est un type opaque.

Pensez à un descripteur de fichier sous Unix. Vous savez que son type est int, vous pouvez donc le forger facilement. Vous pouvez, par exemple, essayer de lire à partir du descripteur 43. S'il se trouve que le programme a un fichier ouvert avec ce descripteur particulier, vous le lirez. Votre code ne doit pas nécessairement être malveillant, il doit simplement être négligé (par exemple, le descripteur peut être une variable non initialisée).

Un type existentiel est caché de votre programme. Si fopen a renvoyé un type existentiel, vous pouvez simplement l'utiliser avec certaines fonctions de bibliothèque qui acceptent ce type existentiel. Par exemple, le pseudo-code suivant serait compilé:

let exfile = fopen("foo.txt"); // No type for exfile!
read(exfile, buf, size);

L’interface " lisez " est déclaré comme:

Il existe un type T tel que:

size_t read(T exfile, char* buf, size_t size);

La variable exfile n'est pas un int, ni un char*, ni un struct File & # 8212; vous ne pouvez rien exprimer dans le système de types. Vous ne pouvez pas déclarer une variable dont le type est inconnu et vous ne pouvez pas convertir, par exemple, un pointeur dans ce type inconnu. La langue ne vous laissera pas.

Pour répondre directement à votre question:

Avec le type universel, les utilisations de T doivent inclure le paramètre de type X. Par exemple T<String> ou T<Integer>. Pour le type existentiel utilisé par T<?>, n'incluez pas ce paramètre car il est inconnu ou sans intérêt - utilisez simplement MyClass (ou en Java ?).

Plus d'informations:

Les types universels / abstraits et les types existentiels sont une dualité de perspective entre le consommateur / client d’un objet / fonction et son producteur / son implémentation. Quand un côté voit un type universel, l’autre voit un type existentiel.

En Java, vous pouvez définir une classe générique:

public class MyClass<T> {
   // T is existential in here
   T whatever; 
   public MyClass(T w) { this.whatever = w; }

   public static MyClass<?> secretMessage() { return new MyClass("bazzlebleeb"); }
}

// T is universal from out here
MyClass<String> mc1 = new MyClass("foo");
MyClass<Integer> mc2 = new MyClass(123);
MyClass<?> mc3 = MyClass.secretMessage();

Du point de vue d'un client sur MyClass<?>, secretMessage() est universel, car vous pouvez substituer tout type à Object lorsque vous utilisez cette classe et vous devez connaître le type réel de T chaque fois que vous utilisez une instance de T<Int>
Du point de vue des méthodes d'instance dans T<Long> lui-même, <=> est existentiel, car il ne connaît pas le type réel de <=>
En Java, <=> représente le type existentiel - ainsi, lorsque vous êtes dans la classe, <=> est fondamentalement <=>. Si vous souhaitez gérer une instance de <=> avec <=> existentiel, vous pouvez déclarer <=> comme dans l'exemple <=> ci-dessus.

Les types existentiels sont parfois utilisés pour masquer les détails d’implémentation de quelque chose, comme indiqué ailleurs. Une version Java de ceci pourrait ressembler à:

public class ToDraw<T> {
    T obj;
    Function<Pair<T,Graphics>, Void> draw;
    ToDraw(T obj, Function<Pair<T,Graphics>, Void>
    static void draw(ToDraw<?> d, Graphics g) { d.draw.apply(new Pair(d.obj, g)); }
}

// Now you can put these in a list and draw them like so:
List<ToDraw<?>> drawList = ... ;
for(td in drawList) ToDraw.draw(td);

C’est un peu délicat de capturer cela correctement car je fais semblant d’être dans une sorte de langage de programmation fonctionnel, ce que Java n’est pas. Mais le point ici est que vous capturez une sorte d'état plus une liste de fonctions qui opèrent sur cet état et que vous ne connaissez pas le type réel de la partie state, mais les fonctions le font car elles ont déjà été appariées à ce type .

Maintenant, en Java, tous les types non primitifs non finaux sont en partie existentiels. Cela peut sembler étrange, mais comme une variable déclarée <=> peut potentiellement être une sous-classe de <=>, vous ne pouvez pas déclarer le type spécifique, mais seulement & "Ce type ou une sous-classe &" ;. Ainsi, les objets sont représentés sous la forme d'un bit d'état et d'une liste de fonctions qui agissent sur cet état - la fonction à appeler est déterminée par la recherche au moment de l'exécution. Cela ressemble beaucoup à l'utilisation des types existentiels ci-dessus dans lesquels vous avez une partie d'état existentiel et une fonction qui agit sur cet état.

Dans les langages de programmation à typage statique sans sous-typage ni transtypage, les types existentiels permettent de gérer des listes d'objets de types différents. Une liste de <=> ne peut pas contenir de <=>. Cependant, une liste de <=> peut contenir n’importe quelle variation de <=>, ce qui permet de placer de nombreux types de données différents dans la liste et de les convertir tous en un entier (ou effectuer toutes les opérations fournies dans la structure de données) à la demande. .

On peut presque toujours convertir un enregistrement de type existentiel en un enregistrement sans utiliser de fermeture. Une fermeture est également typée de manière existentielle en ce sens que les variables libres sur lesquelles elle est fermée sont masquées à l'appelant. Ainsi, un langage qui prend en charge les fermetures mais pas les types existentiels peut vous permettre de créer des fermetures partageant le même état caché que celui que vous auriez placé dans la partie existentielle d’un objet.

Il semble que je & # 8217; j'arrive un peu en retard, mais de toute façon, ce document ajoute une autre vue sur ce que sont les types existentiels, même si ce n'est pas spécifiquement lié au langage, il devrait alors être relativement plus facile à comprendre les types existentiels: < a href = "http://www.cs.uu.nl/groups/ST/Projects/ehc/ehc-book.pdf" rel = "noreferrer"> http://www.cs.uu.nl/groups/ ST / Projets / ehc / ehc-book.pdf (chapitre 8)

La différence entre un type quantifié universellement et existentiellement peut être caractérisée par l'observation suivante:



L'utilisation d'une valeur avec un & # 8704; type quantifié détermine le type à choisir pour l'instanciation de la variable de type quantifiée. Par exemple, l'appelant de la fonction d'identité & # 8220; id :: & # 8704; a.a & # 8594; un & # 8221; détermine le type à choisir pour la variable de type a pour cette application particulière de id. Pour l'application de fonction & # 8220; id 3 & # 8221; ce type est égal à Int.



La création d'une valeur avec un & # 8707; type quantified détermine et masque le type de la variable de type quantifiée. Par exemple, un créateur de & # 8220; & # 8707; a. (A, un & # 8594; Int) & # 8221; peut avoir construit une valeur de ce type à partir de & # 8220; (3, & # 955; x & # 8594; x) & # 8221 ;; un autre créateur a construit une valeur du même type, à partir de & # 8220; (& # 8217; x & # 8217 ;, & # 955; x.!! # 8594; ord x) # 8221 ;. Du point de vue de l'utilisateur, les deux valeurs ont le même type et sont donc interchangeables. La valeur a un type spécifique choisi pour la variable de type a, mais nous ne savons pas quel type, alors cette information ne peut plus être exploitée. Cette information de type spécifique à la valeur a été & # 8216; oubliée & # 8217 ;; nous savons seulement qu'il existe.

Il existe un type universel pour toutes les valeurs du ou des paramètres de type. Un type existentiel n'existe que pour les valeurs du ou des paramètres de type qui satisfont aux contraintes du type existentiel.

Par exemple, en Scala, une façon d’exprimer un type existentiel est un type abstrait qui est limité à certaines limites supérieure ou inférieure.

trait Existential {
  type Parameter <: Interface
}

De manière équivalente, un type universel contraint est un type existentiel comme dans l'exemple suivant.

trait Existential[Parameter <: Interface]

Tout site utilisateur peut utiliser le Interface, car tout sous-type instanciable de Existential doit définir le type Parameter qui doit implémenter le List[_].

Un cas dégénéré d'un type existentiel dans Scala est un type abstrait auquel il n'est jamais fait référence. défini par n'importe quel sous-type. Cela a effectivement une notation abrégée List<?> en scala et <=> en Java.

Ma réponse a été inspirée par la types abstraits et existentiels. La diapositive d'accompagnement facilite la compréhension.

Les recherches sur les types de données abstraits et la dissimulation d’informations ont introduit les types existentiels dans les langages de programmation. Faire un résumé de type de données cache les informations sur ce type, donc un client de ce type ne peut pas en abuser. Supposons que vous ayez une référence à un objet ... certaines langues vous permettent de transformer cette référence en une référence à des octets et de faire tout ce que vous voulez sur ce morceau de mémoire. Afin de garantir le comportement d'un programme, il est utile qu'un langage impose de n'agir que sur la référence à l'objet via les méthodes fournies par le concepteur de l'objet. Vous savez que le type existe, mais rien de plus.

Voir:

Les types abstraits ont un type existentiel, MITCHEL & amp; PLOTKIN

http://theory.stanford.edu/~jcm /papers/mitch-plotkin-88.pdf

J'ai créé ce diagramme. Je ne sais pas si c'est rigoureux. Mais si cela aide, je suis content.

Si je comprends bien, c’est une façon mathématique de décrire les interfaces / classes abstraites.

Comme pour T = & # 8707; X {X a; int f (X); }

Pour C #, cela se traduirait par un type abstrait générique:

abstract class MyType<T>{
    private T a;

    public abstract int f(T x);
}

& "Existentiel &"; signifie simplement qu'il existe un type qui obéit aux règles définies ici.

Licencié sous: CC-BY-SA avec attribution

Non affilié à StackOverflow