Wie Lazy Computing funktioniert

Ursprünglicher Autor: Heinrich Apfelmus
  • Übersetzung
  • Tutorial
Die kleine Lambda entschied, dass die Reinigung des Zimmers auf später verschoben werden könnte.

Lazy Computing ist eine häufig verwendete Technik, wenn ein Computer Haskell-Programme ausführt. Sie machen unseren Code einfacher und modularer, können aber auch Verwirrung stiften, insbesondere wenn es um die Speichernutzung geht, und werden zu einer häufigen Falle für Anfänger. Zum Beispiel ein harmlos aussehender Ausdruck
foldl (+) 0 [1..10^8]
benötigt Gigabyte Speicher für die Berechnung.

In diesem Tutorial möchte ich erklären, wie verzögerte Berechnungen funktionieren und was sie für die Laufzeit und den Speicherbedarf von Haskell-Programmen bedeuten. Ich beginne die Geschichte mit den Grundlagen der Graphenreduktion und diskutiere anschließend die strikte Linksfaltung, das einfachste Beispiel für das Verstehen und Beseitigen von Speicherlecks.

Das Thema Lazy Computing wurde in vielen Lehrbüchern angesprochen (zum Beispiel im Buch von Simon Thompson „Haskell - Das Handwerk der funktionalen Programmierung“ ), aber Informationen darüber scheinen im Netzwerk immer noch problematisch zu sein. Ich hoffe, dass meine Führung zur Lösung dieses Problems beiträgt.

Lazy Computing ist ein Kompromiss. Einerseits helfen sie uns, den Code modularer zu gestalten. Andererseits ist es möglicherweise nicht vollständig nachvollziehbar, wie die Berechnung in einem bestimmten Programm durchgeführt wird - es gibt immer geringfügige Unterschiede zwischen der Realität und Ihrer Meinung dazu. Am Ende des Artikels werde ich Empfehlungen geben, was in solchen Situationen zu tun ist. Also fangen wir an!


Grundlagen: Grafikverkleinerung


Ausdrücke, Zählungen und Redexes


Zum Ausführen von Haskell-Programmen müssen Ausdrücke ausgewertet werden. Die Grundidee dahinter heißt Anwenden einer Funktion . Lass eine Funktion gegeben sein
square x = x*x

Wir können den Ausdruck berechnen
square (1+2),

Ersetzen Sie squaredie linke Seite der Definition durch die rechte Seite, bis Sie den Variablenwert xfür das aktuelle Argument erhalten.
square (1+2)
=> (1+2)*(1+2)

Hier werden zwei Funktionen verwendet: +und*
(1+2)*(1+2)
=> 3*(1+2)
=> 3*3
=> 9

Bitte beachten Sie, dass wir in diesem Fall zweimal rechnen müssen (1+2). Es ist jedoch klar, dass die Antworten tatsächlich dieselben sind, da beide Ausdrücke mit demselben Argument verbunden sind x.

Um unnötige Duplikationen zu vermeiden, verwenden wir eine Methode namens Graph Reduction . Grundsätzlich kann jeder Ausdruck als Grafik dargestellt werden. In unserem Beispiel ist dies wie folgt:
Bild
Jeder Block ist mit der Verwendung der entsprechenden Funktion verknüpft, deren Name in ein weißes Feld geschrieben ist und deren graue Felder Argumente angeben. Diese grafische Notation ähnelt der Darstellung eines Ausdrucks mit Zeigern auf Speicherzellen durch den Compiler.

Jede vom Programmierer definierte Funktion entspricht einer Verkleinerungsregel. Die Regel für lautet beispielsweise squarewie folgt: Ein
Bild
eingekreister Kreis xersetzt einen Untergraphen. Hinweis: Beide Argumente der Multiplikationsfunktion verweisen auf einen einzelnen Teilgraphen. Diese Art der Verwendung ist im Allgemeinen der Schlüssel zur Vermeidung von Duplikaten.

Jede Subgraphen entsprechende Regel genannt abgekürzt sind Ausdruck (reduzierbar Ausdruck) oder redex (redex) der Kürze halber. Wo immer wir einen Redex treffen, können Sie ihn kürzen und das ausgewählte Rechteck aktualisieren, das der Regel entspricht. In unserem Beispiel gibt es zwei Redexes: Entweder Funktion squareoder Addition können reduziert werden (+).
Bild
Wenn wir mit dem Redex beginnen squareund dann die Berechnung mit dem Redex der Addition fortsetzen, erhalten wir die Kette
Bild
Bei jedem Schritt wird der farblich hervorgehobene Redex aktualisiert. In der vorletzten Spalte wird ein neuer Redex angezeigt, der der Multiplikationsregel zugeordnet ist. Wenn wir diese Reduktion durchführen, erhalten wir das Endergebnis 9.

