Haskell ist eine Lazy-evaluierte Sprache. Der GHC-Compiler implementiert diese Semantik, indem Ausdrücke nur so weit evaluiert werden, wie es für das aktuelle Ergebnis nötig ist. Im Gegensatz dazu steht die Eager-Evaluation, bei welcher Ausdrücke vollständig evaluiert werden, sobald diese gebunden sind.

In diesem Artikel wollen wir uns anschauen, welche Vorteile die Laziness mit sich bringt, aber auch welche Fallstricke durch sie entstehen.

Um diesem Artikel folgen zu können, setzen wir eine Vertrautheit mit der Haskell-Syntax sowie grundlegenden Strukturen wie Listen voraus. Es gibt sogar schon eine Blogreihe zum Einstieg in Haskell.

Laziness bedeutet, Ausdrücke so spät wie möglich zu evaluieren. Aber woher weiß unser Programm, wann es einen Wert nun evaluieren muss und wann (noch) nicht?

Wird das evaluiert, oder kann das weg? - Thunks

Die Laziness von Haskell offenbart sich schon bei den einfachsten Beispielen:

main = do
  let x = 5 + 3
      y = error "Fehler" in
      putStrLn $ show x -- => 8

Das Programm läuft und liefert den Wert der Variable x. Und das obwohl wir die Variable y mit error "Fehler" initialisieren?! Das liegt daran, dass der Compiler bereits erkennt, dass wir die Variable y nicht wirklich benutzen. Er spart sich also direkt die Evaluation, weshalb das error nie zu einem Programmabbruch führt.

Man kann sich das Vorgehen des GHC wie folgt vorstellen: Jeder Ausdruck in unserem Code wird durch einen Platzhalter ersetzt. Dieser Repräsentiert einen noch nicht ausgewerteten Wert. Wir nennen diese Platzhalter Thunks. Der Code sieht dann quasi so aus:

main = do
  let x = *THUNK*
      y = *THUNK* in
      putStrLn $ show x

Der Funktionsaufruf show x möchte nun den Wert unseres Thunks in einen String umwandeln. Hierzu braucht es allerdings den tatsächlichen Wert in x… Der Thunk muss nun evaluiert werden und liefert das Ergebnis der Addition: 8.

Schauen wir uns ein weiteres Beispiel an

main = do
  let list = [5, 2 + 3, error "Fehler", 6 - 1] in
      putStrLn $ show $ length list -- => 4

Auch hier ersetzt der Compiler die Liste zuerst mit einem Thunk:

main = do
  let list = *THUNK* in
      putStrLn $ show $ length $ list

Doch wieso läuft jetzt das Programm? Beim Evaluieren des *THUNK* sollte doch der Error in der Liste auftreten, oder nicht?

Nein, denn statt unnötigerweise alle Listenelemente zu evaluieren, passiert dies zuerst nur mit der Listenstruktur: Beim Auswerten der Länge wird der Thunk der Liste so weit ausgewertet, dass die Struktur der Liste sichtbar wird. list wird zum Wert x:xs = *THUNK* : *THUNK*. Der Funktionsaufruf length x:xs benötigt nicht den Wert von x, sondern liefert rekursiv 1 + length xs. Der Thunk x muss somit nie evaluiert werden.

Wir haben nun eine grundlegende Intuition dafür bekommen, wie Haskell das Evaluieren von Ausdrücken verzögert und wenn möglich vermeidet. Aber warum denn eigentlich der ganze Aufwand?

Warum Laziness sinnvoll ist

Performance

Den ersten offensichtlichen Vorteil bietet das eben besprochene Nicht-Evaluieren von Variablen bereits: Gegeben eine Funktion crunchNumber :: Int -> Int welche, wie der Name verspricht, Zahlen crunchen muss und deshalb viel Rechenzeit benötigt. Die verschiedenen Aufrufe dieser Funktion werden im folgenden Beispiel kein einziges Mal tatsächlich ausgeführt. Somit sparen wir uns jede Menge Rechenaufwand.

main = do
  let x = crunchNumber 10 
      list = [1, 2, crunchNumber 3] in
      putStrLn $ show $ take 2 list

In einem vergangenen Blogartikel wurden rekursive Funktionsdefinitionen genutzt, um bei einem Pretty-Printer hunderte von Evaluierungen zu ersparen. Auch hier hat die Laziness von Haskell jede Menge Rechenaufwand eingespart.

Nun gut. Man könnte einwenden, dass erfahrene Entwickler solche unnötigen Ausdrücke ohnehin vermeiden. In der Praxis ist es aber oft nicht möglich, mit einer Umstrukturierung des Programmcodes unnötige Evaluationen zu verhindern. Beim Komponieren von Funktionen beispielsweise: Bei der Eager-Evaluation muss um den Wert des Ausdrucks f . g x y zu berechnen zwangsläufig zuerst g x y evaluiert werden und das Ergebnis danach an die Funktion f gegeben werden. Bei der Lazy-Evaluation können jedoch auch die in der Funktion g entstehenden Thunks an f weitergegeben werden. Falls sich im Programmverlauf dann rausstellt, dass der Wert dieser Thunks gar nicht benötigt wurde, konnte Rechenaufwand eingespart werden.

Strukturelles Umdenken

Neben Performance-Vorteilen führt Laziness auch zu einem anderen Blick auf das Programmieren selbst: Eine Lazy-Sprache ermöglicht es das Modell eines Programms, Zeile für Zeile Ausdrücke zu evaluieren, hinter sich zu lassen. Wir können schlicht nicht mehr wissen, wann ein Ausdruck genau evaluiert wird, aber solange dieser keine Seiteneffekte hat, kann uns das auch komplett egal sein. In diesem Sinne gibt es uns die Freiheit über Programme mehr als eine Beschreibung des gewünschten Resultats nachzudenken, und nicht als strikte Abfolge von Befehlen.

Wollen wir zum Beispiel die any-Funktion implementieren, können wir das auf folgende Weise tun:

any :: (a -> Bool) -> [a] -> Bool
any p = or . map p

Die Definition der Funktion ist einleuchtend: Wir applizieren das Prädikat p auf Elemente einer Liste, und überprüfen anschließend, ob das Prädikat an mindestens einer Stelle True liefert. In einer Sprache mit Eager-Evaluation würde hier sofort ein Problem auftreten: Der Aufruf map p würde zuerst evaluiert werden, und unnötigerweise das Prädikat p auf alle unsere Listenelemente anwenden. Schlimmer noch, ein Aufruf mit einer endlosen Liste any (>100) [1..] ergibt bei Eager-Evaluation gar keinen Sinn. In Haskell müssen wir uns über diese Dinge gar keine Gedanken machen, die Lazy-Evaluation sorgt hier dafür, dass p nur so oft evaluiert wird, wie es gerade nötig ist.

Natürlich kann mit ein wenig Geschick auch in einer Eager-Sprache ein effizientes any implementiert werden, aber der Punkt ist: Bei Lazy-Evaluation müssen wir uns gar nicht erst fragen, ob die gegebene Funktion eventuell unnötige oder vermeidbare Arbeit verrichtet, wir können uns sicher sein, dass sie nur das absolute Minimum an Evaluation tatsächlich durchführt.

Nicht immer perfekt

Da in diesem Beitrag nicht nur die Laziness von Haskell gelobt werden soll, wollen wir der Vollständigkeit halber einige negative Aspekte davon beleuchten:

Zum einen ist der Platzbedarf eines Lazy-Programms nur schwer vorherzusagen. Da Ausdrücke nicht direkt ausgewertet werden, sondern als Thunks im Speicher verbleiben, kann der Heap im Laufe der Programmausführung stark anwachsen. Bei diesen sogenannten Space Leaks benötigt eine eigentlich einfache Berechnung unerwartet viel Speicher.

Und schließlich kann Laziness auch die Performance-Vorhersage erschweren: Während bei Eager-Sprachen oft klar ist, wann und wie viel Arbeit ein Ausdruck verursacht, kann das in Haskell stark von der Art abhängen, wie (und wann) Werte tatsächlich benötigt werden. Manche Optimierungen, die in Eager-Sprachen trivial wären, sind hier plötzlich nicht mehr offensichtlich.

Fazit

Laziness erlaubt es uns in gewisser Weise, Programme als reine Beschreibungen zu formulieren. Berechnungen werden nur dann ausgeführt, wenn sie wirklich gebraucht werden. Um diese Eigenschaft sinnvoll zu nutzen und effizienten Code zu schreiben, muss der Entwickler sich jedoch im Klaren darüber sein, wann Ausdrücke tatsächlich evaluiert werden.

Richtig eingesetzt, macht Laziness Programme performanter und Code einfacher zu verstehen. Das macht Laziness zu einem der elegantesten Werkzeuge in der Haskell-Programmierung.