Kovarianz und Kontravarianz (Informatik) - Covariance and contravariance (computer science)

Viele Programmiersprache Typsysteme unterstützen Subtyping . Wenn der Typ Catbeispielsweise ein Untertyp von ist Animal, Cat sollte ein Typausdruck überall dort ersetzbar sein, wo ein Typausdruck Animalverwendet wird.

Varianz bezieht sich darauf, wie sich die Subtypisierung zwischen komplexeren Typen auf die Subtypisierung zwischen ihren Komponenten bezieht. Wie sollte sich beispielsweise eine Liste von Cats zu einer Liste von Animals verhalten? Oder wie sollte sich eine zurückgebende Funktion Catzu einer zurückgebenden Funktion verhalten Animal?

In Abhängigkeit von der Varianz des Typkonstruktor , wird die Untertypisierungsbeziehung der einfachen Typen kann entweder haltbar gemacht, umgekehrt, oder für die jeweiligen komplexen Typen ignoriert. In der Programmiersprache OCaml ist beispielsweise "list of Cat" ein Untertyp von "list of Animal", da der Listentypkonstruktor kovariant ist . Das bedeutet, dass die Subtypisierungsbeziehung der einfachen Typen für die komplexen Typen erhalten bleibt.

Andererseits ist "function from Animal to String" ein Untertyp von "function from Cat to String", da der Funktionstypkonstruktor im Parametertyp kontravariant ist . Hier ist die Subtypisierungsbeziehung der einfachen Typen für die komplexen Typen umgekehrt.

Ein Programmiersprachen-Designer wird Varianz berücksichtigen, wenn er Typisierungsregeln für Sprachfeatures wie Arrays, Vererbung und generische Datentypen entwickelt . Indem Typkonstruktoren kovariant oder kontravariant statt invariant gemacht werden, werden mehr Programme als gut typisiert akzeptiert. Auf der anderen Seite finden Programmierer Kontravarianz oft nicht intuitiv, und die genaue Nachverfolgung der Varianz zur Vermeidung von Laufzeittypfehlern kann zu komplexen Typisierungsregeln führen.

Um das Typsystem einfach zu halten und nützliche Programme zu ermöglichen, kann eine Sprache einen Typkonstruktor als invariant behandeln, selbst wenn es sicher wäre, ihn als Variant zu betrachten, oder ihn als kovariant behandeln, obwohl dies die Typsicherheit verletzen könnte.

Formale Definition

Innerhalb des Typsystems einer Programmiersprache ist eine Typisierungsregel oder ein Typkonstruktor:

• kovariant, wenn es die Reihenfolge der Typen (≤) beibehält , die Typen von spezifischer zu allgemeiner ordnet: If A ≤ B, then I<A> ≤ I<B>;
• kontravariant, wenn sie diese Reihenfolge umkehrt: Wenn A ≤ B, dann I<B> ≤ I<A>;
• bivariant, wenn beides zutrifft (dh wenn A ≤ B, dann I<A> ≡ I<B>);
• Variante wenn kovariante, kontravariante oder bivariante;
• invariant oder nichtvariant, wenn nicht variabel .

Der Artikel betrachtet, wie dies auf einige gängige Typkonstruktoren zutrifft.

C#-Beispiele

In C# ist if Catbeispielsweise ein Untertyp von Animal, dann:

• IEnumerable<Cat>ist ein Untertyp von . Die Subtypisierung erhalten bleibt , da ist covariant auf .IEnumerable<Animal>IEnumerable<T>T
• Action<Animal>ist ein Untertyp von . Die Subtypisierung umgekehrt wird, da ist kontra auf .Action<Cat>Action<T>T
• Weder noch ist ein Subtyp des andere, da ist unveränderlich auf .IList<Cat>IList<Animal>IList<T>T

Die Varianz einer generischen C#-Schnittstelle wird deklariert, indem das out(kovariante) oder in(kontravariante) Attribut auf (null oder mehr) ihrer Typparameter platziert wird. Für jeden so gekennzeichneten Typparameter überprüft der Compiler abschließend, wobei jede Verletzung fatal ist, dass eine solche Verwendung global konsistent ist. Die obigen Schnittstellen sind als , , und deklariert . Typen mit mehr als einem Typparameter können unterschiedliche Varianzen für jeden Typparameter angeben. Der Delegattyp stellt beispielsweise eine Funktion mit einem kontravarianten Eingabeparameter vom Typ und einem kovarianten Rückgabewert vom Typ dar . IEnumerable<out T>Action<in T>IList<T>Func<in T, out TResult>TTResult

Die Typisierungsregeln für die Schnittstellenvarianz gewährleisten die Typsicherheit. Zum Beispiel stellt an eine erstklassige Funktion dar, die ein Argument vom Typ erwartet , und eine Funktion, die mit jeder Art von Tieren umgehen kann, kann immer anstelle einer Funktion verwendet werden, die nur Katzen verarbeiten kann. Action<T>T

Arrays

Schreibgeschützte Datentypen (Quellen) können kovariant sein; Schreibgeschützte Datentypen (Senken) können kontravariant sein. Veränderliche Datentypen, die sowohl als Quelle als auch als Senke fungieren, sollten invariant sein. Um dieses allgemeine Phänomen zu veranschaulichen, betrachten Sie den Array-Typ . Für den Typ können Animalwir den Typ machen , der ein "Array von Tieren" ist. Für dieses Beispiel unterstützt dieses Array sowohl das Lesen als auch das Schreiben von Elementen. Animal[]

Wir haben die Möglichkeit, dies wie folgt zu behandeln:

• Kovariante: a ist ein ;Cat[]Animal[]
• Kontravariante: an ist a ;Animal[]Cat[]
• Invariante: an ist nicht a und a ist nicht an .Animal[]Cat[]Cat[]Animal[]

