Laziness in Haskell

Haskell ist eine lazy-evaluierte Sprache. Der GHC-Compiler implementiert diese Semantik, indem Ausdrücke nur so weit evaluiert werden wie ihr Ergebnis tatsächlich gebraucht wird. Im Gegensatz dazu steht die strikte (engl. eager) Evaluation, bei welcher Ausdrücke immer sofort und vollständig ausgewertet werden.

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 =
  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 y nicht 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 =
  let x = *THUNK*
      y = *THUNK*
  in putStrLn (show x)

Der Ausdruck putStrLn (show x) möchte nun den Wert unseres Thunks ausgeben. 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 =
  let list = [error "Fehler", 2 + 3, 5, 6 - 1]
  in putStrLn (show (length list)) -- => 4

Trotz dem error in der Liste läuft das Programm und liefert das korrekte Ergebnis. Intuitiv ist natürlich klar: Um die Länge einer Liste auszurechnen, können uns die tatsächlichen Elemente in der Liste egal sein. Der Haskell Compiler erfüllt genau diese Intuition. Zuerst ersetzt er die Liste durch einen Thunk:

main =
  let list = *THUNK*
  in putStrLn (show (length list))

Statt nun aber den *THUNK* vollständig zu evaluieren (und hierbei auch den error zu triggern), wird zuerst nur die Listenstruktur evaluiert: list wird zum Wert x:xs = *THUNK* : *THUNK*. Der Ausdruck length x:xs benötigt nicht den Wert von x, sondern liefert rekursiv 1 + length xs. Weder der Thunk x noch irgendein anderes Listenelement wird jemals ausgewertet.

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

Mit der nicht-strikten Evaluation ergeben sich eine Reihe von Vorteilen beim Entwickeln. Einige sind direkt offensichtlich, während andere sich erst nach längerer Zeit offenbaren.

Neue Strukturen

Durch die standardmäßige Laziness können in Haskell leicht rekursive Datenstrukturen zum Einsatz kommen. Ob unendliche Listen oder Baumstrukturen: Geschickte rekursive Definitionen ermöglichen es, beliebig komplexe und noch so verschachtelte Strukturen zu definieren und effizient zu verwenden.

Beim Sieb des Eratosthenes zum Beispiel, werden Primzahlen ermittelt indem aus einer Liste aller natürlichen Zahlen schrittweise alle vielfachen von kleineren bereits identifizierten Primzahlen entfernt werden. Was in der Liste dann übrig bleibt sind nurnoch Zahlen ohne kleinere Vielfache, also Primzahlen. Dieses Vorgehen kann dank Lazy-Evaluation elegant als Einzeiler ausgedrückt werden:

import Data.List.Ordered (minus, unionAll)

primes = 2 : 3 : minus [5,7..] (unionAll [[p*p, p*p+2*p..] | p <- tail primes])

Die Liste primes ist eine unendliche Liste aller Primzahlen und ein Ausdruck wie take 100 primes liefert uns entsprechend die ersten hundert Primzahlen.

Solche Definitionen zu durchdringen und den hierdurch anders strukturierten Code zu verstehen ist jedoch nicht einfach. Häufig entsteht hierbei eine komplett neue Sichtweise auf unser Programm. In seinem Paper „Why Functional Programming Matters“ erläutert John Hughes wie Lazy-Evaluation die Modularisierung von Programmen ermöglicht. Dies führt uns zum nächsten Punkt:

Strukturelles Umdenken

Laziness führt 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 xs = or $ map p xs

Die Definition der Funktion ist einleuchtend: Wir applizieren das Prädikat p auf Elemente einer Liste xs, und überprüfen anschließend, ob das Prädikat an mindestens einer Stelle True liefert. In einer Sprache mit strikter Evaluation würde hier sofort ein Problem auftreten: Der Ausdruck map p xs 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 strikter 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 das Prädikat p nur so oft evaluiert wird, wie es gerade nötig ist.

Natürlich kann mit ein wenig Geschick und der manuellen Einführung von Thunks auch in einer strikten Sprache ein effizientes any implementiert werden, aber der Punkt ist: Bei Lazy-Evaluation erledigt der Compiler diese Aufgaben für uns. Code bleibt effizient und übersichtlich und die Ausdrucksstärke der Sprache nimmt zu. Denn tatsächlich 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.

Performance

Bei den einführenden Beispielen zur Laziness hat sich auch gezeigt: Oft können unnötige Evaluierungen umgangen werden.

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 sinnlose 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.

Nicht immer perfekt - die Nachteile

Zum einen kann es durch die häufig nach hinten verzögerte Auswertung von unserem Code zu enormen Schwierigkeiten beim Verständnis von Exceptions führen. Nicht selten treten diese an unerwarteten Stellen auf und benötigen ein gewisses Verständnis der zugrundeliegenden Laziness zum Debuggen.

Auch ist der Speicherbedarf 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 dann unerwartet viel Speicher.

Und schließlich kann Laziness auch die Performance-Vorhersage erschweren: Während bei strikten 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 strikten 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.