Normalform und schwache Überschrift Normalform


Wenn der Ausdruck (Graph) keine Redexes enthält, d.h. Daran lässt sich nichts reduzieren, die Sache ist erledigt. Wenn dies geschieht, sagen wir, dass der Ausdruck in normaler Form vorliegt . Dies ist das Endergebnis der Berechnung. Im vorherigen Beispiel war die Normalform die einzige Zahl vertreten durch Graf
Bild
Aber wie Designer Just, Nothingoder Listen von Designern :und []auch auf Normalform reduziert. Außerdem sehen sie wie Funktionen aus, aber da sie durch eine Deklaration dargestellt werden dataund keine rechte Seite haben, gibt es für sie keine Reduktionsregel. Ein Diagramm ist beispielsweise eine
Bild
normale Listenform 1:2:3:[].

Grundsätzlich gibt es zwei weitere Anforderungen an ein Diagramm, damit es als normal bezeichnet werden kann. Erstens muss es endlich sein und zweitens darf es keine Zyklen haben . Das Gegenteil dieser Bedingungen findet sich manchmal in der Rekursion. Zum Beispiel ein Ausdruck definiert als
ones = 1 : ones

korreliert mit einem zyklischen Graphen,
Bild
hat keine Redexes, ist aber auch nicht normal: Der Ende der Liste zeigt rekursiv auf die Liste selbst, was zu einer Endlosschleife führt.

In Haskell wird die normale Form normalerweise nicht vollständig angezeigt. Außerdem hören wir am häufigsten auf, wenn der Graph eine schwache Kopfnormalform (WHNF) erreicht. Ein Graph befindet sich in WHNF, wenn sein oberster Knoten ein Konstruktor ist . Beispiel: Der Ausdruck (7+12):[]oder
Bild
befindet sich in WHNF, weil sein oberster Knoten ein Listenkonstruktor ist (:). Und dies ist keine normale Form, da das erste Argument einen Redex enthält.

Auf der anderen Seite wird jeder Graph aufgerufen, der nicht in WHNF enthalten istkein berechneter Ausdruck oder Konverter . Ein Ausdruck, der mit einem Konstruktor beginnt, befindet sich in WHNF, aber seine Argumente können leicht nicht berechnet werden.

Ein sehr interessantes Beispiel für ein Diagramm in WHNF ist das Diagramm der onesoben genannten Funktion . Am Ende ist das oberste Element der Konstruktor. Bei Haskell können wir endlose Listen erstellen und bearbeiten! Sie eignen sich hervorragend, um den Code modularer zu gestalten.

Berechnungsreihenfolge, Lazy Computing


Oft enthält ein Ausdruck mehrere Redexes. Wie grundlegend ist die Reihenfolge, in der wir sie reduzieren werden?

Eine der Verkleinerungsordnungen, die als heftige Berechnung bezeichnet wird , berechnet die Argumente einer Funktion auf ihre normale Form, bevor sie selbst verkleinert wird. Diese Strategie wird in den meisten Programmiersprachen verwendet.

Haskell-Compiler verwenden jedoch normalerweise eine andere Berechnungsreihenfolge, die als Lazy bezeichnet wirdwenn zuallererst die oberste Anwendung einer Funktion reduziert wird. In diesem Fall müssen möglicherweise einige Argumente berechnet werden, jedoch nur in der erforderlichen Menge. Stellen Sie sich eine Funktion vor, die durch mehrere Gleichungen mithilfe des Mustervergleichs definiert wird. Für jedes von ihnen werden die Argumente von links nach rechts ausgewertet, bis ihr oberer Knoten einen Konstruktor enthält, der dem Muster entspricht. Wenn der Vergleich mit einer regulären Variablen erfolgt, werden die Argumente nicht ausgewertet. Wenn das Modell ein Konstruktor ist, bedeutet dies, dass an WHNF berechnet wird.

Ich hoffe, dass ein Beispiel dieses Konzept verdeutlicht. Es sei eine Funktion gegeben (&&), die ein logisches I implementiert. Ihre Definition lautet wie folgt:
(&&) :: Bool -> Bool -> Bool
True  && x = x
False && x = False

