Was ist eine existentielle Art?

https://stackoverflow.com/questions/292274

08-07-2019
|

Frage

ich durch den Wikipedia-Artikel lesen Existentielle Typen . Ich sammelte, dass sie wegen der existenziellen Betreiber existentielle Typen genannt werden (∃). Ich bin mir nicht sicher, was der Punkt ist, though. Was ist der Unterschied zwischen

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

und

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

Lösung

Wenn jemand eine universelle Art ∀X definiert sie sagen: Sie können in Plug welcher Art auch immer Sie wollen, ich brauche nichts über die Art zu wissen, meine Arbeit zu tun, werde ich nur darauf verweisen deckend als X .

Wenn jemand definiert eine existenzielle Art ∃X sie sagen: Ich werde verwenden, was Typ ich hier wollen; Sie wissen nicht nichts über die Art, so können Sie nur es deckend als X beziehen.

Universal-Typen können Sie schreiben Dinge wie:

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

Die copy Funktion hat keine Ahnung, was T tatsächlich sein wird, aber es nicht braucht.

existentielle Typen würden Sie schreiben Dinge wie:

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);
   }
}

Jede virtuelle Maschine Implementierung in der Liste einen anderen Bytecode-Typen hat. Die runAllCompilers Funktion hat keine Ahnung, was der Bytecode-Typ ist, aber es nicht brauchen; Alles, was es tut, ist den Bytecode von VirtualMachine.compile zu VirtualMachine.run zuleiten.

Java-Typ Platzhalter (ex: List<?>) ist eine sehr begrenzte Form der Existenz Typen

Update: vergessen zu erwähnen, dass Sie eine Art existentielle Typen mit Universaltypen simulieren können. Zuerst wickeln Sie Ihre Universal-Typ den Typ-Parameter zu verbergen. Zweitens Invertzucker Steuerung (dies effektiv tauscht die „Sie“ und „I“ Teil oben in den Definitionen, die die primäre Unterschied zwischen Existenziale und Universalien ist).

// 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);
}

Jetzt können wir haben die VMWrapper eigenen VMHandler nennen, die eine allgemein typisierte handle Funktion hat. Der Netto-Effekt ist der gleiche, unseren Code hat B als undurchsichtig zu behandeln.

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);
         }
      });
   }
}

Ein Beispiel VM Implementierung:

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);
   }
}

Andere Tipps

Ein Wert von eine existentiellen Art wie ∃x. F(x) ist ein Paar enthält einig type x und ein Wert von der Typ F(x). Während ein Wert einer polymorphen Typ wie ∀x. F(x) ist eine Funktion , die irgendeine Art x nimmt und erzeugt einen Wert vom Typ F(x). In beiden Fällen schließt die Art über einige Typkonstruktor F.

Beachten Sie, dass diese Ansicht Typen und Werte mischt. Der Existenzbeweis ist ein Typ und ein Wert. Der universelle Beweis ist eine ganze Familie von Werten nach Typ (oder eine Abbildung von Typen auf Werte) indiziert werden.

So ist der Unterschied zwischen den beiden Typen, die Sie wird wie folgt angegeben:

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

Das bedeutet: Ein Wert vom Typ T enthält einen Typen X einen Wert a:X, und eine Funktion f:X->int genannt. Ein Hersteller von Werten des Typs T bekommt wählen jeder Typ für X und einem Verbraucher nichts über X wissen kann. Abgesehen davon, dass es gibt ein Beispiel dafür a und dass dieser Wert genannt kann in eine int gedreht werden, indem es f. Mit anderen Worten, weiß ein Wert vom Typ T wie ein int irgendwie zu produzieren. Nun, wir könnten den Zwischentyp X beseitigen und einfach sagen:

T = int

Die allquantifizierte ist ein wenig anders aus.

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

Das bedeutet: Ein Wert vom Typ T kann jede Art X gegeben werden, und es wird ein Wert a:X, und eine Funktion f:X->int egal was X ist produzieren. Mit anderen Worten: ein Verbraucher von Werten vom Typ T kann jede Art für X wählen. Und ein Hersteller von Werten des Typs T kann nicht überhaupt etwas über X wissen, aber es muss in der Lage einen Wert a für jede Wahl von X zu produzieren, und der Lage sein, einen solchen Wert in einen int zu drehen.

