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… 😀

Advertisements

3 Gedanken zu “Abstrakte Kunst

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