Unterschied zwischen operativer Semantik in kleinen und großen Schritten

28

Was sind die grundlegenden Unterschiede zwischen der operativen Semantik in kleinen und großen Schritten?

Es fällt mir schwer zu begreifen, was es ist und was die Motivation ist, die beiden zu haben.

Simon Morgan
quelle
1
Der Wikipedia-Artikel zur operativen Semantik sieht vielversprechend aus ... bis man erkennt, dass die Gesamtsumme der Informationen im Abschnitt "Semantik in großen Schritten" "Dieser Abschnitt muss erweitert werden. (Februar 2011)" ist.
David Richerby
1
Was ist Ihre Lernquelle? Was ist in der Sache enthalten? Was denkst du? Hinweis: Was ist die Großschritt-Semantik von x = 0; while ( true ) { x = x + 1; }?
Raphael
@ Raphael Ich lese Understanding Computation . Meiner Meinung nach besteht der Ansatz in kleinen Schritten darin, einen Ausdruck in Unterausdrücke zu reduzieren, bis er nicht mehr weiter reduziert werden kann, und diesen dann zu bewerten. Bei Big Step geht es anscheinend darum, Dinge sofort zu bewerten, aber ich sehe keinen wirklich interessanten Unterschied zwischen den beiden Methoden, da es sich bei beiden um das Aufbohren von Konstrukten höherer Ebenen zu handeln scheint.
Simon Morgan
Großer Schritt: Drilldown von Konstrukten höherer Ebenen durch Auswertung von Unterkonstrukten und kleiner Schritt durch erneutes Reduzieren eines größeren Konstrukts in seine Unterkonstrukte.
Simon Morgan

Antworten:

32

Die Semantik in kleinen Schritten definiert eine Methode zur schrittweisen Auswertung von Ausdrücken. Formal ist eine Kleinschritt-Semantik für eine Ausdruckssprache eine Relation : E × E , die als Reduktionsrelation bezeichnet wird. Die Semantik in kleinen Schritten beschreibt detailliert, was mit einem Ausdruck geschieht. Mit einer unendlichen Kette von e 0e 1e 2… kann es auch nicht beendende Programme genau beschreiben . Ein Abschlussprogramm ist ein solches, dass e 0e 1v istE→:E×Ee0e1e2e0e1v veE,ve

Am anderen Ende des Spektrums befindet sich die Denotationssemantik . Die Denotationssemantik weist jedem Ausdruck eine „Bedeutung“ zu. ist eine Funktion von Ausdrücken zu Bezeichnungen: ( wird als Domäne bezeichnet). Der Bezeichnungsraum kann völlig unabhängig vom syntaktischen Raum sein, z. B. können Ausdrücke sein, die als Zahl ausgewertet werden, und kann eine Menge von Zahlen wie oder .D E D N R[[]]:EDDEDNR

Die Big-Step-Semantik ist sozusagen in der Mitte. Ein großer Schritt-Semantik auf einer Ausdruckssprache und einen Satz von Werten ist eine Beziehung . Es bezieht einen Ausdruck auf seinen Wert (möglicherweise mehrere Werte, wenn die Sprache nicht deterministisch ist). Oft wird ein spezieller Wert für nicht terminierende Ausdrücke verwendet.V : E × V EV⇓:E×V

Warum haben wir diese drei Begriffe? Alle diese Begriffe können sich gegenseitig modellieren, das Modell erhöht jedoch die Komplexität.

  • Bei einer Semantik kleinen Schritten können Sie eine entsprechende Semantik in großen Schritten definieren, die jeden Ausdruck mit seinem Wert (oder Werten, wenn die Reduktion nicht deterministisch ist) in : iff gibt es eine Kette und können nicht weiter reduziert werden. Beachten Sie, dass Sie im Allgemeinen die Semantik kleiner Schritte nicht aus der Semantik großer Schritte rekonstruieren können. Zum Beispiel sind alle nicht terminierenden Ausdrücke unter der Big-Step-Semantik nicht unterscheidbar.e v e e 1v vevee1vv
  • Bei einer Semantik mit großen Schritten kann man sagen, dass es sich um eine Semantik mit kleinen Schritten für . Dies ist nicht besonders nützlich.E V⇓:E×VEV
  • Bei einer Semantik kleinen Schritten können Sie eine entsprechende Denotationssemantik definieren, bei der die Bezeichnung eines Ausdrucks die Menge der Reduktionsketten ist, die von diesem Ausdruck ausgehen. Dies erfüllt die formale Definition, ist jedoch nicht besonders nützlich, da es Objekten einen satztheoretischen Overhead hinzufügt, über den man leichter nachdenken kann, wenn man sich die Syntax direkt ansieht.
  • Bei einer Denotationssemantik können Sie eine Semantik mit kleinen Schritten definieren, indem Sie alle möglichen Denotationen als Werte in der Sprache hinzufügen. Dazu müssen Werte erstellt werden, die nicht Teil der Syntax sind, die der Programmierer schreiben kann. Das bedeutet, dass einige interessante Ergebnisse "für alle Programme, die der Programmierer schreiben kann" und nicht "für alle Programme" enthalten müssen. Dieser ist also auch nicht sehr nützlich.[[]]
  • Bei einer Semantik mit großen Schritten können Sie eine entsprechende Denotationssemantik definieren, bei der die Domäne die Menge der Wertemengen ist: . Wenn die Großschritt-Semantik deterministisch ist (jeder Ausdruck wird auf einen einzelnen Wert reduziert), können Sie eine einfachere Denotationssemantik definieren, bei der die Domäne die Menge der Werte ist.[[[e]]={vev}
  • Umgekehrt können Sie bei gegebener Denotationssemantik eine -Semantik . Auch dieser ist ein wenig sinnlos.E [[[]]E[[]]

Operativ gesehen entspricht die Semantik in kleinen Schritten der Betrachtung jeder Operation, die von einem Interpreter für die Sprache ausgeführt wird. Die Big-Step-Semantik betrachtet nur den resultierenden Wert. Die Denotationssemantik befasst sich mit einer mathematischen Interpretation, die möglicherweise nichts mit dem zu tun hat, was auf einem Computer geschieht.

Die Semantik in kleinen Schritten ist die offensichtlichste. Hier finden Sie nützliche Informationen zu Programmen, die nicht beendet werden. Im Allgemeinen enthält es detaillierte Informationen zum Verhalten des Programms.

Die Denotationssemantik transformiert syntaktische Konstrukte in beliebige mathematische Objekte. es kann ausdrücken, was die Wissenschaftler wollen (Sie können die Bezeichnung eines Ausdrucks als alle möglichen Reduktionsketten daraus definieren), aber auf Kosten einer höheren Komplexität. Es wird verwendet, wenn wir einige Details abstrahieren möchten, z. B. wie der Ausdruck ausgewertet wird.

Die Großschritt-Semantik liegt in der Mitte: Sie abstrahiert die Details der Auswertung, behält aber die syntaktische Natur des Ergebnisses bei. Normalerweise wird das Konzept verwendet, wenn es eine zugrunde liegende Kleinschritt-Semantik gibt, um kurz auszudrücken: „ "als" ". In solchen Konstruktionen sehen die Definitionen sehr ähnlich aus, obwohl die Konzepte sehr unterschiedlich sind (eines erlaubt es uns, über einzelne Rechenschritte und über nicht abschließende Programme zu sprechen, das andere nicht), da in diesem Fall die Regeln, die das definieren, sehr ähnlich sind Die Großschritt-Semantik hat grundsätzlich die Form „wenn und… und und(e1,,en),ee1en and e,eneeene1e2envvist ein Wert dann ”.e1v

Gilles 'SO - hör auf böse zu sein'
quelle
Das lerne ich auch, aber ich habe ein Problem mit etwas, das Sie in Ihrer Antwort gesagt haben und das ich Ihnen erläutern möchte. Sie sagten: "Semantik in großen Schritten ist sozusagen in der Mitte." Wäre small-step nicht das "mittlere" Modell? Betrachten Sie die Ausdrücke: A: ((5 + 7) + 3) B: ((5 + 5) + 5) C: ((1 + 2) + 1) D: ((2 + 1) + 1) Die Bezeichnung würde klassifizieren Sogar C und D mit unterschiedlichen Werten (möglicherweise "C" und "D") und big step würden beide als "4" und A und B als "15" klassifizieren. Allerdings würde small step Ihnen "(12) geben + 3) "und" (10 + 5) "für A und B und" (3 + 1) "für C und D.
Timothy Swan
@TimothySwan Unter der Annahme, dass Sie die übliche arithmetische Auswertung definieren möchten, würde eine Denotationssemantik C und D nicht unterscheiden. Eine Kleinschritt-Semantik würde eine Reduktionskette wie . Eine Semantik mit großen Schritten wäre einer Denotationssemantik sehr ähnlich: vs . Die in der Großschritt-Semantik ist diejenige in der Sprachsyntax, während die in der Denotationssemantik diejenige aus der Metatheorie ist, aber die Unterscheidung ist in diesem einfachen Beispiel nicht sichtbar oder wichtig. ((2+1)+1)3+14((2+1)+1)3[[((2+1)+1)]]=444
Gilles 'SO- hör auf böse zu sein'
Wenn Sie also sagten: "Die Denotationssemantik weist jedem Ausdruck eine" Bedeutung "zu." Sie meinten nicht, Ausdrücke eindeutig zu identifizieren, sondern eine Art bewertungsunabhängige Bedeutung? Können Sie ein einfaches Beispiel angeben, das den Unterschied zwischen der Semantik für große Schritte und der denotationalen Semantik deutlich macht? Erklären Sie bitte auch, dass 3in ((2+1)+1)⇓3meiner Vermutung 'denotational' ein End-All-Wert ist, aber in welchem ​​Fall würde 'big-step' dem nicht unbedingt direkt entsprechen? Hat der Unterschied etwas mit dem Kontext zu tun, zum Beispiel (a + 1)abhängig von der Umgebung, die ihn enthält a?
Timothy Swan
@TimothySwan Solange es keine Nebenwirkungen, keinen Nichtdeterminismus und keine Funktionen gibt, ist die Denotationssemantik eines Ausdrucks der Wert, den er auswertet. Nichtdeterminismus ist ein guter Weg, um den Unterschied zwischen Big Step und Denotational zu veranschaulichen: Die Bezeichnung eines Ausdrucks wäre die Menge von Werten, die er haben kann: , während eine Semantik mit großen Schritten mehrere zulässige Urteile haben würde: und und ... Das war ein Tippfehler. r ein n d ( 1 .. n ) 1 r a n d ( 1 .. n ) 2[[rand(1..n)]]={1,2,,n}rand(1..n)1rand(1..n)23
Gilles 'SO- hör auf böse zu sein'