Comment traiter les tableaux pendant les preuves de correction de style Hoare

Question

Dans la discussion autour cette question, Gilles mentionne à juste titre que toute preuve de correction d'un algorithme qui utilise des tableaux a pour prouver qu'il n'y a pas un tableau hors des limites du terrain accès; en fonction du modèle d'exécution, cela provoquerait une erreur d'exécution ou d'accès à des éléments non-array.

Une technique commune pour effectuer de telles preuves de correction (au moins dans les études de premier cycle et probablement dans la vérification automatisée) est en utilisant

Était-ce utile?

Nous faire parvenir

La solution

Votre axiome est pas vraiment un axiome, il est des hypothèses manquantes. présentations simples de la logique de Hoare manipuler les formules de la forme $ \ {P \} C \ {P \} $ où $ P $ et $ P 'sont des formules logiques $ et $ C $ est une commande. Vous avez besoin de pour que $ C $ est bien formé . Dans les langues simples comme celles souvent utilisées pour une première introduction à la logique de Hoare, bien formedness est syntaxique: il est généralement une question de vérifier que $ C $ est conforme à une grammaire hors-contexte, et peut-être que les variables libres sont dans un autorisés. Si la langue comprend des constructions qui ont une correction sémantique, comme les accès aux éléments du tableau, vous devez ajouter des hypothèses pour exprimer cette exactitude sémantique.

Formellement, vous pouvez ajouter des jugements pour exprimer la correction des expressions et des commandes. Si les expressions ont pas d'effets secondaires, dont ils ont besoin, pas seulement postconditions conditions préalables. Par exemple, vous pouvez écrire des règles bien formedness telles que $$ \ Dfrac {\ {P \} \; \; E du texte {}} wf       {\ {P \ wedge 0 \ le E <\ mathrm {longueur} (A) \} \; \; A [E] \ texte {}} wf \ qquad \ Dfrac {\ {P \} \; \; Le texte de E_1 {wf} \ qquad \ {P \} \; \; E_2 de texte {}} wf       {\ {P \} \; \; E_1 + E_2 \ texte {}} wf $$ et permettre que des expressions bien formées dans les commandes: $$ \ Dfrac {\ {P [x \ leftarrow E] \} \; \; E du texte {}} wf       {\ {P [x \ leftarrow E] \} \; \; x: = E \ {P \}} $$

Une autre approche est de traiter toutes les expressions aussi bien formé, mais pour faire une expression qui implique un calcul mal formé a une valeur spéciale $ \ mathbf {erreur} $. Dans les langues avec les limites d'exécution, la vérification $ \ mathbf {erreur} signifie de $ « ce programme a soulevé une exception fatale ». Vous pouvez ensuite garder une trace de savoir si un programme errored à travers un prédicat $ \ mathbf {erreur} logique $; un programme est valable uniquement si vous pouvez prouver que son postcondition implique $ \ neg \ mathbf {erreur} $. $$ \ Dfrac {}       {\ {P [x \ leftarrow E] \} \; \; x: = E \; \; \ {P \ vee \ mathbf {erreur} \}} \ qquad \ Dfrac {P [x \ leftarrow E] \ implique E \ not \ rightarrow \ mathbf {erreur}}       {\ {P [x \ leftarrow E] \} \; \; x: = E \; \; \ {P \}} $$

Une autre approche consiste à considérer une triple Hoare à tenir que si le programme se termine correctement. Telle est l'approche usualy des programmes nonterminating: le postcondition détient lorsque la commande se termine, ce qui pourrait ne pas toujours le cas. Si vous traitez des erreurs d'exécution que la non-résiliation, vous balayez toutes les questions correctness sous le capot. Vous aurez toujours besoin de prouver l'exactitude du programme en quelque sorte, mais il n'a pas besoin d'être dans la logique de Hoare si vous préférez un autre formalisme pour cette tâche.

Par ailleurs, notez que l'expression ce qui se passe quand une variable composé tel qu'un tableau est modifié est plus impliqué que ce que vous avez écrit. Supposons que P $ était $, disons, $ \ mathrm {IsSorted} (A) $: la substitution $ A [i] \ leftarrow E $ ne changerait pas $ P $, mais l'affectation $ A [i] \ leftarrow P $ pourrait invalidate $ P $. Même si vous restreignez la syntaxe de prédicats parler uniquement des atomes, envisager la cession $ A [A [0] -1]: = A [0] $ sous la condition $ A [0] = 2 \ wedge A [1] = 3 $: vous ne pouvez pas faire une simple substitution pour obtenir le postcondition correct $ a [0] = 1 \ wedge a [1] = 1 $, vous devez évaluer $ a [0] $ (ce qui peut être difficile en général, puisque la condition pourrait ne pas spécifier une seule valeur possible pour $ a [0] $). Vous devez effectuer la substitution sur le tableau lui-même: $ A \ leftarrow A [i \ leftarrow E] $. Notes de cours de Mike Gordon ont une bonne présentation Hoare logique avec des tableaux (mais sans vérification d'erreur).

Answer 1

Votre axiome est pas vraiment un axiome, il est des hypothèses manquantes. présentations simples de la logique de Hoare manipuler les formules de la forme $ \ {P \} C \ {P \} $ où $ P $ et $ P 'sont des formules logiques $ et $ C $ est une commande. Vous avez besoin de pour que $ C $ est bien formé . Dans les langues simples comme celles souvent utilisées pour une première introduction à la logique de Hoare, bien formedness est syntaxique: il est généralement une question de vérifier que $ C $ est conforme à une grammaire hors-contexte, et peut-être que les variables libres sont dans un autorisés. Si la langue comprend des constructions qui ont une correction sémantique, comme les accès aux éléments du tableau, vous devez ajouter des hypothèses pour exprimer cette exactitude sémantique.

Formellement, vous pouvez ajouter des jugements pour exprimer la correction des expressions et des commandes. Si les expressions ont pas d'effets secondaires, dont ils ont besoin, pas seulement postconditions conditions préalables. Par exemple, vous pouvez écrire des règles bien formedness telles que $$ \ Dfrac {\ {P \} \; \; E du texte {}} wf       {\ {P \ wedge 0 \ le E <\ mathrm {longueur} (A) \} \; \; A [E] \ texte {}} wf \ qquad \ Dfrac {\ {P \} \; \; Le texte de E_1 {wf} \ qquad \ {P \} \; \; E_2 de texte {}} wf       {\ {P \} \; \; E_1 + E_2 \ texte {}} wf $$ et permettre que des expressions bien formées dans les commandes: $$ \ Dfrac {\ {P [x \ leftarrow E] \} \; \; E du texte {}} wf       {\ {P [x \ leftarrow E] \} \; \; x: = E \ {P \}} $$

Une autre approche est de traiter toutes les expressions aussi bien formé, mais pour faire une expression qui implique un calcul mal formé a une valeur spéciale $ \ mathbf {erreur} $. Dans les langues avec les limites d'exécution, la vérification $ \ mathbf {erreur} signifie de $ « ce programme a soulevé une exception fatale ». Vous pouvez ensuite garder une trace de savoir si un programme errored à travers un prédicat $ \ mathbf {erreur} logique $; un programme est valable uniquement si vous pouvez prouver que son postcondition implique $ \ neg \ mathbf {erreur} $. $$ \ Dfrac {}       {\ {P [x \ leftarrow E] \} \; \; x: = E \; \; \ {P \ vee \ mathbf {erreur} \}} \ qquad \ Dfrac {P [x \ leftarrow E] \ implique E \ not \ rightarrow \ mathbf {erreur}}       {\ {P [x \ leftarrow E] \} \; \; x: = E \; \; \ {P \}} $$

Une autre approche consiste à considérer une triple Hoare à tenir que si le programme se termine correctement. Telle est l'approche usualy des programmes nonterminating: le postcondition détient lorsque la commande se termine, ce qui pourrait ne pas toujours le cas. Si vous traitez des erreurs d'exécution que la non-résiliation, vous balayez toutes les questions correctness sous le capot. Vous aurez toujours besoin de prouver l'exactitude du programme en quelque sorte, mais il n'a pas besoin d'être dans la logique de Hoare si vous préférez un autre formalisme pour cette tâche.

Par ailleurs, notez que l'expression ce qui se passe quand une variable composé tel qu'un tableau est modifié est plus impliqué que ce que vous avez écrit. Supposons que P $ était $, disons, $ \ mathrm {IsSorted} (A) $: la substitution $ A [i] \ leftarrow E $ ne changerait pas $ P $, mais l'affectation $ A [i] \ leftarrow P $ pourrait invalidate $ P $. Même si vous restreignez la syntaxe de prédicats parler uniquement des atomes, envisager la cession $ A [A [0] -1]: = A [0] $ sous la condition $ A [0] = 2 \ wedge A [1] = 3 $: vous ne pouvez pas faire une simple substitution pour obtenir le postcondition correct $ a [0] = 1 \ wedge a [1] = 1 $, vous devez évaluer $ a [0] $ (ce qui peut être difficile en général, puisque la condition pourrait ne pas spécifier une seule valeur possible pour $ a [0] $). Vous devez effectuer la substitution sur le tableau lui-même: $ A \ leftarrow A [i \ leftarrow E] $. Notes de cours de Mike Gordon ont une bonne présentation Hoare logique avec des tableaux (mais sans vérification d'erreur).

Answer 2

Comme mentionné par Gilles, il y a un axiome d'affectation de tableau (voir notes de Gordon, Sec 2.1.10 ).: $$ \ Dfrac {}       {\ {Q [A \ mapsto A.store (i, expr)] \} \; \; A [i] = expr \; \; \ {Q \}} $$ En d'autres termes, si vous avez une mission de tableau, puis remplacer le tableau original par tableau A.store(i,expr) qui a à la position i la valeur expr. Notez que si vous avez déjà A.store(i,vi) sur le poteau, et assign A[j]=vj, alors vous devriez obtenir A.store(j,vj).store(i,vi) comme avant. (Oui, dans cet ordre - mise à jour récente est exécutée en premier)

De plus, nous avons besoin de l'axiome d'accès au tableau: A.store(i,v)[i] peut être remplacé par v ( « si vous accédez à $ i $ e élément que vous venez de mise à jour, puis retourner la valeur attribuée »)

.

Je pense que pour prouver un programme avec des tableaux est correct ( « pas hors limite les accès »), les axiomes ci-dessus suffisent. Considérons le programme:

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

Nous n'annoter ce programme:

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

où A_length est une variable qui indique la longueur du tableau. Maintenant, essayez de prouver l'annotation - à savoir, le travail hors arrière (de bas en haut, « comme d'habitude » dans les preuves Hoare). Si vous obtenez sur {false}, l'accès de borne peut se produire, sinon, l'expression que vous avez est la condition sine qua non en vertu de laquelle aucun hors-limite les accès sont possibles. (Aussi, nous devons faire en sorte que lorsque tableau est créé comme int A=int[10]; puis dans la post-condition que nous avons {A_length==10}).