Teil 2: Funktionale Programmierung

Game of Life mit Scala – das Tutorial 2

Heiko Seeberger

Inzwischen sollte es sich bei fast allen Java-Entwicklern herumgesprochen haben, dass Scala eine sehr zukunftsträchtige Sprache für die Java Virtual Machine ist. Daher lassen wir jetzt einmal die ganze Prosa bei Seite und machen uns die Hände schmutzig, um selbst ein Gefühl dafür zu bekommen, wie sich Scala eigentlich anfühlt. In diesem zweiteiligen Tutorial bauen wir Schritt für Schritt eine Beispielanwendung und lernen dabei viele wichtige Grundlagen der Sprache kennen.

Im ersten Teil dieses Tutorials haben wir wichtige Scala-Werkzeuge kennengelernt und uns Scala von der objektorientierten Seite her genähert. Damit konnten wir für unsere Beispielanwendung, eine idiomatische und einfache Implementierung des Game of Life [1], bereits die Zellen programmieren. Zur Erinnerung enthält der Kasten „Game of Life: Spielregeln“ nochmals die Spielregeln. Heute wollen wir uns den Generationen zuwenden und dabei insbesondere die Möglichkeiten des funktionalen Programmierens mit Scala kennenlernen.

Game of Life: Spielregeln

Unser Spielfeld ist ein unendliches Gitter. Jedes Gitterquadrat stellt eine Zelle dar, die entweder tot oder lebendig sein kann. Die Gesamtheit aller Zellen zu einem bestimmten Zeitpunkt nennen wir Generation. Wir ermitteln die nächste Generation auf Basis der aktuellen anhand der folgenden Regeln:

  • Eine lebendige Zelle mit zwei oder drei lebendigen Nachbarn bleibt am Leben
  • Eine lebendige Zelle mit weniger als zwei lebendigen Nachbarn stirbt an Einsamkeit
  • Eine lebendige Zelle mit mehr als drei lebendigen Nachbarn stirbt an Überbevölkerung
  • Eine tote Zelle mit genau drei lebendigen Nachbarn wird wiedergeboren

Das gesamte Beispielprojekt ist Open Source unter der Eclipse Public License [2] veröffentlicht und kann auf Github [3] eingesehen oder heruntergeladen werden. Wer Git verwendet, kann sogar anhand der Commit-Historie alle Schritte einzeln nachvollziehen.

Collections

Generationen stellen die Gesamtheit aller Zellen zu einem bestimmten Zeitpunkt dar. Dies führt uns direkt zur Collection Library, die ganz hervorragend dazu geeignet ist, den funktionalen Charakter von Scala zu demonstrieren. Abbildung 1 zeigt wichtige Vertreter der Collection-Hierarchie. Zuoberst finden wir Traversable mit knapp 100 (!) Methoden. An dieser Vielzahl können wir erkennen, dass Scala Collections sehr mächtig sind, was für funktionale Programmiersprachen typisch ist.

Abb. 1: Wichtige Collections

Eine Generation beim Game of Life wollen wir anhand ihrer lebendigen Zellen beschreiben. Wir erstellen also die neue Klasse Generation mit dem Klassenparameter/Feld aliveCells vom Typ Set[Cell]:

package com.weiglewilczek.gameoflife
class Generation(val aliveCells: Set[Cell] = Set.empty)

Hier fallen zwei Dinge auf: Erstens sind Collections in Scala typisiert. Das ist auch kein Wunder, schließlich gehen auch die Java Generics auf Martin Odersky zurück, den „Vater“ von Scala. Zweitens geben wir ein leeres Set als Default-Wert vor, ein neues Feature von Scala 2.8. Damit können wir eine Generation auch ohne aliveCells-Argument anlegen:

scala> val generation = new Generation
generation: com.weiglewilczek.gameoflife.Generation = ...
scala> generation.aliveCells
res0: Set[com.weiglewilczek.gameoflife.Cell] = Set()

Es ist auch in Scala guter Stil, Preconditions zu definieren und zu überprüfen. Hier wollen wir kein null für den aliveCells-Parameter zulassen. Dazu verwenden wir die Methode require, die im Singleton-Objekt Predef enthalten ist, dessen Member vom Scala Compiler automatisch importiert werden. Wird die angegebene Bedingung verletzt, so wird eine IllegalArgumentException geworfen: require(aliveCells != null, „aliveCells must not be null!“).

Collections filtern

Um gemäß den Spielregeln von einer Generation zur nächsten zu gelangen, müssen wir für eine Zelle unter anderem die lebendigen Nachbarn bzw. deren Anzahl ermitteln. Mit der Methode Cell.neighbours haben wir bereits die halbe Miete. Nun müssen wir noch bestimmen, welche von diesen Nachbarzellen lebendig sind. Dazu setzen wir jetzt erstmalig funktionale Programmierung ein, indem wir die Collection-Methode filter aufrufen. Diese erwartet kein „normales“ Argument, sondern eine Funktion. Funktionen ähneln Methoden, denn sie können mit Argumenten aufgerufen werden und geben ein Resultat zurück. Allerdings sind sie nicht wie Methoden an Objekte gebunden, sondern sind, ganz im Sinne von „Alles ist ein Objekt“, selbst Objekte. Ebenso wie für Zahlen oder Strings gibt es auch für Funktionen so genannte Literale, also die Möglichkeit, Werte „einfach hinzuschreiben“. Die von filter erwartete Funktion hat einen Parameter vom gleichen Typ, mit dem die Collection parametrisiert ist, und gibt ein Boolean zurück. In unserem Fall müssen wir also eine Funktion bereitstellen, die als Parameter eine Cell hat:

private def aliveNeighbours(cell: Cell) =
  cell.neighbours filter { neighbour => aliveCells contains neighbour }

Wir sehen, dass Funktionsliterale mit dem Pfeilsymbol notiert werden. Links davon stehen die Parameter, in unserem Fall nur einer, und rechts davon der Rumpf. Dank der Type Inference können wir wieder darauf verzichten, die Typen anzugeben.

Wir können auch eine noch kürzere Notation verwenden. Die filter-Methode benötigt eine Funktion Cell => Boolean, und die contains-Methode des Set aliveCells hat genau diese Signatur. Zwar sind Methoden keine Funktionen, doch wir können jede Methode zu einer Funktion machen, indem wir statt der Parameterliste einen Unterstrich schreiben. In diesem Fall nimmt uns der Scala Compiler sogar diese Arbeit ab, sodass wir einfach Folgendes schreiben können:

private def aliveNeighbours(cell: Cell) =
  cell.neighbours filter aliveCells.contains

Neben den lebendigen Nachbarn benötigen wir auch die toten Nachbarzellen. Der Code ist fast derselbe wie für aliveNeighbours. Da wir hier nicht nur die contains-Methode aufrufen, sondern mit der Negation zusätzliche Logik ausführen, müssen wir die „ausführliche“ Notation für das Funktionsliteral verwenden:

private def deadNeighbours(cell: Cell) =
  cell.neighbours filter { neighbour => !(aliveCells contains neighbour) }

Damit sieht unsere Generation erst einmal wie in Listing 1 dargestellt aus.

Listing 1: Generation.scala
package com.weiglewilczek.gameoflife
class Generation(val aliveCells: Set[Cell] = Set.empty) {
  require(aliveCells != null, "aliveCells must not be null!")
  private def aliveNeighbours(cell: Cell) =
    cell.neighbours filter aliveCells.contains
  private def deadNeighbours(cell: Cell) =
    cell.neighbours filter { neighbour => !(aliveCells contains neighbour) }
}
Geschrieben von
Heiko Seeberger
Kommentare

Schreibe einen Kommentar

Deine E-Mail-Adresse wird nicht veröffentlicht.