Warum wird Lazy Evaluation nicht überall eingesetzt?

32

Ich habe gerade gelernt, wie eine verzögerte Evaluierung funktioniert, und habe mich gefragt, warum die verzögerte Evaluierung nicht in jeder derzeit produzierten Software angewendet wird. Warum noch eifrige Auswertung verwenden?

John Smith
quelle
2
Hier ist ein Beispiel dafür, was passieren kann, wenn Sie einen veränderlichen Zustand mit einer verzögerten Auswertung mischen. alicebobandmallory.com/articles/2011/01/01/…
Jonas Elfström
2
@ JonasElfström: Bitte verwechseln Sie nicht den veränderlichen Zustand mit einer seiner möglichen Implementierungen. Der veränderbare Zustand kann mithilfe eines unendlichen, trägen Stroms von Werten implementiert werden. Dann haben Sie kein Problem mit veränderlichen Variablen.
Giorgio
In imperativen Programmiersprachen erfordert "Lazy Evaluation" eine bewusste Anstrengung des Programmierers. Die generische Programmierung in imperativen Sprachen hat dies leicht gemacht, wird aber niemals transparent sein. Die Antwort auf die andere Seite der Frage wirft eine andere Frage auf: "Warum werden nicht überall funktionierende Programmiersprachen verwendet?", Und die derzeitige Antwort lautet aus heutiger Sicht einfach "Nein".
rwong
2
Funktionale Programmiersprachen werden nicht überall aus dem gleichen Grund verwendet, aus dem wir keine Hämmer an Schrauben verwenden. Nicht jedes Problem kann einfach auf eine funktionale Eingabe-> Ausgabe-Weise ausgedrückt werden. GUI zum Beispiel ist besser dafür geeignet, auf eine zwingende Weise ausgedrückt zu werden .
ALXGTV
Weiterhin gibt es zwei Klassen von funktionalen Programmiersprachen (oder zumindest beide behaupten, funktional zu sein), die imperativen funktionalen Sprachen, z. B. Clojure, Scala und den Deklarativ, z. B. Haskell, OCaml.
ALXGTV

Antworten:

38

Eine verzögerte Bewertung erfordert einen Aufwand für die Buchhaltung. Sie müssen wissen, ob sie bereits bewertet wurde, und solche Dinge. Die eifrige Bewertung wird immer bewertet, sodass Sie es nicht wissen müssen. Dies gilt insbesondere in gleichzeitigen Kontexten.

Zweitens ist es trivial , eifrige Auswertungen in verzögerte Auswertungen umzuwandeln, indem Sie sie in ein Funktionsobjekt packen, das später aufgerufen wird, wenn Sie dies wünschen.

Drittens impliziert eine faule Bewertung einen Kontrollverlust. Was ist, wenn ich das Lesen einer Datei von einer Festplatte faul auswerte? Oder die Zeit bekommen? Das ist nicht akzeptabel.

Die eifrige Bewertung kann effizienter und kontrollierbarer sein und wird trivial in eine verzögerte Bewertung umgewandelt. Warum sollten Sie eine faule Bewertung wünschen?

DeadMG
quelle
10
Träge eine Datei von der Festplatte zu lesen ist eigentlich wirklich ordentlich - für die meisten meiner einfachen Programme und Skripte, Haskell readFileist genau das, was ich brauche. Außerdem ist die Umstellung von fauler auf eifrige Bewertung ebenso trivial.
Tikhon Jelvis
3
Stimmen Sie mit Ausnahme des letzten Absatzes allen zu. Lazy Evaluation ist effizienter, wenn eine
Kettenoperation ausgeführt wird
4
Die Fünfergesetze möchten mit Ihnen über "Kontrollverlust" sprechen. Wenn Sie reine Funktionen schreiben, die mit unveränderlichen Datentypen arbeiten, ist eine verzögerte Auswertung ein Glücksfall. Sprachen wie haskell basieren grundsätzlich auf dem Konzept der Faulheit. Es ist in einigen Sprachen umständlich, besonders wenn es mit "unsicherem" Code gemischt wird, aber Sie lassen es so klingen, als wäre Faulheit standardmäßig gefährlich oder schlecht. Es ist nur "gefährlich" in gefährlichem Code.
Sara
1
@DeadMG Nicht, wenn dir egal ist, ob dein Code terminiert oder nicht ... Was head [1 ..]gibst du in einer mit Spannung bewerteten reinen Sprache, denn in Haskell gibt es das 1?
Semikolon
1
In vielen Sprachen führt die Implementierung einer verzögerten Evaluierung zumindest zu Komplexität. Manchmal ist diese Komplexität erforderlich, und die verzögerte Evaluierung verbessert die Gesamteffizienz - insbesondere dann, wenn das, was evaluiert wird, nur bedingt benötigt wird. Schlecht gemacht, kann es jedoch zu subtilen Fehlern oder schwer zu erklärenden Leistungsproblemen kommen, die auf falschen Annahmen beim Schreiben des Codes beruhen. Es gibt einen Kompromiss.
Berin Loritsch
17

Hauptsächlich, weil fauler Code und Zustand sich schlecht vermischen und einige schwer zu findende Fehler verursachen können. Wenn sich der Status eines abhängigen Objekts ändert, kann der Wert Ihres faulen Objekts bei der Auswertung falsch sein. Es ist viel besser, wenn der Programmierer das Objekt explizit codiert, um faul zu sein, wenn er weiß, dass die Situation angemessen ist.

Nebenbei bemerkt verwendet Haskell Lazy Evaluation für alles. Dies ist möglich, da es sich um eine funktionale Sprache handelt, die keinen Status verwendet (außer in einigen Ausnahmefällen, in denen sie deutlich gekennzeichnet sind).

Tom Squires
quelle
Ja, veränderlicher Zustand + faule Bewertung = Tod. Ich glaube, die einzigen Punkte, die ich bei meinem SICP-Finale verloren habe, waren die Verwendung set!in einem faulen Schema-Interpreter. > :(
Tikhon Jelvis
3
"Lazy Code und State können sich schlecht vermischen": Es kommt wirklich darauf an, wie Sie State implementieren. Wenn Sie es mit gemeinsam genutzten veränderlichen Variablen implementieren und von der Reihenfolge der Auswertung abhängig sind, in der Ihr Status konsistent ist, haben Sie Recht.
Giorgio,
14

Lazy Evaluation ist nicht immer besser.

Die Leistungsvorteile der verzögerten Evaluierung können groß sein, aber es ist nicht schwer zu vermeiden, dass die meisten unnötigen Evaluierungen in eifrigen Umgebungen durchgeführt werden. Mit Faulheit wird dies einfach und vollständig, aber unnötige Evaluierungen im Code sind selten ein großes Problem.

Das Gute an der verzögerten Auswertung ist, dass Sie damit klareren Code schreiben können. Die zehnte Primzahl durch Filtern einer unendlichen Liste natürlicher Zahlen zu erhalten und das zehnte Element dieser Liste zu nehmen, ist eine der präzisesten und klarsten Vorgehensweisen: (Pseudocode)

let numbers = [1,2...]
fun is_prime x = none (map (y-> x mod y == 0) [2..x-1])
let primes = filter is_prime numbers
let tenth_prime = first (take primes 10)

Ich glaube, es wäre ziemlich schwierig, Dinge ohne Faulheit so präzise auszudrücken.

Aber Faulheit ist nicht die Antwort auf alles. Für den Anfang kann Faulheit nicht transparent angewendet werden, wenn der Zustand vorhanden ist, und ich glaube, dass Zustandserhalt nicht automatisch erkannt werden kann (es sei denn, Sie arbeiten beispielsweise in Haskell, wenn der Zustand ziemlich explizit ist). In den meisten Sprachen muss Faulheit also manuell erfolgen, was die Übersichtlichkeit beeinträchtigt und somit einen der großen Vorteile von Lazy Eval zunichte macht.

Darüber hinaus hat Faulheit Leistungsmängel, da sie einen erheblichen Mehraufwand für die Beibehaltung nicht bewerteter Ausdrücke mit sich bringt. Sie belegen Speicherplatz und arbeiten langsamer als einfache Werte. Es ist nicht ungewöhnlich, herauszufinden, dass Sie eifrigen Code benötigen, da die Lazy-Version sehr langsam ist und es manchmal schwierig ist, über die Leistung zu urteilen.

Es gibt keine absolut beste Strategie. Lazy ist großartig, wenn Sie besseren Code schreiben können, indem Sie unendliche Datenstrukturen oder andere Strategien nutzen, die Sie verwenden können, aber eifrig leichter zu optimieren sind.

Alex
quelle
Wäre es einem wirklich cleveren Compiler möglich, den Overhead erheblich zu verringern? oder sogar die Faulheit für zusätzliche Optimierungen ausnutzen?
Tikhon Jelvis
3

Hier ein kurzer Vergleich der Vor- und Nachteile eifriger und fauler Bewertungen:

  • Eifrige Bewertung:

    • Möglicher Overhead durch unnötiges Bewerten von Inhalten.

    • Ungehinderte, schnelle Auswertung

  • Faule Bewertung:

    • Keine unnötige Auswertung.

    • Buchhaltungsaufwand bei jeder Verwendung eines Wertes.

Wenn Sie also viele Ausdrücke haben, die niemals ausgewertet werden müssen, ist Faulheit besser. Wenn Sie jedoch nie einen Ausdruck haben, der nicht ausgewertet werden muss, ist Faulheit ein reiner Aufwand.

Lassen Sie uns nun einen Blick auf die Software der realen Welt werfen: Wie viele der Funktionen, die Sie schreiben, müssen nicht alle ihre Argumente ausgewertet werden? Gerade bei den modernen Kurzfunktionen, die nur eines tun, fällt der Anteil der Funktionen in diese Kategorie sehr gering aus. Daher würde eine verzögerte Auswertung den Buchhaltungsaufwand die meiste Zeit nur einleiten, ohne die Möglichkeit zu haben, tatsächlich etwas zu sparen.

Infolgedessen zahlt sich eine verzögerte Evaluierung im Durchschnitt einfach nicht aus, da eine eifrige Evaluierung für modernen Code besser geeignet ist.

cmaster
quelle
1
"Buchhaltungsaufwand bei jeder Verwendung eines Werts.": Ich glaube nicht, dass der Buchhaltungsaufwand größer ist, als beispielsweise in einer Sprache wie Java auf Nullverweise zu prüfen. In beiden Fällen müssen Sie eine Information überprüfen (ausgewertet / ausstehend im Vergleich zu null / nicht null), und Sie müssen dies jedes Mal tun, wenn Sie einen Wert verwenden. Also, ja, es gibt einen Overhead, aber er ist minimal.
Giorgio,
1
"Wie viele der Funktionen, die Sie schreiben, müssen nicht alle Argumente ausgewertet werden?": Dies ist nur eine Beispielanwendung. Was ist mit rekursiven, unendlichen Datenstrukturen? Können Sie sie mit eifriger Bewertung umsetzen? Sie können Iteratoren verwenden, aber die Lösung ist nicht immer so präzise. Natürlich verpassen Sie wahrscheinlich nichts, was Sie noch nie ausgiebig nutzen konnten.
Giorgio
2
"Folglich zahlt sich eine verzögerte Evaluierung im Durchschnitt einfach nicht aus, eine eifrige Evaluierung passt besser zu modernem Code.": Diese Aussage trifft nicht zu: Es kommt wirklich darauf an, was Sie implementieren möchten.
Giorgio,
1
@Giorgio Der Overhead scheint Ihnen nicht viel zu sein, aber Bedingungen sind eines der Dinge, an denen moderne CPUs scheiße sind: Ein falsch vorhergesagter Zweig erzwingt normalerweise ein vollständiges Leeren der Pipeline und wirft die Arbeit von mehr als zehn CPU-Zyklen weg. Sie wollen keine unnötigen Bedingungen in Ihrer inneren Schleife. Das Zahlen von zehn zusätzlichen Zyklen pro Funktionsargument ist für leistungskritischen Code fast so inakzeptabel wie das Codieren des Objekts in Java. Sie haben Recht, dass Sie bei einer faulen Evaluierung einige Tricks anwenden können, die Sie mit einer eifrigen Evaluierung nicht so einfach erreichen können. Die überwiegende Mehrheit des Codes benötigt diese Tricks jedoch nicht.
cmaster
2
Dies scheint eine Antwort aus Unerfahrenheit mit Sprachen mit fauler Bewertung zu sein. Was ist zum Beispiel mit unendlichen Datenstrukturen?
Andres F.
3

Wie @DeadMG feststellte, erfordert eine faule Auswertung einen Buchhaltungsaufwand. Dies kann relativ zu einer eifrigen Bewertung teuer sein. Betrachten Sie diese Aussage:

i = (243 * 414 + 6562 / 435.0 ) ^ 0.5 ** 3

Dies erfordert einige Berechnungen. Wenn ich Lazy Evaluation verwende, muss ich bei jeder Verwendung überprüfen, ob es evaluiert wurde. Befindet sich dies in einer stark genutzten engen Schleife, erhöht sich der Overhead erheblich, aber es gibt keinen Vorteil.

Mit eifriger Auswertung und einem anständigen Compiler wird die Formel zur Kompilierzeit berechnet. Die meisten Optimierer verschieben die Zuweisung gegebenenfalls aus den Schleifen, in denen sie auftritt.

Die verzögerte Auswertung eignet sich am besten zum Laden von Daten, auf die nur selten zugegriffen wird, und erfordert einen hohen Abrufaufwand. Es ist daher angemessener, Fälle als die Kernfunktionalität zu kanten.

Im Allgemeinen empfiehlt es sich, häufig verwendete Elemente so früh wie möglich zu bewerten. Lazy Evaluation funktioniert mit dieser Praxis nicht. Wenn Sie immer auf etwas zugreifen, ist eine verzögerte Auswertung lediglich mit einem zusätzlichen Aufwand verbunden. Das Kosten-Nutzen-Verhältnis bei der Verwendung der verzögerten Auswertung sinkt, wenn die Wahrscheinlichkeit, dass auf das Element zugegriffen wird, abnimmt.

Die Verwendung von Lazy Evaluation bedeutet auch eine frühzeitige Optimierung. Dies ist eine schlechte Praxis, die häufig zu Code führt, der viel komplexer und teurer ist, als dies ansonsten der Fall wäre. Leider führt eine vorzeitige Optimierung häufig dazu, dass Code langsamer als einfacher ausgeführt wird. Bis Sie den Effekt der Optimierung messen können, ist es eine schlechte Idee, Ihren Code zu optimieren.

Die Vermeidung vorzeitiger Optimierung steht nicht im Widerspruch zu guten Codierungspraktiken. Wenn keine bewährten Methoden angewendet wurden, können erste Optimierungen darin bestehen, bewährte Codierungsmethoden anzuwenden, z. B. das Verschieben von Berechnungen aus Schleifen.

BillThor
quelle
1
Sie scheinen aus Unerfahrenheit zu streiten. Ich schlage vor, Sie lesen den Artikel "Why Functional Programming Matters" von Wadler. Es wird ein Hauptabschnitt behandelt, in dem das Warum der verzögerten Auswertung erläutert wird (Hinweis: Es hat wenig mit der Leistung, der frühen Optimierung oder dem "Laden von Daten, auf die selten zugegriffen wird" und allem, was mit Modularität zu tun hat).
Andres F.
@AndresF Ich habe die Zeitung gelesen, auf die Sie sich beziehen. Ich stimme der Verwendung von Lazy Evaluation in solchen Fällen zu. Eine frühe Bewertung ist möglicherweise nicht angebracht, aber ich würde argumentieren, dass die Rückgabe des Unterbaums für den ausgewählten Zug einen erheblichen Vorteil hat, wenn zusätzliche Züge einfach hinzugefügt werden können. Der Aufbau dieser Funktionalität könnte jedoch eine vorzeitige Optimierung sein. Außerhalb der funktionalen Programmierung habe ich wichtige Probleme mit der Verwendung von Lazy Evaluation und der Nichtverwendung von Lazy Evaluation. Es gibt Berichte über erhebliche Leistungskosten, die sich aus einer verzögerten Bewertung in der funktionalen Programmierung ergeben.
BillThor
2
Sowie? Es gibt Berichte über signifikante Leistungskosten, wenn eifrige Evaluierungen verwendet werden (Kosten in Form von entweder nicht benötigten Evaluierungen oder Nichtbeendigung des Programms). Es gibt Kosten für fast jedes andere (falsch) verwendete Feature. Die Modularität selbst kann kostenpflichtig sein. Die Frage ist, ob es sich lohnt.
Andres F.
3

Wenn wir einen Ausdruck möglicherweise vollständig auswerten müssen, um seinen Wert zu bestimmen, kann eine verzögerte Auswertung ein Nachteil sein. Nehmen wir an, wir haben eine lange Liste von Booleschen Werten und möchten herausfinden, ob sie alle wahr sind:

[True, True, True, ... False]

Um dies zu tun, müssen wir uns jedes Element in der Liste ansehen , egal was passiert, daher gibt es keine Möglichkeit, die Auswertung träge abzubrechen. Wir können eine Falte verwenden, um zu bestimmen, ob alle Booleschen Werte in der Liste wahr sind. Wenn wir ein Fold-Right verwenden, das Lazy Evaluation verwendet, erhalten wir keinen der Vorteile von Lazy Evaluation, da wir uns jedes Element in der Liste ansehen müssen:

foldr (&&) True [True, True, True, ... False] 
> 0.27 secs

Eine Falte nach rechts ist in diesem Fall viel langsamer als eine strenge Falte nach links, die keine verzögerte Auswertung verwendet:

foldl' (&&) True [True, True, True, ... False] 
> 0.09 secs

Der Grund ist, dass eine strikte Fold-Left-Methode die Schwanzrekursion verwendet, dh, sie akkumuliert den Rückgabewert und baut keine große Kette von Operationen auf und speichert sie im Speicher. Dies ist viel schneller als die Lazy Fold-Funktion, da beide Funktionen ohnehin die gesamte Liste anzeigen müssen und die Fold-Funktion keine Schwanzrekursion verwenden kann. Der Punkt ist also, dass Sie das verwenden sollten, was für die jeweilige Aufgabe am besten ist.

tail_recursion
quelle
"Der Punkt ist also, dass Sie das verwenden sollten, was für die anstehende Aufgabe am besten ist." +1
Giorgio