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.
semantics
operational-semantics
small-step-semantics
Simon Morgan
quelle
quelle
x = 0; while ( true ) { x = x + 1; }
?Antworten:
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 0 → e 1 → e 2 → … kann es auch nicht beendende Programme genau beschreiben . Ein Abschlussprogramm ist ein solches, dass e 0 → e 1 → ⋯ → v istE →:E×E e0→e1→e2→… e0→e1→⋯→v v ∀e′∈E,v↛e′
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[[⋅]]:E→D D E D N R
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 ⊥E V ⇓:E×V ⊥
Warum haben wir diese drei Begriffe? Alle diese Begriffe können sich gegenseitig modellieren, das Modell erhöht jedoch die Komplexität.
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),e→e1→…en and ∄e′,en→e′ e⇓en e1→∗e2 en→∗v v ist ein Wert dann ”.e1⇓v
quelle
3
in((2+1)+1)⇓3
meiner 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älta
?3