Das Scala-Typ-System: Parametrisierte Typen und Varianzen, Teil 3

In Scala ist es möglich mit Hilfe von Ko- und Kontravarianz-Annotationen an Typ-Parametern, Zusammenhänge zwischen parametrisierten Klassen aus der Klassenhierarchie des eingesetzten Typs abzuleiten . Der Compiler prüft mit einer Reihe von Regeln , wie die Typ-Parameter in einer Klasse verwendet werden. Dabei überprüft der Compiler, ob alle Vorkommen von Typ-Parametern okay sind, d.h. ob die parametrisierte Klasse typsicher ist.

Typ-Parametrisierte Klassen und ko- und kontravariante Annotationen sind ein mächtiges Werkzeug, das während des Designs einer Klasse und während des Codings an vielen Stellen einsetzbar ist. Wo ist es aber sinnvoll, diese Werkzeuge einzusetzen? Dieser Blog-Post stellt meine Erkenntnisse und meine Momentane Meinung zu diesem Thema vor.

TL;DR

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

Typ-Parameter und Varianzen Sinnvoll Einsetzen

In meiner bisherigen Programmier-Laufbahn habe ich zwei Anwendungsfälle gesehen, in denen Typ-Parameter und Varianzen sinnvoll sind: Das erste sind Frameworks wie Collections Frameworks und Concurrency Frameworks , und das Zweite sind Typ-parametrisierte Methoden. In allen anderen Fällen, in denen (zum Teil auch von mir selbst) Typ-Parameter eingesetzt wurden, habe ich sie als unnötige Komplexität empfunden, die das Verständnis des Codes deutlich erschwert haben ohne einen spürbaren Mehrwert zu liefern. In zwei Java-Frameworks, die ich selbst entwickelt hatte, habe ich mich mit Java Generics sogar so weit in eine Ecke programmiert, dass ich die Typ-Parameter wieder aus dem Code entfernt habe, und durch instanceof-Checks und Casts ersetzt habe. Mittlerweile stehe ich persönlich domänenspezifischem Code äußerst skeptisch gegenüber, der Typ-Parameter intensiv nutzt.

Collection Frameworks

Der Muster –Anwendungsfall für Ko- und Kontravarianz sind meiner Meinung nach Collections wie Listen, Mengen, oder Abbildungen (Maps). Dieser Anwendungsfall motiviert sich dadurch, dass Arrays in Java kovariant sind. Diese Kovarianz ist wegen der Modifizierbarkeit des Array-Inhalts durch Zuweisungen nicht typsicher, wie folgendes Beispiel zeigt:

1String[] strings = new String[1];
2Object[] objects = strings;
3objects[0] = 1;
4strings[0].indexOf(" ");

Durch die Kovarianz von Arrays ist ein String Array auch ein Object Array und die Zuweisung in Zeile 2 möglich. In einem Object Array darf ein beliebiges Objekt eingefügt werden, also auch ein Integer. Der Code wird vom Java-Compiler daher anstandslos akzeptiert. Der Aufruf in Zeile 4 erwartet ein String, bekommt jedoch zur Laufzeit ein Integer. Glücklicherweise kommt es gar nicht zur Ausführung von Zeile 4, denn die Implementierung von Array wirft bereits in Zeile 3 beim Versuch ein Integer in dem String Array zu speichern eine ArrayStoreException (Nebenbemerkung: dieses Verhalten folgt dem Fail-Fast-Prinzip , und erleichtert das Nachvollziehen solcher Probleme in umfangreichen Codebases deutlich).

Als Fazit hat sich mittlerweile etabliert, dass modifizierbare Collections invariant sein müssen; um das gerade beschrieben Problem zu verhindern, darf String Array kein Subtyp von Object Array sein. Unveränderliche Collections leiden nicht unter diesem Problem, und können kovariant implementiert werden, ohne die Typsicherheit zu gefährden. Eine solche unveränderliche Liste kann mittels copy-on-write erzeugt werden, oder als verkettete Liste, die durch Anhängen neuer Elemente erweitert werden kann. Eine Box-implementierung als verkettete Liste könnte zum Beispiel wie folgt aussehen.

