Warum ist das Konzept der Lazy Evaluation sinnvoll?

Eine verzögerte Auswertung von Ausdrücken kann dazu führen, dass ein Programmierer die Kontrolle über die Reihenfolge verliert, in der sein Code ausgeführt wird. Ich habe Probleme zu verstehen, warum dies von einem Programmierer akzeptiert oder gewünscht wird.

Wie kann dieses Paradigma verwendet werden, um vorhersehbare Software zu erstellen, die wie beabsichtigt funktioniert, wenn wir keine Garantie haben, wann und wo ein Ausdruck ausgewertet wird?

Viele der Antworten beziehen sich auf unendliche Listen und Leistungssteigerungen aus nicht bewerteten Teilen der Berechnung, aber hier fehlt die größere Motivation für Faulheit: Modularität .

Das klassische Argument findet sich in der vielzitierten Veröffentlichung "Why Functional Programming Matters" (PDF-Link) von John Hughes. Das Schlüsselbeispiel in diesem Artikel (Abschnitt 5) ist das Spielen von Tic-Tac-Toe mit dem Alpha-Beta-Suchalgorithmus. Der entscheidende Punkt ist (S. 9):

[Lazy evaluation] macht es praktisch, ein Programm als Generator zu modularisieren, der eine große Anzahl möglicher Antworten erstellt, und einen Selektor, der die entsprechende Antwort auswählt.

Das Tic-Tac-Toe-Programm kann als eine Funktion geschrieben werden, die den gesamten Spielbaum ab einer bestimmten Position generiert und eine separate Funktion, die ihn verbraucht. Zur Laufzeit generiert dies nicht den gesamten Spielbaum, sondern nur die Teile, die der Konsument tatsächlich benötigt. Wir können die Reihenfolge und Kombination, in der Alternativen hergestellt werden, ändern, indem wir den Verbraucher wechseln. Der Generator muss nicht gewechselt werden.

In einer eifrigen Sprache können Sie es nicht so schreiben, weil Sie wahrscheinlich zu viel Zeit und Speicher für die Erstellung des Baums aufwenden würden. So endest du entweder:

1. Erzeugung und Verbrauch in einer Funktion zusammenfassen;
2. Schreiben eines Produzenten, der nur für bestimmte Verbraucher optimal funktioniert;
3. Implementieren Sie Ihre eigene Version von Faulheit.

Wie kann dieses Paradigma verwendet werden, um vorhersehbare Software zu erstellen, die wie beabsichtigt funktioniert, wenn wir keine Garantie haben, wann und wo ein Ausdruck ausgewertet wird?

Wenn ein Ausdruck nebenwirkungsfrei ist, wirkt sich die Reihenfolge, in der die Ausdrücke ausgewertet werden, nicht auf ihren Wert aus, sodass das Verhalten des Programms von der Reihenfolge nicht beeinflusst wird. Das Verhalten ist also perfekt vorhersehbar.

Jetzt sind Nebenwirkungen eine andere Sache. Wenn Nebenwirkungen in beliebiger Reihenfolge auftreten könnten, wäre das Verhalten des Programms tatsächlich unvorhersehbar. Dies ist aber eigentlich nicht der Fall. Faule Sprachen wie Haskell legen Wert darauf, referenziell transparent zu sein, dh sicherzustellen, dass die Reihenfolge, in der Ausdrücke ausgewertet werden, sich niemals auf das Ergebnis auswirkt. In Haskell wird dies erreicht, indem alle Vorgänge mit vom Benutzer sichtbaren Nebenwirkungen innerhalb der E / A-Monade erzwungen werden. Dies stellt sicher, dass alle Nebenwirkungen genau in der von Ihnen erwarteten Reihenfolge auftreten.

Wenn Sie mit Datenbanken vertraut sind, ist ein sehr häufiger Weg, Daten zu verarbeiten:

• Stellen Sie eine Frage wie select * from foobar
• Wenn mehr Daten vorhanden sind, gehen Sie wie folgt vor: Holen Sie sich die nächste Ergebnisreihe und verarbeiten Sie sie

Sie können nicht steuern, wie und auf welche Weise das Ergebnis generiert wird (Indizes? Vollständige Tabellenscans?) Oder wann (sollten alle Daten auf einmal oder schrittweise generiert werden, wenn Sie dazu aufgefordert werden?). Alles was Sie wissen ist: Wenn es mehr Daten gibt, erhalten Sie diese, wenn Sie danach fragen.

Lazy Evaluation ist ziemlich ähnlich. Angenommen, Sie haben eine unendliche Liste definiert als dh. die Fibonacci-Folge - wenn Sie fünf Zahlen benötigen, erhalten Sie fünf berechnete Zahlen; Wenn Sie 1000 benötigen, erhalten Sie 1000. Der Trick ist, dass die Laufzeit weiß, was wo und wann bereitzustellen ist. Es ist sehr, sehr praktisch.

(Java-Programmierer können dieses Verhalten mit Iteratoren emulieren. Andere Sprachen haben möglicherweise etwas Ähnliches.)

Fragen Sie in Ihrer Datenbank nach einer Liste der ersten 2000 Benutzer, deren Namen mit "Ab" beginnen und älter als 20 Jahre sind. Sie müssen auch männlich sein.

Hier ist ein kleines Diagramm.

You                                            Program Processor
------------------------------------------------------------------------------
Get the first 2000 users ---------->---------- OK!
                         --------------------- So I'll go get those records...
WAIT! Also, they have to ---------->---------- Gotcha!
start with "Ab"
                         --------------------- NOW I'll get them...
WAIT! Make sure they're  ---------->---------- Good idea Boss!
over 20!
                         --------------------- Let's go then...
And one more thing! Make ---------->---------- Anything else? Ugh!
sure they're male!

