Was ist „formale Semantik“?

Question

Ich bin eine sehr dumme Zeitung zu lesen, und es hält auf zu reden, wie Giotto definiert eine „formale Semantik“.

  

Giotto hat eine formale Semantik, die angibt, die Bedeutung des Modus schaltet, die Inter-Task-Kommunikation und der Kommunikation mit der Programmumgebung.

Ich bin am Rande der, kann aber einfach nicht ganz begreifen, was es bedeutet, von „formaler Semantik.“

Answer 1

Formale Semantik Semantik in beschreiben - na ja, formal - Notation, die die Bedeutung zum Ausdruck bringt die Dinge in eindeutiger Weise.

Es ist das Gegenteil von informeller Semantik, die im Wesentlichen nur alles in einfachem Englisch zu beschreiben ist. Dies kann leichter zu lesen und zu verstehen, aber es schafft das Potenzial für Fehlinterpretationen, die zu Fehlern führen könnte, weil jemand nicht einen Absatz der Art und Weise gelesen haben Sie sie beabsichtigt, es zu lesen.

Eine Programmiersprache kann sowohl formelle und informelle Semantik - die informelle Semantik dann als „Klartext“ Erklärung der formalen Semantik dienen würde, und die formale Semantik würde der Ort zu suchen, wenn Sie nicht sicher sind, was die informelle Erklärung wirklich bedeutet.

Answer 2

Um auf Michael Madsen Antwort erweitern ein wenig, ein Beispiel könnte das Verhalten des ++ Operator. Informell wir den Operator einfaches Englisch beschreiben. Zum Beispiel:

  

Wenn x eine Variable vom Typ int ist, x ++x Ursachen um eins erhöht werden.

(Ich bin keine Integerüberläufe unter der Annahme, und dass ++x nicht alles zurück)

In einer formalen Semantik (und ich werde operationale Semantik verwenden), würden wir ein bisschen Arbeit zu tun haben. Erstens brauchen wir eine Vorstellung von Typen zu definieren. In diesem Fall werde ich davon ausgehen, dass alle Variablen vom Typ int sind. In dieser einfachen Sprache kann der aktuelle Zustand des Programms von einem Speicher beschrieben, die eine Zuordnung von Variablen mit Werten ist. Zum Beispiel an einem gewissen Punkt im Programm, könnte x bis 42 gleich sein, während y bis -5351 gleich ist. Der Speicher kann als Funktion verwendet werden. - so zum Beispiel, wenn der Speicher s hat den Variable x mit dem Wert 42, dann s(x) = 42

Auch in dem aktuellen Stand des Programms enthalten sind die verbleibenden Anweisungen des Programms wir auszuführen haben. Wir können diese sich als <C, s> bündeln, wo C das restliche Programm, und s ist der Laden.

Also, wenn wir den Zustand <++x, {x -> 42, y -> -5351}> haben, diese informell ein Zustand, in dem der einzige verbleibende Befehl ++x, die Variable x hat 42 Wert auszuführen ist, und die Variable y hat Wert -5351.

Wir können dann Übergänge definieren von einem Zustand des Programms zu einem anderen - wir beschreiben, was passiert, wenn wir den nächsten Schritt in dem Programm nehmen. Also, für ++, könnten wir die folgende Semantik definieren:

<++x, s> --> <skip, s{x -> (s(x) + 1)>

Etwas informell, durch ++x Ausführung, ist der nächste Befehl skip, die keinen Einfluss hat, und die Variablen im Speicher sind unverändert, mit Ausnahme von x, die nun den Wert, dass es ursprünglich plus eins hatte. Es gibt noch einige Arbeit zu tun, wie die Notation definiert, die ich für die Aktualisierung des Speichers verwendet (was ich nicht diese Antwort zu stoppen getan habe immer noch mehr!). So könnte eine bestimmte Instanz der allgemeinen Regel sein:

<++x, {x -> 42, y -> -5351}> --> <skip, {x -> 43, y -> -5351}>

Hoffentlich, dass Sie die Idee gibt. Beachten Sie, dass dies nur ein Beispiel für formale Semantik ist -. Zusammen mit operationaler Semantik gibt es axiomatische Semantik (die häufig verwendet Hoare Logik) und denotational Semantik, und wahrscheinlich viel mehr, dass ich bin nicht vertraut mit

Wie ich in einem Kommentar zu einer anderen Antwort erwähnte, ist ein Vorteil der formalen Semantik, dass Sie sie verwenden können, um bestimmte Eigenschaften des Programms zu beweisen, zum Beispiel, dass es endet. Neben Ihrem Programm wie zeigt schlechtes Verhalten nicht (wie nicht-Terminierung) aufweisen, können Sie auch beweisen, dass Ihr Programm verhält sich wie durch den Nachweis, Ihr Programm benötigt, um eine gegebene Spezifikation entspricht. Having said that, habe ich fand nie die Idee der Angabe und ein Programm alle überprüfen, ob überzeugend, da ich die Spezifikation gefunden haben in der Regel nur die in der Logik neu geschrieben Programm zu sein, und so die Spezifikation genauso wahrscheinlich ist fehlerhaft sein.

Answer 3

Wie die Syntax einer Sprache kann durch eine formale Grammatik beschrieben werden (zB BNF ), dann ist es möglich, verschiedene Arten von Formalismen zu verwenden).

Diese Seite von Eine praktische Einführung zu denotationelle Semantics ist eine schöne Einführung, wie [denotational] Semantik bezieht sich auf Syntax. Der Anfang des Buches gibt auch eine kurze Geschichte der anderen, nicht denotational Ansätze zur formalen Semantik (obwohl die Wikipedia-Link Michael geht in noch mehr Detail gab, und ist wahrscheinlich mehr up-to-date).

der Website des Autors:

  

Modelle für Semantik nicht   gefangen-on in gleichem Maße, dass BNF   und seine Nachkommen haben in der Syntax.   Dies kann daran liegen Semantik tut   scheinen einfach nur härter zu sein als   Syntax. Das erfolgreichste System ist   denotational Semantik der beschreibt,   alle fanden die Funktionen in imperativen   Programmiersprachen und verfügt über eine solide   mathematische Grundlage. (Es gibt noch   aktive Forschung in Systemen des Typs und   Parallelprogrammierung.) Viele   denotational Definitionen können sein   als Dolmetscher ausgeführt oder übersetzt   in „Compiler“ Das hat aber noch nicht   führte zu Generatoren effizienter   Compiler, die ein weiterer Grund sein kann,   dass denotational Semantik weniger   populärer als BNF.

Answer 4

Was im Zusammenhang mit einer Programmiersprache wie Giotto gemeint ist, ist, dass eine Sprache mit formaler Semantik, hat eine mathematisch strenge Interpretation der einzelne Sprachkonstrukte.

heute Die meisten Programmiersprachen sind nicht streng definiert. Sie können auf Standard-Dokumente halten, die ziemlich detailliert sind, aber es ist letztlich in der Verantwortung des Compilers auszusenden Code, dass irgendwie hält sich an diesen Standarddokumente.

Eine formal angegebene Sprache auf der anderen Seite wird in der Regel verwendet, wenn es notwendig ist, Argumentation über Programmcode zu tun mit, zum Beispiel Model Checking oder Theorembeweisen. Sprachen, die sich auf diese Techniken verleihen neigen funktionell diejenigen, wie ML oder Haskell zu sein, da diese zwischen ihnen mathematische Funktionen und Transformationen definiert verwenden; Das heißt, die Grundlagen der Mathematik.

C oder C ++ auf der anderen Seite ist durch technische Beschreibungen informell definiert, obwohl es wissenschaftliche Arbeiten gibt, die Aspekte dieser Sprachen (zB Michael Norrish formalisieren: Eine formale Semantik für C ++, https://publications.csiro.au/rpr/pub?pid=nicta:1203 ), aber das oft nicht ihren Weg in die offiziellen Standards finden (möglicherweise aufgrund eines Mangels an Praktikabilität, esp. Schwierigkeit zu halten).