Warum bleibt der Zustand in der kleinen operativen Semantik einer while-Schleife unverändert?

9

Normalerweise sehe ich, dass sich in der strukturellen Darstellung der operativen Semantik für die while-Schleife der Programmstatus nicht ändert:

$(while \> B \> do \>S, \sigma) \rightarrow (if \>B \> then \>S; (while \> B \> do \>S) \> else \> SKIP, \sigma)$

Für mich ist dies nicht intuitiv. Wenn sich der Status nicht ändert (dh der Status des Speichers bleibt gleich), bleibt weiterhin wahr und das Programm wird niemals beendet. $B$

Kann jemand bitte erklären, warum sich der Staat in dieser Regel nicht ändert?

formal-languages programming-languages formal-methods operational-semantics El Marce
quelle

Beachten Sie, dass dies nur dann richtig ist, wenn wir davon ausgehen können, dass

keine Nebenwirkungen hat. Dies gilt in den meisten Programmiersprachen nicht.

B

$B$

Raphael

10

In der Semantik der Programmiersprache ist der Begriff des Programmzustands kein vager philosophischer Begriff, sondern ein sehr präziser mathematischer. Ein Zustand in diesen kleinen Schritten operationale Semantik ist eine Teilfunktion $s$

s : V a r ↪ Z

$s : \mathbf{Var} \hookrightarrow \mathbb{Z}$

das zeichnet die Werte der Variablen auf. Also wenn , dann hat die Variable den Wert . Der Zustand ist notwendigerweise eine Teilfunktion, da es nur sinnvoll ist, die Werte der tatsächlich auftretenden Variablen aufzuzeichnen. $s\, x = v$ $x$ $v$

Das sich entfaltende Axiom

⟨ while b do S, s ⟩ \Rightarrow ⟨ if b then S; while b do S else skip, s ⟩

$\langle \texttt{while}\; b\; \texttt{do}\; S,s \rangle \Rightarrow \langle \texttt{if}\; b\; \texttt{then}\; S; \texttt{while}\; b\; \texttt{do}\; S \; \texttt{else skip},s \rangle$

sagt uns einfach, dass wir eine while-Schleife in eine bedingte Anweisung entfalten, deren Zweig die Schleife enthält. Aus diesem Grund ändern keine Variablen ihren Wert, und aus diesem Grund ändert sich der Status nicht.

Hans Hüttel
quelle

10

Der Zustand kann sich in nachfolgenden Reduktionsschritten ändern, weil auf der rechten Seite von

⟨ w h i l e B d o S, σ ⟩ \to ⟨ i f B t h e n (S; w h i l e B d o S) e l s e s k i p, σ ⟩

$\langle while\ B\ do\ S, \sigma \rangle \quad\rightarrow\quad \langle if\ B\ then\ ( {\color{red}{S}};\ while\ B\ do\ S )\ else\ skip, \sigma\rangle$

Die Schleife wird von bewacht (vorangestellt) . Die Berechnung von kann den Zustand ändern, so dass die Bedingung zu ausgewertet werden kann . $while$ $S$ $S$ $B$ $\mathsf{false}$

Martin Berger
quelle

Das bedeutet also, dass die Zustandsänderung in anderen Regeln ausgedrückt werden sollte, auf die S in einem konkreten Programm möglicherweise reduziert werden könnte?

El Marce

@ ElMarce Ja. Ich schlage vor, ein einfaches Beispiel

zB

und sehen, wie das funktioniert.

x := 2; w h i l e x > 0 d o x := x - 1

$x := 2;\ while\ x > 0\ do\ x := x - 1$

Martin Berger

9

Der Zustand ändert sich nicht, wenn wir , um zu entscheiden, ob eine Iteration der Schleife durchgeführt werden soll, aber er kann sich später ändern, wenn wir den Körper ausführen . Wenn wir also das nächste Mal , kann es zu einer Änderung von . $\sigma$ $B$ $S$ $B$ $\sigma$

Andrej Bauer
quelle

Diese Erklärung ist zwar im Wesentlichen korrekt, bezieht sich jedoch nicht darauf, was Zustände sind (nämlich eine Funktion, die die Werte von Varialbes angibt) und was eine Zustandsänderung bedeutet (nämlich, dass sich der Wert mindestens einer Variablen ändert).

Hans Hüttel

In der Tat ist es unerheblich, was Staaten sind oder wie sie für die Zwecke meiner Antwort implementiert werden. Die Erklärung gilt trotzdem. Und außerdem ist es tatsächlich falsch zu sagen, dass "Zustände wirklich Funktionen sind", weil Theat nur eine Möglichkeit ist, sie mathematisch zu modellieren. Es gibt andere mögliche Modelle. Und lassen Sie uns mathematische Modelle nicht mit der Funktionsweise von Hardware verwechseln.

Andrej Bauer

Die Frage befasst sich jedoch mit einer spezifischen operativen Semantik in kleinen Schritten, für die der Begriff eines Staates genau definiert ist.

Hans Hüttel

Ich habe nie gesagt, dass es nicht so ist. Ich sage nur, dass Ihre Bemerkung unnötig ist, weil meine Erklärung ohne ausdrückliche Erwähnung der Modellierung des Zustands gilt. Vielleicht haben Sie festgestellt, dass das OP nicht wusste, dass der Status eine Zuordnung von Variablen zu Werten ist. Gut für dich, du hast deine Antwort akzeptiert bekommen und ich nicht. Herzliche Glückwünsche. Warum Sie mir jetzt Ihre Antwortweise aufzwingen, ist für mich unverständlich. Warum genau hast du das Bedürfnis, meine Antwort so zu gestalten wie deine? Meine Antwort macht Sinn ohne die Bemerkungen, die Sie für notwendig halten. Vielleicht kommt eines Tages jemand, der nach meiner Antwort sucht.

Andrej Bauer

Warum bleibt der Zustand in der kleinen operativen Semantik einer while-Schleife unverändert?

Antworten: