2009-03-16 11 views
6

Es scheint, als gäbe es viele Beispiele für clevere Dinge, die in einer lazy-evaluated Sprache getan werden, die in einer Umgebung mit strenger Auswertung nicht getan werden können. Zum Beispiel unendliche Listen in Haskell oder replacing every element in a tree with the tree's minimum value in one pass.Wo sind die cleveren Einsatzmöglichkeiten einer strengen Evaluation?

Gibt es Beispiele für clevere Dinge in einer streng bewerteten Sprache, die in einer lazy-evaluated Sprache nicht leicht gemacht werden kann?

+1

Theorie beiseite, kann es clevere Anwendungen der strengen Bewertung in faulen Sprachen geben. Haskell hat das "!" Strictness-Annotation für Datentypen zur Verwendung bei der Erzwingung der Auswertung von Termen, bei denen die Faulheit nur zu einem Speicherblob verursacht hätte. Gute Beispiele dafür, wann man die Faulheit abschalten kann, sind sicherlich "clevere Anwendungen der strengen Bewertung". – rndmcnlly

Antwort

4

Nun, nein, mehr oder weniger per definitionem. In einer Lazy-Evaluation-Sprache, sollten Sie per Definition bekommen die gleichen Ergebnisse, die Sie mit kräftigen bekommen würden (sind Menschen wirklich "streng" jetzt?) Bewertung, mit Ausnahme der für die Verzögerung der Auswertung bis benötigt, Storage Implikationen und das alles. Also, wenn Sie ein anderes Verhalten außer dafür bekommen könnten, wäre es ein Fehler.

+1

Eigentlich Faulheit hat etwas andere Semantik zu Strenge. Zum Beispiel ist in einer strengen Sprache "const 1 undefined" nicht definiert, aber in einer faulen Sprache wird sie mit 1 bewertet. Der Grund dafür ist, dass eine strenge Sprache das "undefinierte" bewertet, eine faule Sprache jedoch nicht. –

0

In einer strengen Auswertungssprache wie C# ist es möglich, eine faule Auswertung zu erreichen, indem ein Thunk auf einen Wert (Func) anstatt auf den Wert selbst zurückgesetzt wird.

public Func<int, int> Y(Func<Func<int, int>, Func<int, int>> f) 
{ 
    return x => f(Y(f))(x); 
} 

wäre prägnanter Diese Erklärung in einer faulen Umgebung:

Y f = f (Y f) 
+0

Dies trifft nicht auf Ihr Y-Combinator-Beispiel zu, aber als Randbemerkung: Um eine Call-by-Need-Bewertung (wie in Haskell) in C# zu erhalten, sollte 'Lazy ', nicht 'Func ' (Letzterer berechnet den Wert bei jeder Verwendung neu. – FunctorSalad

0

als Charlie Martinwrote, das Ergebnis als ein Beispiel in dem Bau des Y-Combinator in C# kann auf diese Art und Weise durchgeführt werden von strengem und faulen Programm sollte gleichwertig sein. Der Unterschied liegt in der zeitlichen und räumlichen Beschränkung und/oder sprachlichen Ausdruckskraft. Neben dem Leistungseffekt der Faulheit für unnötige Werte kann man in fauler Sprache leicht neue Sprachkonstrukte ohne zusätzliches Sprachkonzept einführen (z. B. Makro in LISP). Wie auch immer, Faulheit kann dich gebissen How does Haskell tail recursion work? und dasselbe denke, kann komplizierter sein als in strenger Sprache. (Sollte nicht hakell Compiler erkennen, dass compute +1 ist billiger als make thunk

0

Ich Programm in Erlang ein bisschen, und finde den Mangel an fauler Bewertung, die ich zurück in der Universität ziemlich frustrierend gelernt.

Ich habe kurz auf einige der Euler-Probleme des Projekts geschaut, insbesondere diejenigen, die sich mit Primzahlen befassen.

Mit Lazy Evaluation können Sie eine Funktion haben, die eine Liste aller Primzahlen zurückgibt, aber nur die tatsächlich gewünschten zurückgibt. Daher ist es wirklich einfach zu sagen "gib mir die ersten n Primzahlen".

Ohne faule Bewertung, neigen Sie dazu, mit einer mehr einschränkende "geben Sie mir eine Liste aller Primzahlen zwischen 1 und n".

5

Nein; Es gibt einige Dinge, die Sie tun können * mit fauler Bewertung (AKA-Normal-Ordnungs-Reduktion oder Links-äußerster-Reduktion), die Sie nicht mit strenger Bewertung machen können, aber nicht umgekehrt.

Der Grund dafür ist, dass lazy evaluation in gewisser Weise ist die ‚allgemeinste‘ Art und Weise, zu bewerten, die als bekannt ist:

Der Computational Adequacy Satz: Wenn einig Reihenfolge der Auswertung beendet und erzeugt ein bestimmtes Ergebnis, dann wird auch die faule Auswertung beendet und das gleiche Ergebnis erzeugt.

* (bitte beachten Sie, dass wir nicht reden über Turing-Äquivalenz hier sind)

+0

Trotz der Bewertung als beste Antwort ist Ihre Aussage falsch, siehe meine Antwort unten. – Ingo

8

Die wichtigsten Dinge, die Sie leicht in einer eifrigen (streng) Sprache tun und nicht in einer faulen Sprache:

  • Predict aus dem Quellcode AKTUALISIER die Zeit- und Raumkosten Ihrer Programme

  • Permit Nebenwirkungen, einschließlich konstanter Zeit te von änderbaren Arrays, die es einfacher macht einige Algorithmen schnell

Meiner Meinung nach ist der große Vorteil von einer eifrigen Sprache zu implementieren, dass es viel einfacher ist, den Code zu bekommen, wie Sie wollen, und es ausführen Es gibt sehr wenige Leistungsfallen, bei denen eine kleine Änderung des Codes zu einer enormen Leistungsänderung führt.

Nachdem ich das gesagt habe, ziehe ich es vor, komplizierte Dinge in Haskell zu schreiben.

-5

Die Antwort, die als beste bewertet wurde, leidet leider an einem logischen Fehler. Aus dem Satz Porges geht nicht hervor, dass man in einer faulen Sprache mehr tun kann. Der gegenteilige Beweis besteht darin, dass alle Programme in faulen Sprachen zu Entsprechungen in strengen Sprachen kompiliert werden (die zu Assemblerprogrammen kompiliert werden) oder von einem in einer strengen Sprache geschriebenen Interpreter ausgeführt werden (und ja, der Interpreter ist) ein Assemblerprogramm ultimativ).

+0

Dies ist Turing-Äquivalenz ... Der Fragesteller fragte, ob es irgendwelche "sauberen Tricks" gebe, die mit einer strengen Sprache gemacht werden könnten, die mit einem faulen nicht gemacht werden kann; Dieser Satz sagt nein, weil faule Auswertung die allgemeinste Eval-Reihenfolge ist. (Wenn wir uns das nur aus einem POV mit der Reihenfolge der Reduktion ansehen.) – porges

+0

Ich stimme dir natürlich zu, aber du hast gesagt "dass es einige Dinge gibt, die du tun kannst * mit fauler Bewertung ... die du nicht machen kannst mit strenger Bewertung ". Was bleibt falsch. Natürlich ist die Verwendung einer faulen Liste in Haskell einfacher als in Java, aber das war nicht die Frage. – Ingo

2

Die offensichtlichste Verwendung von Faulheit in einer Alltagssprache ist die "if" -Anweisung, wo nur ein Zweig der Bedingung ausgeführt wird.

Das Gegenteil einer rein nicht-strikten (faulen) Sprache wäre eine rein strikte Sprache.

Es gibt mindestens einen Fall, in dem "rein strikt" von Vorteil ist, nämlich branch predication.

Raute Umschreibung des verlinkten Artikels:

Vor langer Zeit in der Welt des CPUs, Anweisungen geladen execute wurden, wenn die Verzweigungsbedingung getestet wurde. Irgendwann wurden Befehlspipelines hinzugefügt, um die Ladezeit zu reduzieren. Der Nachteil war, dass eine CPU nicht wusste, welchen Zweig sie laden musste, also würde sie standardmäßig einen laden. Wenn der Zweig in die andere Richtung ging, würde die Pipeline blockieren, während der Code für den anderen Zweig geladen wurde.

Die Lösung ist, beide Zweige zu laden, führen Sie beide Zweige aus, dann sagt Ihnen das Ergebnis der bedingten, welches Zweig Ergebnis zu halten, und welche wegwerfen. Dann bekommst du keine Pipeline-Stände.

Dies ist mein liebstes (nur?) Beispiel für den Nutzen einer rein strikten Sprache.

1

'Hello, World' Programme in den Sinn kommen, oder alle Dinge im Zusammenhang mit Nebenwirkungen im Grunde genommen.

In einer strengen Bewertung kann die Auswertung einer Expression leicht einen Nebeneffekt haben, da Sie einen klaren Überblick über die Reihenfolge der Auswertung und damit die Reihenfolge der Nebenwirkungen haben, die normalerweise bei Nebenwirkungen wichtig sind. Das ist der grundlegende Vorteil einer strengen Evaluation und auch, warum die meisten Sprachen es haben. Und warum auch leistungsorientierte Sprachen wie C oft ein pass-by-value-Modell verwenden.

Beide können das gleiche tun, nur mit verschiedenen Ebenen der menschlichen Schwierigkeit, können Sie perfekt unendliche Listen in einer strengen Sprache simulieren, und Sie können alle Auswirkungen von Nebenwirkungen mit nicht strengen Sprachen simulieren.