Wie werden Nebenwirkungen in der Semantik behandelt?

19

In Anthony Aabys Abschnitt "Einführung in Programmiersprachen" über Semantik macht er folgende Bemerkung:

Ein Großteil der Arbeit in der Semantik von Programmiersprachen ist durch die Probleme motiviert, die beim Versuch auftreten, imperative Programme zu konstruieren und zu verstehen - Programme mit Zuweisungsbefehlen. Da der Zuweisungsbefehl den Variablen Werte neu zuordnet, kann die Zuweisung unerwartete Auswirkungen auf entfernte Teile des Programms haben.

Dies erscheint mir als bemerkenswertes Eingeständnis, dass das Zulassen von Nebenwirkungen einen Großteil der Arbeit in der Semantik motivieren würde.

Wie wirkt sich das Vorhandensein von Nebenwirkungen in einer Programmiersprache auf die Fähigkeit aus, ein Programm einem Rechenmodell zuzuordnen? Gibt es Ansätze zur Bewältigung des Zustands, die diesen Prozess verbessern und gleichzeitig Nebenwirkungen zulassen können?

Shane
quelle
Sollte dies als weiche Frage markiert werden? Da "ein Großteil der Arbeit in der [...] Semantik durch [Nebenwirkungen] motiviert ist", können Sie mit Sicherheit keine kurze und strenge Antwort erwarten.
Radu GRIGore
1
@Radu: Auf MO würde dies wahrscheinlich mit [big picture] markiert sein, die meistens nicht [soft question] oder CW sind.
Charles Stewart
Das Tag-Big-Picture ist noch besser. Ich habe es vergessen.
Radu GRIGore
Guter Vorschlag; Ich habe den Tag hinzugefügt.
Shane

Antworten:

18

Aufbauend auf Charles 'Antwort besteht die Hauptschwierigkeit in der Theorie der Programmiersprachen darin, dass der natürliche Begriff der Äquivalenz von Programmen weder in der einfachsten mathematischen Semantik, die Sie geben können, noch im zugrunde liegenden Maschinenmodell eine strikte Gleichheit darstellt. Betrachten Sie beispielsweise das folgende Stück Java-ähnlichen Codes:

Object x = new Object();
Object y = new Object();
... some more code ...

Also erstellt dieses Programm ein Objekt und benennt es mit x, erstellt dann ein zweites Objekt mit dem Namen y und führt dann weiteren Code aus. Angenommen, ein Programmierer beschließt, die Zuordnungsreihenfolge dieser beiden Objekte umzudrehen:

Object y = new Object();
Object x = new Object();
... some more code ...

Stellen Sie nun die Frage: Ändert dieses Refactoring das Verhalten des Programms? Zum einen werden auf der zugrunde liegenden Maschine x und y in den beiden Programmläufen an unterschiedlichen Stellen zugeordnet. In diesem Sinne verhält sich das Programm also anders.

In einer Java-ähnlichen Sprache können Sie Referenzen jedoch nur auf Gleichheit und nicht auf Ordnung testen. Dies ist also ein Unterschied, den der "etwas mehr Code" nicht feststellen kann . Infolgedessen erwarten die meisten Programmierer, dass die Umkehrung der Reihenfolge keinen Einfluss auf die endgültige Antwort hat, und die meisten Compiler-Autoren erwarten, dass sie auf dieser Basis Nachbestellungen und Optimierungen vornehmen können. (Auf der anderen Seite, in einem C-ähnlicher Sprache, Sie können Zeiger für die Bestellung vergleichen, indem man sich auf ganze Zahlen zuerst Gießen und so diese Neuanordnung tut nicht unbedingt beobachtbares Verhalten erhalten.)

Eine der zentralen Fragen der Semantik ist die Beantwortung der Frage, wann zwei Programme beobachtbar gleichwertig sind. Da unser Begriff der Beobachtung von den Merkmalen der Programmiersprache abhängt, ergibt sich eine Definition wie "zwei Programme sind äquivalent, wenn kein Client-Programm unterschiedliche Antworten auf der Grundlage des Empfangs dieser Programme als Eingaben berechnen kann". Die Quantifizierung aller Client-Programme macht diese Frage schwierig - es scheint, als müssten Sie etwas über alle möglichen Client-Programme sagen, um etwas über zwei bestimmte Codeteile zu sagen.

Der Trick bei der Denotationssemantik besteht darin, eine mathematische Interpretation zu geben, mit der Sie diese universelle Quantifizierung vermeiden können. Sie sagen, dass die Bedeutung eines Codeteils ein mathematischer Wert ist, und vergleichen sie, indem Sie prüfen, ob sie mathematisch gleich oder gleich sind nicht. Dies ist lokal (dh kompositorisch) und beinhaltet keine Quantifizierung über alle möglichen Kunden. (Sie müssen zeigen, dass die Denotationssemantik eine kontextbezogene Äquivalenz impliziert, damit sie stichhaltig ist. Wenn sie vollständig ist - wenn die Denotationsgleichheit genau der kontextbezogenen Äquivalenz entspricht, ist die Semantik "vollständig abstrakt".)

Dies bedeutet jedoch, dass Sie sicherstellen müssen, dass die Denotationssemantik diese Äquivalenzen validiert. Wenn Sie also in diesem Beispiel eine Denotationssemantik für diese Java-ähnliche Sprache angeben möchten, müssen Sie sicherstellen, dass beim Aufruf von new nicht nur ein Heap erstellt und ein neuer Heap mit dem neu erstellten Objekt zurückgegeben wird, sondern auch die Bedeutung des Programms ist unter allen Permutationen des Eingabeheaps gleich. Dies kann recht komplexe mathematische Strukturen beinhalten (zB in diesem Fall in einer Kategorie arbeiten, die sicherstellt, dass alles Modulo einer geeigneten Permutationsgruppe funktioniert).

Neel Krishnaswami
quelle
"Zwei Programme sind äquivalent, wenn kein Client-Programm unterschiedliche Antworten berechnen kann, basierend auf dem Empfang dieser Programme als Eingaben." Das verwirrt mich. Wenn Sie ein Programm X und ein Client- Programm Y haben, dann verstehe ich, dass Y X 'aufruft. Aber dann scheinen Sie zu sagen, dass Y den Text von X als Eingabe liest , in diesem Fall würde ich kaum aufrufen Y ein "Kunde" von X. Könnten Sie bitte klären?
Radu GRIGore
1
Mit "Client von X" meine ich genau das Gleiche wie "Programmkontext", was nur ein "größeres Programm, das X als Subterm enthält" ist.
Neel Krishnaswami
Sie verwenden also 'X ist ein Klient von Y', austauschbar mit 'X liest Y als Eingabe', weil Sie X als ein Lambda betrachten, das auf Y angewendet wird? Es macht Sinn, ist aber ein bisschen verdreht, wenn man über Java spricht. :)
Radu GRIGore
1
@RaduGRIGore: Programmkontext bedeutet etwas anderes. Sie lesen den Beitrag korrekt, aber wenn X den Quellcode von Y als Eingabe liest (wie ich den Beitrag interpretiere), können Sie alle zwei syntaktisch unterschiedlichen Programme unterscheiden. Wenn Y eine Lambda-Funktion für X ist, können Sie zu wenige Programme unterscheiden. Neels Kommentar zum "Programmkontext" ist die richtige Definition: Ein Programmkontext Y ist ein Programm mit einem Loch in seinem AST, in dem Sie zwei verschiedene Programmfragmente X1 und X2 (sinnvoll) platzieren können.
Blaisorblade
@NeelKrishnaswami: könntest du vielleicht klarstellen, was du in der Post meinst? Sie können einfach Ihr Beispiel weiter verwenden und über ein Programm sprechen, in das Sie das eine oder andere Fragment einfügen können.
Blaisorblade
12

Es gibt natürlich Möglichkeiten, mit Effekten in (denotationaler) Semantik umzugehen. Zum Beispiel können wir die Idee von Eugenio Moggi verwenden , dass Computereffekte Monaden sind (diese Idee wurde auch beim Entwurf von Haskell verwendet). Eines der Probleme dabei ist, dass Monaden schwer zu kombinieren sind. Gordon Plotkin und John Power schlugen eine Verfeinerung von Moggis Monaden zu Lawvere-Theorien oder algebraischen Theorien, wie sie auch genannt werden, vor, die algebraische Effekte umfassen (die meisten Effekte sind algebraisch, wie Zustand, E / A, Nichtdeterminismus, aber Fortsetzung sind es nicht). Für eine umfassende Behandlung siehe Matija Pretnars These .

Ich sollte auch die mögliche Weltsemantik für den lokalen Staat erwähnen , die von Frank Oles und John Reynolds entwickelt wurde (Entschuldigung, es gibt keinen besseren Link, das Zeug stammt aus dem Jahr 1982) und die Moggis Monaden vorausgeht. Sie verwendeten Kategorien von Presheaves, um eine Semantik einer algolähnlichen Sprache bereitzustellen, die viele Aspekte des lokalen Staates korrekt modellierte (aber nicht alle, ich denke, das Modell erlaubte Snapback, aber vielleicht dient mir mein Gedächtnis falsch).

Andrej Bauer
quelle
1
Ja, die Funktionskategoriesemantik hat nicht alle Meyer-Sieber-Äquivalenzen validiert. Peter O'Hearn und Robert Tennant entwickelten Mitte der 90er Jahre eine parametrische Version der Funktionskategorie-Semantik, die (IIRC) alle Meyer-Sieber-Beispiele enthielt, aber ich weiß nicht, ob sie vollständig abstrakt war oder nicht.
Neel Krishnaswami
O'Hearn and Tennent-Modell ist nicht vollständig abstrakt. Das wird in der Zeitung selbst besprochen. Aber die Verfeinerung von O'Hearn und Reynolds unter Verwendung der linearen Lambda-Rechnung ist bis zur zweiten Ordnung vollständig abstrakt. Es bricht für die dritte Ordnung, Beispiele dafür sind die von Ahmed, Dreyer, Birkedal et al.
Uday Reddy
12

Matthias Felleisen präsentierte in seiner Reihe "Syntaktische Kontroll- und Zustandstheorien" eine überzeugende Lösung für das Nebenwirkungsproblem in der Semantik.

Aus dieser Arbeit heraus entstand die CESK-Maschine, ein einfaches abstraktes Maschinen-Framework, mit dem funktionale, objektorientierte, imperative und sogar logische Sprachen präzise modelliert werden können. Das CESK-Framework behandelt nicht nur Nebenwirkungen, sondern auch "komplexe" Steuerungskonstrukte wie Ausnahmen, Fortsetzungen, Faulheit und sogar Threads.

Die CESK-Maschine und die Small-Step-Operational-Semantik sind seit etwa zwei Jahrzehnten der De-facto-Standard in der Theorie der Programmiersprachen.

Kurz gesagt, eine CESK-Maschine ist eine Kleinschrittmaschine mit vier Komponenten, die jeden Maschinenzustand beschreiben: die Steuerzeichenfolge (eine Verallgemeinerung des Programmzählers), die Umgebung, einen Speicher (auch Heap genannt) und die aktuelle Fortsetzung.

Die Umgebung ordnet Variablen Adressen zu. Der Store ordnet Adressen Werten zu.

Dies macht es einfach, veränderbare Variablen zu modellieren: Ändern Sie einfach den Wert an seiner Adresse.

Es erleichtert auch das Modellieren von Zeigern und die dynamische Zuordnung: Legen Sie einfach erstklassige Werte für die Speicheradressen fest.

In ähnlicher Weise ergeben sich erstklassige Fortsetzungen daraus, dass sie adressierbare Werte sind.

Matt Might
quelle
6

Wie wirkt sich das Vorhandensein von Nebenwirkungen in einer Programmiersprache auf die Fähigkeit aus, ein Programm einem Rechenmodell zuzuordnen?

Dies macht es nicht unbedingt schwierig, schränkt jedoch die Art und Weise ein, in der die Semantik größerer Ausdrücke aus kleineren Ausdrücken konstruiert werden kann. Es kann sehr schlecht mit bestimmten anderen Programmierkonstrukten interagieren, zum Beispiel, wenn man eine schottische Denotationssemantik für eine Sprache angeben möchte, die die Zuordnung von Funktionen höherer Ordnung zu globalen Referenzen ermöglicht.