Offensichtlich diese Art der Umsetzung ist nicht möglich, weil es kein Programm, das einen Wert von jeder erdenklichen Art produzieren kann. Es sei denn, Sie erlauben Absurditäten wie null oder Böden.

Da ein existentielles ein Paar ist, ein existentielles Argument kann über auf einen universellen umgewandelt wird currying .

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

ist die gleiche wie:

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

Das erstere ist ein Rang-2 existentiell. Dies führt zu der folgenden nützlichen Eigenschaft:

Jede existenzquantifizierte Art von Rang n+1 ist eine universell quantifizierten Art von Rang n.

Es ist ein Standard-Algorithmus für Existenziale in Universalien drehen, genannt Skolemisierung .

Ich denke, dass es Sinn macht, mit Universal-Typen existentielle Typen zusammen zu erklären, da die beiden Konzepte sind komplementär, das heißt eine ist das „Gegenteil“ von der anderen Seite.

Ich kann nicht jedes Detail über existentielle Typen beantworten (wie gibt eine genaue Definition, eine Liste alle möglichen Verwendungen, ihre Beziehung zu abstrakten Datentypen, etc.), weil ich einfach nicht sachkundig genug. Ich werde zeigen, nur (mit Java), welche dieses HaskellWiki Artikel Staaten die sein Hauptwirkung der Existenz Typen:

können Existentielle Typen verwendet für verschiedene Zwecke. Aber was sie tun ist zu ‚verstecken‘ eine Variable vom Typ auf der rechten Seite. Normalerweise auch auf der linken Seite jeder Typ Variable auf der rechten Seite erscheinen, erscheinen [...]

Beispiel Set-up:

Der folgende Pseudo-Code ist nicht ganz gültig Java, obwohl es leicht genug sein würde, das zu beheben. In der Tat, das ist genau das, was ich in dieser Antwort tun werde!

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

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

Lassen Sie mich kurz für Sie buchstabieren. Wir definieren ...

eine rekursive Art Tree<α> die einen Knoten in einem binären Baum darstellt. Jeder Knoten speichert eine value eines Typs α und hat Hinweise auf optionale left und right Unterstrukturen des gleichen Typs.
eine Funktion height die die weiteste Entfernung von jedem Blattknoten zum Wurzelknoten t zurückgibt.

Lassen Sie uns nun die obige Pseudo-Code für height in die richtige Java-Syntax verwandeln! (Ich werde auf halten einige Textvorschlag der Kürze halber weggelassen, wie Objektorientierung und Zugänglichkeit Modifikatoren.) Ich werde zwei mögliche Lösungen zeigen.

1. Universallösung:

Die naheliegendste Lösung ist einfach height generic zu machen, indem Sie den Typ-Parameter Einführung α in seine Signatur:

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

Auf diese Weise könnten Sie Variablen deklarieren und Ausdrücke vom Typ erstellen α innerhalb dieser Funktion, wenn man will. Aber ...

2. Existentielle Typ Lösung:

Wenn Sie an unserer Methode Körper betrachten, werden Sie feststellen, dass wir nicht tatsächlich den Zugriff auf oder die Arbeit mit, etwas vom Typ α ! Es gibt keine Ausdrücke, den Typen, noch irgendwelche Variablen mit diesem Typ deklarierten ... so, warum müssen wir height Generika überhaupt machen? Warum kann nicht einfach vergessen wir α ? Wie sich herausstellt, können wir:

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

Wie ich am Anfang dieser Antwort schrieb, existenzielle und universelle Typen ergänzen / dual in der Natur. So war, wenn die Universallösung height machen mehr generic, dann sollten wir erwarten, dass existentielle Typen die entgegengesetzte Wirkung haben: so dass es weniger generic, nämlich durch Ausblenden / Entfernen der Typ-Parameter α .

Als Folge können Sie nicht beziehen sich mehr auf die Art der t.value in diesem Verfahren noch manipulieren Bekundungen dieser Art, weil keine Kennung an ihn gebunden ist. (Die ? Wildcard ein spezielles Token ist, nicht eine Kennung, die „Captures . "a-Typ) t.value hat effektiv undurchsichtig; vielleicht das einzige, was man damit noch tun kann, ist Typ Guss es Object.

Zusammenfassung:

===========================================================
                     |    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   |                  
=====================+=====================================

Das sind alles gute Beispiele, aber ich wählen, um es ein wenig anders zu beantworten. Erinnern Sie sich an Mathe, dass ∀x. P (x) bedeutet "für alle x ist, ich das P beweisen kann (x)". Mit anderen Worten, es ist eine Art von Funktion, geben Sie mir eine x und ich habe eine Methode, die für Sie zu beweisen.

Bei Typ-Theorie, wir sprechen hier nicht über Beweise, sondern von Typen. Also in diesem Raum, den wir meinen „für jede Art X Sie mir geben, gebe ich Ihnen einen bestimmten Typ P“. Jetzt, da wir nicht viele Informationen über P X neben der Tatsache geben, dass es ein Typ ist, kann P nicht viel tun mit ihm, aber es gibt einige Beispiele. P<X> = Pair<X, X> = (X, X): P kann die Art der „alle Paare des gleichen Typs“ erstellen. Oder wir können die Option Typ erstellen: P<X> = Option<X> = X | Nil, wo Nil die Art der Null-Zeiger ist. Wir können eine Liste machen aus ihm heraus: List<X> = (X, List<X>) | Nil. Beachten Sie, dass die letzte ist rekursiv, Werte von List<X> sind entweder paarweise, wo das erste Element ist ein X und das zweite Element ist ein List<X> oder es ist ein Nullzeiger.

Nun, in Mathe ∃x. P (x) bedeutet „kann ich beweisen, dass es eine bestimmte x, so ist, dass P (x) wahr ist“. Es kann viele solcher xs sein, aber um es zu beweisen, ist genug. Eine weitere Möglichkeit, daran zu denken, dass es eine nicht-leere Menge von evidenz und sicheren Paare bestehen muss {(x, P (x))}.

übersetzt Theorie: Ein Typ in der Familie ∃X.P<X> ist ein Typ X und ein entsprechender Typ P<X>. Beachten Sie, dass während bevor wir X P gab, (so dass wir alles wussten von X aber P sehr wenig), dass das Gegenteil jetzt wahr ist. P<X> verspricht keine Informationen über X, nur, dass es dort ist, und dass es in der Tat eine Art.

Wie ist das sinnvoll? Nun, P ein Typ sein könnte, die einen Weg hat seine internen Typ X. Ein Beispiel Aussetzen würde ein Objekt sein, das die interne Darstellung seines Zustands X. versteckt Obwohl wir keine Möglichkeit, direkt zu manipulieren sie haben, können wir seine Wirkung beobachten, indem bei P. Stossen Es könnte viele Implementierungen dieser Art sein, aber man konnte alle diese Typen unabhängig davon, welche bestimmten gewählt wurde verwenden.

Eine existentielle Art ist eine undurchsichtige Art.

Denken Sie an einer Datei-Handelte in Unix. Sie kennen den Typ int ist, so können Sie es leicht fälschen. Sie können zum Beispiel versuchen, vom Griff 43 lesen Wenn es passiert, so dass das Programm eine Datei mit diesem Griff geöffnet hat, werden Sie von ihnen lesen. Der Code muss nicht böswillig sein, nur schlampig (zum Beispiel der Griff könnte eine nicht initialisierte Variable sein).

Eine existenzielle Art ist aus Ihrem Programm versteckt. Wenn fopen eine existenzielle Art zurückgegeben, alles, was man damit machen könnte, ist es mit einigen Bibliotheksfunktionen zu verwenden, der diese existenzielle Art akzeptieren. Zum Beispiel würde der folgende Pseudo-Code kompilieren:

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

Die Schnittstelle "lesen" wird erklärt, wie:

Es gibt einen Typ T, so dass:

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

Die Variable exfile ist kein int, kein char*, kein struct Datei-nichts, was man in der Art System zum Ausdruck bringen kann. Sie können nicht eine Variable, deren Typ unbekannt erklären und Sie können nicht werfen, sagen, einen Zeiger in diese unbekannten Typs. Die Sprache wird Sie nicht.

Um direkt Ihre Frage zu beantworten:

Mit dem Universal-Typ verwendet von T muss den Typ-Parameter X umfassen. Zum Beispiel T<String> oder T<Integer>. Für die existentielle Art von T verwendet nicht, dass Typ-Parameter enthalten, weil es unbekannt oder irrelevant ist -. Nur T (oder in Java T<?>) verwendet

Weitere Informationen:

Universal- / abstrakte Typen und existentielle Typen sind eine Dualität der Perspektive zwischen dem Verbraucher / Client eines Objekts / Funktion und dem Hersteller / Umsetzung davon. Wenn eine Seite einen universellen Typ sieht, sieht der andere eine existenzielle Art.

In Java können Sie eine generische Klasse definieren:

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();

Aus der Perspektive eines Client von MyClass, T ist universell, weil Sie jede Art für T ersetzen können, wenn Sie diese Klasse verwenden, und Sie müssen die tatsächliche Art von T wissen, wann immer Sie eine Instanz verwenden MyClass
Aus der Perspektive der Instanzmethoden in MyClass selbst, T ist existentiell, weil es nicht die wirkliche Art von T weiß
In Java stellt ? die existentielle Art - also, wenn Sie in der Klasse sind, T grundsätzlich ? ist. Wenn Sie eine Instanz von MyClass mit T existentiellen behandeln möchten, können Sie MyClass<?> wie im secretMessage() obigen Beispiel erklären.

Existentielle Typen werden manchmal verwendet, um die Details der Implementierung etwas zu verbergen, wie an anderer Stelle diskutiert. Eine Java-Version könnte dies wie folgt aussehen:

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);