Wenn wir Typfehler vermeiden wollen, dann ist nur die dritte Wahl sicher. Natürlich kann nicht jeder so behandelt werden, als wäre es ein , da ein Client, der aus dem Array liest , ein erwartet , aber ein z . B. ein enthalten kann . Die kontravariante Regel ist also nicht sicher. Animal[]Cat[]CatAnimal[]Dog

Umgekehrt kann a nicht als a behandelt werden . Es sollte immer möglich sein, ein in ein einzufügen . Bei kovarianten Arrays kann dies nicht garantiert werden, da der Hintergrundspeicher tatsächlich ein Array von Katzen sein kann. Die kovariante Regel ist also auch nicht sicher – der Array-Konstruktor sollte invariant sein . Beachten Sie, dass dies nur bei veränderlichen Arrays ein Problem darstellt. die Kovariantenregel ist für unveränderliche (schreibgeschützte) Arrays sicher. Ebenso wäre die kontravariante Regel für schreibgeschützte Arrays sicher. Cat[]Animal[]DogAnimal[]

Mit C# können Sie dies umgehen, indem Sie das dynamische Schlüsselwort über array/collection/generics mit duck typing verwenden , der Intellisense geht auf diese Weise verloren, aber es funktioniert.

Kovariante Arrays in Java und C#

Frühe Versionen von Java und C# enthielten keine Generika, die auch als parametrischer Polymorphismus bezeichnet werden . In einer solchen Umgebung schließt die Invarianz von Arrays nützliche polymorphe Programme aus.

Ziehen Sie beispielsweise in Betracht, eine Funktion zum Mischen eines Arrays zu schreiben, oder eine Funktion, die zwei Arrays mit der Object. equalsMethode auf die Elemente. Die Implementierung hängt nicht vom genauen Elementtyp ab, der im Array gespeichert ist, daher sollte es möglich sein, eine einzelne Funktion zu schreiben, die mit allen Arraytypen funktioniert. Es ist einfach, Funktionen des Typs zu implementieren:

boolean equalArrays(Object[] a1, Object[] a2);
void shuffleArray(Object[] a);

Würden Array-Typen jedoch als invariant behandelt, könnten diese Funktionen nur für ein Array genau des Typs aufgerufen werden . Man könnte zum Beispiel nicht ein Array von Strings mischen. Object[]

Daher behandeln sowohl Java als auch C# Array-Typen kovariant. In Java ist beispielsweise ein Untertyp von und in C# ein Untertyp von . String[]Object[]string[]object[]

Wie oben besprochen, führen kovariante Arrays zu Problemen beim Schreiben in das Array. Java und C# gehen damit um, indem sie jedes Array-Objekt beim Erstellen mit einem Typ markieren. Jedes Mal, wenn ein Wert in einem Array gespeichert wird, überprüft die Ausführungsumgebung, ob der Laufzeittyp des Werts dem Laufzeittyp des Arrays entspricht. Bei Nichtübereinstimmung wird ein ArrayStoreException(Java) oder ArrayTypeMismatchException(C#) geworfen:

// a is a single-element array of String
String[] a = new String[1];

// b is an array of Object
Object[] b = a;

// Assign an Integer to b. This would be possible if b really were
// an array of Object, but since it really is an array of String,
// we will get a java.lang.ArrayStoreException.
b[0] = 1;

Im obigen Beispiel kann man sicher aus dem Array (b) lesen . Nur der Versuch , in das Array zu schreiben , kann zu Problemen führen.

Ein Nachteil dieses Ansatzes besteht darin, dass die Möglichkeit eines Laufzeitfehlers besteht, den ein strengeres Typsystem zur Kompilierzeit hätte abfangen können. Außerdem wird die Leistung beeinträchtigt, da jeder Schreibvorgang in ein Array eine zusätzliche Laufzeitprüfung erfordert.

Mit dem Hinzufügen von Generika bieten Java und C# jetzt Möglichkeiten, diese Art von polymorpher Funktion zu schreiben, ohne sich auf Kovarianz zu verlassen. Den Array-Vergleichs- und Shuffling-Funktionen können die parametrisierten Typen zugewiesen werden

<T> boolean equalArrays(T[] a1, T[] a2);
<T> void shuffleArray(T[] a);

Um zu erzwingen, dass eine C#-Methode schreibgeschützt auf eine Sammlung zugreift, kann man alternativ die Schnittstelle verwenden, anstatt ihr ein Array zu übergeben . IEnumerable<object>object[]

Funktionstypen

Sprachen mit erstklassigen Funktionen haben Funktionstypen wie "eine Funktion, die eine Katze erwartet und ein Tier zurückgibt" ( in OCaml- Syntax oder in C# -Syntax geschrieben). Cat -> AnimalFunc<Cat,Animal>

Diese Sprachen müssen auch angeben, wann ein Funktionstyp ein Untertyp eines anderen ist, dh wann es sicher ist, eine Funktion eines Typs in einem Kontext zu verwenden, der eine Funktion eines anderen Typs erwartet. Es ist sicher, eine Funktion f durch eine Funktion g zu ersetzen, wenn f einen allgemeineren Argumenttyp akzeptiert und einen spezifischeren Typ als g zurückgibt . Beispielsweise können Funktionen vom Typ , , und überall dort verwendet werden, wo a erwartet wurde. (Man kann dies mit dem Robustheitsprinzip der Kommunikation vergleichen: "Sei liberal in dem, was du akzeptierst und konservativ in dem, was du produzierst.") Die allgemeine Regel lautet: Animal -> CatCat -> CatAnimal -> AnimalCat -> Animal

${\displaystyle (P_{1}\rightarrow R_{1})\leq (P_{2}\rightarrow R_{2})}$wenn und .${\displaystyle P_{1}\geq P_{2}}$${\displaystyle R_{1}\leq R_{2}}$

Unter Verwendung der Inferenzregel-Notation kann dieselbe Regel wie folgt geschrieben werden:

${\displaystyle {\frac {P_{1}\geq P_{2}\quad R_{1}\leq R_{2}}{(P_{1}\rightarrow R_{1})\leq (P_{2} \rightarrow R_{2})}}}$

Mit anderen Worten, der → Typkonstruktor ist im Parametertyp (Eingabe) kontravariant und im Rückgabetyp (Ausgabe) kovariant . Diese Regel wurde zuerst von John C. Reynolds formell erklärt und in einem Papier von Luca Cardelli weiter bekannt gemacht .

Bei Funktionen, die Funktionen als Argumente annehmen , kann diese Regel mehrmals angewendet werden. Wenn wir beispielsweise die Regel zweimal anwenden, sehen wir, dass wenn . Mit anderen Worten, der Typ ist an der Position von kovariant . Bei komplizierten Typen kann es verwirrend sein, mental zu verfolgen, warum eine bestimmte Typspezialisierung typsicher ist oder nicht, aber es ist leicht zu berechnen, welche Positionen ko- und kontravariant sind: eine Position ist kovariant, wenn sie auf der linken Seite von liegt eine gerade Anzahl von Pfeilen, die darauf zutreffen. ${\displaystyle ((P_{1}\nach R)\nach R)\leq ((P_{2}\nach R)\nach R)}$${\displaystyle P_{1}\leq P_{2}}$${\displaystyle (A\nach B)\nach C)}$${\displaystyle A}$

