Teil 14.1: Varianzen

Mit Varianzen können Aussagen darüber gemacht werden ob die Vererbungshierarchie eines parametrisierten Typs auf eine generische Klasse übertragen werden soll. Das Hauptaugenmerk liegt dabei auf der Frage ob eine generische Klasse mit einem Typ Foo, der Untertyp von Bar ist (Foo <: Bar), auch ein Untertyp der selben generischen Klasse mit einem Typ Bar ist (GenClass[Foo] <: GenClass[Bar]).

Gehen wir einmal davon aus, dass obige Aussage zutreffen würde, dann müsste folgender Code korrekt kompilieren:

val xs: Array[Any] = Array[Int](18)
xs(0) = "hello"

Int ist ein Untertyp von Any (Int <: Any), also trifft dies auch auf die Arrays zu (Array[Int] <: Array[Any]). Da String <: Any gilt wird folglich auch die Zuweisung in der nächsten Zeile korrekt kompilieren. Sobald dieser Code jedoch ausgeführt werden würde, würden wir eine Exception bekommen, da ein String nicht in einem Int-Array abgespeichert werden kann (type-erasure gilt nicht für Arrays!).

Dies ist ein gefährlicher Fehler, vor dem uns der Scala-Compiler aber vortrefflich schützt – obiger Code würde nicht kompilieren:

scala> val xs: Array[Any] = Array[Int](18)
<console>:7: error: type mismatch;
 found   : Array[Int]
 required: Array[Any]
Note: Int <: Any, but class Array is invariant in type T.
You may wish to investigate a wildcard type such as `_ <: Any`. (SLS 3.2.10)
       val xs: Array[Any] = Array[Int](18)
                                      ^

Bei List bekommen wir diesen Fehler nicht:

scala> val xs: List[Any] = List[Int](18)
xs: List[Any] = List(18)

Der Grund, warum die Varianz der Liste nicht so funktioniert wie bei Arrays, liegt in der Unveränderlichkeit. Die Elemente einer List lassen sich nach ihrer Erstellung nicht mehr verändern, die von Array dagegen schon. Der Compiler schützt uns also davor, Schabernack mit veränderlichen Objekten zu machen.

Invarianz

Es gibt drei verschiedene Arten von Varianzen. Die Invarianz, die die Standardvarianz in Scala ist, wollen wir uns als erstes anschauen. Immer dann, wenn wir einen generischen Parameter ohne weitere Kennzeichnung erstellen, erstellen wir einen invarianten parametrisierten Typ.

Invarianz bedeutet, dass sich der Beziehungsstatus von parametrisierten Typen nicht auf die generischen Klassen überträgt. Es gilt:

A <: B => keine Beziehung zwischen C[A] und C[B]

Arrays sind in Scala wegen ihrer Veränderlichkeit invariant. Es ist uns also nicht möglich ein Array vom Typ Int auf ein Array vom Typ Any zu mappen. obwohl Int <: Any.

Wir können das invariante Verhalten von Array leicht nachbauen:

scala> case class Box[A](var a: A)
defined class Box

scala> val b1 = Box(9)
b1: Box[Int] = Box(9)

scala> val b2: Box[Any] = b1
:13: error: type mismatch;
 found   : Box[Int]
 required: Box[Any]
Note: Int You may wish to define A as +A instead. (SLS 4.5)
       val b2: Box[Any] = b1
                          ^

Kovarianz

Die zweite mögliche Form ist die Kovarianz, die es uns erlaubt den Beziehungsstatus von Typen, ganz im Gegensatz zur Invarianz, auf die generischen Klassen zu übertragen. Es gilt:

A <: B => C[A] <: C[B]

Ein Beispiel für eine invariante Datenstruktur in Scala ist List. Die Beziehung lautet List[Int] <: List[Any], da Int <: Any. Wir können unsere eigenen invarianten Datentypen erstellen, indem wir der Typisierung ein + voranstellen:

scala> case class Box[+A](a: A)
defined class Box