Abhängig vom Wert des ersten Arguments wird es durch zwei Reduzierungsregeln dargestellt: Trueoder False.
Bild

Bild
Betrachten Sie nun den Ausdruck
('H' == 'i') && ('a' == 'm')


Bild

Dargestellt als beide Argumente sind Redexes. Die erste Gleichung der Funktion (&&)prüft, ob das erste Argument mit dem Konstruktor übereinstimmt True. Lazy Calculation beginnt also mit dem Reduzieren des ersten Arguments: Das
Bild

zweite Argument wird nicht berechnet, da die oberste Anwendung der Funktion bereits ein Redex ist. Lazy Computing startet die Reduktion immer am obersten Knoten, was wir anhand der Regel für die Funktion tun werden (&&). Wir bekommen
Bild
diesen Ausdruck in normaler Form - daher ist alles fertig!

Bitte beachten Sie, dass, wenn Sie die Anwendung reduzieren(&&)So schnell wie möglich müssen Sie nie nach dem Wert des zweiten Arguments suchen, wodurch sich die Gesamtzeit verringert. Einige imperative Sprachen verwenden einen ähnlichen Trick, der als " Kurzschlussberechnung " bezeichnet wird. In der Regel ist diese Funktionalität jedoch in die Sprache „eingenäht“ und funktioniert nur für logische Operationen. In Haskell kann diese Methode auf alle Funktionen angewendet werden - es ist nur eine Folge von verzögerten Berechnungen.

Im allgemeinen Fall unterscheidet sich die mit faulen Berechnungen erhaltene Normalform nie vom Ergebnis der Ausführung des gleichen Ausdrucks durch ihren energischen Kollegen. In diesem Sinne spielt es also keine Rolle, in welcher Reihenfolge die Reduzierung erfolgt. Lazy-Berechnungen werden jedoch in weniger Schritten ausgeführt und können sich mit zyklischen (unendlichen) Graphen befassen, auf die für intensive Berechnungen nicht zugegriffen werden kann.

Textansicht


Ich hoffe, dass Ihnen die visuelle Darstellung von Ausdrücken in Form von Diagrammen dabei geholfen hat, ein allgemeines Konzept des Lazy Computing zu entwickeln, da das Konzept des Redex und die erforderliche Verkleinerungsreihenfolge deutlich hervorgehoben werden. Für bestimmte Berechnungen ist das Zeichnen von Bildern jedoch etwas mühsam. Um den Verkleinerungsprozess zu verfolgen, arbeiten wir normalerweise mit Textdarstellung unter Verwendung der Haskell-Syntax.

Diagramme erleichtern die Visualisierung gängiger Untergraphen. In einer Textdarstellung müssen wir allgemeine Ausdrücke bezeichnen, indem wir ihnen Namen mit einem Schlüsselwort geben let. Das erste Beispiel zum Reduzieren eines Ausdrucks square (1+2)sieht beispielsweise so aus:
square (1+2)
=>  let x = (1+2) in x*x
=>  let x = 3 in x*x
=>  9

Mit der Syntax let … inkönnen Sie einen allgemeinen Ausdruck erstellen x = (1+2). Beachten Sie, dass eine verzögerte Auswertung zuerst die Funktion reduziert squareund erst dann das Argument bewertet x.

Unser zweites Beispiel - logisches UND - wird zu
('H' == 'i') && ('a' == 'm')
=>  False && ('a' == 'm')
=>  False

In diesem Fall müssen keine Unterausdrücke gemeinsam verwendet werden, sodass letder Code kein Schlüsselwort enthält.

Ab sofort verwenden wir nur noch die Textdarstellung.

Zeit & Erinnerung


Lassen Sie uns nun untersuchen, wie sich die Verwendung von Lazy Computing auf die Betriebszeit und den Speicherbedarf von Haskell-Programmen auswirkt. Wenn Sie sich bisher nur mit heftigen Berechnungen befasst haben, dann machen Sie sich auf Überraschungen gefasst (besonders wenn es um das Gedächtnis geht).

Zeit


Wie viele Schritte sind erforderlich, um einen Ausdruck zu bewerten? Die Antwort auf die Frage nach der Leistungsfähigkeit von Computern ist einfach: Für jede Anwendung einer Funktion addieren wir die für die Berechnung ihrer Argumente erforderliche Zeit mit der Zeit, die für die Ausführung des Funktionskörpers selbst erforderlich ist. Aber was ist mit Lazy Computing? Zum Glück ist die Situation hier günstig. Wir haben die folgende Obergrenze:

