Alles fließt!


…sagte schon der alte Heraklit, und Recht hat er!

In Java begegnen uns „Ströme“ vorwiegend bei der Ein- und Ausgabe. Scala sieht das größere Bild und macht aus den Streams eine universelle Datenstruktur ähnlich einer einfach verketteten Liste. Jetzt wollen wir diese Scala-Streams etwas genauer unter die Lupe nehmen.

In Ordnung, wie würden wir nun einen „Strom von Quadratzahlen“ in Java realisieren? Dazu würde sich sicherlich die Verwendung von Iteratoren anbieten, etwa so:

class Squares implements Iterator<Integer> {
   private int last = 0
   private int step = 1
   
   public Integer next() {
      last += step;
      step += 2;
      return last;
   }
   public boolean hasNext() { return true; }
   public void remove() { throw new IllegalArgumentException(); }
}

Tja, das funktioniert zwar, wird aber keinen Schönheitspreis gewinnen. Um damit „vernünftig“ arbeiten zu können, braucht man noch mindestens einen Iterable-Wrapper drumherum, denn nur damit kann eine foreach-Schleife etwas anfangen.

Nun der Herausforderer Scala:

def squares = {
   def loop(last:Int, delta:Int):Stream[Int] = 
       Stream.cons(last+delta, loop(last + delta, delta+2))
   loop(0,1)
}

Zuerst wird jedem, der schon mal etwas von Lisp und Konsorten gehört hat, das „cons“ auffallen. Wer es noch nicht kennt: ein Cons ist einfach ein „Listen-Knoten“, der einen Wert und die Referenz auf die restliche Liste hält. Wir haben also eine Art Liste vor uns, allerdings eine „faule“: Der rekursive Aufruf von loop in Stream.cons wird erst dann ausgeführt, wenn auch wirklich jemand darauf zugreift. Soweit ich weiß, gibt es in einigen Sprachen wie Haskell nur solche Listen.

Weiterhin fällt auf, dass es zwei ineinander geschachtelte Methoden gibt: Die äußere dient nur dem „setup“, während die innere die eigentliche Rekursion besorgt. Diese Konfiguration ist ziemlich typisch in Scala.
In Java geht so etwas nicht, es gibt zwar lokale Klassen, aber keine lokalen Methoden, was mir schon immer ziemlich seltsam vorkam: In meinem nicht ganz kurzen Programmiererleben habe ich erst ein einziges Mal eine lokale Klasse verwendet (als Key für eine HashMap), mir aber oft lokale Methoden gewünscht, die von „außen“ nicht zu sehen und schon rein optisch als Hilfsmethoden für die äußere Methode zu erkennen sind. Ein weiterer Vorteil lokaler Methoden (den man hier aber nicht erkennen kann) ist, dass diese auch Argumente und Variablen der äußeren Methode „sehen“ kann, ähnlich wie in Java innere Klassen die Member der umgebenden Klasse „sehen“ können.

Und als letzte Auffälligkeit springt das völlige Fehlen von Variablen-Deklarationen ins Auge. Wir verändern keine Daten, sondern erzeugen nur (rekursiv) neue Daten aus alten. Stream ist also – im Gegensatz zu unserem Iterator oben, unveränderlich (immutable). Wie man sieht, stört uns das nicht im Geringsten, hat aber handfeste Vorteile: Den Iterator oben sollte man tunlichst nicht zwei verschiedenen Threads in die Hand drücken. Man kann sich das Chaos vorstellen, wenn beide gleichzeitig drauflositerieren. Nicht so bei unserem Stream: Da bei jedem Schritt ein neuer Stream erzeugt wird, kann jeder Thread in seinem eigenen Tempo itererieren. Und es wird dabei nicht etwa alles doppelt berechnet, sondern ordentlich wiederverwertet: Schaut der langsamere von beiden Threads auf den „Rest“ seines Streams, ist der einfach „schon da“, weil er für den anderen Thread schon ausgerechnet worden ist. Klingt erst mal verwirrend bis schizophren, ist aber cool, weil es eben „einfach funktioniert“.

Wie verwendet man nun dieses Konstrukt? Eigentlich wie eine ganz normale Liste, nur dass man aufpassen muss, dass man auch irgendwann mal wieder aufhört. squares.take(42).foreach(println) gibt 42 Quadratzahlen aus, mit takeWhile lässt sich auch eine Bedinung angeben, so liefert squares.takeWhile(_ < 1000).foreach(println) alle Quadratzahlen kleiner 1000. Natürlich gibt es noch mehr Methoden, so ziemlich alle "üblichen" Methoden (map, flatMap, foreach, drop, dropWhile, append usw.) sind verfügbar. Allerdings gibt es einen kleinen Haken:

squares.filter(_ % 10 == 6).takeWhile(_ < 1000)
//--> res0: Stream[Int] = Stream(16, ?)

Eigentlich sollten wir doch jetzt alle Quadratzahlen kleiner 1000, die auf 6 enden, bekommen, oder? Nun, Faulheit ist bekanntlich ansteckend, und so ist sowohl unser filter als auch unser takeWhile so faul geworden, uns nur den ersten Wert zu liefern. Wie bekommt man nun den Rest? Indem man den Stream mittels force oder toList in eine fleißigere Struktur, nämlich eine Liste, umwandelt:

squares.filter(_ % 10 == 6).takeWhile(_ < 1000).toList
//--> res1: List[Int] = List(16, 36, 196, 256, 576, 676)

Für "zyklische" Streams gibt es übrigens ein ganz besonders einfaches Idiom:

def trafficLight:Stream[String] =
   Stream("red", "yellow", "green", "yellow") append trafficLight

Auch append agiert hier "faul", deshalb gibt es keine Endlos-Schleife (genauer gesagt gibt schon eine, nur erst dann, wenn ich wirklich versuche, alle Elemente abzurufen).

Nachdem wir nun soviel von der Unendlichkeit der Streams geredet haben, sollte ich zumindest noch erwähnen, dass man Streams auch beenden kann. Stream(2,3,4,5) ist z.B. von Natur aus "endlich", aber auch selbstgebastelte Streams lassen sich abschnippeln, z.B. indem man bei Stream.cons als zweites Argument Stream.empty übergibt (was dem Nil in einer Liste entspricht).

Sooo, auch der strömendste Erguss muss mal ein Ende haben, vorzugsweise bevor alle Leser eingeschlafen sind. Vielen Dank für eure Aufmerksamkeit!

Advertisements

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