1abstract class Box[+A] {
2  def isEmpty: Boolean
3 
4  def contains[B] (item: B): Boolean
5  def prepend[B <: A](item: B): BoxItem[B] = new BoxItem[B](item, this)
6}
7 
8case class BoxItem[+A](item: A, next: Box[A]) extends Box[A] {
9  def isEmpty = false
10 
11  def contains[B] (item: B) = this.item == item || next.contains(item) 
12}
13 
14case class EmptyBox[+A]() extends Box[A] {
15  def isEmpty = true
16 
17  def contains[B] (item: B) = false
18}

Interessant an diesem Code ist vor allem die Box.prepend-Methode: es ist nicht erlaubt, den Typ A als Typ des Parameters item in Box.prepend zu verwenden, da das eine kontravariante Position ist. Es ist aber erlaubt, den Typ-Parameter A als untere Schranke für die neue und invariante Variable B zu verwenden. Damit lässt sich der Parameter A kovariant annotieren, und folgender Code ist gültig:

1var apple = new Apple
2var orange = new Orange
3var apples = new BoxItem(apple, new EmptyBox)
4var fruits: Box[Fruit] = apples.prepend(orange)
5 
6if(fruits.contains(apple))
7  println("box contains the apple")

An diesem Beispiel wird deutlich, dass der Compiler auch in der Lage ist, den Typ des Teilausdrucks orange in apples.prepend(orange) zu inferieren als den kleinsten Typ, von dem Apple und Orange erben. Das heißt, das der Typ-Parameter B beim Aufruf der prepend-Methode nicht an den Typ Orange gebunden wird, sondern an den Typ Fruit. Damit liefert der Methodenaufruf ein Objekt vom Typ BoxItem[Fruit] zurück, was wiederum ein Subtyp von Box[Fruit] ist.

Alles in Allem sind als Typ-Parameter und die ko- und kontravariante Annotationen ein mächtiges Werkzeug, das gerade in der Implementierung von Collection-Frameworks nützlich ist, und auch Clients dieser Frameworks hilft, einerseits Typsicherheit zu garantieren, und andererseits ihre Absichten zu dokumentieren: Eine Liste kann als Liste von Fruit deklariert werden, und nicht mehr nur als eine Liste von irgendwelchen Objekten.

Typ-Parametrisierte Methoden

Typ-parametrisierte Methoden finden sich vor allem in Code-Bibliotheken, können aber auch in domänenspezifischem Code verwendet werden, um Zusammenhänge zwischen Parametern zu kommunizieren. Für eine Sortierungsmethode, die eine Sortier-Ordnung und eine Collection verlangt, sieht das zum Beispiel so aus:

1trait Ordering[T] {
2  def compare(x: T, y: T): Int
3}
4 
5abstract class Boxes {
6  def sort[A, B >: A](box: Box[A], order: Ordering[B])
7}

In diesem Beispiel wird durch Typ-Parameter festgehalten, dass die Ordnung für einen Supertyp B des Typ-Parameters A definiert sein muss. In vielen Fällen stellt sich aber auch die Frage, ob eine Methode, die Zusammenhänge zwischen ihren Parameter-Typen über Typ-Variablen herstellen muss, in eines ihrer Parameter verschoben werden sollte. Im sort-Beispiel ist eine naheliegende Lösung, die Methode der Klasse Box zuzuweisen. Vielleicht hat die typ-parametrisierte Methode zu viele Parameter, die zu Objekten zusammengefasst werden sollten. Falls weder das eine noch das andere zutrifft, bleiben Typ-Parameter in eine sinnvolle und mögliche Lösungsoption in diesem Anwendungsfall.

Varianzen Einführen

