Sonntag, 31. Juli 2011

Scala Einführung - Teil 3

Nachdem bisher hauptsächlich die von Java vertrauten, objektorientierten Konzepte betrachtet wurden, widmet sich dieser Post der funktionalen Programmierung und deren Umsetzung in Scala.

Funktionale Programmierung


Funktionale Programmierung ist ein Programmierstil, bei dem Programme aus einer Komposition von Funktionen bestehen. Die funktionale Programmierung leitet sich vom Lambda-Kalkül [1] ab, einer formalen Sprache zur Untersuchung von mathematischen Funktionen, die von Alonzo Church und Stephen Kleene in den 1930er Jahren entwickelt wurde, noch bevor es die ersten Computer gab.

Im Gegensatz zur imperativen Programmierung, die sich an der Von-Neumann-Architektur [2] orientiert und bei der Programme aus Abfolgen von Rechenschritten bestehen, beschreiben funktionale Programme intuitiv betrachtet, was berechnet wird, statt wie. Funktionen und Variablen werden dabei oft im mathematischen Sinne verstanden. Das heißt, das Ergebnis einer Funktion hängt ausschließlich von den übergebenen Argumenten ab und nicht von irgend einer Art von Zustand. Und Variablen sind unveränderliche Definitionen, denen man keine neuen Werte zuweisen kann.

Diese Auslegungen haben den Vorteil, dass man beim Nachvollziehen des Programmablaufs keinen sich ändernden Zustand im Kopf behalten muss, und man beim Schreiben des Programms nicht darauf achten muss, ob an irgendeiner Stelle des Programms Zustände "unerlaubt" geändert werden. Dies bietet auch Vorteile bei nebenläufigen Programmen, da es keinen veränderlichen Zustand gibt, der synchronisiert werden muss.

Funktionale Programmierung in Scala


Scala ist keine rein funktionale Programmiersprache, wie aus den vorangegangenen Posts schon ersichtlich geworden ist. Es erzwingt also keinen funktionalen Programmierstil, unterstützt diesen aber. Zu den wichtigsten Merkmalen der funktionalen Programmierung gehören Funktionen höherer Ordnung. Dies sind Funktionen, die andere Funktionen als Parameter erwarten oder als Ergebnis zurück liefern. Dies wird dadurch ermöglicht, dass Funktionen schlicht Objekte sind, die als Argumente übergeben werden können, wie alle anderen auch.

Darüber hinaus bietet Scala unveränderliche Variablen mit dem Schlüsselwort val, unveränderliche Methodenparameter und verschiedene unveränderliche Datenstrukturen wie Listen, Sets und Maps.

Grundlagen der funktionalen Programmierung


Da funktionale Programme keine veränderlichen Variablen kennen, kann es in ihnen keine herkömmlichen Schleifen geben. Stattdessen nutzt man Rekursion. Im folgenden Beispiel wird gezeigt, wie man per Rekursion die Zahlen in einem ganzzahligen Intervall aufaddieren kann 1 und zum Vergleich ist zuerst eine imperative Implementierung angegeben.

def sumImperative(a: Int, b: Int): Int = {
  var sum = 0
  for(i <- a to b) {
    sum += i
  }
  sum
}

def sum(a: Int, b: Int): Int = {
  if(a > b) 0 else a + sum(a + 1, b)
}

Bei Nutzung von Rekursion ruft sich die Methode selbst mit veränderten Parametern so lange auf, bis eine Abbruchbedingung erfüllt ist. Allerdings kann man nicht jede Schleife wie oben umschreiben. Oft braucht man einen weiteren Parameter, den Akkumulator. In diesem Fall wäre es nicht zwingend notwendig, aber schreibt man die obige Methode so um, dass sie einen Akkumulator verwendet, sieht sie folgendermaßen aus.

def sum(a: Int, b: Int): Int = {
  def sumacc(a: Int, b: Int, acc: Int): Int = {
    if(a > b) acc else sumacc(a + 1, b, acc + a)
  }
  sumacc(a, b, 0)
}

Hier wird eine innere Methode eingeführt, um die eigentliche Implementierung nach außen hin zu verbergen. Dies ist notwendig, weil die innere Methode nur dann korrekte Ergebnisse liefert, wenn man den Akkumulator richtig initialisiert, hier mit Null.

Ein weiterer Unterschied dieser Implementierung gegenüber der vorherigen ist, dass sie nicht nur rekursiv, sondern sogar endrekursiv ist. Endrekursiv ist eine Methode genau dann, wenn der rekursive Aufruf der letzte zu berechnende Ausdruck bei der Auswertung der Methode ist. Im ersten Beispiel ist dies nicht der Fall, da stets noch das Ergebnis des rekursiven Aufrufs zu a hinzuaddiert wird, der letzte Ausdruck der Auswertung ist also eine Addition. Der Vorteil von endrekursiven Methoden gegenüber rekursiven ist, dass der rekursive Aufruf keinen zusätzlichen Speicher auf dem Stack alloziert, wie es sonst bei Methodenaufrufen der Fall ist. Daher können endrekursive Methoden beliebig tiefe Rekursion nutzen, ohne dass es zum Stacküberlauf kommt 2. Dies gilt allerdings nur für Sprachen, die Endrekursion optimieren, so wie Scala. Java hingegen leistet dies nicht.

Funktionen


Funktionen sind Instanzen der verschiedenen FunctionX-Traits, wobei das X für die Anzahl der Parameter der Funktion steht. Eine Funktion, die einen Int-Parameter erwartet und einen String zurückliefert, hat beispielsweise den Typen Function1[Int, String] und eine Funktion, die zwei Int-Parameter hat und Boolean zurück liefert, Function2[Int, Int, Boolean]. Da Funktionstypen häufig verwendet werden, gibt es für sie eine spezielle, abkürzende Syntax. Für die beiden gerade beschriebenen Typen sind das Int => String und (Int, Int) => Boolean. Die Klammer um die Parameter-Typen darf man weglassen, wenn die Funktion genau einen Parameter hat.

Wenden wir uns nun der Erzeugung von Funktionsinstanzen zu. Das folgende Beispiel zeigt, wie man Instanzen von Funktionen mit sogenannten Funktionsliteralen erzeugt und wie man Funktionen auswertet beziehungsweise aufruft.

val toStringFunction = (x: Int) => x.toString
val threeAsString = toStringFunction(3)
// threeAsString ist "3"

val isGreaterFunction = (x: Int, y: Int) => x > y
val oneGreaterTwo = isGreaterFunction(1, 2)
// oneGreaterTwo ist false

Man sieht, dass Funktionen genauso wie Methoden aufgerufen werden. Vom Compiler wird diese Syntax in Aufrufe der Methode apply der Funktionsinstanzen übersetzt. Die gezeigten Funktionsliterale sind ebenso syntaktischer Zuckerguss. Das folgende Beispiel zeigt, wie es ohne diesen aussieht.

val toStringFun = new Function1[Int, String] {
  def apply(x: Int) = x.toString
}

val threeAsString = toStringFun.apply(3)

Bei Funktionsliteralen mit genau einem Parameter kann man die Klammern um diesen weglassen, wenn sein Typ nicht angegeben wird. Dies wiederum ist aber nur dann möglich, wenn der Typ inferiert werden kann. Im nächsten Beispiel wird dies durch die Angabe des Typen bei der Wertedefinition erreicht.

val toStringFun: (Int => String) = (x => x.toString)

oder

val toStringFun: Int => String = x => x.toString

