Wie man mit Arrays während der Korrektheit von Korrekturen im Hoare-Stil umgeht

Question

In der Diskussion um diese Frage, Gilles erwähnt korrekt, dass jeder Korrektheitserscheinung eines Algorithmus, der Arrays verwendet, beweisen muss, dass es keine Array-Zugriffe außerhalb des Bounds gibt. Abhängig vom Laufzeitmodell würde dies zu einem Laufzeitfehler oder zu Zugriff auf Nicht-Array-Elemente führen.

Eine gemeinsame Technik zur Durchführung solcher Korrektheitserachse (zumindest in Studentenstudien und wahrscheinlich bei der automatisierten Überprüfung) ist die Verwendung Hoare Logik. Mir ist nicht bewusst, dass die Standard -Regeln alles in Bezug auf Arrays enthalten. Sie scheinen auf monadische Variablen beschränkt zu sein.

Ich kann mir vorstellen, Axiome der Form hinzuzufügen

$ qquad displayStyle frac {} { {0 leq i lt A. mathrm {Länge} land {p [a [i]/e]} } a [i]: = e; {P }} $

Mir ist jedoch nicht klar, wie Sie mit einem Array -Zugriff auf der rechten Seite umgehen würden, dh wenn es Teil eines komplexen Ausdrucks ist $ e $ in einer Erklärung $ x: = e $.

Wie können Arrays -Zugriffe in Hoare -Logik modelliert werden, damit das Fehlen ungültiger Zugriffe für die Programm Korrektheit der Programme nachgewiesen werden kann und muss?

Antworten können davon ausgehen, dass wir Array -Elemente nicht zulassen, die in anderen Aussagen als $ a [i] verwendet werden sollen: = e $ oder als Teil von einigen $ e $ in $ x: = e $, da dies die Ausdruckskraft nicht einschränkt; Wir können immer eine temporäre Variable zuweisen, den gewünschten Wert, dh $ t: = a [i]; mathtt {if} (t> 0) dots $ anstelle von $ mathtt {if} (a [i]> 0) Punkte $.

Answer 1

Ihr Axiom ist nicht wirklich ein Axiom, es fehlt Hypothesen. Einfache Präsentationen von Hoare -Logik manipulieren Formeln des Formulars $ {p } c {p '} $ wobei $ p $ und $ p' $ logische Formeln sind und $ C $ ein Befehl ist. Sie müssen Stellen Sie sicher, dass $ C $ gut geformt ist. In einfachen Sprachen wie denjenigen, die häufig für eine erste Einführung in die Hoare-Logik verwendet werden, ist die Wohltatseinheit syntaktisch: In der Regel geht es darum, zu überprüfen erlaubt Set. Wenn die Sprache Konstrukte enthält, die eine semantische Korrektheit haben, z. B. Zugriffe auf Array -Elemente, müssen Sie Hypothesen hinzufügen, um diese semantische Korrektheit auszudrücken.

Formal können Sie Urteile hinzufügen, um die Korrektur von Ausdrücken und Befehlen auszudrücken. Wenn Ausdrücke keine Nebenwirkungen haben, benötigen sie keine Postkonditionen, nur Voraussetzungen. Zum Beispiel können Sie Wohlformigkeitsregeln wie $$ dfrac { {p } ; ; E text {wf}} { {p keedge 0 le e < mathhrm {Länge} (a) } ; ; A [e] text {wf}} qquad dfrac { {p } ; ; E_1 text {wf} qquad {p } ; ; E_2 text {wf}} { {p } ; ; E_1 + e_2 text {wf}} $$ und erlauben Sie nur gut geformte Ausdrücke in Befehlen: $$ dfrac { {p [x linke e] } ; ; E text {wf}} { {p [x linksarrow e] } ; ; x: = e {p }} $$

Ein anderer Ansatz besteht darin, alle Ausdrücke als gut geformt zu behandeln, aber jeden Ausdruck mit einer schlecht geformten Berechnung einen Sonderwert $ MathBf {Fehler} $ zu haben. In Sprachen mit Laufzeitgrenzen überprüft $ mathbf {error} $ „Dieses Programm hat eine tödliche Ausnahme angehoben“. Sie würden dann verfolgen, ob ein Programm, das durch ein logisches Prädikat $ mathbf {error} $ ausgeübt wurde; Ein Programm ist nur gültig, wenn Sie beweisen können, dass seine Post -Condition $ neg mathbf {error} $ impliziert. $$ dfrac {} { {p [x linsearrow e] } ; ; x: = e ; ; {P vee mathbf {error} }} qquad dfrac {p [x Leftarrow e] impliziert e nicht rightarrow mathbf {error}} { {p [x linke e] } ; ; x: = e ; ; {P }} $$

Ein anderer Ansatz besteht darin, ein Hoare -Triple nur dann zu betrachten, wenn das Programm korrekt endet. Dies ist der übliche Ansatz für nicht ordnungsgemäße Programme: Die Postkondition gilt, wenn der Befehl endet, was möglicherweise nicht immer passieren könnte. Wenn Sie Laufzeitfehler als Nicht-Termination behandeln, fegen Sie alle Korrektheitsprobleme unter der Haube. Sie müssen immer noch die Richtigkeit des Programms irgendwie nachweisen, aber es muss nicht in Hoare -Logik sein, wenn Sie einen anderen Formalismus für diese Aufgabe bevorzugen.

Beachten Sie übrigens, dass das Ausdrücken, was passiert, wenn eine zusammengesetzte Variable wie ein Array modifiziert ist, mehr beteiligt als das, was Sie geschrieben haben. Angenommen, $ p $ war beispielsweise $ mathhrm {issortiert} (a) $: Die Substitution $ a [i] Leftarrow E $ würde sich nicht ändern $ p $ ungültig $ p $. Selbst wenn Sie die Syntax von Prädikaten einschränken, um nur über Atome zu sprechen, betrachten Sie die Zuordnung $ A [A [0] -1]: = A [0] $ unter der Voraussetzung $ a [0] = 2 Keil a [1] = 3 $: Sie können keine einfache Substitution erstellen, um die richtige Postzustand zu erhalten. Da die Vorkondition möglicherweise keinen einzigen möglichen Wert für $ a [0] $) angibt. Sie müssen die Substitution auf dem Array selbst ausführen: $ a linksarrow a [i linksarrow e] $. Mike Gordons Vorlesungsnotizen Haben Sie eine gute Präsentation Hoare Logic mit Arrays (jedoch ohne Fehlerprüfung).

Answer 2

Wie von Gilles erwähnt, gibt es ein Array -Zuweisungs -Axiom (siehe Gordons Notizen, Sec. 2.1.10): $$ dfrac {} { {q [a mapsto.store (i, expr)] } ; ; A [i] = expr ; ; {q }} $$ In Wörtern, wenn Sie eine Array -Zuordnung haben, dann das ursprüngliche Array durch Array ersetzen A.store(i,expr) das hat an Position i der Wert expr. Beachten Sie das, wenn Sie bereits haben A.store(i,vi) auf der Post und zuweisen A[j]=vj, dann solltest du bekommen A.store(j,vj).store(i,vi) als pre (ja, in dieser Reihenfolge - aktuell wird zuerst ausgeführt!).

Zusätzlich benötigen wir das Array Access Axiom: A.store(i,v)[i] kann durch ersetzt werden durch v ("Wenn Sie auf $ i $ TH Element zugreifen, das Sie gerade aktualisiert haben, geben Sie den zugewiesenen Wert zurück").

Ich denke, um ein Programm mit Arrays zu beweisen, ist korrekt ("keine außergewöhnlichen Zugriffe"), sind die oben genannten Axiome ausreichend. Betrachten wir das Programm:

...
A[i] = 12
...

Wir würden dieses Programm kommentieren:

...
@ {0<i<A_length}
A[i] = 12
...

wo A_length ist eine Variable, die die Arraylänge angibt. Versuchen Sie nun, die Annotation zu beweisen - nämlich nach hinten (von unten nach oben "wie normalerweise in Hoare -Proofs). Wenn Sie oben sind, erhalten Sie {false}, Dann kann der außer gebundene Zugriff auftreten. Andernfalls ist der Ausdruck, den Sie erhalten haben, die Voraussetzung, unter der keine außergewöhnlichen Zugriffe möglich sind. (Außerdem müssen wir sicherstellen, dass das Array wie erstellt wird int A=int[10]; Dann haben wir in der Post-Kondition {A_length==10}).