Kann Java abstrakte Typ-Member simulieren?

Scala kennt von Anfang an abstrakte Typ-Member als Alternative zu Generics. Eine Übersicht findet sich hier, und ich habe auch schon damit herumgespielt. Die Kurzfassung: Während generische Klassen ihre Parameter nach außen bekanntmachen, und diese überall mit „durchgeschleift“ werden (müssen), werden abstrakte Typ-Member eher als eine Art Implementierungsdetail angesehen und somit sozusagen als „innere Angelegenheit“ behandelt.

Und gestern abend dämmerte mir, das Java zumindest prinzipiell etwas Ähnliches erlaubt – und nicht erst seit Java 8. Ich habe keine Ahnung, wie weit diese „Technik“ trägt – und ganz sicher ist sie nicht so flexibel wie Scalas Ansatz, der ja „dafür gebaut“ worden ist. Aber ich werde gleich zwei Instanzen mit unterschiedlichen Member-Typen in ein und dieselbe Liste packen – ohne Wildcards, Raw-Types, Casts oder Compiler-Warnungen. Sozusagen „innen generisch, außen nicht“ – ähnlich wie bei abstrakten Typ-Membern:

public class Outer<T> {

    public class Inner {
        public final T t;

        public Inner(T t) {
            this.t = t;
        }
    }

    public static void main(String[] args) {
        List<Outer.Inner> list = new ArrayList<>();
        list.add(new Outer<String>().new Inner("blubb"));
        list.add(new Outer<Integer>().new Inner(42));
        for(Outer.Inner inner : list) {
            System.out.println(inner.t);
        }
    }
}

Tadaaaaa! Das ist also der Trick: Innere Klassen, die die Generics von ihren äußeren Klassen „benutzen“. Übrigens: Wer solche seltsamen Konstruktoraufrufe wie im Beispielcode noch nicht gesehen hat, ist nicht allein – ich kannte die Syntax auch nicht, bis ich für die „Java Programmer“-Zertifizierung von Oracle lernen musste (daher auch die „Inspiration“ für diesen etwas kranken Code). Ich muss erst einmal sehen, in wie weit dieses Konstrukt überhaupt sinnvoll ist, und wie groß die Beschränkung durch die erzwungene „Innerklassigkeit“ in der Praxis ist. Falls ihr auch damit herumspielt, würden mich natürlich die Ergebnisse eurer Experimente brennend interessieren.

[Update]
Ich bin darauf hingeweisen worden, dass der „volle“ Typ meiner Liste eigentlich etwas wie List<Outer<String>.Inner> sein müsste, ich hier also doch mit Raw-Types arbeite (auch wenn ich keine Warnung sehe). Das macht das Ganze natürlich hinsichtlich der Typsicherheit obsolet, weil damit kein Unterschied zu einer normalen generischen Top-Level-Klasse, die als Raw-Typ verwendet wird, besteht. Schade…

Werbeanzeigen

Abstrakte Kunst

Heute möchte ich über Abstraktion mit Traits sprechen, und auch die Verwendung von abstrakten Type-Members, die ich schon hier vorgestellt hatte, mit einem (hoffentlich) etwas geeigneterem Beispiel vertiefen.

Angenommen, man hat die Aufgabe, Prim’s Algorithmus zur Berechnung von minimalen Spannbäumen in ungerichteten Graphen zu implementieren. Aber sollte man den Algorithmus fest verdrahten? Es kommt natürlich auf den jeweiligen Kontext an, aber wenn nichts dagegen spricht, kann es nicht schaden, auch Platz für andere Implementierungen zu lassen, etwa Kruskal’s Algorithmus.

Nun stellt sich die Frage, wie wir unseren Graph repräsentieren wollen. Haben wir eine eigene Graph-Klasse? Oder einfach eine Adjazenz-Matrix? Wenn ja, sollen wir Arrays verwenden oder doch lieber eine Implementierung für schwach besetzte Matritzen? Nun, die eleganteste (wenn auch nicht performanteste) Antwort darauf ist: Es sollte uns völlig egal sein! Und weil man es meiner Meinung nach nicht oft genug wiederholen kann, sage ich es auch nochmal: Es sollte uns völlig egal sein! Wenn wir ein paar grundlegende Operationen auf unserem Graph ausführen können, reicht das für unseren und – potentiell – viele andere Algorithmen aus. Wir abstrahieren!