Es sind nicht nur Nebenwirkungen wie der Zustand, die das Problem verursachen. Einfache imperative Sprachen wie Dijkstras geschützte Befehlssprache haben diese Art von Nebenwirkungen und eine nette Semantik. Probleme treten bei Erweiterungen des Lambda-Kalküls mit der Art der operativen Semantik auf, die von Programmiersprachen auch ohne Nebenwirkungen erwartet wird: Der frühesten, Plotkins PCF, wurden relativ früh Bezeichnungsmodelle gegeben, aber die Semantik war nicht vollständig abstrakt, was bedeutet, dass Die Denotationssemantik war zu allgemein und entsprach nicht genau ihrer operativen Semantik. In den späten 1980er Jahren erhielt PCF schließlich eine vollständig abstrakte Denotationssemantik mit Spielesemantik, die überhaupt nicht mit Scotts ordnungstheoretischer Semantik vergleichbar ist. Parallelität hat immer noch keine völlig angemessene Denotationsbehandlung erhalten.

Viele hinterfragen die Bedeutung dieser Art von Semantik. Wir können immer eine Art von operationeller Semantik bereitstellen, auch wenn diese "Semantik" nur die Programmquelle und die Namen einiger Maschinen ist, die das Programm kompiliert und ausgeführt haben. Aus diesem Grund hat Strachey die operationelle Semantik verurteilt. Die strukturelle Operationssemantik von Plotkin hat jedoch gezeigt, wie die operationelle Semantik von Maschinenmodellen getrennt werden kann, und Pitts Arbeit hat gezeigt, wie diese Semantik ähnliche Argumente über Programme und Programmiersprachen wie die denotationale Semantik unterstützen kann. Daher ist die operative Semantik eine praktikable Alternative zur denotationalen Semantik und wurde mit Erfolg auf eine beträchtliche Anzahl von Programmiersprachen wie Standard-ML angewendet.

Gibt es Ansätze zur Bewältigung des Zustands, die diesen Prozess verbessern und gleichzeitig Nebenwirkungen zulassen?

In gewissem Maße entsprechen die Schwierigkeiten beim Bereitstellen der Semantik den Schwierigkeiten beim Bereitstellen leistungsfähiger Programmiersprachen, die sich wie erwartet verhalten. Pragmatisch motivierte Entwurfsentscheidungen - wie das Vermeiden der Verwendung des globalen Status zusammen mit der gleichzeitigen Verwendung, normalerweise durch die gleichzeitige Übermittlung von Nachrichten - erleichtern die Bereitstellung von Semantik.

Charles Stewart
quelle
Scotts PCF hat keinen Status und Scott auch nicht, oder? Siehe en.wikipedia.org/wiki/…
Andrej Bauer
@Andrej: Ähm, angesichts der Tatsache, dass Luke Ong meinen D.Phil beaufsichtigt hat, sollte ich diesen Fehler nicht machen. Ich habe eine Teaser-Zusammenfassung von Milners PCF und Scotts LCF gepostet, die mehr ... als die von WPs als LtU-Story zu verstehen ist : lambda-the-ultimate.org/node/2196 Mir fällt ein, dass Sie möglicherweise Zugriff auf den vermissten Scott haben (1969) Manuskript ...
Charles Stewart
Das wäre Plotkins PCF, denke ich :-) Ich kann versuchen, das Manuskript zu bekommen, aber ich habe es eigentlich nicht.
Andrej Bauer
Es bleibt jedoch der Punkt, dass PCF keinen Status hat. Welchen "Grund" sagen Sie, dass Strachey die operative Semantik verurteilt? Es war mir nicht klar. Der letzte Absatz widerspricht dem, was Sie zuvor gesagt haben, nämlich geschützte Befehle haben eine nette Semantik, PCF jedoch nicht!
Uday Reddy
@Andrej, Uday: Ich habe meinen Posten weniger als drei Jahre später repariert.
Charles Stewart