No that is all. :(       ---------->---------- FINE! Getting records!

                         --------------------- Here you go. 
Thanks Postgres, you're  ---------->----------  ...
my only friend.

Wie Sie an dieser schrecklichen, schrecklichen Interaktion sehen können, tut die "Datenbank" nichts, bis sie bereit ist, alle Bedingungen zu bewältigen. Die Ergebnisse werden bei jedem Schritt faul geladen und es werden jedes Mal neue Bedingungen angewendet.

Im Gegensatz zu den ersten 2000 Benutzern werden sie zurückgegeben, nach "Ab" gefiltert, zurückgegeben, nach über 20 gefiltert, zurückgegeben und nach Männern gefiltert und schließlich zurückgegeben.

Faules Laden auf den Punkt gebracht.

Eine langsame Auswertung von Ausdrücken führt dazu, dass der Designer eines bestimmten Codeteils die Kontrolle über die Reihenfolge verliert, in der der Code ausgeführt wird.

Der Designer sollte sich nicht um die Reihenfolge kümmern, in der Ausdrücke ausgewertet werden, vorausgesetzt, das Ergebnis ist dasselbe. Wenn Sie die Auswertung verschieben, können Sie möglicherweise die Auswertung einiger Ausdrücke ganz vermeiden, was Zeit spart.

Sie können die gleiche Idee auf einer niedrigeren Ebene beobachten: Viele Mikroprozessoren können Befehle in einer falschen Reihenfolge ausführen, wodurch sie ihre verschiedenen Ausführungseinheiten effizienter nutzen können. Der Schlüssel ist, dass sie Abhängigkeiten zwischen Anweisungen untersuchen und vermeiden, neu zu ordnen, wo dies das Ergebnis verändern würde.

Es gibt mehrere Argumente für eine faule Bewertung, die ich für zwingend halte

1. Modularität Mit Lazy Evaluation können Sie Code in Teile aufteilen. Angenommen, Sie haben das Problem, "die ersten zehn Kehrwerte von Elementen in einer Listenliste zu finden, sodass die Kehrwerte kleiner als 1 sind." In so etwas wie Haskell kann man schreiben

   take 10 . filter (<1) . map (1/)
   

   Dies ist jedoch in einer strengen Sprache einfach falsch, da Sie, wenn Sie es [2,3,4,5,6,7,8,9,10,11,12,0]angeben, durch Null dividieren. Siehe die Antwort von Sacundim, warum dies in der Praxis großartig ist

2. Mehr Dinge funktionieren Streng (Wortspiel beabsichtigt) beenden mehr Programme mit nicht strenger Bewertung als mit strenger Bewertung. Wenn Ihr Programm mit einer "eifrigen" Evaluierungsstrategie endet, endet es mit einer "faulen", aber das Gegenteil ist nicht wahr. Man bekommt Dinge wie unendliche Datenstrukturen (die wirklich nur ein bisschen cool sind) als spezifische Beispiele für dieses Phänomen. Weitere Programme arbeiten in faulen Sprachen.

3. Optimalität Die Call-by-Need-Auswertung ist zeitlich asymptotisch optimal. Obwohl die wichtigsten faulen Sprachen (im Wesentlichen Haskell und Haskell) kein Call-by-Need versprechen, können Sie mehr oder weniger ein optimales Kostenmodell erwarten. Strenge Analysatoren (und spekulative Bewertungen) halten den Aufwand in der Praxis niedrig. Der Weltraum ist eine kompliziertere Angelegenheit.

4. Forces Purity mit Lazy Evaluation macht den undisziplinierten Umgang mit Nebenwirkungen zum absoluten Schmerz, denn wie Sie sagen, verliert der Programmierer die Kontrolle. Das ist eine gute Sache. Die referenzielle Transparenz erleichtert das Programmieren, Refractoring und Schließen von Programmen erheblich. Strenge Sprachen unterliegen unweigerlich dem Druck, unreine Teile zu haben - etwas, dem Haskell und Clean wunderbar widerstanden haben. Das soll nicht heißen, dass Nebenwirkungen immer böse sind, aber ihre Kontrolle ist so nützlich, dass dieser Grund allein ausreicht, um faule Sprachen zu verwenden.

Angenommen, Sie haben viele teure Berechnungen im Angebot, wissen jedoch nicht, welche tatsächlich benötigt werden oder in welcher Reihenfolge. Sie könnten ein kompliziertes Mother-May-I-Protokoll hinzufügen, um den Konsumenten zu zwingen, herauszufinden, was verfügbar ist, und Berechnungen auszulösen, die noch nicht durchgeführt wurden. Oder Sie könnten einfach eine Schnittstelle bereitstellen, die sich so verhält, als wären alle Berechnungen abgeschlossen.

Angenommen, Sie haben ein unendliches Ergebnis. Die Menge aller Primzahlen zum Beispiel. Es ist offensichtlich, dass Sie die Menge nicht im Voraus berechnen können, daher muss jede Operation im Bereich der Primzahlen faul sein.

Mit Lazy Evaluation verlieren Sie nicht die Kontrolle über die Codeausführung, sie ist dennoch absolut deterministisch. Es ist jedoch schwer, sich daran zu gewöhnen.

Eine verzögerte Auswertung ist nützlich, da dies eine Methode zur Reduzierung des Lambda-Terms ist, die in einigen Fällen enden wird, in denen eine eifrige Auswertung fehlschlägt, nicht jedoch umgekehrt. Dies beinhaltet 1) wenn Sie eine Verknüpfung mit dem Berechnungsergebnis herstellen müssen, bevor Sie die Berechnung tatsächlich ausführen, z. B. wenn Sie eine zyklische Diagrammstruktur erstellen, dies jedoch im funktionalen Stil tun möchten, 2) wenn Sie eine unendliche Datenstruktur definieren, aber diesen Strukturfeed verwenden nur einen Teil der Datenstruktur verwenden.