Die Klammern um den Typen und um das gesamte Funktionsliteral sind nur zur besseren Übersichtlichkeit gesetzt und optional. Macht man Gebrauch von Funktionen höherer Ordnung, kann diese Schreibweise zu umständlich sein. Daher gibt es noch eine weitere Möglichkeit, Funktionen zu notieren, die nur aus einem einzelnen Ausdruck bestehen.

val toStringFun: Int => String = _.toString
val isGreaterFun: (Int, Int) => Boolean = _ > _

Jeder Unterstrich steht dabei für einen neuen, anonymen Parameter. Bei isGreaterFun wird also nicht ein und derselbe Parameter mit sich selbst verglichen, sondern der erste mit dem zweiten Parameter.

Darüber hinaus gibt es auch die Möglichkeit, Methoden zu Funktionen zu erheben 3. Dies geschieht mit folgender Syntax.

def isGreaterMethod (x: Int, y: Int) = x  >  y
val isGreaterFun = isGreaterMethod _

Man schreibt den Methoden-Namen, gefolgt von einem Unterstrich, wobei unbedingt darauf zu achten ist, Leerzeichen dazwischen einzufügen, da der Unterstrich sonst als Teil des Bezeichners verstanden wird. Die sich ergebende Funktion hat die gleiche Signatur, wie die zugrunde liegende Methode, und ist per Delegation auf diese implementiert.

Einen Sonderfall gibt es, wenn eine Methode dort verwendet werden soll, wo eine Funktion mit zur Methode passendem Typen erwartet wird. In diesem Fall kann der Unterstrich weggelassen werden.

def filter(p: Int => Boolean) = ...
def greaterThree(x: Int) = 3 < x

filter(greaterThree)
filter(3.<)
filter(3 <)

In den letzten beiden Zeilen macht man sich zunutze, dass für das Objekt 3 die Methode "<" definiert ist.

Pattern-Matching


Pattern-Matching ist eine Art mächtige switch-Anweisung, ist allerdings ein Ausdruck und gibt damit einen Wert zurück. Das Beispiel zeigt einige Anwendungsmöglichkeiten.

def matcher(exp: Any) = exp match {
  case "Guten Tag" => "Hallo"                 // 1. Fall
  case i: Int => (i * i).toString             // 2. Fall
  case d: Double if(d > 0) => d.toString      // 3. Fall
  case Person(Name(vorname, _), alter) =>     // 4. Fall
    vorname + " ist " + alter
  case _ => "Default"
}

Die Methode matcher besteht aus einem Pattern-Match, der durch das Schlüsselwort match eingeleitet wird. Das Schlüsselwort case leitet jeweils einen neuen Fall ein und das Symbol => trennt das abzugleichende Muster und den Code, der bei Übereinstimmung ausgewertet wird. Die Fälle "fallen" nicht nach unten durch, wie man es von Java kennt, weswegen break oder return nicht notwendig und auch nicht zulässig sind 4. Die Fälle werden in der angegebenen Reihenfolge geprüft, bis eine Übereinstimmung gefunden wird. Dieser Fall wird ausgewertet und das Ergebnis zurückgegeben. Der Default-Fall ist optional, hat als Muster einen Unterstrich und passt auf jede Eingabe. Passt keiner der angegebenen Fälle, so wird ein MatchError geworfen.

Auf bestimmte Werte kann geprüft werden, indem diese als Muster angegeben werden, wie im ersten Fall. Der zweite Fall zeigt die Prüfung auf einen bestimmten Typen. Der dritte Fall zeigt zusätzlich einen sogenannten Guard, eine zusätzliche Bedingung, die erfüllt werden muss. Man sieht, dass die Variablen, die in den Mustern belegt werden, sowohl im Guard als auch im Rumpf des Falles benutzt werden können.

Der vierte Fall benutzt Case-Klassen. Man erkennt, warum sich diese gut für Pattern-Matching eignen und dass man Muster auch ineinander verschachteln kann. Außerdem wird hier wieder das Muster _ verwendet, welches für einen beliebigen Wert steht, ohne ihm einen Namen zu geben.

Beim Pattern-Matching geht es also nicht allein darum zu prüfen, ob ein Muster passt, sondern auch darum, Teile des Musters zu benennen um mit ihnen zu arbeiten. Eine Möglichkeit komplexe Muster zu benennen bietet das @-Symbol. Damit kann eine Prüfung auf einen komplexen, zusammengesetzten Wert erfolgen und man hat trotzdem die Möglichkeit, den kompletten Ausdruck an eine Variable zu binden.

def register(x: Any) = x match {
  case paul @ Person(Name("Paul", _), _) => registerVip(paul)
  case _ => // Unwichtig
}

Die Unterscheidung, ob ein Bestandteil eines Musters eine Variable oder einen abzugleichenden Wert darstellt, hängt vom ersten Zeichen des Bezeichners ab. Fängt er mit einem Kleinbuchstaben an, wird er als Variable interpretiert, bei einem Großbuchstaben als Wert.

Pattern-Matching und funktionale Programmierung


Pattern-Matching wird in der funktionalen Programmierung häufig eingesetzt, beispielsweise um die Abbruchbedingung einer Rekursion zu prüfen. Betrachtet wird dazu das Beispiel einer einfachen funktionalen Implementierung des Quicksort-Algorithmus.

def quicksort(list: List[Int]): List[Int] = list match {
  case x :: xs =>
    val lesser = xs.filter(_ <= x)
    val greater = xs.filter(_ > x)
    quicksort(lesser) ::: x :: quicksort(greater)
  case _ => Nil
}

Scalas Typ List repräsentiert eine unveränderliche und einfach verkettete Liste 5. Eine solche Liste ist entweder die leere Liste Nil, oder ein Knoten bestehend aus einem Wert und einer Referenz auf die restliche Liste. Listen werden durch Voranstellen von Elementen an vorhandene Listen mit dem Operator :: gebildet, beispielsweise 42 :: Nil, was eine Liste mit genau einem Element liefert, dem Int 42. Das Muster x :: xs prüft daher, ob es sich bei der Eingabe um eine nicht leere Liste handelt, wobei das erste Element der Liste x und der Rest der Liste xs zugewiesen wird, wobei xs dann auch die leere Liste Nil zugewiesen werden kann.

Wird quicksort also mit einer nicht leeren Liste gerufen, so wird deren erstes Element als Pivot-Element x ausgewählt. Dann werden alle Elemente der Restliste, die kleiner oder gleich x sind, in lesser und alle Elemente der Restliste, die größer als x sind, in greater gespeichert. Als Rückgabe dient eine Liste bestehend aus den mit quicksort sortierten Elementen von lesser, dem Element x und dann allen mit quicksort sortierten Elementen von greater. Der Operator ::: dient dazu, einer Liste eine Liste voranzustellen, statt nur ein einzelnes Element, wie bei ::.
Im Fall, dass quicksort mit der leeren Liste aufgerufen wird, wird schlicht die leere Liste zurückgeliefert.

Abschließend


Man sieht am Beispiel von quicksort, dass funktionale Konzepte, wie Pattern-Matching, Rekursion und Funktionen höherer Ordnung, Hand in Hand gehen und gemeinsam das Potential bieten, Algorithmen sehr elegant und kompakt auszudrücken.

Fußnoten

1 Die Summe der Zahlen im Intervall [a, b] berechnet sich zu (b – a + 1)(a + b)/2, aber wir wollen uns ja mit Rekursion beschäftigen.

2 Die nicht endrekursive Methode sum führt auf dem System des Autors ab einer Rekursionstiefe von ca. 9000 zu einem StackOverflowError.

3 Der Autor ist sich nicht sicher, ob "erheben" der richtige Ausdruck ist – es ist die Übersetzung des englischen "to lift".