Theorem : Lazy Computing führt niemals mehr Rechenschritte durch als energetisches Computing.

Dies bedeutet, dass wir bei der Analyse der Ausführungszeit des Algorithmus immer so tun können, als würden die Argumente „energetisch“ berechnet. Sie können beispielsweise den Code des Sortieralgorithmus in Haskell umwandeln und sicherstellen, dass das Ergebnis die gleiche (und manchmal bessere) algorithmische Komplexität aufweist wie sein energetisches Doppel.

Lazy Computing erfordert jedoch einen gewissen Verwaltungsaufwand. Für Anwendungen mit hoher Leistung, wie z. B. Bildverarbeitung oder digitale Simulationen, ist es vorteilhaft, nicht faul zu sein und näher an der Hardware zu bleiben. Ansonsten führt uns das Mantra "einfacher und modularer Code" zu faulen Berechnungen. Durch die Optimierung eines Compilers mit der Bezeichnung " Thread-Zusammenführung " soll beispielsweise die Leistung von Operationen mit Arrays wie bei einer modularen, listenartigen Schnittstelle gesteigert werden. Diese Idee ist in der Vektorbibliothek enthalten .

Die Erinnerung


Leider ist die Situation mit der Speichernutzung nicht so einfach wie mit der Zeit. Der Kern des Problems besteht darin, dass die für einen nicht berechneten Ausdruck erforderliche Speichermenge erheblich von der Menge abweichen kann, die von seiner normalen Form belegt wird. Der Ausdruck benötigt umso mehr Platz, je mehr Knoten das Diagramm enthält. Zum Beispiel
((((0 + 1) + 2) + 3) + 4)

Benötigt mehr Speicher als normal 10. Ein Gegenbeispiel ist der Ausdruck
enumFromTo 1 1000

deren vertrautere Syntax wie folgt aussieht [1..1000]. Diese Anwendung der Funktion besteht nur aus drei Knoten, weshalb sie deutlich weniger Speicher benötigt als eine Liste 1:2:3:…:1000:[]mit mindestens tausend Elementen.

Wenn eine Option mit einem nicht berechneten Ausdruck außer Kontrolle gerät, tritt ein Speicherverlust auf . Die Lösung besteht darin, den gesamten Berechnungsprozess so zu steuern, dass er so schnell wie möglich abgeschlossen wird. Haskell hat einen Kombinator für diesen Zweck.
seq :: a -> b -> b

Wie aus Typdeklarationen hervorgeht, gibt es im Wesentlichen nur das zweite Argument zurück und verhält sich eher wie eine Funktion const. Der Ausdruck wird jedoch seq x yzuerst als WHNF ausgewertet x, wonach wir weiterarbeiten werden y. Im Gegenteil, das const x yzweite Argument wird überhaupt ynicht angesprochen, sondern xunverzüglich berechnet.

Stellen Sie sich ein typisches Beispiel vor, das die Verwendung seqzeigt und das jeder Haskell-Programmierer kennen sollte: Strikte Linksfaltung . Es sei die Aufgabe gegeben, alle Zahlen von 1bis zu summieren 100. Wir werden dies unter Verwendung des Akkumulationsparameters tun, d.h. wie in der linken Faltung
foldl (+) 0 [1..100]

Als Referenz: Die Foldl- Funktion ist in Haskell Prelude als definiert
foldl :: (a -> b -> a) -> a -> [b] -> a
foldl f a []     = a
foldl f a (x:xs) = foldl f (f a x) xs

Der Berechnungsprozess ist wie folgt:
foldl (+) 0 [1..100]
=>  foldl (+) 0 (1:[2..100])
=>  foldl (+) (0 + 1) [2..100]
=>  foldl (+) (0 + 1) (2:[3..100])
=>  foldl (+) ((0 + 1) + 2) [3..100]
=>  foldl (+) ((0 + 1) + 2) (3:[4..100])
=>  foldl (+) (((0 + 1) + 2) + 3) [4..100]
=>  …

Wie Sie sehen, wächst der akkumulierende Parameter von Zweig zu Zweig - es kommt zu einem Speicherverlust. Um dies zu vermeiden, müssen Sie sicherstellen, dass die Batterie im WHNF ständig vorhanden ist. Die nächste Version foldlmacht diesen Trick:
foldl' :: (a -> b -> a) -> a -> [b] -> a
foldl' f a []     = a
foldl' f a (x:xs) = let a' = f a x
                    in seq a' (foldl' f a' xs)