Es ist ein bisschen schwierig, diese richtig zu erfassen, weil ich in einer Art funktionalen Programmiersprache sein bin so zu tun, die Java nicht. Aber der Punkt ist, dass Sie irgendeine Art von Staat und eine Liste der Funktionen werden erfasst, die an diesem Zustand arbeiten und Sie nicht wissen, die reale Art des Staates Teil, aber die Funktionen tun, da sie mit dieser Art abgestimmt wurden bereits .

Nun, in Java alle nicht endgültig nicht-primitiven Typen sind zum Teil existenziell. Das mag seltsam klingen, aber weil eine Variable als Object erklärt möglicherweise stattdessen eine Unterklasse von Object sein könnte, können Sie die spezifische Art nicht erklären, nur „diese Art oder eine Unterklasse“. Und so werden die Objekte als ein bisschen Zustand sowie eine Liste von Funktionen dargestellt, die an diesem Zustand arbeiten - genau das nennt funktionieren wird zur Laufzeit durch Nachschlagen bestimmt. Dies ist sehr ähnlich wie die Verwendung von existenziellen Typen oben, wo Sie haben einen existentiellen Zustand Teil und eine Funktion, die auf diesem Zustand arbeitet.

In statisch typisierte Programmiersprachen ohne Subtyping und Abgüsse, existentielle Typen erlauben eine Listen unterschiedlich typisierte Objekte zu verwalten. Eine Liste von T<Int> kann keine T<Long> enthalten. Allerdings kann eine Liste von T<?> jede Variation von T enthält, eine viele verschiedene Arten von Daten in die Liste und wandeln sie alle in einen int (oder tun, was Operationen sind vorgesehen, innerhalb der Datenstruktur) auf Anfrage setzen ermöglicht.

Man kann so ziemlich immer einen Datensatz mit einem existentiellen Typ in einen Datensatz umwandeln, ohne Verschlüsse zu verwenden. Ein Verschluss ist existentiell getippt, auch dadurch, dass die freien Variablen es über von dem Anrufer verborgen ist geschlossen. Somit ist eine Sprache, die Schließungen aber nicht existentielle Typen unterstützt, können Sie Verschlüsse machen lassen, die den gleichen versteckten Zustand teilen, die Sie in den existenziellen Teil eines Objekts gesetzt haben würde.

Es scheint, ich bin ein bisschen spät kommt, aber wie auch immer, dieses Dokument ist ein weiterer Blick auf, was existentielle Typen sind, die aber nicht spezifisch sprachunabhängig, es dann einfacher sein sollte ziemlich existenziellen Typen zu verstehen: http://www.cs.uu.nl/groups/ST/Projects/ehc /ehc-book.pdf (Kapitel 8)

