Was ist der Unterschied zwischen Reduktionsstrategien und Bewertungsstrategien?

Aus dem Artikel zur Bewertungsstrategie auf Wikipedia:

Der Begriff der Reduktionsstrategie in der Lambda-Rechnung ist ähnlich, aber unterschiedlich.

Aus dem Artikel zur Reduktionsstrategie auf Wikipedia:

Es ähnelt dem Begriff der Bewertungsstrategie in der Informatik, unterscheidet sich jedoch geringfügig davon.

Was ist der subtile Unterschied zwischen Bewertungsstrategien und Reduktionsstrategien, auf den diese beiden Artikel hinweisen? Sind es nur zwei ähnliche Konzepte aus verschiedenen Bereichen?

Eine Reduktionsstrategie ist eine Funktion von Lambda, die einen Redex (reduzierbaren Ausdruck) aus allen möglichen Redexen auswählt - je nachdem, was Sie als Redex definieren.

Informell ist eine Bewertungsstrategie die Reihenfolge, in der eine Sprache ihre Argumente bewertet. Eine Parameterübergabestrategie ist das, was die Sprache der Funktion übergibt.

Um den Zusammenhang zwischen diesen zu verstehen, lesen Sie Plotkins Artikel über Call-by-Name, Call-by-Value und den Lambda-Kalkül. Er legt klar fest, dass Sie je nach gewünschter Bewertungsreihenfolge unterschiedliche AXIOME auswählen möchten. Für Cb-Name möchten Sie das alte Beta-Axiom und für Cb-Wert möchten Sie ein Beta-Wert-Axiom. Wenn Sie das tun, funktionieren alle Metasätze für beide Geschmacksrichtungen gleich. Ich habe später (mit vielen Mitarbeitern) gezeigt, dass sich diese Idee auf alles verallgemeinert, was die Welt von PL studiert hat.

Es ist alles technisch, kein Gedicht, das interpretiert werden kann. Lies es einfach nach.

- Matthias Felleisen

ps Ich werde sagen, dass ich denke, dass es den Menschen leichter fallen wird, Plotkins Artikel aus Teil I in unserem Redex-Buch zu verstehen. Aber ja, es ist dreimal so lang.

Der Wikipedia-Artikel "Reduktionsstrategie" wird vollständig aus einer bestimmten Bearbeitung extrahiert, die von einer anonymen IP des Artikels "Bewertungsstrategie" vorgenommen wurde.

Die Ansicht, die es darstellt, ist nicht einvernehmlich, in dem Sinne, dass ich vermute, dass relativ wenige Leute auf dem Gebiet diese Antwort spontan geben werden, wenn Sie sie fragen: "Würden Sie die Namen" Reduktionsstrategie "und" Bewertungsstrategie "unterscheiden?". Ich habe es nur von Matthias Felleisen gehört, der über die Bedeutung dieser Unterscheidung unerbittlich ist - und ich gehe davon aus, dass dieser Standpunkt von anderen geteilt wird, die die Gelegenheit hatten, sich Zeit zu nehmen, um diese Punkte ausführlich mit ihm zu besprechen.

Mein derzeitiges Verständnis dieses Punktes (aber ich habe die technischen Details noch nicht vollständig untersucht) betrifft Folgendes: Hier geht es darum, ob Sie die Semantik "großer Schritt" gegenüber "kleiner Schritt" verwenden - diese Unterscheidung ist Standard und wird verstanden von allen auf dem Gebiet. Die Semantik kleiner Schritte definiert einen atomaren Reduktionsschritt, und das Ergebnis ist im Allgemeinen immer noch reduzierbar. Die Big-Step-Semantik definiert einen "großen" Reduktionsschritt, der vom Startprogramm bis zu seinem Wert reicht (oder einen reichhaltigeren "Antwort" -Typ, wenn Ihre Sprache andere beobachtbare Auswirkungen hat als die Rückgabe eines Werts, z. B. Eingabe / Ausgabe oder veränderlicher Zustand).

