Das Scala-Typsystem: Parametrisierte Typen und Varianzen, Teil 2

Was meint der Scala-Typchecker mit der Fehlermeldung covariant type occurs in contravariant position? Welche Regeln stecken dahinter? Wie lassen sich diese Regeln auf den vertrauten Subtyp-Polimorphismus zurückführen? Dieser Post befasst sich mit diesen Frage, nachdem im letzten Post Typ-Parameter und Varianz-Annotationen beleuchtet wurden.

Einleitung

Ko- und kontravariante Annotationen erlauben es, die Vererbungshierarchie eines generischen Typs aus der Vererbungshierarchie seines Typ-Parameters abzuleiten. Wenn man diese Möglichkeit nutzt, lässt sich der Typ-Parameter allerdings nicht mehr überall verwenden; der Scala-Compiler weist einige Konstellationen in generischen Klassen zurück, und produziert Fehlermeldungen der Form covariant type T occurs in contravariant position oder contravariant type T occurs in covariant position. Hinter diesen Fehlermeldungen stecken Regeln, die der Scala-Typchecker auf generische Klassen anwendet. Ein für mich Spannender Aspekt dieser Regeln ist, dass sie einerseits unverständlich erscheinen, und sich andererseits aus dem Subtyp-Polimorphismus motivieren lassen.

Um zu verstehen, wie der Scala-Typchecker versucht, die Typsicherheit einer Codebase zu garantieren, und wie sich die Regeln, die er dabei verwendet, auf ein so vertrautes Konzept zurückführen lässt, werden wir zunächst diskutieren, was mit Subtyp-Polimorphismus gemeint ist. Danach werden wir sehen, wie bereits beim Overriding von Methoden das Thema Ko- und Kontravarianz auftaucht. Die Erkenntnisse, die wir daraus gewinnen, können wir im Anschluss nutzen, um besser zu verstehen, wie Typ-Parameter-Varianzen geprüft werden, und wie Typ-Parameter mit Varianzen verwendet werden dürfen. Danach werden wir noch diskutieren, wie die Checking-Regeln bei unteren Typ-Schranken zur Anwendung kommen, und warum die erlaubten Konstellationen typsicher sind.

TL;DR

Keine Zeit? Die Ergebnisse sind am Ende des Artikels zusammengefasst.

Subtyp-Polymorphismus

Bevor wir zu den Regeln kommen, die der Scala-Typchecker beim Prüfen von Typ-Parametern anwendet, hole ich aus um das Prinzip des Subtyp-Polymorphismus zu umreißen, auf dem diese Checks basieren (ausführlichere Erklärungen finden sich in unserem Blog , auf Wikipedia , und in diesem Buch ). Betrachten wir (nochmal) folgende Klassenhierarchie von Kisten und Früchten.

1abstract class Fruit { def name: String }
2class Orange extends Fruit { def name = "Orange" }
3class Apple extends Fruit { def name = "Apple" }
4 
5abstract class Box {
6 
7  def fruit: Fruit
8 
9  def contains(aFruit: Fruit) = fruit.name.equals(aFruit.name)
10}
11 
12class OrangeBox(orange: Orange) extends Box {
13  def fruit: Orange = orange
14}
15 
16class AppleBox(apple: Apple) extends Box {
17  def fruit: Apple = apple
18}

Bei dieser Hierarchie erlaubt der Scala-Compiler, einer Variablen vom Typ Box ein Objekt vom Typ AppleBox (oder OrangeBox) zuzuweisen. Der Hintergedanke dabei ist, dass aufgrund der Vererbungsbeziehung garantiert ist, dass das zugewiesene Objekt über alle Methoden und Felder verfügt, die Box implementiert (wie die contains-Methode), oder in Box verlangt sind und eine konkrete Subklasse implementiert (wie die fruit-Methode). Nach der gleichen Logik darf ein Apple oder Orange-Objekt als aktueller Parameter verwendet werden, wenn ein Fruit-Objekt erwartet wird:

1var apple = new Apple
2 
3// eine AppleBox darf einer Box-getypten Variablen zugewiesen werden.
4var box: Box = new AppleBox(apple)
5 
6// 'contains' erwartet ein Fruit-Objekt, ein Apple-Objekt ist auch ok.
7if (box contains apple) {
8  // box.fruit garantiert ein Objekt vom Typ Fruit, dadurch hat es eine Methode 'name'.
9  var fruitName = box.fruit.name
10  println("box contains an $fruitName") 
11}

Das Konzept, dass es immer zulässig ist eine Instanz eine Typs durch eine Instanz eines Subtyps zu ersetzen, wird als Subtyp-Polymorphismus bezeichnet.

Subtyp-Polymorphismus und das Overriding von Methoden