Der Unterschied zwischen einem universell und existenzquantifizierte Typ kann durch die folgende Beobachtung charakterisiert werden:



Die Verwendung eines Wertes mit einem ∀ quantifizierten Typ bestimmt die Art für die Instanziierung der quantifizierten Variable vom Typ zu wählen. Zum Beispiel kann der Anrufer der Identitätsfunktion „id :: ∀a.a → a“ bestimmt den Typ für die Variable vom Typ a für diese spezielle Anwendung von ID zu wählen. Für die Funktionsanwendung „id 3“ diese Art gleich Int.



Die Schaffung eines Wert mit einem ∃ quantifizierten Typ bestimmt, und Häuten, die Art des quantifizierten Typ Variable. „∃a (a, a → Int)“ zum Beispiel, ein Schöpfer eines haben kann einen Wert dieses Typs, hergestellt aus „(3, & lgr; x → x)“; ein anderer Schöpfer hat einen Wert mit der gleichen Art von „(‘ x‘, & lgr; x → ord x)“ aufgebaut. Von einem Benutzer Sicht haben beide Werte die gleiche Art und sind somit austauschbar. Der Wert hat einen bestimmten Typ für Typ Variable a gewählt, aber wir wissen nicht, welche Art, so dass diese Informationen nicht mehr genutzt werden. Dieser Wert spezifische Art Informationen wurden ‚vergessen‘; wir wissen nur, es existiert.

Ein Universaltyp existiert für alle Werte des Typs Parameter (s). Ein Existenztyp existiert nur für Werte des Typparameters (s), die die Randbedingungen des Existenztypen entsprechen.

Beispiel in Scala Ein Weg, eine Existenz Art auszudrücken ist eine abstrakte Art, die zu einigen oberen oder unteren Grenzen eingeschränkt wird.

trait Existential {
  type Parameter <: Interface
}

In äquivalentem ein eingeschränkten universellen Typ ist eine existentielle Art, wie im folgende Beispiel.

trait Existential[Parameter <: Interface]

Jede Website Verwendung können die Interface verwenden, da alle instantiable Subtypen von Existential müssen die type Parameter definieren, die die Interface implementieren müssen.

degenerierter Fall ein existentiellen Typ in Scala ist eine abstrakte Art, die nie bezeichnet wird und somit nicht zu sein brauchen von jedem Subtyp definiert. Dies hat effektiv eine Kurzschreibweise von List[_] in Scala und List<?> in Java.

war meine Antwort von Martin Odersky Vorschlag zur Vereinheitlichung abstrakt und existentielle Typen. Das begleitende Dia Hilfsmittel Verständnis.

Forschung in abstrakte Datentypen und Information Hiding existentielle Typen in Programmiersprachen gebracht. einen Datentyp abstrakt zu machen verbirgt Informationen über diese Art, so ein Kunde von dieser Art kann es nicht missbrauchen. Sagen Sie bitte einen Verweis auf ein Objekt haben ... erlauben einige Sprachen, die Sie, dass der Bezug auf den Verweis auf Bytes zu werfen und tun alles, was Sie zu diesem Teil des Speichers werden soll. Für die Zwecke des Verhaltens eines Programms zu gewährleisten, ist es sinnvoll für eine Sprache zu erzwingen, dass Sie nur auf der Referenz wirken auf das Objekt über die Methoden der Designer des Objekts bereitstellt. Sie kennen die Art existiert, aber nicht mehr.

Siehe auch:

Abstrakte Typen haben Existentielle Typ, MITCHEL & Plotkin

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

Ich habe dieses Diagramm. Ich weiß nicht, ob es streng ist. Aber wenn es hilft, ich bin froh.

Wie ich verstehe, es ist eine mathematische Weise Schnittstellen / abstrakte Klasse zu beschreiben.

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

Für C # es zu einem allgemeinen abstrakten Typ übersetzen würde:

abstract class MyType<T>{
    private T a;

    public abstract int f(T x);
}

„Existenzielle“ bedeutet nur, dass es eine Art ist, die hier die Regeln gehorchen definiert.

Lizenziert unter: CC-BY-SA mit Zuschreibung

Nicht verbunden mit StackOverflow