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 😀

Advertisements

2 Gedanken zu “Auf die Bäume, ihr Affen!

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