Wenn die Entscheidung für den Einsatz von Typ-Parametern gefallen ist, bleibt noch die Frage zu klären, ob auch Varianz-Annotationen eingeführt werden sollten. Bei der Klärung dieser Frage sind zwei Effekte zu berücksichtigen.

Der erste Effekt ist, dass Varianzen zusätzliche Einschränkungen bei der Entwicklung einer Klasse einführen. Kontravariante Typ-Parameter können beispielsweise nicht mehr einfach als Rückgabetyp von Methoden verwendet werden. Wenn eine Klasse noch in der frühen Entwicklungsphase steckt und vielen Änderungen und Refactorings unterliegt, können die durch Varianz-Annotationen eingeführten Einschränkungen behindernd wirken. Wenn die Schnittstelle einer Klasse stabilisiert ist, kann im Nachgang überprüft werden, ob das Einführen von Varianz-Annotationen an Typ-Parametern möglich ist.

Der zweite Effekt von Varianz-Annotationen ist, dass der Client-Code der generischen Klasse die Möglichkeit bekommt, die Klassenhierarchie der eingesetzten Typen auf die generische Klasse zu übertragen. Instanzen eines bestimmten generischen Typs können dadurch gemäß Subtyp-Polymorphismus an Variablen eines allgemeineren Typs zugewiesen werden. Das bedeutet, dass das Zurücknehmen einer einmal hinzugefügten Varianz-Annotation die Möglichkeiten der Clients einschränken würde – das Entfernen von Varianz-Annotationen ist also eine inkompatible Änderung. Andererseits werden durch das Einführen einer Varianz-Annotation die Möglichkeiten für Client-Code erweitert, das heißt, es handelt sich bei der Einführung von Varianz-Annotationen um eine Änderung, die mit bereits existierendem Client-Code kompatibel ist. Das bedeutet zusammengefasst, dass es einfacher sein kann, nachträglich und bei Bedarf Varianz-Annotationen einzuführen, als sie zunächst zu deklarieren und Gefahr zu laufen sie nachträglich entfernen zu müssen.

Das Problem mit den Namen

Phil Karlton stellte fest, dass Namensgebung eines der zwei einzigen schwierigen Probleme der Informatik ist. Typ-Parameter zu benennen wird zusätzlich durch Namenskonventionen erschwert, denn Style guides empfehlen meistens , einen einzelnen Großbuchstaben für Typ-Parameter zu verwenden. Dadurch können sie von Klassennamen, gewöhnlichen Variablen und Konstanten unterschieden werden, gleichzeitig verringert sich die Verständlichkeit des Codes aber deutlich – vor allem ab zwei und mehr Typ-Parametern; Klauseln der Form [E, S >: T] sind einfach schwer auf Anhieb zu verstehen, und schrecken eher ab. Auch läuft man bei Verwendung dieser Namenskonvention Gefahr, aus Nachlässigkeit aufeinanderfolgende Buchstabenfolgen zu wählen, die sehr beliebig wirken: z.B A, B, C; oder S, T, U; oder U, V, W. Ich habe in diesem Artikel exzessiven Gebrauch dieser Ein-Großbuchstaben-Konvention gemacht, und daher enthält dieser Artikel ausreichend (hoffentlich abschreckendes) Anschauungsmaterial.

In C# und C++ ist es üblich, für Typ-Parameter großgeschriebene Namen mit vorangestelltem T zu verwenden (z.B. TElement). In Scala sind auch großgeschriebene Namen erlaubt, was zu Verwechselungen mit Klassennamen führen kann. Bei Konzepten, die noch nicht allgemein etabliert sind (anders als z.B. E für den Element-Typ einer Collection), empfehle ich die Namenskonvention trotz Verwechslungsgefahr zu verwenden. Beim Lesen von Scala-Code muss man ohnehin im Hinterkopf zu behalten, dass Typ-Parameter wie Klassennamen aussehen können. Das Sortierungsbeispiel von oben mit ausgeschriebenen Typ-Parametern nach Scala-Konvention ist zwar länger, dafür aber auch verständlicher:

1trait Ordering[Type] {
2  def compare(x: Type, y: Type): Int
3}
4 
5abstract class Boxes {
6  def sort[Item, OrderedType >: Item](box: Box[Item], order: Ordering[OrderedType])
7}

Die gebräuchliche Ein-Großbuchstaben-Schreibweise für Typ-Parameter macht Code schwerer verständlich. Diese Konventionen sind bei der Entscheidung für oder gegen Typ-Parameter zu berücksichtigen. Für mich ist diese Konvention ein weiterer Grund, der bei dieser Abwägung gegen parametrisierte Klassen spricht.

Zusammenfassung

Die hier gegebene Antwort auf die Frage, wo Typ-Parameter und ko- und kontravariante Annotationen sinnvoll sind, basiert auf meinen ganz persönlichen Blickwinkel, den ich durch meine bisherige Programmier-Laufbahn gewonnen habe. Ich kann weder behaupten, dass meine Ansichten allgemeine Gültigkeit haben, noch kann ich vorhersehen, dass ich für immer bei diesen Ansichten bleiben werde. Vielleicht bringt mich ein Entwickler im nächsten Java-Projekt, oder das Einlesen ins nächste Scala-Framework zu neuen Einsichten, die meine bisherigen Erkenntnisse um neue Aspekte ergänzen.

Momentan bin ich der Meinung, dass Typ-Parameter wie auch ko- und kontravariante Annotationen theoretisch interessante Themen sind, die in der Praxis nur mit Vorsicht und nach reichlich Überlegung eingesetzt werden sollten. Wer im Eifer des Gefechts Typ-Parameter einführt, und diese auch gleich mit ko-/kontravarianten Annotationen versieht, kann schnell mehrere Tage Arbeit versenken um zur Erkenntnis zu gelangen, dass das geschaffene generische Konstrukt nicht funktioniert. Wer es geschafft hat, einen funktionierenden generischen Klassenverbund zu entwickeln, kann nach einigen Wochen oder Monaten feststellen, dass weder er selbst noch andere Entwickler dazu in der Lage sind, das funktionierende System zu verstehen, zu erweitern und zu debuggen.

Ich habe diese Erkenntnis durch eigene Erfahrung gewonnen: Ich habe mir selbst schon mindestens zwei mal durch Typ-Parameter die Lesbarkeit meiner Codebase verschlechtert, und mir gleichzeitig ein so enges Korsett programmiert, dass ich mich nur noch durch ein Typ-Parameter-Kahlschlag zu helfen wusste. Aktuelle Forschungsergebnisse (Full Text paywalled) stützen die Wahrnehmung, dass komplexe Typsysteme nicht nur positive Effekte haben. Wie habt ihr Typ-Parameter verwendet? Wo fandet ihr den Einsatz von Ko- und Kontravarianten Typ-Parametern sinnvoll? Wo nicht? Schreibt mir eure Erfahrungen und eure Meinung, ich bin auf euren Input sehr gespannt.

Die Ergebnisse in Kurzform

Hier sind die Ergebnisse aus allen drei 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.

Einführen von Typ-Parametern

• Typ-Parameter sind bei der Entwicklung von Basis-Frameworks und APIs hilfreich (z.b. in Collection APIs und Concurrency Frameworks).
• Eigene Klassen mit Typ-Parameter sind schwierig zu programmieren, der entstehende Code wird oft schwer verständlich. Ich empfehle daher, sie zu vermeiden.
• Die Ko-/Kontravarianz-Regeln sind schwierig zu verstehen und einzuhalten, und der Nutzen ist oft gering. Eigene typparametrisierte Klassen sollten zunächst als invariant entwickelt werden, und bei Bedarf modifiziert werden.
• Verwende in Scala großgeschriebene Bezeichner auch für Typ-Parameter, und behalte im Hinterkopf, dass Typ-Parameter wie Klassen aussehen.