Das Konzept des Subtyp-Polymorphismus, das wir an Variablen-Zuweisungen und Methoden-Aufrufen motiviert haben, lässt sich auch auf Methoden-Signaturen übertragen. Betrachten wir folgende abgeänderte AppleBox-Klasse.

1class AppleBox(apple: Apple) extends Box {
2  // Subklasse Apple statt Fruit als Rückgabetyp erlaubt.
3  def fruit: Apple = apple
4}
5 
6var apple = new Apple
7var box: Box = new AppleBox(apple)
8 
9// box.fruit liefert ein Apple, d.h. eine Subklasse von Fruit.
10println("box contains an $box.fruit.name")

Mit dem Rückgabetyp Apple erfüllt die AppleBox.fruit-methode die Anforderung der Box.fruit-Methode: Jeder Client, der beim Aufruf der konkreteren AppleBox.fruit-Methode ein Fruit-Objekt als Rückgabewert erwartet, bekommt ein Apple-Objekt. Damit bekommt er eine Instanz eines Subtyps, was nach der Idee des Subtyp-Polymorphismus in Ordnung ist. Dieses Sprach-Feature heißt Covariant Return Type , und existiert zum Beispiel in Java seit Version 5, in Scala, und in C++.

Durch eine ähnliche Argumentation könnte eine typsichere Sprache erlauben, den Methodenparameter-Typ zu verallgemeinern, wenn eine Methode überschrieben wird. Dieses Feature heißt Contravariant method argument type , und kann von Sprachen, die auf der JVM laufen, zur Zeit nicht unterstützt werden. Folgender Beispiel-code in daher in Scala nicht erlaubt, auch wenn er typsicher wäre (die Erklärung des Beispiels folgt nach dem Code).

1abstract class Box {
2 
3  def fruit: Fruit
4 
5  def contains(apple: Apple) = fruit.name.equals(apple.name)
6}
7 
8class AppleBox(apple: Apple) extends Box {
9 
10  def fruit: Apple = apple
11 
12  // Allgemeinere Klasse Fruit statt Apple: wäre typsicher, ist aber nicht erlaubt.
13  override def contains(aFruit: Fruit) = fruit.name.equals(aFruit.name)
14}

Da die Methode Box.contains ein Objekt vom Typ Apple verlangt, darf bei einem Aufruf kein Objekt vom Typ Fruit übergeben werden. Die konkretere Implementierung AppleBox.contains kann diese Einschränkung aber lockern und lediglich ein Objekt vom Supertyp Fruit verlangen: Jeder client-code, der eine Variable vom Typ Box enthält, ist beim Aufruf von contains verpflichtet eine Instanz des konkreteren Typs (Apple) zu übergeben. Falls dieser Variable ein Objekt vom Typ AppleBox zugewiesen ist, wird bei Aufruf von contains die Methode AppleBox.contains aufgerufen. Diese Methode kann mit Objekten vom Typ Apple aufgerufen werden, da Apple eine Subklasse von Fruit ist.

Client-code, der eine Referenz auf ein Objekt des konkreteren Typ AppleBox hält, kann andererseits die zusätzliche Möglichkeit nutzen, die AppleBox.contains-Methode mit Objekten vom Typ Fruit aufzurufen, z.B. mit Orange-Objekten.

Insgesamt lässt sich also festhalten, dass das Prinzip von Kovarianz und Kontravarianz bereits auf der ebene von Methoden-Signaturen existiert und auf dem Konzept des Subtyp-Polymorphismus beruht. Dabei ist es sinnvoll, dass der Rückgabetyp von Methoden kovariant konkretisiert werden darf, und Typen von Methodenparametern kontravariant verallgemeinert werden dürfen.

Erlaubte Varianz-Annotationen

Varianz-Annotationen werden vom Scala-Compiler geprüft, und nicht immer sind alle Varianz-Annotationen gültig. Beim Prüfen geht der Compiler nach dem Prinzip vor, das ich gerade beschrieben habe: Rückgabetypen dürfen nur invariant oder kovariant sein, und Methodenparameter-Typen nur invariant oder kontravariant. Wenn diese Regeln eingehalten werden, dann kann der Typchecker garantieren, dass die polymorphe Zuweisung von typ-paramtetrisierten Klassen typsicher ist. Um das genauer zu sehen, schauen wir uns folgendes Beispiel an.

1abstract class Box[+F <: Fruit] {
2 
3  def fruit: F
4 
5  def contains(aFruit: Fruit) = fruit.name.equals(aFruit.name)
6}
7 
8class OrangeBox(orange: Orange) extends Box[Orange] {
9  def fruit = orange
10}
11 
12class AppleBox(apple: Apple) extends Box[Apple] {
13  def fruit = apple
14}
15 
16var fruitBox: Box[Fruit] = new AppleBox(new Apple)
17 
18var fruit: Fruit = fruitBox.fruit