scala> val b: Box[Any] = Box[Int](8)
b: Box[Any] = Box(8)

Versuchen wir nun unseren Typ veränderlich zu machen, beschwert sich sofort wieder der Compiler:

scala> case class Box[+A](var a: A)
:10: error: covariant type A occurs in contravariant position in type A of value a_=
       case class Box[+A](var a: A)
                  ^

Falls dieser Code kompilieren würde, wäre nicht sicher gestellt, dass Box auch nur den Typ aufnimmt, für den es bestimmt wurde:

// does not compile
val b: Box[Any] = Box[Int](9)
b.a = "hello"

Kontravarianz

Die letzte mögliche Variante ist die Kontravarianz. Sie funktioniert genau verkehrt herum wie die Kovarianz. Es gilt:

A <: B => C[B] <: C[A]

Kontravarianz wird sehr selten eingesetzt, da es im Grunde nicht viele Anwendungsfälle dafür gibt. Ein Beispiel wäre z.B. das Folgende:

class Foo[-A] {
  def bar(a: A): Int =
    sys.error("unimplemented")
}

scala> val base = new Foo[Any]
base: Foo[Any] = Foo@e18a9e8

scala> val derived: Foo[Int] = base
derived: Foo[Int] = Foo@e18a9e8

Zu Recht stellt man sich am Anfang die Frage warum ein Foo[Any] als Foo[Int] angesprochen werden kann, schließlich ist Int <: Any. Schauen wir uns also ein paar weitere Beispiele an um die Unterschiede zwischen den einzelnen Varianzen stärker hervorzuheben.

Anwendungsfälle

Zur Invarianz sollte es nichts mehr zu sagen geben. Alle veränderlichen parametrisierten Typen sind invariant, da es sonst möglich wäre sie mit einem ungültigen Typ zu überschreiben. Bitte beachtet, dass es einen Unterschied zwischen

val xs: Array[Any] = Array(3)

und

val xs: Array[Any] = Array[Int](3)

gibt. Nur die erste Variante würde erfolgreich kompilieren, die zweite würde aufgrund des invarianten Arrays eine Fehlermeldung verursachen. Dank Scalas Typinferenz erstellt der Compiler im ersten Beispiel ein Array[Any], weist diesem aber ein Int zu. Dies funktioniert ohne Probleme, da Int <: Any. Im zweiten Beispiel würde ein Array[Int] erzeugt werden, das als Array[Any] betrachtet werden soll – das ist verboten.

Mit der Kovarianz können wir schon deutlich mehr anstellen. Das Beispiel mit List[Int] <: List[Any] wurde schon genannt. Die Frage ist jetzt nur was für einen konkreten Vorteil man davon hat eine List[Int] als List[Any] anzusprechen. Um diese Frage zu klären schauen wir uns folgenden Code an:

// does not compile

abstract class Animal
class Cow extends Animal
class Pig extends Animal

class Farm {
  
  private val cows = new Array[Cow](3)
  
  cows(0) = new Cow
  cows(1) = new Cow
  
  def animals: Array[Animal] = cows // type mismatch
}

Auf einem Bauernhof werden verschiedenen Tiere verwaltet. Intern können die Tiere korrekt angesprochen werden. Von außerhalb des Hofes wollen wir aber nicht, dass irgendjemand eines der Tiere direkt ansprechen kann, weshalb wir nur die Information weitergeben, dass zwar Tiere vorhanden sind, aber nicht welche genau. Falls dieser Code kompilieren würde, könnte jetzt jemand von außerhalb einfach so ein Schwein auf einen Bauernhof mit lauter Kühen platzieren, was aber nicht funktionieren darf, da z.B. keine Nahrung für Schweine vorhanden ist.

Ändern wir das Array zu einer List würde der Code erfolgreich kompilieren.

class Farm {
  
  private var cows = List.empty[Cow]
  
  cows :+= new Cow
  cows :+= new Cow
  
  def animals: List[Animal] = cows
}