Bauen wir uns ein Trait, das Typen für einen Graphen sowie seine Knoten und Kanten definiert, und dazu ein paar nützliche Operationen:

//Scala 2.8
import scala.collection.immutable._

trait GraphAdapter {
    type G; //Graph
    type V; //Knoten (Vertex)
    type E; //Kante (Edge)
    def vertexList(g:G):Traversable[V]
    def edges(vertex:V, g:G):Traversable[E]
    def vertices(edge:E, g:G):(V,V)
    def getEdgeOrdering(g:G):Ordering[E]
}

Die Typen habe ich als abstrakte Type-Members repräsentiert, obwohl auch Generics möglich gewesen wären. Aber GraphAdapter soll ja gerade die Abhängigkeit von einer bestimmten Graph-Implentierung beseitigen, insofern schien es mir aus „philosophischer Sicht“ nur konsequent, die Typen auch zu „verstecken“. Die aufgelisteten Operationen sind nicht wirklich überraschend, außer vielleicht die letzte: Ordering ist die Scala-Spezialisierung von Java’s Comparator. Für die Berechnung des minimalen Spannbaums braucht man nämlich gar nicht die konkreten Abstände der Knoten, sondern es reicht schon aus, wenn man zwei beliebige Kanten miteinander vergleichen kann (totale Ordnung). Die Rückgabetypen wurden möglichst allgemein gehalten: Statt Set, List u.s.w. wurde deshalb das Supertrait Traversable verwendet.

Wie sieht nun eine konkrete Implementierung aus? Hier eine ziemlich krude Version für Adjazenz-Matrizen:

trait AdjacenceMatrix extends GraphAdapter {
    type G = Array[Array[Option[Int]]]
    type V = Int
    type E = (Int, Int)
    def vertexList(g:G):Traversable[V] = (0 until g.length).force
    def edges(v:V, g:G):Traversable[E] =
       g(v).zipWithIndex.filter(_._1 != None).toList.map(w => (v min w._2, v max w._2))
    def vertices(edge:E, g:G):(V,V) = edge
    def getEdgeOrdering(g:G) = new Ordering[E] {
       def compare(x:E, y:E) = {
           g(x._1)(x._2).get - g(y._1)(y._2).get
       }
    }
}

Knoten sind einfach Ints, Kanten sind Tupel zweier Knoten. Die zweidimensionale Matrix hat allerdings nicht Int als Elementtyp, sondern Option[Int]. Dadurch können „nicht vorhandene Verbindungen“ durch None gekennzeichnet werden, so dass man nicht auf gefährliche „magische Werte“ (wie -1 oder Integer.MIN_VALUE) zurückgreifen muss. Die edges-Implementierung sieht komplizierter aus, als sie eigentlich ist, was der wenig objektorientierten „low-level“ Repräsentation unseres Graphen geschuldet ist.
Die hier verwendete Implementierung ist ziemlich fragil, denn es wird einfach vorausgesetzt, dass die Matrix quadratisch und symmetrisch ist. Für unser Beispiel ist das nicht weiter schlimm, trotzdem sollte man das für ernsthafte Anwendungen nicht unbedingt nachahmen.

Nun schreiben wir ein Trait, das für einen gegebenen Graph-Adapter den Spannbaum berechnet. Damit wir schön abstrakt bleiben, wenn wir den Algorithmus einmal austauschen wollen, haben wir auch ein „abstraktes“ Supertrait:

trait MinimalSpanningTree  {
    self:GraphAdapter =>
    def minimalSpanningTree(g:G):Traversable[E]
}