Im Beispiel ist der Typ-Parameter von Box[+F] kovariant, daher darf einer Box[Fruit]-getypten Variablen fruitBox ein Objekt vom Typ Box[Apple] zugewiesen werden. Das ist okay, solange der Typ F nur als Rückgabetyp von Methoden auftaucht, wie z.B. in der Methode Box.fruit. Beim Aufruf von fruitBox.fruit ist garantiert, dass ein Objekt vom Typ Fruit oder von einem konkreten Subtyp zurückliefert wird: Da der Typ-Parameter kovariant ist, darf der Typ-Parameter im tatsächlich zugewiesenen Objekt nur an einen Typ gebunden werden, der konkreter als Fruit ist.

Angenommen, wir hätten eine Methode replace, in der F als Parameter verwendet wird:

1abstract class Box[+F <: Fruit] {
2 
3  def fruit: F
4 
5  // F als Typ des Parameters 'replacement' wird vom Typchecker zurückgewiesen.
6  def replace(replacement: F)
7}
8 
9// wäre wegen Kovarianz von F erlaubt
10var fruitBox: Box[Fruit] = new AppleBox(new Apple)
11 
12// wäre wegen Subtyp-Polymorphismus erlaubt, da Orange Subtyp von Fruit ist
13fruitBox.replace(new Orange)

Hier haben wir ein Problem: während im Aufruf von replace ein Orange-Objekt übergeben wird, akzeptiert die Methode AppleBox.replace nur Apple-Objekte. Der Typchecker verbietet daher aus gutem Grund, F als Typ des Parameters replacement zu verwenden. Durch kovariante Annotation darf der an F gebundene Typ konkreter werden als Fruit, in unserem Fall muss er aber gleich bleiben oder allgemeiner sein. Hätten wir F kontravariant annotiert, wäre das garantiert. Dann wäre der Aufruf fruitBox.replace(new Orange) möglich, aber die Zuweisung var fruitBox: Box[Fruit] = new AppleBox(new Apple) wird vom Typchecker zurückgewiesen, da Box[Apple] ein Supertyp von Box[Fruit] ist, und kein Subtyp.

Je nachdem, wo ein Typ-Parameter in einer typ-parametrisierten Klasse verwendet wird, sind bestimmte Varianz-Annotationen erlaubt oder verboten: In der Box[+F <: Fruit]-Klasse zum Beispiel wird der Typ-Parameter F als Rückgabetyp der Methode Box.fruit verwendet; deswegen darf der Typ-Parameter F nur als invariant oder kovariant annotiert werden.

Der Scala-Compiler führt beim Prüfen einer Klassendeklaration Buch über alle Vorkommen eines Typ-Parameters, und bestimmt die erlaubte Varianz eines Vorkommens nach der Position im Code. Die Fehlermeldung des Scala-Compilers, die angibt, dass ein Typ in einer unerlaubten Position vorkommt, meint, dass ein Vorkommen eines Typ-Parameters nur eine bestimmte Varianz erlaubt (z.b. kontravariant), der Typ-Parameter aber mit einer anderen Varianz annotiert wurde (z.b. kovariant).

Die genauen Regeln finden sich in der Scala Sprachspezifikation , und einen guten Einstieg in die Logik dieser Spezifikiation liefert die Zusammenfassung von Marko Bonaci . In der Spezifikation wird davon geschrieben, dass die erlaubte Varianz eines Typ-Parameters zunächst Kovarianz ist, und dass sie in bestimmten Positionen zwischen Kovarianz und Kontravarianz durch Invertierung hin- und herwechselt.

Die erlaubte Varianz wechselt zum Beispiel bei:

1. Methoden-Parametern (von kovariant zu kontravariant),
2. Typ-Parameter-Klauseln von Methoden,
3. unteren Schranken von Typ-Parametern und
4. aktuellen Typ-Parametern von parametrisierten Typen, falls der entsprechende formale Typ-Parameter kontravariant annotiert ist.

Die folgenden Beispiele beleuchten diese vier Regeln:

• In def method(parameter: T) ist T in einer kontravarianten Position, da Regel 1 greift.
• In def method[U <: T]() ist T in einer kontravarianten Position, da Regel 2 greift.
• In def method[U >: T]() ist T in einer kovarianten Position, da Regeln 2 und 3 greifen.
• Angenommen, der Typ-Parameter der Klasse Box ist durch class Box[-A] kontravariant annotiert. Dann ist T in def method(parameter: Box[T]) in einer kovarianten Position, da Regeln 1 und 4 greifen.

Durch diese Beispiel-Regeln ergeben sich einige interessante Möglichkeiten und Einschränkungen. Ein Beispiel wurde bereits zu Beginn des Abschnitts diskutiert. Mit einem zweiten Beispiel im nächsten Abschnitt betrachten wir die Regel für untere Typ-Schranken genauer.