Vererbung in objektorientierten Sprachen

Wenn eine Unterklasse eine Methode in einer Oberklasse überschreibt , muss der Compiler überprüfen, ob die überschreibende Methode den richtigen Typ hat. Während einige Sprachen erfordern, dass der Typ genau mit dem Typ in der Superklasse übereinstimmt (Invarianz), ist es auch typsicher, der überschreibenden Methode einen "besseren" Typ zu erlauben. Nach der üblichen Subtyping-Regel für Funktionstypen bedeutet dies, dass die überschreibende Methode einen spezifischeren Typ (Rückgabetyp-Kovarianz) zurückgeben und ein allgemeineres Argument akzeptieren sollte (Parametertyp-Kontravarianz). In der UML- Notation sind die Möglichkeiten wie folgt:

• Varianz- und Methodenüberschreibung: Übersicht
• 

  Subtyping des Parameters/Rückgabetyps der Methode.

• 

  Invarianz . Die Signatur der überschreibenden Methode bleibt unverändert.

• 

  Kovarianter Rückgabetyp . Die Subtypisierungsbeziehung verläuft in die gleiche Richtung wie die Beziehung zwischen ClassA und ClassB.

• 

  Kontravarianter Parametertyp . Die Subtypisierungsbeziehung ist in die entgegengesetzte Richtung zu der Beziehung zwischen ClassA und ClassB.

• 

  Kovarianter Parametertyp . Nicht typsicher.

Nehmen wir für ein konkretes Beispiel an, wir schreiben eine Klasse, um ein Tierheim zu modellieren . Wir gehen davon aus, dass dies Cateine Unterklasse von Animalist und dass wir eine Basisklasse haben (mit Java-Syntax).

class AnimalShelter {

    Animal getAnimalForAdoption() {
        // ...
    }
    
    void putAnimal(Animal animal) {
        //...
    }
}

Nun ist die Frage: Wenn wir eine Unterklasse AnimalShelter, welche Arten sind erlaubt wir zu geben getAnimalForAdoptionund putAnimal?

Rückgabetyp der kovarianten Methode

In einer Sprache, die kovariante Rückgabetypen zulässt , kann eine abgeleitete Klasse die getAnimalForAdoptionMethode überschreiben , um einen spezifischeren Typ zurückzugeben:

class CatShelter extends AnimalShelter {

    Cat getAnimalForAdoption() {
        return new Cat();
    }
}

Unter den Mainstream-OO-Sprachen unterstützen Java , C++ und C# (ab Version 9.0) kovariante Rückgabetypen. Das Hinzufügen des kovarianten Rückgabetyps war eine der ersten Modifikationen der Sprache C++, die 1998 vom Normenausschuss genehmigt wurde. Scala und D unterstützen auch kovariante Rückgabetypen.

Parametertyp der kontravarianten Methode

Ebenso ist es typsicher, einer überschreibenden Methode zu erlauben, ein allgemeineres Argument zu akzeptieren als die Methode in der Basisklasse:

class CatShelter extends AnimalShelter {
    void putAnimal(Object animal) {
        // ...
    }
}

Nicht viele objektorientierte Sprachen erlauben dies tatsächlich. C++, Java und die meisten anderen Sprachen, die Überladung und/oder Spiegelung unterstützen, würden dies als Methode mit einem überladenen oder gespiegelten Namen interpretieren.

Allerdings Sather unterstützt sowohl Kovarianz und Kontra. Aufrufkonventionen für überschriebene Methoden sind kovariant mit out- Parametern und Rückgabewerten und kontravariant mit normalen Parametern (mit dem Modus in ).

Kovarianter Methodenparametertyp

Ein paar Mainstream Sprachen, Eiffel und Dart erlauben die Parameter eines übergeordneten Verfahren ein haben mehr spezifische Art als die Methode in der übergeordneten Klasse (Parametertyp Kovarianz). Somit würde der folgende Dart-Code check eingeben, wobei putAnimaldie Methode in der Basisklasse überschrieben wird:

class CatShelter extends AnimalShelter {

    void putAnimal(covariant Cat animal) {
        // ...
    }
}

Dies ist nicht typsicher. Durch Hochwerfen von a CatShelterauf a AnimalShelterkann man versuchen, einen Hund in ein Katzenheim zu bringen. CatShelterDies entspricht nicht den Parameterbeschränkungen und führt zu einem Laufzeitfehler. Der Mangel an Typsicherheit (bekannt als "Catcall-Problem" in der Eiffel-Community, wobei "cat" oder "CAT" eine geänderte Verfügbarkeit oder ein geänderter Typ ist) ist ein seit langem bestehendes Problem. Im Laufe der Jahre wurden verschiedene Kombinationen aus globaler statischer Analyse, lokaler statischer Analyse und neuen Sprachfunktionen vorgeschlagen, um dies zu beheben, und diese wurden in einigen Eiffel-Compilern implementiert.

Trotz des Typsicherheitsproblems halten die Eiffel-Designer kovariante Parametertypen für entscheidend für die Modellierung der Anforderungen der realen Welt. Das Katzenheim veranschaulicht ein häufiges Phänomen: Es ist eine Art Tierheim, hat aber zusätzliche Einschränkungen und es erscheint sinnvoll, Vererbung und eingeschränkte Parametertypen zu verwenden, um dies zu modellieren. Indem sie diese Verwendung der Vererbung vorschlagen, lehnen die Eiffel-Designer das Liskov-Substitutionsprinzip ab , das besagt, dass Objekte von Unterklassen immer weniger eingeschränkt sein sollten als Objekte ihrer Oberklasse.

Eine andere Instanz einer Mainstream-Sprache, die Kovarianz in Methodenparametern erlaubt, ist PHP in Bezug auf Klassenkonstruktoren. Im folgenden Beispiel wird die Methode __construct() akzeptiert, obwohl der Methodenparameter kovariant zum Methodenparameter der Eltern ist. Wäre diese Methode etwas anderes als __construct(), würde ein Fehler auftreten:

interface AnimalInterface {}


interface DogInterface extends AnimalInterface {}


class Dog implements DogInterface {}


class Pet
{
    public function __construct(AnimalInterface $animal) {}
}


class PetDog extends Pet
{
    public function __construct(DogInterface $dog)
    {
        parent::__construct($dog);
    }
}

Ein weiteres Beispiel, bei dem kovariante Parameter hilfreich erscheinen, sind sogenannte binäre Methoden, dh Methoden, bei denen erwartet wird, dass der Parameter vom gleichen Typ ist wie das Objekt, auf das die Methode aufgerufen wird. Ein Beispiel ist die compareToMethode: prüft, ob in einer bestimmten Reihenfolge vor oder nach kommt , aber der Vergleich von beispielsweise zwei rationalen Zahlen unterscheidet sich von dem Vergleich zweier Strings. Andere gängige Beispiele für binäre Methoden sind Gleichheitstests, arithmetische Operationen und Mengenoperationen wie Teilmenge und Vereinigung. a.compareTo(b)ab

In älteren Java-Versionen wurde die Vergleichsmethode als Schnittstelle angegeben Comparable:

interface Comparable {

    int compareTo(Object o);
}

Der Nachteil dabei ist, dass die Methode so angegeben ist, dass sie ein Argument vom Typ akzeptiert Object. Eine typische Implementierung würde dieses Argument zuerst downcasten (und einen Fehler ausgeben, wenn es nicht vom erwarteten Typ ist):

class RationalNumber implements Comparable {
    int numerator;
    int denominator;
    // ...
 
    public int compareTo(Object other) {
        RationalNumber otherNum = (RationalNumber)other;
        return Integer.compare(numerator * otherNum.denominator,
                               otherNum.numerator * denominator);
    }
}

In einer Sprache mit kovarianten Parametern könnte dem Argument to compareTodirekt der gewünschte Typ übergeben werden RationalNumber, wodurch die Typumwandlung ausgeblendet wird. (Natürlich würde dies immer noch einen Laufzeitfehler ergeben, wenn compareTodann zB eine aufgerufen würde String.)

Vermeidung von kovarianten Parametertypen

Andere Sprachmerkmale können die offensichtlichen Vorteile kovarianter Parameter bieten, während die Liskov-Ersetzbarkeit erhalten bleibt.

In einer Sprache mit Generika (auch bekannt als parametrischer Polymorphismus ) und beschränkter Quantifizierung können die vorherigen Beispiele typsicher geschrieben werden. Anstatt zu definieren AnimalShelter, definieren wir eine parametrisierte Klasse . (Ein Nachteil dabei ist, dass der Implementierer der Basisklasse vorhersehen muss, welche Typen in den Unterklassen spezialisiert werden müssen.) Shelter<T>

class Shelter<T extends Animal> {

    T getAnimalForAdoption() {
        // ...
    }

    void putAnimal(T animal) {
        // ...
    }
}

    
class CatShelter extends Shelter<Cat> {

    Cat getAnimalForAdoption() {
        // ...
    }

    void putAnimal(Cat animal) {
        // ...
    }
}

Ebenso wurde in neueren Java-Versionen die ComparableSchnittstelle parametrisiert, wodurch der Downcast typsicher weggelassen werden kann:

class RationalNumber implements Comparable<RationalNumber> {

    int numerator;
    int denominator;
    // ...
         
    public int compareTo(RationalNumber otherNum) {
        return Integer.compare(numerator * otherNum.denominator, 
                               otherNum.numerator * denominator);
    }
}

Eine weitere Sprachfunktion, die hilfreich sein kann, ist der Mehrfachversand . Ein Grund dafür, dass binäre Methoden umständlich zu schreiben sind, besteht darin, dass bei einem Aufruf wie die Auswahl der richtigen Implementierung von wirklich vom Laufzeittyp von und abhängt , aber in einer herkömmlichen OO-Sprache nur der Laufzeittyp von berücksichtigt wird. In einer Sprache mit Multiple Dispatch im Common Lisp Object System (CLOS)-Stil könnte die Vergleichsmethode als generische Funktion geschrieben werden, bei der beide Argumente für die Methodenauswahl verwendet werden. a.compareTo(b)compareToaba

Giuseppe Castagna beobachtete, dass in einer typisierten Sprache mit mehrfachem Versand eine generische Funktion einige Parameter haben kann, die den Versand steuern, und einige "übrige" Parameter, die dies nicht tun. Da die Methodenauswahlregel die spezifischste anwendbare Methode auswählt, verfügt die überschreibende Methode über spezifischere Typen für die steuernden Parameter, wenn eine Methode eine andere Methode überschreibt. Um die Typsicherheit zu gewährleisten, muss die Sprache jedoch immer noch verlangen, dass die übrig gebliebenen Parameter mindestens so allgemein sind. Unter Verwendung der vorherigen Terminologie sind Typen, die für die Auswahl der Laufzeitmethode verwendet werden, kovariant, während Typen, die nicht für die Auswahl der Laufzeitmethode der Methode verwendet werden, kontravariant sind. Konventionelle Single-Dispatch-Sprachen wie Java folgen dieser Regel ebenfalls: Nur ein Argument wird für die Methodenauswahl verwendet (das Empfängerobjekt, das als verstecktes Argument an eine Methode übergeben wird this), und tatsächlich ist der Typ von thisinnerhalb überschreibender Methoden spezialisierter als in den Superklasse.

Castagna schlägt vor, dass Beispiele, in denen kovariante Parametertypen überlegen sind (insbesondere binäre Methoden), mit multiplem Dispatch behandelt werden sollten; was natürlich kovariant ist. Die meisten Programmiersprachen unterstützen jedoch keinen Mehrfachversand.

Zusammenfassung von Varianz und Vererbung

Die folgende Tabelle fasst die Regeln zum Überschreiben von Methoden in den oben besprochenen Sprachen zusammen.

Generische Typen

In Programmiersprachen, die Generics unterstützen (auch bekannt als parametrischer Polymorphismus ), kann der Programmierer das Typsystem mit neuen Konstruktoren erweitern. Eine C#-Schnittstelle wie beispielsweise ermöglicht es, neue Typen wie oder zu erstellen . Es stellt sich dann die Frage, wie groß die Varianz dieser Typkonstruktoren sein soll. IList<T>IList<Animal>IList<Cat>

Es gibt zwei Hauptansätze. In Sprachen mit Varianzannotationen an der Deklarationsstelle (z. B. C# ) kommentiert der Programmierer die Definition eines generischen Typs mit der beabsichtigten Varianz seiner Typparameter. Bei Verwendungs-Site-Varianz-Annotationen (z. B. Java ) kommentiert der Programmierer stattdessen die Stellen, an denen ein generischer Typ instanziiert wird.

Anmerkungen zur Abweichung von Deklarationsstandorten

Die beliebtesten Sprachen mit Varianzannotationen für Deklarationssites sind C# und Kotlin (mit den Schlüsselwörtern outund in) sowie Scala und OCaml (mit den Schlüsselwörtern +und -). C# erlaubt nur Varianzannotationen für Schnittstellentypen, während Kotlin, Scala und OCaml sie sowohl für Schnittstellentypen als auch für konkrete Datentypen zulassen.

Schnittstellen

In C# kann jeder Typparameter einer generischen Schnittstelle als kovariant ( out), kontravariant ( in) oder invariant (keine Annotation) gekennzeichnet werden. Beispielsweise können wir eine Schnittstelle mit schreibgeschützten Iteratoren definieren und sie in ihrem Typparameter als kovariant (out) deklarieren. IEnumerator<T>

interface IEnumerator<out T>
{
    T Current { get; }
    bool MoveNext();
}

Mit dieser Deklaration IEnumeratorwird in seinem Typparameter als kovariant behandelt, zB ist ein Untertyp von . IEnumerator<Cat>IEnumerator<Animal>

Der Typprüfer erzwingt, dass jede Methodendeklaration in einer Schnittstelle nur die Typparameter in Übereinstimmung mit den in/ out-Annotationen erwähnt. Das heißt, ein Parameter, der als kovariant deklariert wurde, darf an keiner kontravarianten Position vorkommen (wobei eine Position kontravariant ist, wenn sie unter einer ungeraden Anzahl von kontravarianten Typkonstruktoren auftritt). Die genaue Regel lautet, dass die Rückgabetypen aller Methoden in der Schnittstelle kovariant gültig sein müssen und alle Methodenparametertypen kontravariant gültig sein müssen , wobei gültig S-ly wie folgt definiert ist:

• Nicht generische Typen (Klassen, Strukturen, Aufzählungen usw.) sind sowohl ko- als auch kontravariant gültig.
• Ein Typparameter Tist kovariant gültig, wenn er nicht markiert wurde in, und kontravariant gültig, wenn er nicht markiert wurde out.
• Ein Array-Typ ist gültig S-ly, wenn es ist. (Das liegt daran, dass C# kovariante Arrays hat.)A[]A
• Ein generischer Typ ist S-ly gültig, wenn für jeden Parameter , G<A1, A2, ..., An>Ai
  • Ai ist gültig S-ly, und der i- te Parameter to Gwird als kovariant deklariert, oder
  • Ai ist gültig (nicht S)-ly, und der i- te Parameter zu Gwird als kontravariant deklariert, oder
  • Ai ist sowohl kovariant als auch kontravariant gültig, und der i- te Parameter to Gwird als invariant deklariert.

Betrachten Sie als Beispiel für die Anwendung dieser Regeln die Schnittstelle. IList<T>

interface IList<T>
{
    void Insert(int index, T item);
    IEnumerator<T> GetEnumerator();
}

Der Parameter type Tvon Insertmuss kontravariant gültig sein, dh der Parameter type Tdarf nicht mit Tags versehen sein out. Ebenso muss der Ergebnistyp von kovariant gültig sein, dh (da es sich um eine kovariante Schnittstelle handelt) muss der Typ kovariant gültig sein, dh der Typparameter darf nicht mit Tags versehen sein . Dies zeigt, dass die Schnittstelle weder ko- noch kontravariant markiert werden darf. IEnumerator<T>GetEnumeratorIEnumeratorTTinIList

Im allgemeinen Fall einer generischen Datenstruktur wie z. B. IListbedeuten diese Einschränkungen, dass ein outParameter nur für Methoden verwendet werden kann, die Daten aus der Struktur herausholen, und ein inParameter nur für Methoden verwendet werden kann, die Daten in die Struktur einfügen, daher die Wahl von Schlüsselwörter.

Daten

C# erlaubt Varianzannotationen zu den Parametern von Schnittstellen, aber nicht zu den Parametern von Klassen. Da Felder in C#-Klassen immer veränderbar sind, wären unterschiedlich parametrisierte Klassen in C# nicht sehr nützlich. Aber Sprachen, die unveränderliche Daten betonen, können kovariante Datentypen gut nutzen. In Scala , Kotlin und OCaml ist beispielsweise der unveränderliche Listentyp kovariant: ist ein Untertyp von . List[Cat]List[Animal]

Die Regeln von Scala zum Prüfen von Varianzannotationen sind im Wesentlichen die gleichen wie die von C#. Es gibt jedoch einige Redewendungen, die insbesondere für unveränderliche Datenstrukturen gelten. Sie werden durch die folgende (Auszug aus der) Definition der Klasse veranschaulicht . List[A]

sealed abstract class List[+A] extends AbstractSeq[A] {
    def head: A
    def tail: List[A]

    /** Adds an element at the beginning of this list. */
    def ::[B >: A] (x: B): List[B] =
        new scala.collection.immutable.::(x, this)
    /** ... */
}

Erstens müssen Klassenmember mit einem Variantentyp unveränderlich sein. Hat headhier den Typ A, der als kovariant ( +) deklariert wurde und tatsächlich headals Methode ( def) deklariert wurde . Der Versuch, es als veränderliches Feld ( var) zu deklarieren, würde als Typfehler abgelehnt.

Zweitens weist eine Datenstruktur, selbst wenn sie unveränderlich ist, häufig Methoden auf, bei denen der Parametertyp kontravariant auftritt. Betrachten Sie beispielsweise die Methode, ::die ein Element am Anfang einer Liste hinzufügt. (Die Implementierung funktioniert, indem sie ein neues Objekt der ähnlich benannten Klasse erzeugt :: , der Klasse der nicht leeren Listen.) Der offensichtlichste Typ wäre

def :: (x: A): List[A]

Dies wäre jedoch ein Typfehler, da der kovariante Parameter Aan einer kontravarianten Position (als Funktionsparameter) erscheint. Aber es gibt einen Trick, um dieses Problem zu umgehen. Wir geben ::einen allgemeineren Typ an, der es ermöglicht, ein Element eines beliebigen Typs hinzuzufügen, B solange Bes ein Supertyp von ist A. Beachten Sie, dass dies darauf beruht List, kovariant zu sein, da this hat Typ und wir behandeln ihn als mit Typ . Auf den ersten Blick mag es nicht offensichtlich sein, dass der generalisierte Typ korrekt ist, aber wenn der Programmierer mit der einfacheren Typdeklaration beginnt, weisen die Typfehler auf die Stelle hin, die generalisiert werden muss. List[A]List[B]

Abweichung ableiten

Es ist möglich, ein Typsystem zu entwerfen, bei dem der Compiler automatisch die bestmöglichen Varianzannotationen für alle Datentypparameter herleitet. Die Analyse kann jedoch aus mehreren Gründen komplex werden. Erstens ist die Analyse nicht lokal, da die Varianz einer Schnittstelle Ivon der Varianz aller Ierwähnten Schnittstellen abhängt . Zweitens muss das Typsystem bivariante Parameter (die gleichzeitig ko- und kontravariant sind) zulassen, um eindeutige beste Lösungen zu erhalten . Und schließlich sollte die Varianz der Typparameter wohl eine bewusste Entscheidung des Designers einer Schnittstelle sein und nicht etwas, das einfach passiert.

Aus diesen Gründen führen die meisten Sprachen nur sehr geringe Varianzinferenzen durch. C# und Scala leiten überhaupt keine Abweichungsanmerkungen ab. OCaml kann die Varianz parametrisierter konkreter Datentypen ableiten, aber der Programmierer muss die Varianz abstrakter Typen (Schnittstellen) explizit angeben.

Betrachten Sie beispielsweise einen OCaml-Datentyp, Tder eine Funktion umschließt

type ('a, 'b) t = T of ('a -> 'b)

Der Compiler folgert automatisch, dass Tder erste Parameter kontravariant und der zweite kovariant ist. Der Programmierer kann auch explizite Annotationen bereitstellen, deren Erfüllung der Compiler überprüft. Somit entspricht die folgende Deklaration der vorherigen:

type (-'a, +'b) t = T of ('a -> 'b)

Explizite Anmerkungen in OCaml werden bei der Angabe von Schnittstellen nützlich. Beispielsweise enthält die Standardbibliotheksschnittstelle für Assoziationstabellen eine Anmerkung, die besagt, dass der Konstruktor des Kartentyps im Ergebnistyp kovariant ist. Map.S

module type S =
    sig
        type key
        type (+'a) t
        val empty: 'a t
        val mem: key -> 'a t -> bool
        ...
    end

Dadurch wird sichergestellt, dass zB ein Untertyp von ist . cat IntMap.tanimal IntMap.t

Anmerkungen zur Abweichung der Website (Platzhalter)

Ein Nachteil des Deklarationssite-Ansatzes besteht darin, dass viele Schnittstellentypen invariant gemacht werden müssen. Zum Beispiel haben wir oben gesehen, dass IListdas invariant sein muss, da es sowohl Insertund enthält GetEnumerator. Um mehr Varianz aufzudecken, könnte der API-Designer zusätzliche Schnittstellen bereitstellen, die Teilmengen der verfügbaren Methoden bereitstellen (z. B. eine "Nur-Einfügen-Liste", die nur bereitstellt Insert). Dies wird jedoch schnell unhandlich.

Varianz der Verwendungsstelle bedeutet, dass die gewünschte Varianz mit einer Anmerkung an der spezifischen Stelle im Code angegeben wird, an der der Typ verwendet wird. Dies gibt Benutzern einer Klasse mehr Möglichkeiten zur Subtypisierung, ohne dass der Designer der Klasse mehrere Schnittstellen mit unterschiedlicher Varianz definieren muss. Stattdessen kann der Programmierer an dem Punkt, an dem ein generischer Typ in einen tatsächlichen parametrisierten Typ instanziiert wird, angeben, dass nur eine Teilmenge seiner Methoden verwendet wird. Tatsächlich stellt jede Definition einer generischen Klasse auch Schnittstellen für die kovarianten und kontravarianten Teile dieser Klasse bereit .

Java bietet Varianzannotationen für die Nutzungsorte durch Wildcards , eine eingeschränkte Form von begrenzten existentiellen Typen . Ein parametrisierter Typ kann durch einen Platzhalter ?zusammen mit einer Ober- oder Untergrenze, zB oder , instanziiert werden . Ein unbegrenzter Platzhalter wie ist äquivalent zu . Ein solcher Typ repräsentiert einen unbekannten Typ, der die Schranke erfüllt. Wenn beispielsweise type vorhanden ist , wird die Typprüfung akzeptiert List<? extends Animal>List<? super Animal>List<?>List<? extends Object>List<X>XlList<? extends Animal>

Animal a = l.get(3);

weil der Typ Xals Untertyp von bekannt ist Animal, aber

l.add(new Animal());

wird als Typfehler abgewiesen, da an Animalnicht unbedingt an ist X. Im Allgemeinen verbietet ein Verweis auf eine gegebene Schnittstelle die Verwendung von Methoden aus der Schnittstelle, wobei die Art der Methode kontravariant vorkommt. Umgekehrt, wenn man Typ hätte, könnte man anrufen, aber nicht . I<T>I<? extends T>TlList<? super Animal>l.addl.get

Wildcard-Subtyping in Java kann als Cube visualisiert werden.

Während parametrisierte Typen ohne Platzhalter in Java invariant sind (z. B. gibt es keine Subtypisierungsbeziehung zwischen und ), können Platzhaltertypen durch Angabe einer engeren Grenze spezifischer gemacht werden. Ist beispielsweise ein Untertyp von . Dies zeigt, dass Wildcard-Typen in ihren oberen Grenzen kovariant sind (und auch in ihren unteren Grenzen kontravariant sind ). Insgesamt gibt es bei einem Platzhaltertyp wie , drei Möglichkeiten, einen Untertyp zu bilden: durch Spezialisierung der Klasse , durch Angabe einer engeren Grenze oder durch Ersetzen des Platzhalters durch einen bestimmten Typ (siehe Abbildung). List<Cat>List<Animal>List<? extends Cat>List<? extends Animal>C<? extends T>CT?

Durch Anwenden von zwei der oben genannten drei Formen der Untertypisierung wird es beispielsweise möglich, ein Argument vom Typ an eine Methode zu übergeben, die eine . Dies ist die Ausdruckskraft, die sich aus kovarianten Schnittstellentypen ergibt. Der Typ fungiert als Schnittstellentyp, der nur die kovarianten Methoden von enthält , aber der Implementierer von musste ihn nicht im Voraus definieren. List<Cat>List<? extends Animal>List<? extends Animal>List<T>List<T>

Im allgemeinen Fall einer generischen Datenstruktur werden IListkovariante Parameter für Methoden verwendet, die Daten aus der Struktur erhalten, und kontravariante Parameter für Methoden, die Daten in die Struktur einfügen. Die Mnemonik für Producer Extends, Consumer Super (PECS) aus dem Buch Effective Java von Joshua Bloch bietet eine einfache Möglichkeit, sich daran zu erinnern, wann Kovarianz und Kontravarianz verwendet werden sollten.

Wildcards sind flexibel, haben aber einen Nachteil. Während die Varianz der Nutzungssite bedeutet, dass API-Designer die Varianz von Typparametern zu Schnittstellen nicht berücksichtigen müssen, müssen sie stattdessen häufig kompliziertere Methodensignaturen verwenden. Ein gängiges Beispiel betrifft die ComparableSchnittstelle. Angenommen, wir möchten eine Funktion schreiben, die das größte Element in einer Sammlung findet. Die Elemente müssen die compareToMethode implementieren , daher könnte ein erster Versuch sein:

<T extends Comparable<T>> T max(Collection<T> coll);

Dieser Typ ist jedoch nicht allgemein genug – man kann das Maximum von a finden , aber nicht a . Das Problem ist, dass nicht implementiert wird , sondern die (bessere) Schnittstelle . In Java wird es im Gegensatz zu C# nicht als Untertyp von . Stattdessen muss der Typ von geändert werden: Collection<Calendar>Collection<GregorianCalendar>GregorianCalendarComparable<GregorianCalendar>Comparable<Calendar>Comparable<Calendar>Comparable<GregorianCalendar>max

<T extends Comparable<? super T>> T max(Collection<T> coll);

Der begrenzte Platzhalter überträgt die Informationen, die nur kontravariante Methoden von der Schnittstelle aufrufen. Dieses spezielle Beispiel ist frustrierend, weil alle Methoden in kontravariant sind, so dass diese Bedingung trivialerweise wahr ist. Ein Deklaration-Site-System könnte dieses Beispiel mit weniger Unordnung handhaben, indem es nur die Definition von annotiert . ? super TmaxComparableComparableComparable

Vergleichen von Anmerkungen zu Deklarations-Sites und Verwendungs-Sites

Anmerkungen zur Verwendung der Site-Varianz bieten zusätzliche Flexibilität und ermöglichen mehr Programmen die Typprüfung. Sie wurden jedoch für die Komplexität kritisiert, die sie der Sprache hinzufügen, was zu komplizierten Typsignaturen und Fehlermeldungen führt.

Eine Möglichkeit zu beurteilen, ob die zusätzliche Flexibilität nützlich ist, besteht darin, zu sehen, ob sie in bestehenden Programmen verwendet wird. Eine Untersuchung einer großen Anzahl von Java-Bibliotheken ergab, dass 39 % der Wildcard-Annotationen direkt durch Annotationen der Deklarations-Site hätten ersetzt werden können. Somit sind die verbleibenden 61 % ein Hinweis auf Orte, an denen Java davon profitiert, dass das Use-Site-System verfügbar ist.

In einer Deklarationssite-Sprache müssen Bibliotheken entweder weniger Varianz offenlegen oder mehr Schnittstellen definieren. Beispielsweise definiert die Scala Collections-Bibliothek drei separate Schnittstellen für Klassen, die Kovarianz verwenden: eine kovariante Basisschnittstelle, die allgemeine Methoden enthält, eine invariante veränderliche Version, die nebeneffektive Methoden hinzufügt, und eine kovariante unveränderliche Version, die die geerbten Implementierungen spezialisieren kann, um strukturelle teilen. Dieses Design funktioniert gut mit Annotationen von Deklarationssites, aber die große Anzahl von Schnittstellen verursacht Komplexitätskosten für die Clients der Bibliothek. Und das Ändern der Bibliotheksschnittstelle ist möglicherweise keine Option – insbesondere bestand ein Ziel beim Hinzufügen von Generika zu Java darin, die binäre Abwärtskompatibilität aufrechtzuerhalten.

Andererseits sind Java-Wildcards selbst komplex. In einer Konferenzpräsentation kritisierte Joshua Bloch, dass sie zu schwer zu verstehen und zu verwenden seien, und erklärte, dass wir uns beim Hinzufügen von Unterstützung für Schließungen "einfach keine weiteren Wildcards leisten können ". Frühe Versionen von Scala verwendeten Varianz-Annotationen für Verwendungsorte, aber Programmierer fanden es schwierig, sie in der Praxis zu verwenden, während Annotationen für Deklarationssites beim Entwerfen von Klassen sehr hilfreich waren. Spätere Versionen von Scala fügten existenzielle Typen und Platzhalter im Java-Stil hinzu; Wenn jedoch keine Interoperabilität mit Java erforderlich wäre, wären diese laut Martin Odersky wahrscheinlich nicht enthalten gewesen.

Ross Tate argumentiert, dass ein Teil der Komplexität von Java-Wildcards auf die Entscheidung zurückzuführen ist, die Varianz der Nutzungsorte mit einer Form existentieller Typen zu codieren. Die ursprünglichen Vorschläge verwendeten eine spezielle Syntax für Varianzanmerkungen und schrieben anstelle von Javas ausführlicheren . List<+Animal>List<? extends Animal>

Da Wildcards eine Form existentieller Typen sind, können sie für mehr als nur Varianz verwendet werden. Ein Typ wie ("eine Liste unbekannten Typs") ermöglicht es, Objekte an Methoden zu übergeben oder in Feldern zu speichern, ohne ihre Typparameter genau anzugeben. Dies ist besonders nützlich für Klassen, bei denen die meisten Methoden den Typparameter nicht erwähnen. List<?>Class

Allerdings Typinferenz für existentielle Typen ist ein schwieriges Problem. Für den Compiler-Implementierer führen Java-Platzhalter zu Problemen mit der Beendigung der Typprüfung, der Inferenz von Typargumenten und mehrdeutigen Programmen. Im Allgemeinen ist es unentscheidbar, ob ein Java-Programm, das Generics verwendet, gut typisiert ist oder nicht, daher muss jeder Typprüfer bei einigen Programmen in eine Endlosschleife oder eine Zeitüberschreitung gehen. Für den Programmierer führt dies zu komplizierten Typfehlermeldungen. Der Java-Typ überprüft Wildcard-Typen, indem er die Wildcards durch neue Typvariablen ersetzt (sogenannte Capture-Konvertierung ). Dies kann das Lesen von Fehlermeldungen erschweren, da sie sich auf Typvariablen beziehen, die der Programmierer nicht direkt geschrieben hat. Wenn Sie beispielsweise versuchen, a Catzu a hinzuzufügen , erhalten Sie einen Fehler wie List<? extends Animal>

method List.add (capture#1) is not applicable
  (actual argument Cat cannot be converted to capture#1 by method invocation conversion)
where capture#1 is a fresh type-variable:
  capture#1 extends Animal from capture of ? extends Animal

Da sowohl Deklarations-Site- als auch Use-Site-Annotationen nützlich sein können, bieten einige Typsysteme beides.

Etymologie

Diese Begriffe stammen aus dem Begriff der kovarianten und kontravarianten Funktoren in der Kategorientheorie . Betrachten Sie die Kategorie, deren Objekte Typen sind und deren Morphismen die Subtypbeziehung ≤ darstellen. (Dies ist ein Beispiel dafür, wie jede teilweise geordnete Menge als Kategorie betrachtet werden kann.) Dann nimmt zum Beispiel der Funktionstypkonstruktor zwei Typen p und r und erzeugt einen neuen Typ p → r ; so nimmt es Objekte in Objekte in . Durch die Subtypisierungsregel für Funktionstypen kehrt diese Operation ≤ für den ersten Parameter um und behält es für den zweiten bei, so dass es im ersten Parameter ein kontravarianter Funktor und im zweiten ein kovarianter Funktor ist. ${\displaystyle C}$${\displaystyle C^{2}}$${\displaystyle C}$

Siehe auch

• Polymorphismus (Informatik)
• Vererbung (Informatik)
• Liskov-Substitutionsprinzip

Verweise

Externe Links

• Fabulous Adventures in Coding : Eine Artikelserie zu Implementierungsproblemen im Zusammenhang mit Co/Kontravarianz in C#
• Contra Vs Co Variance (beachten Sie, dass dieser Artikel nicht über C++ aktualisiert wird)
• Closures für die Programmiersprache Java 7 (v0.5)
• Die Theorie hinter Kovarianz und Kontravarianz in C# 4