Warum ist das Konzept der Lazy Evaluation sinnvoll?

30

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?

akashchandrakar
quelle
10
In den meisten Fällen spielt es einfach keine Rolle. Für alle anderen kann man einfach die Strenge durchsetzen.
Cat Plus Plus
22
Der Sinn rein funktionaler Sprachen wie haskell ist, dass Sie sich nicht darum kümmern müssen, wenn Code ausgeführt wird, da er frei von Nebenwirkungen ist.
Bitmaske
21
Sie müssen aufhören, über "Ausführen von Code" nachzudenken und über "Berechnen von Ergebnissen" nachdenken, denn das ist genau das, was Sie bei den interessantesten Problemen wirklich wollen. Natürlich müssen Programme normalerweise auch in irgendeiner Weise mit der Umgebung interagieren, aber das kann oft auf einen kleinen Teil des Codes reduziert werden. Im Übrigen können Sie rein funktional arbeiten , und Faulheit kann das Denken erheblich vereinfachen.
Leftaroundabout
6
Die Frage im Titel ("Warum Lazy Evaluation verwenden?") Unterscheidet sich sehr von der Frage im Textkörper ("Wie verwenden Sie Lazy Evaluation?"). Ersteres finden Sie in meiner Antwort auf diese verwandte Frage .
Daniel Wagner
1
Ein Beispiel, wenn Faulheit nützlich ist: In Haskell head . sorthat O(n)Komplexität durch Faulheit (nicht O(n log n)). Siehe Lazy Evaluation und Zeitkomplexität .
Petr Pudlák

Antworten:

62

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.
Sacundim
quelle
Bitte mehr Infos oder ein Beispiel. Das klingt faszinierend.
Alex Nye
1
@ AlexNye: Das John Hughes-Papier enthält weitere Informationen. Obwohl es sich um eine akademische Arbeit handelt - und daher zweifellos einschüchternd -, ist sie tatsächlich sehr zugänglich und lesbar. Wenn nicht für seine Länge, würde es wahrscheinlich als Antwort hier passen!
Tikhon Jelvis
Um diese Antwort zu verstehen, muss man vielleicht das Papier von Hughes lesen ... da ich es nicht getan habe, weiß ich immer noch nicht, wie und warum Faulheit und Modularität zusammenhängen.
Stakx
@stakx Ohne eine bessere Beschreibung scheinen sie nur zufällig miteinander verwandt zu sein. Der Vorteil von Faulheit in diesem Beispiel ist, dass ein fauler Generator alle möglichen Spielzustände erzeugen kann, aber keine Zeit / Speicher verschwendet, da nur die verbraucht werden, die passieren. Der Generator kann vom Verbraucher getrennt werden, ohne faul zu sein, und es ist möglich (wenn auch schwieriger), faul zu sein, ohne vom Verbraucher getrennt zu sein.
Izkata
@Iztaka: "Der Generator kann vom Verbraucher getrennt werden, ohne faul zu sein, und es ist möglich (wenn auch schwieriger), faul zu sein, ohne vom Verbraucher getrennt zu sein." Beachten Sie, dass Sie auf dieser Route möglicherweise einen ** übermäßig spezialisierten Generator ** haben - der Generator wurde entwickelt, um einen Verbraucher zu optimieren, und wenn er für andere wiederverwendet wird, ist er suboptimal. Ein häufiges Beispiel sind objektrelationale Mapper, die ein gesamtes Objektdiagramm abrufen und erstellen, nur weil Sie eine Zeichenfolge aus dem Stammobjekt möchten. Faulheit vermeidet viele solche Fälle (aber nicht alle).
Sacundim
32

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.

sepp2k
quelle
15
Aus diesem Grund unterstützen standardmäßig nur Sprachen mit "erzwungener Reinheit" wie Haskell Faulheit überall. Sprachen wie Scala, bei denen es um "ermutigte Reinheit" geht, müssen vom Programmierer ausdrücklich angegeben werden, wo sie Faulheit wollen, und es ist Sache des Programmierers, sicherzustellen, dass die Faulheit keine Probleme verursacht. Eine Sprache, die standardmäßig faul ist und unauffällige Nebenwirkungen hat, ist in der Tat schwer vorhersehbar zu programmieren.
Ben
1
Sicherlich können auch andere Monaden als IO Nebenwirkungen verursachen
jk.
1
@jk Nur E / A kann externe Nebenwirkungen verursachen.
Dave4420
@ dave4420 ja aber das sagt diese antwort nicht
jk.
1
@jk In Haskell eigentlich nein. Keine Monade außer IO (oder einer, die auf IO aufbaut) hat Nebenwirkungen. Und das nur, weil der Compiler IO unterschiedlich behandelt. IO wird als "Unveränderlich Aus" betrachtet. Monaden sind nur eine (clevere) Möglichkeit, eine bestimmte Ausführungsreihenfolge sicherzustellen (Ihre Datei wird also erst gelöscht, nachdem der Benutzer "yes" eingegeben hat).
scarfridge
22

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

samthebrand
quelle
Guter Punkt. Zum Beispiel Collection2.filter()implementiert (wie auch die anderen Methoden aus dieser Klasse) ziemlich faul Auswertung: Das Ergebnis "sieht aus wie" ein gewöhnliches Collection, aber die Reihenfolge der Ausführung ist möglicherweise nicht intuitiv (oder zumindest nicht offensichtlich). Außerdem gibt es yieldin Python (und ein ähnliches Feature in C #, an das ich mich nicht erinnern kann) noch näher an der Unterstützung von Lazy Evaluation als an einem normalen Iterator.
Joachim Sauer
@JoachimSauer in C # seine Rendite zurückgeben, oder natürlich können Sie die vorgefertigten Linq-Operatoren verwenden, von denen etwa die Hälfte faul sind
jk.
+1: Für die Erwähnung von Iteratoren in einer imperativen / objektorientierten Sprache. Ich habe eine ähnliche Lösung für die Implementierung von Streams und Stream-Funktionen in Java verwendet. Unter Verwendung von Iteratoren könnte ich Funktionen wie take (n), dropWhile () für einen Eingabestream unbekannter Länge verwenden.
Giorgio
13

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.

sergserg
quelle
1
Dies ist meiner Meinung nach eine wirklich miese Erklärung. Leider habe ich nicht genug Repräsentanten auf dieser speziellen SE-Site, um sie abzustimmen. Der eigentliche Grund für eine träge Auswertung ist, dass keines dieser Ergebnisse tatsächlich produziert wird, bis etwas anderes bereit ist, sie zu konsumieren.
Alnitak
Meine gepostete Antwort sagt genau dasselbe wie Ihr Kommentar.
Sergserg
Das ist ein sehr höflicher Programmprozessor.
Julian
9

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.

Caleb
quelle
5

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.

Philip JF
quelle
2

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.

ddyer
quelle
1

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.

permeakra
quelle