trait PrimMST extends MinimalSpanningTree {
    self:GraphAdapter =>
    def minimalSpanningTree(g:G):Traversable[E] = if(vertexList(g).isEmpty) List[E]() else {
        implicit val edgeOrder:Ordering[E] = getEdgeOrdering(g)
        val vList = vertexList(g)
        val edgeSet = vList.foldLeft(TreeSet[E]())((e,v) => e ++ edges(v,g))
        def loop(vIn:Set[V], vOut:Set[V], mst:Set[E], eOut:Set[E]):Set[E] =
        if (vOut.isEmpty) mst else {
            val newE = eOut.find(e => vIn.contains(vertices(e,g)._1) ||
                vIn.contains(vertices(e,g)._2)).getOrElse(error("disconnected graph"))
            val newV = if (vIn.contains(vertices(newE,g)._1)) vertices(newE,g)._2
                       else vertices(newE,g)._1
            val new_vOut = vOut - newV
            loop(vIn + newV, new_vOut, mst + newE, eOut.filter(e =>
                new_vOut.contains(vertices(e,g)._1) || new_vOut.contains(vertices(e,g)._2)))
        }
        loop(Set(vList.head), Set[V]() ++ vList.tail, Set[E](), edgeSet)
    }
}

Auf die Details des Algorithmus will ich gar nicht weiter eingehen – einen Schönheitspreis wird meine Implementierung bestimmt nicht gewinnen. Die Grundidee ist recht einfach und wird im Wikipedia-Artikel sehr anschaulich dargestellt. Wichtig ist in unserem Beispiel der „Selbsttyp“, das self:GraphAdapter => am Anfang: Damit sagt man dem Trait, dass es nur zu einem GraphAdapter „hinzugemixt“ werden darf. Theoretisch könnte man stattdessen auch Vererbung verwenden, aber das wäre semantisch falsch: Der Algorithmus ist kein GraphAdapter, er arbeitet auf einem. Entsprechend werden die GraphAdapter-Operationen auch nicht implementiert, sondern nur benutzt.

Wofür nun der ganze Aufwand? Wir haben damit den Grundstein gelegt für einen kleinen Baukasten, mit dem man nach Lust und Laune Graphen und Algorithmen zusammenstöpseln kann, und es dann „einfach funktioniert“:

val calc = new AdjacenceMatrix with PrimMST 
val data = Array(Array(None,    Some(2), Some(2), Some(4)),
                 Array(Some(2), None,    Some(3), None ),
                 Array(Some(2), Some(3), None,    Some(5)),
                 Array(Some(4), None,    Some(5), None))
println(calc.minimalSpanningTree(data))
//--> Set((0,2), (1,2), (0,3))

Ich bin sicher nicht der einzige, dem das erst einmal „ein bisschen zu magisch“ vorkommt. Aber gehen wir in uns: Hatten wir nicht alle schon Fälle, wo wir uns geärgert haben, dass diese verdammt komplizierte und clevere Methode, die unser Kollege geschrieben hat, nur mit ints und nicht mit doubles arbeitet? Oder dass diese nützliche Bibliothek leider nur ihre eigenen Datentypen verwendet, die man erst einmal mühselig „von Hand“ füllen muss? Hatten wir noch nie Schmerzen bei einem Refactoring, bei dem ein grundlegender Datentyp des Systems geändert werden musste, und damit alles und jedes, was mit ihm irgendwie in Verbindung stand? In solchen und ähnlichen Situationen hätte uns eine abstraktere Implementierung das Leben sehr erleichtert, und Scala hätte uns wiederum bei der Implementierung dieser Abstraktion sehr geholfen.

Unser Beispiel ist auch in anderer Hinsicht interessant: Es wurden keine Klassen verwendet, nur Traits. Sicher, ich hätte z.B. aus AdjacenceMatrix auch eine abstrakte Klasse machen können. Aber Traits erlauben durch die „Zusammensteckbarkeit“ (a.k.a. Mixin-Komposition) eine erstaunliche Flexibilität – etwas, mit dem man als „einfach-vererbender“ Java-Programmierer erst einmal lernen muss umzugehen. Wenn man keine Konstruktor-Argumente übergeben muss, spricht in Scala kaum etwas dagegen, ein Trait zu verwenden.

Unser Beispiel ist nur eine von den vielen Abstraktions-Möglichkeiten, die Scala bietet. Wer Scala nur als „besseres Java“ verwendet, verpasst solche Chancen zu höherer Abstraktion. Natürlich sollte man nicht den Fehler machen, auf Teufel komm raus bis in die Stratosphäre hinein zu abstrahieren, denn wie heißt es so schön: Das Gegenteil eines Fehlers ist wieder ein Fehler. Aber da, wo Abstraktion wirklich gebraucht wird, kann sie unheimlich nützlich sein.

Ich hoffe nur, dass meine Ausführungen jetzt nicht zu abstrakt waren… 😀

Auf die Bäume, ihr Affen!

Heute möchte ich abstrakte Type-Members vorstellen, die eine ähnliche Funktionalität wie Generics bieten. Auf die Frage, warum es in Scala zwei Wege gibt, über Typen zu abstrahieren, habe ich bisher nur relativ schwammige Antworten gehört:

Bill Venners: In Scala, a type can be a member of another type, just as methods and fields can be members of a type. And in Scala those type members can be abstract, like methods can be abstract in Java. Is there not some overlap between abstract type members and generic type parameters? Why does Scala have both? And what do abstract types give you beyond what the generics give you?

Martin Odersky: Abstract types give you some things beyond what generics give you, but let me first state a somewhat general principle. There have always been two notions of abstraction: parameterization and abstract members. In Java you also have both, but it depends on what you are abstracting over. In Java you have abstract methods, but you can’t pass a method as a parameter. You don’t have abstract fields, but you can pass a value as a parameter. And similarly you don’t have abstract type members, but you can specify a type as a parameter. So in Java you also have all three of these, but there’s a distinction about what abstraction principle you can use for what kinds of things. And you could argue that this distinction is fairly arbitrary.

What we did in Scala was try to be more complete and orthogonal. We decided to have the same construction principles for all three sorts of members. So you can have abstract fields as well as value parameters. You can pass methods (or „functions“) as parameters, or you can abstract over them. You can specify types as parameters, or you can abstract over them. And what we get conceptually is that we can model one in terms of the other. At least in principle, we can express every sort of parameterization as a form of object-oriented abstraction. So in a sense you could say Scala is a more orthogonal and complete language.

Now you could say, well I could do the same thing with parameterization [Generics]. And indeed you can. You could parameterize class Animal with the kind of food it eats. But in practice, when you do that with many different things, it leads to an explosion of parameters, and usually, what’s more, in bounds of parameters. At the 1998 ECOOP, Kim Bruce, Phil Wadler, and I had a paper where we showed that as you increase the number of things you don’t know, the typical program will grow quadratically. So there are very good reasons not to do parameters, but to have these abstract members, because they don’t give you this quadratic blow up.

(Artima Interview: The Purpose of Scala’s Type System)

Je nach Situation ist also die eine oder andere Formulierung bequemer. Ich will nun keine tiefschürfende Theorie betreiben, sondern einfach versuchen, einer typischen Generics-Implementierung eine Version mit abstrakten Type-Members gegenüberzustellen.

Als „einfaches“ Beispiel habe ich mir binäre Bäume herausgepickt – natürlich die immutable Version. Im Nachhinein muss ich sagen, dass auch diese rudimentäre Implementierung mit Generics so ihre Tücken hat, und der Code sicher noch um einiges verbessert werden könnte. Beginnen wir mit einem Trait für unseren Baum:

trait BinTree[T] {
  val isEmpty:Boolean
  def add(t:T):BinTree[T]
  def contains(t:T):Boolean
  def toList:List[T]
}

Die zugehörige Implementierung habe ich im Begleit-Objekt versteckt:

//Scala 2.8
object BinTree {
  def apply[T]()(implicit ord: Ordering[T]):BinTree[T] = new BinTree[T] {
    val isEmpty = true
    def add(t:T):BinTree[T] = Node[T](t,this,this)(ord)
    def contains(t:T) = false
    def toList = Nil
  }

  private case class Node[U](value:U, left:BinTree[U], right:BinTree[U])
      (implicit val ord: Ordering[U]) extends BinTree[U] {

    val isEmpty = true

    def add(u:U):BinTree[U] =
      if (u < value) Node(value, left.add(u), right)
      else if (u > value) Node(value, left,  right.add(u))
      else this

    def contains(u:U):Boolean = u == value ||
      {if (u < value) left.contains(u) else right.contains(u)}

    def toList:List[U] = left.toList ::: value :: right.toList
  }
}

In der apply-Methode hätte ich gern darauf verzichtet, jedesmal eine Implementierung für einen „leeren“ Knoten zu basteln, und lieber auf ein Standard-Objekt analog zu Nil oder None zurückgegriffen, aber irgendwie wollte der übliche Nothing-Trick nicht so flutschen – für Verbesserungsvorschläge wäre ich dankbar. Die toList-Methode ist alles andere als performant, das dauernde ::: (append) sollte man tunlichst vermeiden. Die Übergabe eines impliziten Parameters für eine „Ordering“ ist neu in Scala 2.8 – ohne dieses zusätzliche Argument könnte ich nicht einfach < und > verwenden.

Ein kleiner Test:

    var tree = BinTree[Int]()
    tree = tree.add(3);  tree = tree.add(2); tree = tree.add(5) 
    tree = tree.add(1);  tree = tree.add(6);  tree = tree.add(1)
    tree = tree.add(4)
    println(tree.contains(4))
    println(tree.contains(0))
    println(tree.toList)

//--> true
//--> false
//--> List(1, 2, 3, 4, 5, 6) 

Schaut soweit erst einmal gut aus. Nun zur Variante mit den abstrakten Type-Members. Zur besseren Unterscheidung habe ich an die entsprechenden Namen jeweils „AT“ angehängt. Zuerst wieder das Trait:

trait BinTreeAT {
  self =>
  type T
  val isEmpty:Boolean
  def add(t:T)(implicit ord: Ordering[T]):BinTreeAT{ type T = self.T}
  def contains(t:T)(implicit ord: Ordering[T]):Boolean
  def toList:List[T]
}

Zuerst fällt das self => auf. In dieser Situation wird es nur als Hilfsmittel benutzt, um auf die aktuelle Instanz zu verweisen, es ist also einfach ein Alias für „this“. Danach kommt der abstrakte Type-Member T. An dieser Stelle könnten wir noch Bounds angeben, also z.B. dass T von irgendeiner Klasse abgeleitet sein muss u.s.w., aber unser Container soll ja beliebige Typen aufnehmen können. An den Methoden add und contains fällt auf, dass sie jetzt Ordering als impliziten Parameter übergeben bekommen. Da der Typ T nicht mehr generisch ist, gibt es auch keine Möglichkeit, ihn in einer Unterklasse als implizites Konstruktorargument zu übergeben (aber wahrscheinlich gibt es noch andere Möglichkeiten, die Übergabe zu realisieren). Dann besitzt add den seltsamen Rückgabetyp BinTreeAT{ type T = self.T}. An dieser Stelle habe ich eine Weile geknobelt, denn das einfache BinTreeAT hat sich als zu „unpräzise“ erwiesen: Wenn ich einen BinTreeAT für Ints erzeugt hatte, ging sonst nach einem add die „Spezialisierung“ für Int verloren, d.h. der Compiler ließ auf dem Rückgabewert z.B. kein weiteres add(Int) zu.

Nun die „konkreten“ Klassen:

//Scala 2.8
object BinTreeAT {
  def apply[U]()(implicit ord: Ordering[U]):BinTreeAT{ type T = U } = new BinTreeAT {
    self => 
    type T = U
    val isEmpty = true

    def add(t:T)(implicit ord: Ordering[T]):BinTreeAT{ type T = self.T} = new NodeAT{
       type T = self.T
        val value = t
        val left = self
        val right = self
    }

    def contains(t:T)(implicit ord: Ordering[T]) = false

    def toList = Nil
  }

  abstract class NodeAT extends BinTreeAT {
    self =>
    val value:T
    val left:BinTreeAT{ type T = self.T}
    val right:BinTreeAT{ type T = self.T}
    val isEmpty = true

    def add(t:T)(implicit ord: Ordering[T]):BinTreeAT{ type T = self.T} =
      if (t < value) new NodeAT{
        type T = self.T
        val value = self.value
        val left = self.left.add(t)
        val right = self.right
      }
      else if (t > value) new NodeAT{
        type T = self.T
        val value = self.value
        val left = self.left
        val right = self.right.add(t)
      }
      else this
  
    def contains(t:T)(implicit ord: Ordering[T]):Boolean = t == value ||
      {if (t < value) left.contains(t) else right.contains(t)}
    
    def toList:List[T] = left.toList ::: value :: right.toList
  }
}

Alles ist etwas „länglicher“ geworden, wir finden den schon erwähnten self => Trick und den „spezialisierten“ Rückgabewert – diesmal BinTreeAT{ type T = self.T} – wieder. Auch die NodeAT-Klasse ist jetzt abstrakt, und man baut sich daraus die konkreten Versionen „on the fly“ zusammen. Es war relativ schwierig, die Typen konsistent hinzubekommen. Gewöhnungsbedürftig für den Javaner dürfte sein, dass Typen hier wirklich wie Member-Variablen angesprochen werden, und dass man immer im Auge behalten muss, was T im aktuellen Kontext (sprich:Scope) gerade bedeutet. Im Nachhinein sieht das Ganze gar nicht so unlogisch aus, aber es war doch eine ziemliche Frickelei für mich als „abstrakten Type-Member-Neuling“. Umso größer die Freude, dass es auch wirklich (in Scala 2.8) funktioniert.

Hat sich nun der Aufwand „gelohnt“? Ganz ehrlich: Containerklassen sind bestimmt nicht das geeignete Anwendungsgebiet für abstrakte Type-Members. Ich denke, es gibt einen „philosophischen“ Unterschied zwischen den beiden Konzepten: Generics machen den parametrischen Typ sehr explizit zum Teil ihrer Schnittstelle: Der Typ ist etwas, das einen Teil des „Wesens“ der generischen Klasse ausmacht. Collections sind ein typisches Beispiel, oft interessiert uns der Typ der Elemente viel mehr als der Typ der Collection. Beispielsweise ist mir eigentlich ziemlich egal, ob ich nun eine Liste oder ein Set von Ints summiere. Abstrakte Type-Members „verstecken“ dagegen den zu parametrisierenden Typ: Er mag wichtig sein, ein unverzichtbarer Teil, um das Ganze ordentlich zusammenzustecken zu können, aber er ist hier eben kein Teil des „Wesens“, sondern mehr „Kontext“. Ich könnte mir z.B. vorstellen, dass für die Implementierung eines A*-Algorithmus die Repräsentation des zugrundeliegenden Graphen zwar wichtig ist, aber nicht in dem Sinne wie der Element-Typ einer Collection, und dass deshalb hier abstrakte Type-Members besser geeignet sind.

Wie ich schon zugegeben habe, bin ich mit abstrakten Type-Members noch lange nicht auf du und du, aber ich hoffe, dass ich ein wenig Appetit gemacht habe. Wer sich bessere Beispiele und exaktere Aussagen wünscht, sei auf A Tour of Scala, Scala-Overview, Kapitel 5.2 oder Programming Scala (D. Wampler, A. Payne) verwiesen.

Noch ein paar Worte in eigener Sache. Das Blog macht mir Spaß, auch wenn ich immer mehr nachdenken muss, was ich eigentlich schreiben soll: Nicht etwa, dass es über Scala nicht genügend interessante Dinge zu berichten gäbe, sondern weil ich merke, dass ich bei vielen Fragen noch ziemlich an der Oberfläche kratze. Und vielleicht stellt sich bei mir auch schon die berüchtigte Betriebsblindheit ein, so dass ich Dinge als „normal“ betrachte, die vielleicht für den Scala-Neuling durchaus interessant sein können. Ich würde mich deshalb nicht nur über Feedback zu den aktuellen Beiträgen freuen, sondern auch darüber, welche Beiträge ihr hier zukünftig gern sehen würdet. Andererseits gibt es natürlich auch Sachen, die sich besser „interaktiv“ lösen lassen, etwa im Scala-Forum, das ich auch regelmäßig besuche. Wie auch immer, lasst mal etwas von euch hören 😀