Come comportarsi con gli array durante le prove di correttezza in stile Hoare

Question

Nella discussione intorno questa domanda , Gilles cita giustamente che qualsiasi prova di correttezza di un algoritmo che utilizza le matrici ha per dimostrare che non esistono fuori dal campo accessi matrice; a seconda del modello di esecuzione, ciò causerebbe un errore di esecuzione o l'accesso a elementi non-array.

Una tecnica comune per eseguire tali prove di correttezza (almeno negli studi undergrad e, probabilmente, a verifica automatica) è quello di utilizzare logica Hoare . Non sono a conoscenza che il set standard di regole containes nulla in materia di matrici; sembrano essere limitato alle variabili monadici.

posso immaginare l'aggiunta di assiomi della forma

$ \ qquad \ displaystyle \ frac {} {\ {0 \ leq i \ lt A. \ mathrm {lunghezza} \ terra {P [A [i] / E]} \} \ A [i]: = E; \ \ {P \}} $

Tuttavia, non mi è chiaro come si dovrebbe fare con un accesso agli array sul lato destro della strada, vale a dire se è parte di un complesso espressione $ E $ in qualche dichiarazione $ x:. = E $

Come possono gli array accessi essere modellati nella logica Hoare in modo che l'assenza di accessi non validi può e deve essere provata per la correttezza del programma?

Le risposte possono presumere che Noi non consentire elementi di un array da utilizzare nelle dichiarazioni diverse da $ A [i]: = E $ o come parte di un po 'di $ E $ in $ x: = E $ in quanto ciò non limita espressività; possiamo sempre assegnare una variabile temporanea il valore desiderato, vale a dire scrivere $ t: = A [i]; \ \ mathtt {if} (t> 0) \ puntini $ invece di $ \ mathtt {if} (A [i]> 0) \ puntini $.

Answer 1

Il tuo assioma in realtà non è un assioma, è ipotesi manca. Semplici presentazioni di logica Hoare manipolano formule del \ {P \} C \ {P '\} $ dove $ P $ e $ P' $ sono formule logiche e $ C $ è un comando modulo $. Si ha bisogno di in modo che $ C $ è ben formato . In linguaggi semplici come quelli spesso utilizzati per una prima introduzione alla logica Hoare, ben formati è sintattico: è in genere una questione di verificare che $ C $ conforme ad una grammatica context-free, e possibilmente che le variabili libere sono all'interno di un consentito set. Se la lingua include costrutti che hanno una correttezza semantica, come accessi a elementi di un array, è necessario aggiungere le ipotesi per esprimere questa semantica correttezza.

Formalmente, è possibile aggiungere i giudizi di esprimere la correzione di espressioni e comandi. Se le espressioni non hanno effetti collaterali, non hanno bisogno di post-condizioni, solo precondizioni. Ad esempio, è possibile scrivere regole ben formati, come $$ \ Dfrac {\ {P \} \; \; E \ text {}} wf {\ {P \ cuneo 0 \ le E <\ mathrm {} lunghezza (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 $$ e consentire solo le espressioni ben formate nei comandi: $$ \ Dfrac {\ {P [x \ leftarrow E] \} \; \; E \ text {}} wf {\ {P [x \ leftarrow E] \} \; \; x: = E \ {P \}} $$

Un approccio diverso è quello di trattare tutte le espressioni come ben formato, ma per rendere ogni espressione che coinvolge un calcolo mal formate hanno una speciale mathbf {error} $ valore di $ \. In lingue con limiti di run-time di controllo o di $ \ mathbf {error} $ significa “questo programma ha sollevato un'eccezione irreversibile”. Si potrebbe quindi tenere traccia di se un programma errored attraverso una logica dei predicati $ \ mathbf {Error} $; un programma è valido solo se si può dimostrare che la sua postcondizione implica $ neg \ mathbf {Error} $ \. $$ \ Dfrac {} {\ {P [x \ leftarrow E] \} \; \; x: = E \; \; \ {P \ vee \ mathbf {Error} \}} \ qquad \ Dfrac {P [x \ leftarrow E] \ implica E \ non \ rightarrow \ mathbf {error}} {\ {P [x \ leftarrow E] \} \; \; x: = E \; \; \ {P \}} $$

Un altro approccio è quello di considerare un Hoare tripla per contenere solo se il programma termina correttamente. Questo è l'approccio prenotiamo per nonterminating programmi: la postcondizione tiene quando i termina di comando, che potrebbero non sempre accadere. Se si trattano errori di runtime come non-terminazione, si spazzare tutte le questioni di correttezza sotto il cofano. Sarà ancora bisogno di dimostrare la correttezza del programma in qualche modo, ma non deve essere nella logica di Hoare, se si preferisce qualche altro formalismo per quel compito.

A proposito, si noti che esprimono ciò che accade quando una variabile composto come un array viene modificato è più coinvolto che quello che hai scritto. Supponiamo che $ P $ è stato, diciamo, $ \ mathrm {IsSorted} (A) $: la sostituzione $ A [i] \ leftarrow E $ non cambierebbe $ P $, ma l'assegnazione $ A [i] \ leftarrow P $ forza invalidate $ P $. Anche se si limita la sintassi dei predicati solo a parlare di atomi, prendere in considerazione l'assegnazione $ A [A [0] -1]: = A [0] $ sotto la precondizione $ A [0] = 2 \ wedge A [1] = 3 $: non si può fare una semplice sostituzione per ottenere il corretto postcondizione $ a [0] = 1 \ wedge a [1] = 1 $, è necessario valutare $ a [0] $ (che può essere difficile, in generale, dal momento che la precondizione potrebbe non specificare un singolo valore possibile per $ a [0] $). È necessario eseguire la sostituzione sulla matrice stessa: $ A \ leftarrow A [i \ leftarrow E] $. dispense di Mike Gordon hanno una buona presentazione Hoare logica con array (ma senza controllo degli errori).

Answer 2

Come menzionato da Gilles, c'è un assioma assegnazione array (vedi note di Gordon, Sez 2.1.10 ).: $$ \ Dfrac {} {\ {Q [A \ mapsto A.store (i, espressione)] \} \; \; A [i] = expr \; \; \ {Q \}} $$ In parole, se si dispone di un'assegnazione matrice, quindi sostituire la matrice originale A.store(i,expr) matrice che presenta in posizione i valore expr. Si noti che se si dispone già di A.store(i,vi) sul palo, e A[j]=vj assegnare, allora si dovrebbe ottenere A.store(j,vj).store(i,vi) come il pre. (Sì, in questo ordine -! Recente aggiornamento viene eseguito per primo)

Inoltre, abbiamo bisogno l'assioma di accesso agli array: A.store(i,v)[i] può essere sostituito da v ( "se si accede a $ i $ esimo elemento che appena aggiornato, quindi restituire il valore assegnato")

.

Credo che al fine di dimostrare un programma con gli array è corretto ( "nessun out-of-bound accessi"), gli assiomi di cui sopra sono sufficienti. Prendiamo in considerazione il programma:

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

sarebbe annotare questo programma:

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

dove A_length è una variabile che specifica la lunghezza della matrice. Ora provate a dimostrare l'annotazione - vale a dire, il lavoro fuori indietro (dal basso verso l'alto "come di solito" in prove Hoare). Se sulla parte superiore si ottiene {false}, allora il fuori accesso vincolato può accadere, in caso contrario, l'espressione che hai è il presupposto in base al quale nessun accessi out-of-bound sono possibili. (Anche, dobbiamo fare in modo che, quando array è creato come int A=int[10]; poi nel post-condizioni che abbiamo {A_length==10}).