Es befindet sich im Modul Data.List . Nun sieht der Berechnungsprozess so aus:
foldl' (+) 0 [1..100]
=>  foldl' (+) 0 (1:[2..100])
=>  let a' = 0 + 1 in seq a' (foldl' (+) a' [2..100])
=>  let a' = 1 in seq a' (foldl' (+) a' [2..100])
=>  foldl' (+) 1 [2..100]
=>  foldl' (+) 1 (2:[3..100])
=>  let a' = 1 + 2 in seq a' (foldl' (+) a' [3..100])
=>  let a' = 3 in seq a' (foldl' (+) a' [3..100])
=>  foldl' (+) 3 [3..100]
=>  …

Während der Berechnung hat der Ausdruck eine konstante Größe. Die Verwendung seqstellt sicher, dass der WHNF-Akkumulationsparameter abgeleitet wird, bevor der nächste Listeneintrag berücksichtigt wird.

In der Regel ist eine Funktion foldlanfällig für Speicherverluste, daher ist es besser, foldl'oder zu verwenden foldr.

Übrigens: In einer Sprache mit intensiven Berechnungen für die Aufsummierung von Ziffern von 1bis können 100Sie niemals Code wie den obigen schreiben. Tatsächlich wird in diesem Fall [1..100]die Liste zuerst in die normale Form berechnet , was genauso viel Speicher beansprucht wie die ineffiziente Versionfoldl. Wenn Sie das Problem effizient lösen möchten, müssen Sie eine rekursive Schleife schreiben. Bei Haskell können Sie dies jedoch mit einer Anwendung eines Allzweck-Kombinators für eine Liste tun [1..100], die "nach Bedarf" berechnet wird. Dies ist ein weiteres Beispiel dafür, wie Code modularer gestaltet werden kann.

Eine weitere wichtige Lehre, die aus dem betrachteten Problem gezogen werden kann, ist die folgende: Tatsächlich passiert die Berechnung, die ich gezeigt habe, nicht ganz so. Wenn wir die Auflistung [n..m]als definieren
enumFromTo n m = if n < m 
then n : enumFromTo (n+1) m 
else []

dann sieht die Reduzierung des WHNF tatsächlich so aus:
[1..100]
=>  1 : [(1+1)..100]

d.h. Das neue erste Argument ist nicht 2, sondern ein Ausdruck (1+1). Nicht, dass es einen großen Unterschied gegeben hätte, aber denken Sie daran: Sie müssen sehr vorsichtig sein, wenn Sie Lazy Calculations genau nachzeichnen - sie tun nie genau das, was Sie sich vorstellen. Der tatsächliche Code für enumFromTo unterscheidet sich geringfügig von dem oben gezeigten. Beachten Sie insbesondere, dass es sich [1..]um eine Liste von Zahlen handelt, die nicht in WHNF enthalten sind.

Im Prinzip habe ich so lange darüber gesprochen, um zu einer einfachen Schlussfolgerung zu gelangen: Mit trägen Berechnungen ist es nicht möglich, die Spur im Detail zu verfolgen, außer bei sehr einfachen Beispielen. Daher ist die Analyse der Speichernutzung durch Haskell-Programme keine leichte Aufgabe. Mein Rat: Tun Sie etwas nur, wenn ein Speicherleck vorliegt. Zu diesem Zweck würde ich empfehlen, Profilerstellungstools zu verwenden, um herauszufinden, was gerade passiert. Sobald das Problem formuliert wird, wie Werkzeuge Invarianten Raum , und seqsie können die Berechnung der entsprechenden Ausdrücke WHNF, unabhängig von den kleinen Details durchführen lazy evaluation garantieren.

Das ist alles, was ich über Lazy Computing und Speichernutzung erzählen wollte. Es gibt ein weiteres wichtiges Beispiel für ein Leck, das ich nicht angesprochen habe, das aber nicht weniger lesbar ist:
let small' = fst (small, large) in … small' …

Ein Ausdruck small'behält einen Verweis auf einen Ausdruck bei, largeauch wenn er von einer Funktion verworfen wird fst. Vielleicht sollten Sie den Ausdruck small'in WHNF irgendwie auswerten, damit Sie den verwendeten Speicher problemlos nutzen können large.

Jetzt auch beliebt: