Sind "normale Reihenfolge" und "Call-by-Name" dasselbe?

9

Ich habe das Buch Struktur und Interpretation von Computerprogrammen studiert und in Abschnitt 1.1.5 Das Substitutionsmodell für die Verfahrensanwendung erklärt der Autor die Konzepte der normalen Ordnung und der anwendbaren Ordnung , die ich meines Erachtens gut verstanden habe.

Nun, ich nehme einen Kurs über Coursera genannt Funktion Programmierprinzipien in Scala und es der Professor Martin Odersky (die viel von seinem Kurs basiert auf dem Buch oben zitierten) erklärt die gleichen Konzepte unter den Namen von Call-by-Name und Call- nach Wert .

In seinem Kurs sagt Professor Odersky, dass das Substitutionsmodell auf dem Lambda-Kalkül basiert. Deshalb habe ich ein Buch in meiner Bibliothek konsultiert. Eine Einführung in die funktionale Programmierung Obwohl Lambda-Kalkül und auf Seite 22 definiert der Autor die Begriffe als anwendbare Reihenfolge und normale Reihenfolge . Interessanterweise sagt er in seiner Definition, dass die anwendbare Reihenfolge wie Pascals Call-by-Value ist, während die normale Reihenfolge wie Algols Call-by-Name ist.

Die Verwendung der Worte "ist wie" in seiner Erklärung hat mich zweifeln lassen. Also meine Fragen:

  • Sind diese beiden Begriffe gleichwertig oder gibt es subtile Unterschiede?
  • Kann ich das eine oder andere austauschbar verwenden, ohne das Risiko einzugehen, einen Fehler in der Bedeutung zu machen, die sie vermitteln?
  • Gibt es Gründe, die Sie kennen und die die Existenz unterschiedlicher Terminologie rechtfertigen, um sich auf dasselbe zu beziehen?
edalorzo
quelle
1
In diesem Wikipedia-Artikel heißt es, dass im Gegensatz zur normalen Reihenfolge "eine Call-by-Name-Strategie nicht innerhalb des Körpers einer nicht angewendeten Funktion ausgewertet wird". Es wird jedoch kein spezifisches Zitat gegeben.
Chrisaycock
4
Nur als Referenz wissen Sie, dass Martin Odersky der Hauptdesigner von Scala ist, oder?
KChaloux

Antworten:

7

Normale Auftragsbewertung und Call-by-Name-Bewertung sind nicht ganz dasselbe. Bei der Bewertung in normaler Reihenfolge wird die äußerste Funktion vor einem ihrer Argumente ausgewertet, und diese Argumente werden nur bei Bedarf ausgewertet. Bei der Call-by-Name-Auswertung werden die Argumente effektiv in den Hauptteil der äußersten Funktion kopiert, und dann wird diese Funktion ausgewertet. In beiden Fällen wird die äußerste Funktion vor den Argumenten technisch ausgewertet. Bei einem reinen Call-by-Name werden die Argumente jedoch jedes Mal ausgewertet, wenn sie verwendet werden (entweder null, eins oder viele Male). In normaler Reihenfolge werden die Funktionsargumente mindestens nur dann ausgewertet, wenn sie zum ersten Mal benötigt werden (normalerweise null oder einmal).

Daher lässt die normale Reihenfolgebewertung die Möglichkeit offen, die Argumente als Optimierung zu speichern (manchmal als Call-by-Need bezeichnet), während Call-by-Name dies nicht tut. Man könnte also sagen, dass die Call-by-Name-Bewertung ein Sonderfall der normalen Auftragsbewertung ist. Mit anderen Worten, die Bewertung der normalen Reihenfolge bezieht sich auf den allgemeinen Ansatz der Bewertung einer Funktion vor ihren Argumenten, während sich die Bewertung nach Namen auf eine bestimmte Technik zur Implementierung der Bewertung der normalen Reihenfolge bezieht.

Als Beispiel f(x, y) = sqrt(x*x + y*y)könnten wir zwei Möglichkeiten zur Implementierung f(a+b, c+d)mit normaler Auftragsbewertung haben:

Auswendig gelernt:

t1 = a+b;
t2 = c+d;
return sqrt(t1*t1 + t2*t2);

Call-by-Name:

return sqrt((a+b)*(a+b) + (c+d)*(c+d));

Wie Sie sehen können f(random(1,100), ask_user_for_value()), haben die beiden ein sehr unterschiedliches Verhalten , wenn der Aufruf von f andere Funktionsaufrufe (dh ) enthält. Die gespeicherte Version quadriert eine einzelne Zufallszahl und fragt den Benutzer nur einmal nach einem Wert, während die Call-by-Name-Version zwei Zufallszahlen multipliziert und den Benutzer zweimal nach einem Wert fragt.

Um mehr über diese Konzepte zu erfahren, empfehle ich, die Wikipedia-Seite zur Bewertungsstrategie und /cs/7702/applicative-order-and-normal-order-in-lambda-calculus zu lesen .

Randall Cook
quelle
Danke, @edalorzo. Wenn Sie es wertvoll fanden, ziehen Sie bitte in Betracht, es zu akzeptieren. :)
Randall Cook