4 Die Schlüsselwörter break, return und continue gibt es in Scala nicht, allerdings bietet die Standardbibliothek zumindest für break Ersatz.

5 Dies ist nicht zu verwechseln mit Javas List, dem Super-Interface für alle geordneten Collections in Java. Geordnete Collections werden oft als Sequenzen bezeichnet, weswegen es in Scala das Trait Seq dafür gibt.

Referenzen

[1] Wikipedia, Der Lambda-Kalkül
[2] Wikipedia, Von-Neumann-Architektur

Sonntag, 27. Februar 2011

Scala Einführung - Teil 2

Nachdem es im letzten Teil eine allgemeine Einführung zu Scala gab, stelle ich in diesem Post die objektorientierten Aspekte der Sprache vor.

Klassen


Klassendefinitionen unterscheiden sich in vielen Details von Java, weshalb ich schrittweise die wichtigsten Änderungen einführe. Im einfachsten Fall hat eine Klasse keine Member. In diesem Fall kann man die geschweiften Klammern für den leeren Klassenrumpf weglassen. Da alle Definitionen standardmäßig public sind, beschreibt das folgende Beispiel eine leere, öffentliche Klasse:

class Beispiel

Properties


Möchte man einer Klasse Felder hinzufügen, stehen dazu die auch zur Variablendefinition verwendeten Schlüsselwörter var und val zur Verfügung. Hier werden zwei öffentliche Felder a und b definiert:

class Beispiel {
  val a = 42
  var b = "abc"
}

Genauer gesagt werden hier nicht Felder definiert, sondern Properties, also Felder mit Zugriffsmethoden. Die erzeugten Methoden folgen allerdings nicht der JavaBean-Konvention, da man sich in Scala gerne etwas kürzer fasst und das Voranstellen von get, set oder is daher nicht gewünscht ist. Stattdessen trägt der Getter schlicht den Namen des Feldes. In diesem Beispiel werden also zwei Methoden mit Namen a und b generiert. Setter tragen den Namen des Feldes mit einem angehängten "_=". Da a als val unveränderlich ist, wird kein Setter generiert, b allerdings ist veränderlich und bekommt daher einen Setter mit dem Namen "b_=".
Für jeden Zugriff auf ein Feld wird automatisch die entsprechende Zugriffsmethode benutzt. Im Beispiel wird bei lesendem Zugriff auf Feld b die Methode "b", bei schreibendem Zugriff die Methode "b_=" gerufen:

val bsp = new Beispiel

println(bsp.b) // Aufruf von Methode b
bsp.b = "xyz" // Aufruf von Methode b_=
bsp.b_=("xyz") // Äquivalent zur Zeile darüber

Namensräume


Natürlich kann man die Zugriffsmethoden von Properties auch selbst definieren. Allerdings muss man dabei beachten, dass Scala nur zwei Namensräume kennt, einen für alle Typen und einen weiteren für den Rest, wie Methoden und Felder. Deshalb kann ein Feld, im Gegensatz zu Java, nicht den gleichen Namen tragen wie eine Methode der gleichen Klasse. Im Beispiel soll das Feld intern eine Gleitkommazahl sein, aber beispielsweise aus historischen Gründen nach außen hin als Int erscheinen:

class Beispiel(private var aIntern: Float) {
  def a = aIntern.toInt
  def a_=(s: Int) { aIntern = s.toFloat }
}

Dies ist ein Beispiel, bei dem Scala nicht sonderlich elegant ist, da man für das private Feld zwingend einen anderen Namen wählen muss, als für die öffentliche Property.

Konstruktoren


Anders als in Java hat in Scala jede Klasse im Grunde genommen nur einen Konstruktor – den sogenannten primären Konstruktor. Dessen Parameter werden direkt nach dem Klassennamen angegeben:

class Beispiel(a: Int, val b: Int, var c: Int)

In diesem Beispiel hat der primäre Konstruktor drei Parameter a, b und c und alle sind vom Typ Int. Dabei gibt es eine Besonderheit: mit den Schlüsselwörtern val oder var definierte Parameter werden automatisch zu Properties der Klasse, im Beispiel also b und c. Der Klassenrumpf ist gleichzeitig der Rumpf des Konstruktors. Im folgenden Beispiel ruft der Konstruktor die Methode println.

class Beispiel(val a: Int) {
  println("a ist " + a)
}

Außerdem gibt es noch sogenannte Hilfskonstruktoren. Diese werden wie Methoden mit dem Namen this definiert und müssen als erstes den primären Konstruktor oder einen darüber definierten Hilfskonstruktor rufen:

class Beispiel(val s: String) {
  def this(i: Int) = this(i.toString)
}

Methodendefinitionen sind bereits aus dem ersten Teil bekannt. Erwähnenswert ist, dass Methoden auch innerhalb anderer Methoden definiert werden können. Diese inneren Methoden sind nur innerhalb der sie umgebenden Methode sichtbar. Dazu ein Beispiel:

class Beispiel {
  def a() = b(42)

  private def b(i: Int) = println(42 + i)

  def outer(i: Int) = {
    def square(x: Int) = x * x
    println(square(i))
  }
}

Abschließend noch ein Beispiel, welches im Vergleich zu Java zeigt, dass Definitionen von Value-Klassen sehr kompakt geschrieben werden können. Die folgenden beiden Klassen sind äquivalent:

Java:
public class Beispiel {
  private final int a;
  private final int b;

  public Beispiel(int a, int b) {
    this.a = a;
    this.b = b;
  }

  public int getA() {
    return a;
  }

  public int method(int x) {
    return b + x;
  }
}

Scala:
class Beispiel(val a: Int, b: Int) {
  def method(x: Int) = b + x
}

Superklassen


Möchte man bei der Klassendefinition eine Superklasse angeben, so macht man dies mit dem Schlüsselwort extends. Die Parameter des Superkonstruktors werden direkt nach dem Namen der Superklasse notiert:

class A(val i: Int)
class B extends A(42)
class C(a: Int, val s: String) extends A(a)

Traits


Das Gegenstück zu den Interfaces bei Java sind die Traits. Man kann mit ihnen allerdings nicht nur abstrakte Methoden definieren, sondern auch konkrete Implementierungen von Methoden und Properties. Genauer gesagt erlauben Traits alles, was auch mit Klassen möglich ist, wie von anderen Traits oder Klassen abzuleiten. Die einzige Ausnahme ist, dass ein Trait keine Konstruktorparameter haben kann.

Da Traits nicht auf Schnittstellendefinitionen beschränkt sind, aber einem Typen trotzdem in beliebiger Zahl hinzugefügt werden können, werden sie auch als Mixins bezeichnet. Die Bezeichnung rührt daher, dass beliebige Funktionalität „beigemischt“ werden kann. Das folgende Beispiel zeigt die Syntax für Traits. Die Basisklasse, beziehungsweise das Basis-Trait, wird mit extends angegeben, alle weiteren Traits werden mit dem Schlüsselwort with deklariert. Für die Beimischung von Traits bei der Instanziierung eines Wertes benutzt man stets nur das Schlüsselwort with:

trait TA
trait TB
trait TC
trait TD

class C extends TA with TB with TC

val c = new C
val d = new C with TD

Traits und Vererbung


Ein weiteres Beispiel zeigt die Möglichkeiten im Zusammenspiel von Traits und Vererbung:

class Geber {
  def gib = 3
}

trait Doppelt extends Geber {
  override def gib = super.gib * 2
}

trait PlusZehn extends Geber {
  override def gib = super.gib + 10
}

val a = new Geber with Doppelt with PlusZehn
val b = new Geber with PlusZehn with Doppelt

a.gib // gibt 16 zurück
b.gib // gibt 26 zurück

Hier gibt der Aufruf von a.gib den Wert 16 und der Aufruf von b.gib das Ergebnis 26 zurück. Offensichtlich ist die Reihenfolge relevant, in der Traits beigemischt werden. Der Grund dafür ist, dass Traits eine Delegationskette bilden. Um die Reihenfolge der Delegationen zu finden, wird die baumartige Vererbungshierarchie eines Typs in eine verkettete Liste transformiert, in der jeder Typ nur noch ein Mal vorkommt. Nach welchen Regeln diese Linearisierung erfolgt, kann man unter [1] nachlesen. Die Linearisierung bestimmt, welche Semantik das Schlüsselwort super hat, denn es bezieht sich stets auf den in der Linearisierung nachfolgenden Typen. Die Werte a und b aus dem Beispiel oben haben die folgenden Linearisierungen:

a -> Doppelt -> PlusZehn -> Geber -> AnyRef -> Any
b -> PlusZehn -> Doppelt -> Geber -> AnyRef -> Any

Self-Types


Möchte man die Typen einschränken, denen ein Trait beigemischt werden kann, so macht man dies über die Angabe eines Self-Types. Im Gegenzug erhält das Trait Zugriff auf die Member des Self-Types, ähnlich, als wäre es vom Self-Type abgeleitet. Dazu ein Beispiel, bei dem der Self-Type von T auf A festgelegt wird:

class A {
  def a = 42
}

trait T { this: A =>
  def b = "Die Antwort ist " + a // a kommt aus Klasse A
}

class B

val a = new A with T // Ok
val b = new B with T // Kompilierfehler

Der Versuch der Klasse B das Trait T beizumischen wird mit einem Kompilierfehler quittiert.

Singleton-Objekte


Wie im ersten Teil schon erwähnt, gibt es in Scala keine statischen Konstrukte. Der Grund ist, dass sie eigentlich nicht zur Objektorientierung gehören und daher als Sonderfall weggelassen wurden. Als Ersatz gibt es mit dem Schlüsselwort object definierte Singleton-Objekte. Sie definieren stets gleichzeitig eine Klasse und einen Namen für deren einzige Instanz, im Beispiel Counter:

object Counter {
  private var counter = 0
  
  def next(): Int = {
    counter += 1
    counter
  }
}

val next = Counter.next()

Bei der Definition von Objekten hat man die gleichen Möglichkeiten wie bei Klassendefinitionen, beispielsweise kann man Vererbung benutzen. Nur Konstruktorparameter können nicht verwendet werden, denn es gibt keine Stelle an der man die Parameter übergeben könnte.

Um die Interoperabilität mit Java zu gewährleisten, wird für jedes Objekt noch eine zusätzliche, aus Scala heraus unsichtbare Java-Klasse erzeugt, die für alle Methoden des Objekts ein statisches Äquivalent hat, welches an das Objekt delegiert. Dies ist auch der Grund, warum eine main-Methode in einem Objekt von der JVM als Programmeinstiegspunkt genutzt werden kann.

Kompagnon-Objekte


Da Objekte als Ersatz für alle statischen Konstrukte dienen, muss es möglich sein, aus einem Objekt heraus Zugriff auf private Member einer Klasse zu haben, beispielsweise um Fabrikmethoden zu implementieren, die einen privaten Konstruktor aufrufen. Zu diesem Zweck gibt es die sogenannten Kompagnon-Objekte. Sie zeichnen sich dadurch aus, dass sie den gleichen Namen tragen, wie ihre Kompagnon-Klasse, und zusätzlich in der gleichen Datei definiert sind. Eine Klasse und ihr Kompagnon-Objekt haben gegenseitig Zugriff auf ihre privaten Member.

Die Methode apply


In Scala ist es ein Standardvorgehen, Fabrikmethoden im Kompagnon-Objekt zu definieren, die den Namen apply tragen. Der Grund dafür ist eine Spezialsyntax für Methoden dieses Namens. Schreibt man direkt nach einem Ausdruck eine Parameterliste mit Klammern, so interpretiert der Compiler dies als einen Aufruf der apply- Methode mit den angegebenen Parametern. Ein Beispiel macht dies anschaulich – so sind die beiden folgenden Ausdrücke äquivalent:

value.apply(param)
value(param)

Hat man beispielsweise eine Fabrikmethode mit Namen apply auf dem Kompagnon-Objekt Person definiert, kann man diese wie einen Konstruktor aufrufen, nur ohne das Schlüsselwort new.

val peter = Person("Peter", "Huber")
val paul = Person("Paul", "Schmidt")

Diese Syntax wird auch an vielen anderen Stellen in Scala benutzt. So werden auch Zugriffe auf Collections und Arrays mit Hilfe der apply-Methode durchgeführt:

val arthur = personenSequenz(42)
val peter = personenMap("Huber")
val element = meinArray(3)

Case-Klassen


Es existiert noch eine besondere Art von Klassen, die sich besonders dazu eignen, Value-Objekte zu implementieren, die sogenannten Case-Klassen. Eine Case-Klasse definiert man wie eine gewöhnliche Klasse, nur dass man vor das Schlüsselwort class noch das Schlüsselwort case setzt. Im Unterschied zu normalen Klassen verhalten sich die Konstruktorparameter standardmäßig so, als seien sie mit dem Schlüsselwort val versehen und werden zu öffentlichen Properties der Klasse. Außerdem kann man Case-Klassen ohne das Schlüsselwort new instanziieren, da der Compiler automatisch ein Kompagnon-Objekt mitsamt Fabrikmethode erzeugt. Zusätzlich werden Implementierungen der Methoden equals, hashcode und toString bereitgestellt, welche auf den Konstruktorparametern basieren. Weiterhin wird eine Methode copy generiert, welche Default-Parameter benutzt, um auf einfache Weise abgewandelte Kopien zu erzeugen.

case class Person(vorname: String, nachname: String, alter: Int)

val arthur = Person("Arthur", "Dent", 28)
val twin = arthur.copy(vorname = "Richard")
val oldArthur = arthur.copy(alter = 42)

Darüber hinaus unterstützen Case-Klassen auch das im ersten Teil kurz vorgestellte Pattern-Matching, auf das in einem späteren Post noch genauer eingegangen wird.

Schluss


Dieser Teil hat sich eingehender mit den objektorientierten Aspekten von Scala befasst und hat hoffentlich zeigen können, dass es sich in dieser Hinsicht nicht hinter Java verstecken muss. Vor allem Traits haben großes Potential zur Vermeidung von Code-Duplizierung.
Der nächste Post wird sich mit den funktionalen Aspekten der Sprache beschäftigen, denen nachgesagt wird, dass sie den Code-Umfang und damit die Entwicklungsdauer erheblich reduzieren können.

Referenzen

[1] The Scala Language Specification, Sektion 5.1.2

Sonntag, 6. Februar 2011

Scala Einführung - Teil 1

Ich habe mich entschlossen eine an Java-Entwickler gewandte Einführung in die Programmiersprache Scala zu schreiben. Dies ist der erste Post einer kleinen Serie und gibt einen Überblick zur Sprache.

Hintergrund


Scala wird unter der Regie von Martin Odersky am Ecole Polytechnique Fédérale de Lausanne in der Schweiz entwickelt. Die ersten Designentwürfe wurden bereits 2001 gemacht und Version 1.0 wurde 2003 veröffentlicht. Mit Version 2.0 wurden 2006 viele tiefgreifende Änderungen vorgenommen. Die Sprache entwickelt sich stetig weiter und ist mittlerweile bei Version 2.8.1 angekommen.

Scala steht für Scalable Language. Diese Namensgebung drückt aus, dass die Schöpfer der Sprache sich das Ziel gesetzt haben, sie zum Schreiben von Programmen beliebiger Größe und Komplexität geeignet zu machen. Scala läuft auch unter .Net, wenngleich die Unterstützung zumindest momentan noch weit hinter der von Java zurückbleibt.

Grundideen


Die Grundideen der Sprache sind ein besseres Java zu sein und sowohl objektorientierte als auch funktionale Paradigmen zu unterstützen. Durch die Nähe zu Java soll der Umstieg erleichtert werden. Ein Grundsatz der Sprache ist das Streben nach Kürze und Prägnanz und hat zwei Ausprägungen. Einerseits soll der in ihr geschriebene Code prägnant und ohne überflüssige Syntax-Elemente sein, andererseits soll die Sprache selbst, beziehungsweise ihre Spezifikation, möglichst kurz sein. Dies bewirkt, dass es nur sehr wenige Ausnahmen und Sonderfälle gibt. Im Gegensatz zu Java sind die Sprachkonstrukte nicht auf spezielle Anwendungsfälle zugeschnitten, sondern möglichst allgemein und zueinander orthogonal gehalten1. Dadurch stehen dem Entwickler in Scala sehr mächtige Ausdrucksmöglichkeiten zur Verfügung und viele Features lassen sich als Bibliotheksfunktionen realisieren, die normalerweise als Sprachkonstrukte bekannt sind.

Hier noch exemplarisch einige Verallgemeinerungen und Vereinfachungen gegenüber Java. Es gibt keine primitiven Typen, sondern nur Objekte. Es gibt keine Operatoren, sondern stattdessen Methoden in Infixnotation. Die import-Anweisung kann praktisch überall stehen und auch Methoden und Felder aus unveränderlichen Werten statt nur aus Typen importieren. Und der Vergleich mit "==" wird mit Hilfe der equals-Methode realisiert – möchte man tatsächlich Referenzen vergleichen, kann man dies mit den Operatoren "eq" und "ne" tun.

Beispiele


Um einen Vorgeschmack zu vermitteln, wie Scala-Code im Vergleich zu Java aussieht und welche Vorteile es bringen kann, folgen nun einige Beispiele.

Eine Value-Klasse, die einen Angestellten repräsentiert, komplett mit Zugriffsmethoden2 und equals, hash-Code und toString:

case class Angestellter(
  name: String,
  abteilung: String,
  gehalt: BigDecimal
)

Eine Methode, welche eine Sequenz3 von Angestellten nach ihrem Gehalt sortiert und die zehn Bestverdiener zurückliefert:

def topTen(angestellte: Seq[Angestellter]) = {
  angestellte.sortBy(_.gehalt).takeRight(10)
}

Eine Methode, die aus einer Sequenz von Angestellten eine Sequenz von Strings macht, die jeweils aus Name und Abteilung eines Angestellten bestehen:

def namen(angestellte: Seq[Angestellter]) = {
  angestellte.map(a => a.name + ": " + a.abteilung)
}

Eine Methode, die von einer Sequenz von Mitarbeitern alle externen Mitarbeiter zurückliefert:

def externe(mitarbeiter: Seq[Mitarbeiter]) = {
  mitarbeiter.filter(_.istExtern)
}

Eine Methode, die beliebige Objekte4 in einen String umwandelt:

def asString(x: Any) = x match {
  case null => "null"
  case "" => "Der leere String"
  case d: Date => dateFormat.format(d)
  case i: Int if(i < 100) => "Eine kleine Zahl"
  case _ => x.toString
}

Eine Methode, welche die Fakultät einer Zahl berechnet, wobei BigInt5 verwendet wird, um Überläufe zu vermeiden:

def fakultaet(n: BigInt): BigInt = {
  if (n == 0) 1 else n * fakultaet(n – 1)
}

Augenscheinliche Unterschiede


Es folgt ein Hello-World-Programm, um einige Besonderheiten der Sprache zu erläutern:

object HelloWorld {

  def main(args: Array[String]) {
    hello("World")
  }

  def hello(s: String) {
    println("Hello " + s)
  }
}

Man sieht, dass die main-Methode nicht statisch ist. Statische Methoden oder Felder gibt es generell nicht. Stattdessen gibt es die Möglichkeit Objekte mit Hilfe des Schlüsselworts object zu definieren. Sie sind benannte Singleton-Instanzen, die unter anderem als Ersatz für alle statischen Konstrukte Javas dienen. Weiter fällt auf, dass die Methodendefinitionssyntax ungewohnt ist. Eine Methodendefinition wird stets mit dem Schlüsselwort def eingeleitet und die Typen der Parameter werden durch einen Doppelpunkt getrennt hinter dem Namen des Parameters notiert. Die Methoden sind ohne Sichtbarkeitsmodifikator definiert. In Java entspräche dies der Sichtbarkeit package-private, in Scala ist die Standardsichtbarkeit public. Außerdem enthält der Code keine Semikolons, da diese in Scala optional sind. Der Compiler versucht sie bei deren Fehlen nach bestimmten Regeln selbst zu setzen. Dies nennt man auch Semikoloninferenz.

Definitionssyntax


Im Folgenden sollen nun nach und nach die wichtigsten Sprachkonstrukte vorgestellt werden, beginnend mit der Syntax für Definitionen. Zuerst eine Gegenüberstellung der Syntax von Java auf der linken Seite und Scala auf der rechten Seite:

int i;
final int i;
void method() { }
int num() { return res; }
int add(int a) { }
class Foo<T> { }
var i: Int
val i: Int
def method { }
def num: Int = res
def add(a: Int): Int = { }
class Foo[T] { }

Man sieht, dass Definitionen in Scala stets mit einem Schlüsselwort, wie val, def und class eingeleitet werden und Typangaben durch einen Doppelpunkt getrennt nachgestellt werden. Weiterhin können die geschweiften Klammern um die Rümpfe von Methoden weggelassen werden, wenn diese aus nur einem Ausdruck bestehen. Zu beachten ist, dass Methoden implizit den Rückgabetyp Unit, das Äquivalent zu Javas void, haben, wenn nach der Methodensignatur kein Gleichheitszeichen gesetzt ist. Außerdem ist das return optional – wird es weggelassen, gibt die Methode den Wert des letzten Ausdrucks zurück.

Typinferenz


Einer der Gründe für die geänderte Definitionssyntax, im Vergleich zu Java, ist die Typinferenz. Sie bewirkt, dass der Compiler den Typ einer Definition auch ohne explizite Angabe bestimmt und verwendet. Dazu ein Beispiel:

var i = 42

Dieser Ausdruck ist nicht untypisiert, sondern stattdessen wird der Typ vom Compiler bestimmt. Der Compiler wählt dabei immer den spezifischsten, passenden Typen. In diesem Fall wird der Typ von i auf Int festgelegt und das Programm verhält sich genau so, als hätte man dies explizit angegeben. Würde man im Folgenden versuchen, der Variable i einen Wert vom Typ String zuzuweisen, würde es beim Compilieren zu einem Fehler kommen. Auch mit Typinferenz ist somit die statische Typprüfung gewährleistet.

Ausdrücke


Betrachten wir, wie die Syntax für Ausdrücke aussieht. Prinzipiell ist sie Javas sehr ähnlich, allerdings gibt es einige Besonderheiten, die zu beachten sind. Methodenaufrufe können nicht nur wie in Java geschrieben werden:

obj.methode(arg)

sondern auch in Infixnotation, wie man es sonst nur von Operatoren, wie +, kennt:

obj methode arg

Dies ist möglich, weil Scala generell nicht zwischen Methoden und Operatoren unterscheidet. Daher sind beispielsweise auch folgende Ausdrücke äquivalent6:

1 + 2 und 1.+(2)

Mancher Leser wird sich nun fragen, wie die mathematischen Grundregeln, wie Punkt vor Strich, realisiert werden. Dafür wird das erste Zeichen des Methodennamens zur Präzedenzbestimmung herangezogen. Eine Methode, die mit dem Zeichen + beginnt, hat niedrigere Präzedenz, als eine Methode, die mit dem Zeichen * beginnt. Somit ist gewährleistet, dass sich die operatorähnlichen Methoden von der Präzedenz her so verhalten, wie man es von den Operatoren aus Java gewohnt ist. Die Präzedenz ist aber nur relevant, wenn man die Infixnotation nutzt. Herkömmliche Methodenaufrufe mit Punkt werden, wie gewohnt, von links nach rechts ausgewertet.

Bedingte Ausdrücke werden mit if notiert. Allerdings ist das if, im Gegensatz zu Java, ein Ausdruck und keine Anweisung, was den Fragezeichenoperator überflüssig macht:

if (cond) exprA else exprB

aber auch

val v = if (cond) exprA else exprB

Schleifen werden mit while oder mit for geschrieben, wobei sich die for-Schleife von Javas unterscheidet und in der Ausdrucksstärke weit darüber hinausgeht. Daher wird sie in einem späteren Post noch einmal im Detail betrachtet und hier nur in ihrer einfachsten Form vorgestellt. Die while-Schleife hingegen gleicht der von Java:

for (element <- collection) { expr }
while (cond) { expr }

Do it youself


Wer selbst mit der Sprache experimentieren will, dem sei empfohlen sich unter [3] das Current Stable Release herunterzuladen und den interaktiven Modus, genannt REPL7, auszuprobieren. Den REPL-Modus startet man, indem man mit einer Kommandozeile in das Unterverzeichnis bin der Scala-Distribution wechselt und dort das Script scala startet. Wer gleich ein Projekt in seiner Lieblings-IDE aufsetzen will, der hat die Wahl zwischen den Plugins für Eclipse [4], Netbeans [5] und IntelliJ IDEA [6].

Abschließend


Damit ist der erste Einblick in die Sprache Scala abgeschlossen. Die elementaren Unterschiede zu Java wurden vorgestellt und es ist hoffentlich gelungen, die Neugierde zu wecken und Lust auf mehr zu machen. Der nächste Post beschäftigt sich mit Klassen, Traits und Objekten.

Fußnoten

1 Siehe zu dem Thema auch [1] und [2].

2 Scala generiert Getter und Setter, aber nicht nach den JavaBean-Vorgaben.

3 Eine Sequenz in Scala ist, vereinfacht gesagt, das Pendant zu java.util.Collection.

4 Any ist Supertyp für jeden anderen Typen und damit die Wurzel der Typhierarchie in Scala.

5 BigInt ist ein Wrapper um java.math.BigInteger aus der Scala-Standardbibliothek.

6 Oder doch nicht ganz äquivalent, denn im zweiten Fall wird die Eins als Fließkommazahl interpretiert. Richtig müsste es also (1).+(2) heißen.

7 REPL steht für Read Evaluate Print Loop und entspricht den von früher bekannten Interpretern.

Referenzen

[1] Neal Gafter's blog - Failure of Imagination in Language Design
[2] Stephen Colebourne's Weblog - Java language design by use case
[3] Scala's Current Stable Release
[4] Eclipse Scala-IDE
[5] NetBeans Scala
[6] JetBRAINS Scala Plugin for IntelliJ IDEA

Dienstag, 6. Juli 2010

Scala Actors - Lastverteilung

Nachdem ich zuvor darüber geschrieben habe, wie man ein Producer-Consumer-Pattern umsetzen kann, möchte ich diesmal zeigen, wie man Arbeitseinheiten automatisch auf mehrere Actors aufteilen kann.

Es bietet sich an, mehrere Actors zu verwenden, wenn man ein System mit mehreren Rechenkernen hat und diese alle auslasten möchte. Dabei sollte man allerdings beachten, dass es vom zugrunde liegenden Thread-Pool abhängt, wie viele Threads tatsächlich zur Verfügung stehen, um Actors parallel aktiv sein zu lassen. Somit schafft man bei Verwendung von n Actors die Voraussetzung, um bis zu n Threads gleichzeitig zu nutzen.

Wenden wir uns nun der Implementierung zu. Die Grundidee basiert darauf, dass Actors sehr leichtgewichtig sind. Also bietet es sich an, für jede Arbeitseinheit einen eigenen Actor zu erzeugen, der nichts tut, außer seine Arbeitseinheit zu verarbeiten und dann einem anderen Actor das Ergebnis als Nachricht zu schicken.

Damit brauchen wir drei Typen von Actors: einen der verteilt, einen der arbeitet und einen der die Ergebnisse einsammelt.

Das Code-Beispiel unten zeigt, wie man es implementieren könnte.

En Detail


Der Distributor bekommt einen Iterator übergeben, der die Arbeitspakete erzeugt. Der Distributor erzeugt immer neue Worker, die jeweils eine Arbeitseinheit bekommen, so lange es noch Arbeitseinheiten gibt und das Limit von Arbeitseinheiten in Bearbeitung es zulässt. Zu beachten ist hier, dass der Parameter worker des Collectors lazy ist und der übergebene Ausdruck "new Worker(...)" daher bei jedem Zugriff auf worker neu ausgewertet wird.

Jeder Worker wartet einmalig auf seine Arbeitsanweisung, arbeitet diese ab, schickt dem Collector das Ergebnis und gibt schlussendlich dem Distributor Bescheid, dass die Arbeitseinheit erledigt ist.

Der Collector sammelt die Ergebnisse der Worker ein und gibt jedem Actor eine Zusammenfassung der Ergebnisse, welcher eine Query-Nachricht an ihn schickt.

Hat der Distributor alle Arbeitseinheiten verteilt und von allen Workern eine Verarbeitungsbestätigung bekommen, warten er zum Schluss noch einmal auf eine Query-Nachricht und bestätigt diese bei Empfang. Dies ermöglicht es einem anderen Actor auf die Abarbeitung aller Arbeitseinheiten zu warten, so wie es hier in der main-Methode gemacht wird.

Erst dann wird in der main-Method die Zusammenfassung vom Collector abgefragt, um sicherzustellen, dass bereits alle Einzelergebnisse berücksichtigt sind.

Der Code


import scala.actors._
import Actor._


case object Query
case object Done
case object Finished

case class Result(count: Int, sum: Int)


object LoadDistributorExample {

  def main(args: Array[String]) {
    val collector = new Collector
    val distributor = new Distributor(Iterator.range(0, 10000),
                                      new Worker(collector))
    
    distributor !? Query
    collector !? Query match {
      case result: Result => println("The result is " + result)
    }
    collector ! Finished
  }
}


class Distributor[T](source: Iterator[T],
                     worker: => Actor,
                     limit: Int = 10)
extends Actor {
  
  start
  
  private var pending = 0
  
  def act {
    distribute()
    
    if(pending > 0) react {
      case Done => pending -= 1; println("Worker is done"); act()
    }
    
    react {
      case Query => reply(Done)
    }
  }
  
  private def distribute() = while(source.hasNext && pending < limit) {
    println("Distributing one unit of work")
    worker ! source.next
    pending += 1
  }
}


class Worker(collector: Collector) extends Actor {

  start
  
  def act = react {
    case n: Int => collector !? work(n); reply(Done)
  }
  
  def work(n: Int) = (0 until 10000).foldLeft(0) {
    (acc, x) => acc + x * n
  }
}


class Collector extends Actor {
  
  start
  
  private var count = 0
  private var sum = 0
  
  def act() = react {
    case n: Int =>
      println("Collected result")
      count += 1
      sum += n
      reply(Done)
      act()
    case Query => reply(Result(count, sum)); act()
    case Finished => reply(Done)
  }
}

Samstag, 3. Juli 2010

Scala Actors - Producer-Consumer

Heute möchte ich kurz einige Gedanken zu Scala Actors vorstellen, insbesondere, wie man damit ein Producer-Consumer-Pattern implementieren kann.

Eine Einführung zu Actors in Scala gibt es beispielsweise hier und die API wird hier näher erläutert.

Zurück zu Producer und Consumer. Vom Prinzip ist dies ganz einfach. Man braucht nur einen Actor, der Arbeitseinheiten als Nachrichten verschickt, und einen Actor, der immer wenn er eine solche Nachricht erhält, die Arbeitseinheit verarbeitet.

Soweit so einfach. Ein bisschen schwieriger wird es, wenn das Produzieren einer Arbeitseinheit sehr billig und das Abarbeiten einer Arbeitseinheit sehr teuer ist. In diesem Fall kann es leicht passieren, dass der Producer viel schneller Arbeitseinheiten verschickt, als der Consumer diese verarbeiten kann. Dadurch beginnt sich die Mailbox des Consumers schnell zu füllen. Hat man viele Arbeitseinheiten und sind diese vielleicht auch noch recht Speicher-intensiv, dann möchte man vielleicht vermeiden, dass der Heap unnötig stark mit noch nicht bearbeiteten Arbeitseinheiten gefüllt wird.

Also müssen wir den Producer drosseln. Dies geschieht zum Beispiel dadurch, dass der Consumer dem Producer immer dann eine Nachricht "Produziere!" sendet, wenn er merkt, dass kaum noch Arbeitseinheiten auf Halde liegen. Daraufhin kann der Producer dann ruhigen Gewissens einige Arbeitseinheiten schicken.

Unten ist etwas Code, der zeigt, wie man es implementieren könnte. Der Consumer merkt sich, wie viele Arbeitseinheiten er schon angefordert hat, die noch nicht abgearbeitet sind. Fällt diese Zahl unter einen Schwellwert, fordert er neue Arbeitseinheiten an.

Der Producer ist einfacher. Er verschickt bei jeder Aufforderung die gewünschte Zahl an Arbeitseinheiten und schickt ein "Fertig!", wenn es nichts mehr zu Produzieren gibt.

import scala.actors._
import Actor._


object ConsumerProducer {

  def main(args: Array[String]) {
    // Die Arbeitseinheiten sind Ints
    val producer = new Producer(Iterator.range(0, 10000))
    val consumer = new Consumer(producer)
  }
}


case class Produce(count: Int)
case object Finished


class Producer[T](source: Iterator[T]) extends Actor {
  
  start
  
  def act() {
    loopWhile(source.hasNext) {
      react {
        case Produce(n: Int) => produce(n)
      } 
    }
  }
  
  def produce(n: Int) {
    println("Producing " + n)
    var remaining = n
    source takeWhile(_ => remaining > 0) foreach {
      x => sender ! x; remaining -= 1
    }
    if(!source.hasNext) sender ! Finished
  }
}

class Consumer(producer: Actor) extends Actor {
  
  start
  
  private var remaining = 0
  
  def act() {
    requestWork()
    consume()
  }
  
  def consume(): Nothing = react {
    case Finished => println("Finished")
    case n: Int => work(n); requestWork(); consume()
  }
  
  def requestWork() = if(remaining < 5) {
    remaining += 10
    producer ! Produce(10)
  }

  def work(n: Int) = {
    val res = (0 until 10000).foldLeft(0) { (acc, x) => acc + x * n }
    println(n + ": " + res)
    remaining -= 1
  }
}

Samstag, 26. Juni 2010

Collection-Literale in Java

...oder wie man die Warnung "Type safety : A generic array of T is created for a varargs parameter" vermeiden kann.

Ich bin kürzlich über folgende Blog-Posts gestoßen, die zeigen, wie man mit Java-Bordmitteln Unterstützung für Collection-Literale erhält:

Building your own literals in Java – Lists, and Arrays
und
Building your own literals in Java – Tuples and Maps

Eine sehr schöne Idee, die an den entsprechenden Stellen den Code wesentlich leserlicher werden lässt. Die resultierende Syntax erinnert an Scala und sieht wie folgt aus:

List<Integer> list = List(1, 2, 3);
Map<Integer, String> map = Map(Pair(1, "A"), Pair(2, "B"));
Map<Integer, String> map = ImmutableMap(Pair(1, "A"), Pair(2, "B"));
Set<String> set = Set("a", "b", "c");

Insbesondere wenn man anfängt Map-Literale zusammen mit Paaren / 2-Tupeln zu unterstützen, wird man aber feststellen, dass man folgende, unschöne Warnung vom Java-Compiler bekommt: "Type safety : A generic array of T is created for a varargs parameter".

Das Problem ist, dass die statische Methode, die das Literal realisiert, ein varargs-Argument hat, welches in Java als Array von Object implementiert ist. Wer mehr dazu wissen will, dem kann ich folgenden Blog-Post sehr empfehlen:

Anatomy of an Annoyance

Die Lösung


Zu dieser Problematik gibt es eine einfache Lösung. Das Problem entsteht ja erst durch die Verwendung von varargs zusammen mit Generics. Da wir auf Generics nicht verzichten wollen, lassen wir eben die varargs weg. Dazu müssen wir sie nachbilden, in dem wir statt einer varargs-Methode eben n + 1 Methoden schreiben, um 0..n Parameter zu unterstützen. Dies lohnt sich auch für List-Literale, da auch hier die Typ-Warnung auftritt, sobald man generische Typen benutzt.

Ein weiterer Vorteil dieser Implementierung ist die Möglichkeit Map-Literale ohne Paare zu erzeugen:

Map<Integer, String> map2 = Map(1, "A", 2, "B");

Die dazugehörige Methodensignatur sieht folgendermaßen aus:

public static <K, V> Map<K, V> Map(K key1, V value1, K key2, V value2)

Do it like Google does it


An dieser Stelle möchte ich erwähnen, dass es noch andere gibt, die auf die Idee gekommen sind, statische Methoden als Helfer zu verwenden. Wenn man sich Google-Collections ansieht, stellt man fest, dass es auch hier statische Methoden gibt, um Collections zu erzeugen. Beispielsweise die Methode Lists.newArrayList, wobei hier leider wieder mit varargs gearbeitet wird, um die Elemente zu übergeben, mitsamt den erwähnten Problemen. Die zur Verfügung stehenden Map-Methoden sind aber Generics-sicher implementiert und verwenden keine varargs.

Google-Collections sind somit eine Möglichkeit, die hier vorgestellte, kompakte Syntax zum Erzeugen von Collections in das eigene Projekt einfließen zu lassen. Vielleicht eben auch dann, wenn man es nicht schafft, den Projektleiter zu überzeugen, eine selbst gestrickte Lösung aufzunehmen. Zumal Google-Collections noch viel mehr bieten, um das Entwicklerherz höher schlagen zu lassen und dem Projekt zum sicheren Gelingen zu verhelfen. ;-)

Eclipse


Hat man nun seine Collection-Literale, ärgert man sich vielleicht erst mal über Eclipse, denn es macht es einem nicht leicht, statische Imports zu verwenden. Schließlich wollen wir die Literale bzw. statischen Methoden nicht immer mit ihrem Klassennamen qualifizieren.

Aber es gibt zwei Möglichkeiten, die das Leben mit Eclipse etwas einfacher machen. Möglichkeit Eins ist, das Literal zunächst mit Klassennamen zu schreiben und anschließend den "Add Import"-Shortcut Ctrl+Shift+M zu verwenden, mit dem Cursor über dem Methodennamen. Eclipse fügt dann einen statischen Import hinzu und entfernt auch gleich den qualifizierenden Klassennamen. So wird aus CollectionLiterals.List(...) schlicht ein List(...).

Noch einfach wird dies, wenn man Eclipse unter "Preferences -> Java -> Code Style -> Organize Imports" sagt, dass es statische Imports schon ab dem ersten Import per Wildcard * importieren soll. Dann kann man nach dem ersten Import auf oben genannte Weise die restlichen Literale ohne qualifizierenden Klassennamen und per Content-Assist eingeben.

Alternativ kann man seine Literalklassen auch unter "Preferences -> Java -> Editor -> Content Assist -> Favorites" eintragen, dann bietet Eclipse alle statischen Methoden dieser Klasse bei Benutzung von Content-Assist an, auch wenn man sie noch nicht importiert hat. Dies ist dann noch komfortabler als die oben beschriebene Vorgehensweise, aber auch etwas invasiver.

Man sieht also, man kann auch in Java einfach zu benutzende Collection-Literale haben, die den Code leserlicher und die Intention klarer machen.

Samstag, 12. Juni 2010

Iterator.continually und das Loan-Pattern

Heute möchte ich zwei Features von Scala vorstellen. Das Loan-Pattern und eine in Scala 2.8 neu hinzugekommene Methode der Collection-Klassen, Iterator.continually.

Ein Beispiel


Als Beispiel soll das Kopieren einer Datei dienen. Schauen wir uns zuerst das Kopieren an sich an, ohne korrekte Fehlerbehandlung, da diese den Algorithmus etwas unübersichtlich macht. Später betrachten wir, wie man es korrekt macht.

In Java könnte dies wie folgt aussehen:

public void copyUnsafe(String from, String to) throws IOException {
   FileInputStream in = new FileInputStream(from);
   FileOutputStream out = new FileOutputStream(to);
   byte[] buffer = new byte[1024];

   int count = 0;
   while((count = in.read(buffer)) != -1) {
      out.write(buffer, 0, count);
   }

   out.close();
   in.close();
}

Setzt man dies Eins zu Eins in Scala um, bekommt man Code, der dem Java-Beispiel sehr ähnlich sieht, aber nicht wirklich schön und Scala-esque ist:

@throws(classOf[IOException])
def copyUnsafe(from: String, to: String) {
  val in = new FileInputStream("source")
  val out = new FileOutputStream("target")
  val buffer = new Array[Byte](1024)

  var count = 0
  while({count = in.read(buffer); count >= 0}) {
    out.write(buffer, 0, count)
  }

  out.close()
  in.close()
}

Here comes the Iterator


Betrachten wir nun die Methode Iterator.continually. Sie ist folgendermaßen definiert:

def continually[A](elem: => A): Iterator[A]

Damit kann ein Iterator erzeugt werden, der bei jedem Aufruf von next den übergebenen Block elem neu auswertet und das Ergebnis zurück gibt.

Im einfachsten Fall kann man damit einen endlosen Iterator erzeugen, der stets das gleiche Ergebnis zurück liefert. Interessanter wird es allerdings, wenn man einen Block mit Zustand oder Seiteneffekten verwendet. In unserem Beispiel sieht das so aus:

@throws(classOf[IOException])
def copyUnsafe(from: String, to: String) {
  val in = new FileInputStream("source")
  val out = new FileOutputStream("target")
  val buffer = new Array[Byte](1024)

  Iterator.continually(in.read(buffer))
      .takeWhile(_ != -1)
      .foreach { out.write(buffer, 0 , _) }

  out.close()
  in.close()
}

Wir erzeugen hier einen Iterator, der für jeden Aufruf seiner next-Methode die read-Methode des InputStreams aufruft und die Anzahl der gelesenen Bytes als Wert liefert. Solange nicht -1 geliefert wird, holt sich takeWhile neue Elemente des Iterators. Für jedes dieser Elemente wird wiederum write auf dem OutputStream gerufen. Damit schließt sich der Kreis bzw. der Kopiervorgang.

Wie war das mit dem Loan-Pattern?


Betrachten wir nun die Änderungen, die erforderlich sind, damit mit auftretenden Exceptions richtig umgegangen wird. Es geht darum, einen geöffneten Stream auf jeden Fall auch wieder zu schließen, um etwaige Betriebssystemressourcen freizugeben.

Hier möchte ich anmerken, dass es sehr leicht passiert, die copy-Methode fehlerhaft zu implementieren. Erschreckend ist, dass bei einer Google-Suche nach "java copy file" die ersten drei Treffer Beispiele zeigen, die im Falle von Exceptions die geöffneten Streams entweder gar nicht, oder nur teilweise wieder schließen.

Betrachten wir nun eine korrekte Java-Fassung:

public void copy(String from, String to) throws IOException {
  FileInputStream in = new FileInputStream(from);
  try {
    FileOutputStream out = new FileOutputStream(to);
    try {
      byte[] buffer = new byte[1024];
      int count = 0;
      while ((count = in.read(buffer)) != -1) {
        out.write(buffer, 0, count);
      }
    } finally {
      out.close();
    }
  } finally {
    in.close();
  }
}

Dies ist nicht allzu schön, da zwei geschachtelte try-finally-Blöcke notwendig sind. Aber können wir es in Scala besser machen? Ja! Dazu wenden wir das Loan-Pattern an. Zunächst schreiben wir uns folgende Helfer-Methode:

def use[T <: { def close(): Unit }](closable: T)(f: T => Unit) {
  try {
    f(closable)
  }
  finally {
    closable.close()
  }
}

Dieser Methode werden ein Closable und eine Funktion f übergeben, die selbst ein Closable als Parameter erwartet. Ein Closable ist so definiert, dass es schlicht eine close-Methode haben muss. Die Funktion f wird zunächst mit dem übergebenen Closable aufgerufen und anschließend wird sichergestellt, dass dessen close-Methode aufgerufen wird.
Der Funktion f wird also das Closable "geliehen", aber das Erzeugen und Aufräumen wird anderweitig sichergestellt. Daher der Name Loan-Pattern.

Gut, und wie sieht nun die fertige copy-Methode aus?

@throws(classOf[IOException])
def copy(from: String, to: String) {
  use(new FileInputStream(from)) { in =>
    use(new FileOutputStream(to)) { out =>
      val buffer = new Array[Byte](1024)
      Iterator.continually(in.read(buffer))
          .takeWhile(_ != -1)
          .foreach { out.write(buffer, 0 , _) }
    }
  }
}

Und die Moral von der Geschicht?


Dieser Code ist kompakter als das Java-Äquivalent und drückt in meinen Augen auch besser aus, was die Methode leistet. Vielleicht muss man sich erst an die Verwendung von Methoden wie use gewöhnen, aber hat man dies einmal getan, möchte man die damit einhergehende Vereinfachung und Sicherheit nicht mehr missen.

Denjenigen, denen Iterator.continually gefallen hat, kann ich nur empfehlen sich einmal die Methoden iterate und tabulate anzuschauen. Diese drei Methoden stehen übrigens auch auf dem Objekt Stream zur Verfügung, um entsprechende Streams zu erzeugen.