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

5 Kommentare

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 MusterAnwendungsfall 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:

String[] strings = new String[1];
Object[] objects = strings;
objects[0] = 1;
strings[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.

abstract class Box[+A] {
  def isEmpty: Boolean
 
  def contains[B] (item: B): Boolean
  def prepend[B <: A](item: B): BoxItem[B] = new BoxItem[B](item, this)
}
 
case class BoxItem[+A](item: A, next: Box[A]) extends Box[A] {
  def isEmpty = false
 
  def contains[B] (item: B) = this.item == item || next.contains(item) 
}
 
case class EmptyBox[+A]() extends Box[A] {
  def isEmpty = true
 
  def contains[B] (item: B) = false
}

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:

var apple = new Apple
var orange = new Orange
var apples = new BoxItem(apple, new EmptyBox)
var fruits: Box[Fruit] = apples.prepend(orange)
 
if(fruits.contains(apple))
  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:

trait Ordering[T] {
  def compare(x: T, y: T): Int
}
 
abstract class Boxes {
  def sort[A, B >: A](box: Box[A], order: Ordering[B])
}

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:

trait Ordering[Type] {
  def compare(x: Type, y: Type): Int
}
 
abstract class Boxes {
  def sort[Item, OrderedType >: Item](box: Box[Item], order: Ordering[OrderedType])
}

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.

Kommentare

  • Heiko Seeberger

    17. April 2015 von Heiko Seeberger

    Ich finde Typparameter bzw. parametric polymorphism unersetzlich, viel wichtiger als Vererbung. Im Zusammenspiel mit Type Inference sehe ich auch kaum Probleme bei der Verwendung; das Schreiben von parametrisierten Libraries hingegen ist wegen der Abstraktion zwangsläufig schwieriger, mit ein wenig Übung aber auch zu meistern.

    Varianz hingegen habe ich in meinem Code eher weniger verwendet. Dennoch bin ich heilfroh, dass Scala Variance Annotations anbietet, denn ich seltenen Fällen geht es nicht ohne.

    Was siehst Du denn als Alternative zu Typparametern? Zurück zu unityped Collections wie vor Java 5?

    • Andreas Schroeder

      17. April 2015 von Andreas Schroeder

      Hallo Heiko,

      freut mich dass Du meinen Artikel gelesen hast, und vielen Dank für Dein Feedback. Wenn Du ein paar Zeilen open-source- und domänenspezifischen Code hast, der Typ-Parameter und Varianzen einsetzt, und von dem Du sagst er ist elegant und gut wartbar, dann würde ich den Code sehr gerne lesen. Vielleicht fehlt mir bisher einfach nur ein gutes positiv-Beispiel.

      Wodurch generische Typ-Parameter zu ersetzen wären kann ich nicht beantworten – ich habe mich bisher nicht mit Programmiersprachdesign beschäftigt, und habe großen Respekt vor den Leuten, die sich dran wagen. Zurück zu einer Welt ohne Generics, ohne parametrisierten Collections würde ich definitiv nicht wollen. Dafür sind sie viel zu nützlich, auch um die Lesbarkeit von Code zu erhöhen. Gleichzeitig bin ich der Meinung, dass Klassen oft zu leichtfertig parametrisiert werden, ohne über die Konsequenzen nachzudenken – einfach, weil es geht und vielleicht auch weil man auch selber gerne mal coolen Code schreiben möchte. Ich denke meist reicht es, generische Klassen aus Frameworks zu verwenden, die Typ-Parameter sinnvoll zu belegen, und darauf zu verzichten, selbst generische Klassen zu schreiben. Ich habe zwar auch schon eine codebase gesehen, die durch Schachtelung von Maps, Lists und Sets recht unleserlich gemacht wurde (Map of List of Map …), aber mit jedem Sprachfeature lässt sich auch unleserlicher Code schreiben. Ganz ohne Typen komme ich aber auch gut klar, wenn ich muss. In Sprachen ganz ohne statische Typchecks werden für mich Unit-Tests und Tests allgemein deutlich wichtiger.

      Kurz zusammengefasst: nein, zurück zu einer Welt ohne generische Typen möchte ich nicht. Gleichzeitig glaube ich, dass es besonders wichtig ist vorsichtig und planvoll vorzugehen wenn man eigene Typ-Parameter einführt.

      • Heiko Seeberger

        17. April 2015 von Heiko Seeberger

        Hallo Andreas,

        Deinen Artikel habe ich sehr gerne gelesen!

        Wir müssen bei der Diskussion ein bisschen aufpassen, nicht in das Thema statische vs. dynamische Typisierung bzw. Typen vs. keine Typen abzudriften. Lass uns also eine statisch typisierte Sprache wie Java, Scala, Go (hat gar keine Generics), Rust oder Haskell voraussetzen.

        Wir sind uns einig, dass die Einführung von Typparametern grundsätzlich die Komplexität erhöht, ganz einfach weil „etwas dazukommt“. Daher sollte man Typparameter natürlich nur da einsetzen, wo sie sinnvoll sind, weil sie durch die von ihnen angebotene Abstraktion im Endeffekt die Komplexität reduzieren. Collection Libraries sind hierfür ein gutes Beispiel, weil un(i)typisierte Collections (wie in Java bis einschließlich 1.4) in statisch typisierten Sprachen viel schwieriger (Typ-Checks, Typ-Casts, Fehler!, etc.) zu verwenden sind, als die zusätzlichen Typargumente.

        Die von Dir genannten Motivationen „ohne über die Konsequenzen nachdenken“ und „coolen Code schreiben“ gehören für mich nicht zu sinnvollen Einsatzfeldern, von Experimenten und Lernen einmal abgesehen. Aber diese gehören meiner Meinung nach sowieso nicht zum ernsthaften Programmieren.

        Lange Rede, kurzer Sinn: Ich denke, dass Typparameter eine sehr nützliche Bereicherung darstellen, die wie jedes andere Sprachfeature bewusst eingesetzt werden müssen.

        Heiko

        • Andreas Schroeder

          20. April 2015 von Andreas Schroeder

          Hallo Heiko,

          Die Diskussion über statisch typisierte Sprachen versus Sprachen ohne statisches Typsystem brauchen wir hier nicht führen, da gebe ich Dir absolut Recht.

          Was Dein Standpunkt zu parametrisierten Typen betrifft: Ich denke dass wir da nicht weit voneinander entfernt sind. Typparameter und parametrisierten Typen finde ich auch sehr nützlich. Und ich finde auch, dass man sie bewusst einsetzen muss, wie jedes andere Sprachfeature auch. Aber ich finde, dass die Entscheidung für oder gegen den Einsatz gerade bei Typparametern besonders überlegt werden sollte. Einerseits erhöht sich durch die Einführung von Typparametern die Komplexität der Codebase, andererseits wird durch den generischen Programmierstil, der damit einhergeht, von Lesern der Codebase ein spürbar höheres Abstraktionsvermögen verlangt. Meiner Meinung nach geht es bei der Entscheidung für oder gegen Typparameter letztlich um die Frage, ob eine verständlichere und elegantere Lösung dadurch entsteht, d.h. ob ich dem „Keep it Simple“-Prinzip folge. Dass man diese Entscheidung nicht leichtfertig treffen sollte ist der Punkt, den ich in diesem Post besonders betonen wollte.

          Noch eine Nebenbemerkung: mir geht es nicht um die Entscheidung für oder gegen den Einsatz bereits vorhandener parametrisierter Typen in z.B. Collection oder Concurrency Libraries. Ich denke wenn eine Library die Möglichkeit bietet, Typparameter zu binden, dann sollte man diese Möglichkeit nutzen. Der Einsatz generischer Typen ist in diesen Bibliotheken wohl überlegt worden. Darüber hinaus vermute ich dass die Einführung von Typparametern in einer Sprache vor allem durch den Mehrwert, den sie in diesen Libraries erzeugen, motiviert ist. Da wäre es schade, keinen Nutzen daraus zu ziehen.

  • Heiko Seeberger

    23. April 2015 von Heiko Seeberger

    Hallo Andreas,

    „Keep it simple“ unterstütze ich voll und ganz!

    Allerdings hat simple nichts mit easy zu tun (siehe Rich Hickey’s Simple Made Easy, http://www.infoq.com/presentations/Simple-Made-Easy), sodass Code mit Typparametern für das ungeübte Auge schon schwerer zu verstehen sein kann. Wichtig ist jedoch, dass der Code in seiner Gesamtheit simpler ist, und das schließt auch die Nutzung ein. In diesem Sinne möchte ich auf den aktuellen Blogpost Deines Kollegen Sven (https://blog.codecentric.de/2015/04/cascaded-builder-pattern-in-java/) verweisen, in dem sehr intensiv mit Typparametern gearbeitet wird, um eine Library bereitzustellen, die sehr einfach (jetzt mische ich auch simpel und einfach 😉 zu benutzen ist.

    Heiko

Kommentieren

Deine E-Mail-Adresse wird nicht veröffentlicht. Erforderliche Felder sind mit * markiert.