Wenn Sie sowohl eine Big-Step- als auch eine Small-Step-Beziehung definieren, können Sie überprüfen, ob die Big-Step-Semantik im transitiven Abschluss der Small-Step-Beziehung enthalten ist und ob sich die Small-Step-Beziehung nicht auf andere feststeckende Begriffe als reduziert diejenigen, die durch die Big-Step-Beziehung erreicht werden, oder divergieren, wenn die Big-Step-Reduktion definiert ist. Dies ist die erwartete Kohärenzbeziehung zwischen beiden.

Ich denke, dass der Wortlaut des Artikels in modernen Begriffen mehr oder weniger als "Bewertungsstrategie ist die Beziehung in großen Schritten", "Reduktionsstrategie ist die Beziehung in kleinen Schritten" beschrieben werden kann. Beachten Sie, dass es in der Diskussion im Artikel "Reduktionsstrategie" hauptsächlich um Artikel und Forschung (und vor allem um beredte Standpunkte, die beim Lesen und Schreiben entstanden sind) zwischen 1973 und 1991 geht, zu einer Zeit, als diese Begriffe gerade geboren wurden, und wahrscheinlich nicht so gut verstanden wie heute. (Die Semantik großer Schritte wurde 1987 von Kahn hervorgehoben, und eine der wichtigsten Arbeiten zur Semantik kleiner Schritte ist Wright und Felleisen, 1992)

Für die eher einfühlsame Seite, warum Felleisen auf der Wichtigkeit dieses Unterschieds besteht (das heißt, warum es mehr als nur "kleiner Schritt gegen großer Schritt, meh" gibt), ist mein derzeitiges Verständnis das Folgende: das Es wird darauf hingewiesen, dass die Semantik in kleinen Schritten als Implementierungsdetail betrachtet werden sollte. DasNach diesem Argument ist die Semantik die abstrakte Funktion, die jedes Programm seinem Wert / seiner Antwort zuordnet, und der Rest sind Implementierungsgeräte, die darauf ausgelegt sind, es zu approximieren (oder einen Grund für die durch diese Semantik induzierte Äquivalenz). Wenn wir heute einen großen Schritt sagen, denken wir an ein System von Inferenzregeln syntaktischer Natur, aber die oben diskutierte "Reduktionsstrategie" ist tatsächlich ihre Abstraktion als Abbildung. (Ich denke nicht, dass dies dem Begriff in der Praxis mehr Ausdruckskraft oder Stärke verleiht, aber es macht ihn abstrakter.)

Ich denke also, dass diese Wikipedia-Seite und Matthias Felleisen so etwas wie sagen: "Definieren Sie Ihre Bewertung nach Belieben, aber am Ende des Tages kommt es darauf an, wie Ihre Programme ihren Werten zugeordnet werden. Antworten / Verhaltensweisen, und dies sollte als "operative Semantik" bezeichnet und begründet werden. "

Beachten Sie, dass diese Position etwas gegen die derzeitige Unterscheidung zwischen "operativer Semantik" und "denotationaler Semantik" verstößt (die meiner Meinung nach eher einvernehmlich ist, aber möglicherweise eine kulturelle Tendenz darstellt), wobei erstere als syntaktischer angesehen wird (definiert als Reduktionsrelation), und letztere ist typischerweise durch die Tatsache gekennzeichnet, dass rechnerisch äquivalente Programme genau dieselbe Bezeichnung haben (so dass die Bezeichnung den tatsächlichen Berechnungsmechanismus nicht berücksichtigt). Unter dieser letzteren Ansicht würde das, was in den Artikeln und meiner obigen Erklärung als "Bewertungsstrategie" oder "operationelle Semantik" vorgeschlagen wird, eher als denotationale Semantik angesehen - aber zugegebenermaßen konkreter als die meisten: Werte / Antworten / Verhaltensweisen sind syntaktischen Objekten näher als viele semantische Domänen.

Referenzen: Um diesen Standpunkt zu verstehen, ist es wahrscheinlich nützlich, zu seiner proklamierten Quelle zurückzukehren, die der Artikel von Gordon Plotkin aus dem Jahr 1973 ist. Vielleicht haben Sie auch viel Glück, wenn Sie einen der letzteren Artikel ausprobieren, die auf Wikipedia zitiert werden. Ich fand zum Beispiel heraus, dass "Parameter-Passing and the Lambda Calculus" von Crank und Felleisen, 1991, auf den ersten Seiten einen sehr klaren Überblick über ihre Position zu diesem Thema gab.