Varianz-Positionen von Typ-Schranken

Warum ist es sinnvoll, eine Typ-Parameter-Position von kontravariant auf kovariant zu invertieren, wenn er als untere Schranke einer Typ-Parameter-Klausel auftaucht? Nun, ein kovarianter Typ-Parameter T in einer Klasse Box[+T] kann durch Subtyp-Polimorphismus nur konkretisiert werden. Das heißt, der konkrete Typ für T kann in der Vererbungshierarchie nur nach unten wandern. Wird er als untere Schranke für einen anderen Typ U verwendet, dann bedeutet das, dass die untere Schranke für U durch Konkretisierung von T gelockert wird. Es besteht also keine Gefahr, dass durch Konkretisierung von T ein zuvor erfolgreicher Check von U >: T ungültig wird. Schauen wir uns ein Beispiel an:

1class Box[+T] {
2  def method[U >: T](p: U) = { /* here be code */ }
3} 
4var apple: Apple = new Apple
5var box: Box[Fruit] = new Box[Orange]
6box.method(apple)

Der Aufruf von Box.method bleibt gültig, auch wenn box durch ein Objekt eines Subtyps (z.B. Box[Orange]) ersetzt wird, denn T wird dann an einen konkreteren Typ gebunden. Der Typ-Parameter U ist gleichzeitig nicht nach oben beschränkt; falls also der konkrete Typ des Parameters p stark von T abweicht, kann der Compiler für den Typ-Parameter U einen beliebig allgemeinen Typ auswählen, bis hinauf zu scala.Any. Es besteht also keine Gefahr, dass die Typsicherheit verletzt wird, sondern lediglich, dass der an U gebundene Typ sehr allgemein wird.

Zusammenfassung

Wir haben gesehen, wie ko- und kontravariante Typ-Parameter vom Typchecker behandelt werden. Spannend ist dabei, dass die Typchecking-Regeln von Typ-Parametern mit dem Konzept des Subtyp-Polimorphismus erklärbar sind, wenn auch über einen Umweg. Der Umweg besteht in der Anwendung des Subtyp-Polimorphismus auf das Methoden-Overriding. Hier haben wir gesehen, dass die kontravariante Verallgemeinerung von Methodenparameter-Typen sinnvoll ist, wie auch die kovariante Konkretisierung von Rückgabetypen; letzteres wurde auch mit Java 5 eingeführt. Ich vermute, dass dieses Sprach-Feature mittlerweile einigermaßen bekannt ist, aber dennoch selten genutzt wird.

Nachdem wir jetzt gesehen haben, was Varianz-Annotationen von Typ-Parameter sind, und wie sie vom Typchecker behandelt werden, wird es im nächsten Post darum gehen, wie Typ-Parameter und Varianz-Annotationen in Scala sinnvoll eingesetzt werden können.

Die Ergebnisse in Kurzform

Hier sind die Ergebnisse aus den ersten beiden Posts zusammengefasst.

Subtyp-Beziehungen

Angenommen, class Orange extends Fruit gilt. Falls class Box[A] deklariert ist, kann A mit Präfix + oder - annotiert werden.

• A ohne Annotation ist invariant, d.h.:
  • Box[Orange] steht in keinem Zusammenhang zu Box[Fruit].
• +A ist kovariant, d.h.:
  • Box[Orange] ist eine Subklasse von Box[Fruit].
  • var f: Box[Fruit] = new Box[Orange]() ist erlaubt.
• -A ist kontravariant, d.h.:
  • Box[Fruit] ist eine Subklasse von Box[Orange].
  • var f: Box[Orange] = new Box[Fruit]() ist erlaubt.

Erlaubte Positionen

• Invariante Typ-Parameter sind überall erlaubt:
  • abstract class Box[A] { def foo(a: A): A } ist erlaubt.
  • abstract class Box[A] { var a: A } ist erlaubt.
• Kovariante Typ-Parameter sind nur als Rückgabetypen von Methoden erlaubt:
  • abstract class Box[+A] { def foo(): A } ist erlaubt.
• Kontravariante Typparemeter sind nur als Typ von Methodenparametern erlaubt:
  • abstract class Box[-A] { def foo(a: A) } ist erlaubt.
• Workaround um einen Kovarianten Typ in einen Methodenparameter-Typ zu verwenden:
  • abstract class Box[+A] { def foo[B >: A](b: B) } ist erlaubt.
• Workaround um einen Kontravarianten Typ in einem Rückgabetyp zu verwenden:
  • abstract class Box[-A] { def foo[B <: A](): B } ist erlaubt.
• Die vollständigen Regeln sind umfangreicher als hier zusammengefasst. Im Artikel werden sie genauer besprochen.