Da List nicht veränderlich ist, würde unserem Kühe-Bauernhof auch nichts passieren wenn er durch Schweine ergänzt werden würde. Schließlich würden dadurch alle Tiere geklont werden und könnten auf einem neuen Bauernhof platziert werden – der alte Bauernhof bleibt unangetastet.

Vereinfacht gesagt erzeugt Kovarianz read-only-Datenstrukturen. Deren Daten können zwar jederzeit abgerufen aber nie verändert werden. Die Kontravarianz dagegen macht das genaue Gegenteil. Sie erzeugt write-only-Datenstrukturen. Schauen wir uns an wofür das nützlich ist:

// P = parameter value; R = return value
abstract class AnimalTransformator[-P, +R] {
  def apply(p: P): R
}

val animal2cow = new AnimalTransformator[Animal, Cow] {
  def apply(p: Animal) = /* a lot of magic here */ new Cow
}

val pig2animal: AnimalTransformator[Pig, Animal] = /* also a lot of magic here */ animal2cow

Es existieren magische Geräte, die Tiere in andere Tiere verwandeln können. Welche Tiere dabei herauskommen ist nicht immer festzustellen. Eines dieser Geräte (animal2cow) erzeugt jedoch immer eine Kuh, egal was für ein Tier es als Eingabe erhält. Ein anderes Gerät (pig2animal) erzeugt aus einem Schwein irgendein Tier. Wenn letzteres Gerät nun sein Schwein an das erste Gerät weiterreicht und dessen Kuh entgegen nimmt, dann wäre das kein Verstoß seiner Funktionsweise, da Pig <: Animal und Cow <: Animal. Das erste Gerät kann immer ein Schwein entgegen nehmen, das zweite dagegen immer eine Kuh. In Scala funktioniert das aber nur wenn wir P als kontravariant und R als kovariant markieren.

Gut, das Beispiel war jetzt sehr an den Haaren herbeigezogen, man sollte daran aber auch die Funktionsweise des Leseschutzes erkennen können. Folgender Code würde nämlich nicht funktionieren:

// in AnimalTransformator
def clone(p: P): P

// signature in our case
// clone(Animal): Animal

Diese Methode würde ein Tier klonen, was auch funktionieren darf. Das Klonen könnte theoretisch aber auch schief gehen, was zur Folge hätte, dass z.B. ein unsichtbarer Klon erzeugt werden würde. Was machen wir dann? Wir könnten nicht herausbekommen ob das Tier geklont oder fälschlicherweise transformiert wurde. Ein Tier als Eingabe würde auch ein Tier als Ausgabe produzieren – so ist unsere Spezifikation. Wir könnten unser Tier als Tier ansprechen, aber eben nicht als irgendeine Spezialisierung – der Leseschutz offenbart sich also als Hilfe, die uns daran hindert, eine Kuh als Schwein zu betrachten.

Als kleine Merkhilfe kann die Position eines Typs dienen. Parameter von Methoden können kontravariant, jedoch nie kovariant sein. Die Rückgabewerte dürfen dagegen nie kontravariant sein. Warum das so ist solltet ihr aufgrund den obigen Erklärungen nun verstanden haben. Falls dem noch nicht so ist, geht die Beispiele noch einmal durch, baut euch eure eigene Beispiele und überlegt nochmal, was passieren würde wenn kovariante Parametertypen und kontravariante Rückgabetypen erlaubt wären.

Ausnahmefälle

Mit Collections gibt es einen schönen Anwendungsfall, bei dem wir kovariante Typen benötigen, diese aber auch als Parameter verwenden müssen. Nehmen wir als Collection-Beispiel die altbekannte List von der wir schon im Kapitel über Extraktoren eine eigene Implementierung geschrieben haben. Diese wollen wir nun zu einer generischen Liste ausbauen, damit wir sie für alle Typen nutzen können und nicht nur für Int. Damit wir keine Namensprobleme mit der Liste aus den Scala-Collections bekommen, werden wir einen anderen Namen wählen:

abstract class LinkedList[A] {
  def head: A
  def tail: LinkedList[A]
  def isEmpty: Boolean
  
  def :: (a: A): LinkedList[A] =
    new ::(a, this)
}

case class :: [A](head: A, tail: LinkedList[A]) extends LinkedList[A] {
  def isEmpty = false
}

case object LNil extends LinkedList[Nothing] {
  def head = throw new UnsupportedOperationException("nil head")
  def tail = throw new UnsupportedOperationException("nil tail")
  def isEmpty = true
}

Die einzige Neuerung sollte in diesem Codebeispiel der Typ „Nothing“ sein. Nothing ist ein Untertyp jedes anderen Typs (A => Nothing <: A) und kann somit als Typisierung der List verwendet werden. Einem object können wir keinen Typparameter mitgeben, weshalb wir auf Nothing angewiesen sind.

Einziges Problem ist jetzt die Erstellung einer geeigneten Liste:

scala> val xs = 1 :: 2 :: 3 :: LNil
<console>:13: error: type mismatch;
 found   : x$1.type (with underlying type Int)
 required: Nothing
       val xs = 1 :: 2 :: 3 :: LNil
                            ^

Unsere List ist invariant, weshalb der Compiler es nicht akzeptiert eine LinkedList[Nothing] an eine LinkedList[Int] zu hängen, obwohl Nothing <: Int. Führen wir also Kovarianz ein:

abstract class LinkedList[+A] { ... }

Leider taucht nun eine weitere Fehlermeldung auf:

<console>:19: error: covariant type A occurs in contravariant position in type A of value a
         def :: (a: A): LinkedList[A] =
                 ^

Ein kovarianter Paramertyp – das geht verständlicherweise nicht. Aber was machen wir da jetzt? Die Lösung liegt in der Benutzung eines weiteren Typparameters:

// in class LinkedList
def :: [B >: A](b: B): LinkedList[B] =
  new ::(b, this)

Die Bedeutung dieses Konstrukts zu verstehen ist jetzt auch nicht mehr viel komplizierter als der Rest von Varianzen. Unser Ausgangspunkt zur Erstellung einer LinkedList ist LNil. Dieses Objekt ist mit Nothing parametrisiert. Die Typsignatur der Methodenaufrufe würde also so aussehen:

LinkedList[Nothing].::(Int).::(Int).::(Int): LinkedList[Int]

Um von einer LinkedList[Nothing] zu einer LinkedList[Int] zu kommen benötigt es einem Lower-Bound (B >: A => Int >: Nothing). Nichts anderes sagt der zusätzliche Parameter in der Konkatenations-Methode aus, die eine LinkedList mit dem höherwertigen Typ zurück gibt.

Ich denke, dass es angebracht ist euch an dieser Stelle zu beruhigen. Falls ihr bisher noch nie mit Varianzen zu tun hattet, dann werdet ihr ihre praktische Bedeutung vermutlich nicht vollständig verstanden haben (wenn ihr überhaupt irgendetwas verstanden habt ;)). Varianzen gehören aber nun mal zur Typ-Theorie dazu, weshalb man sich damit früher oder später beschäftigen sollte. Falls euch das alles also ein wenig zu kompliziert war, dann kommt zu einem späteren Zeitpunkt darauf zurück.

Advertisements

No comments yet

Kommentar verfassen

Trage deine Daten unten ein oder klicke ein Icon um dich einzuloggen:

WordPress.com-Logo

Du kommentierst mit Deinem WordPress.com-Konto. Abmelden / Ändern )

Twitter-Bild

Du kommentierst mit Deinem Twitter-Konto. Abmelden / Ändern )

Facebook-Foto

Du kommentierst mit Deinem Facebook-Konto. Abmelden / Ändern )

Google+ Foto

Du kommentierst mit Deinem Google+-Konto. Abmelden / Ändern )

Verbinde mit %s

%d Bloggern gefällt das: