Quickie: Scala Parallel Collections

Ich bin gerade dabei mir die aktuelle Version der scala.collection.parallel._ anzuschauen (ist im nightly) und prompt habe ich einen Bug gefunden. Der Fehler tritt in ParArray[T], sowie ParSeq[T] auf und betrifft die Methode foldLeft. Offenbar verschluckt die Methode ab und an ein paar Werte, so dass gelegentlich ein falsches Ergebnis herauskommt. Kleines Beispiel:

import scala.collection.parallel.mutable._
val a = ParArray(0 until 10: _*)
for(i <- 0 until 10) println("Should be: " + a.sum + " is: " + a.foldLeft(0)(_+_))

Dieser Code liefert folgende (oder ähnliche) Ausgabe:

Should be: 45 is: 45
Should be: 45 is: 43
Should be: 45 is: 38
Should be: 45 is: 38
Should be: 45 is: 41
Should be: 45 is: 40
Should be: 45 is: 21
Should be: 45 is: 45
Should be: 45 is: 45
Should be: 45 is: 45

Wie man sehen kann sind es teilweise gravierende Unterschiede. Auch schön sehen kann man es anhand eines Strings:

import scala.collection.parallel.mutable._
val a = ParArray("foobar": _*)
for(i <- 0 until 10) println(a.foldLeft("")(_+_))

Ausgabe:

oo
fboor
fbooar
fobr
fboar
fboar
fbooar
fbooar
fbooar
baro

Hier ist nicht nur zu sehen, dass teilweise über 50% der Elemente komplett ignoriert werden, sondern dass auch noch die Reihenfolge absolut willkürlich ist. Tauscht man in beiden Fällen das foldLeft durch ein foldRight erhält man die zu erwartenden Ergebnisse.

Ich werde mir die Parallel Collections noch weiter ansehen und ggf. weitere Fehler oder Merkwürdigkeiten hier posten.


So long

Tail Recursion

Mein erster Eintrag in diesem Blog soll sich mit dem Thema Tail Recursion beschäftigen, da ich in letzter Zeit häufig bemerke, dass es ein Thema ist, mit dem viele Programmierer noch nicht wirklich vertraut sind.

Was ist Tail Recursion eigentlich?

Tail Recursion ist eine Form der Rekursion, in der kein Stack aufgebaut werden muss. In diesem Artikel möchte ich darauf eingehen, warum Tail Recursion benutzt werden sollte und wie man Iterationen und normale Rekursionen in Tail Recursion umgebaut werden können.


Warum ist Tail Recursion besser als eine Iteration?

In den meisten Fällen lassen sich Rekursionen einfacher lesen und schreiben als Iterationen. Einige Sprachen verzichten auch vollkommen auf Schleifen, z.B. rein funktionale Sprachen, in denen es keine mutable States gibt, sich somit also auch keine Abbruchkriterien sinnvoll nutzen lassen.

Wie funktioniert Tail Recursion?

Wie bereits erwähnt wird bei einer Tail Recursion kein Stack aufgebaut, was daran liegt, dass der letzte Ausdruck der Funktion nur der Rekursionsaufruf ist. Weitere Aufrufe müssen vor dem Rekursionsauruf ausgeführt werden. Ein kleines Beispiel in Scala sollte das verdeutlichen:

Die erste Funktion ist nicht Tail Recursive, da der letzte Aufruf die Addition von i und dem Rekursionsaufruf ist.

def rec(i: Int): Int = if(i <= 0) 0 else rec(i-1) + i;

Die Funktion lässt sich einfach in eine Tail Recursive Variante abändern, in dem man das Ergebnis einfach als Parameter mitschleift und zum Schluss zurückgibt. Um eine Manipulation dieses Parameters zu verhindern schreiben wir uns einfach einen Helper, der von außen nicht sichtbar ist.

def tailrec(i: Int) = {
  def helper(i: Int,j: Int): Int = if(i<=0) j else helper(i-1, j+i)
  helper(i,0)
}

Noch deutlicher wird es, wenn man die erste Funktion in Clojure schreibt, da man hier sehr schön sieht, dass der letzte Aufruf die Addition ist:

(defn rec
  ([i]
    (if (<= i 0) 
      0 
      (+ i (rek (- i 1)))
    )))

Der Vollständigkeit halber auch noch einml die Tail Recursion in Clojure:

(defn tailrec
  ([i]
    (defn helper
      ([i j]
        (if (<= i 0)
          j
          (recur (- i 1) (+ j i)))))
    (helper i 0)))

Und wie sieht das im Programm aus?

Statt die Funktion noch einmal aufzurufen werden bei einer Tail Recursion nur die Parameter geändert und dann zum Anfang der Funktion gesprungen, was auch der Grund dafür ist, dass kein Stack aufgebaut wird.



Ich hoffe meine Ausführung ist einigermaßen verständlich. Für Kritik und Lob bin ich immer gerne zu haben ;-)