如何在hoare式的正确性证明期间处理阵列

Question

在周围的讨论中 这个问题, ，吉尔斯正确地提到，使用数组的任何正确性证明必须证明没有界外数组访问；根据运行时模型，这将导致运行时错误或对非阵列元素的访问。

执行此类正确性证明的一种常见技术（至少在本科研究和自动验证中）是使用 Hoare逻辑. 。我不知道标准规则包含与数组有关的任何内容；它们似乎仅限于单声道变量。

我可以想象添加表格的公理

美元 {p }} $

但是，我尚不清楚您如何处理右侧的数组访问，即，如果它是某些语句$ x：= e $的复杂表达式$ e $的一部分。

如何以Hoare逻辑为模型来建模数组访问，以便没有无效的访问权限可以并且必须被证明为程序正确性？

答案可以假设我们不允许在$ a [i]：= e $的语句中使用的数组元素或作为$ x：= e $的某些$ e $的一部分，因为这不限制表达式；我们始终可以分配一个临时变量所需的值，即写入$ t：= a [i]; dots $而不是$ mathtt {if}（a [i]>） 0）点$。

Answer 1

您的公理并不是真正的公理，而是缺失的假设。 hoare逻辑操纵公式的简单演示$ {p } c {p'} $，其中$ p $和$ p'$是逻辑公式，$ c $是命令。你确实需要 确保$ c $成型. 。在简单的语言中，例如通常用于首次介绍hoare逻辑的语言，形式良好的是句法：通常是检查$ c $符合无上下文的语法的问题允许集。如果该语言包含具有语义正确性的构造，例如访问数组元素，则需要添加假设以表达这种语义正确性。

正式地，您可以添加判断以表达表达式和命令的校正。如果表达式没有副作用，则不需要后条件，只需要前提条件。例如，您可以编写良好的规则，例如$$ dfrac { {p } ; ; e text {wf}}} { {p wedge 0 le e < mathrm {length}（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}} $$，并且仅允许命令中的良好表达式：$$ dfrac { {p [x leftarrow e] } ; ;; e text {wf}} { {p [x leftarrow e] } ; ; x：= e {p }} $$

一种不同的方法是处理所有表达式且形成良好的方法，但是使任何涉及不正确计算的表达式具有特殊的值$ mathbf {error} $。在具有运行时范围检查的语言中，$ mathbf {error} $表示“此程序提出了致命的例外”。然后，您会跟踪程序是否通过逻辑谓词$ mathbf {error} $出错。只有在您可以证明其后条件暗示$ neg mathbf {error} $的情况下，程序才有效。 $$ dfrac {} { {p [x leftarrow e] } ; ; x：= e ; ; {p vee mathbf {error} }}} qquad dfrac {p [x leftarrow e] nim e not not rightarrow rightarrow mathbf {erry}}} { ; ; x：= e ; ; {p }} $$

另一种方法是考虑只有在程序正确终止的情况下，只有三倍才能持有。这是非终止程序的常用方法：命令终止时，后条件可能并非总是发生。如果将运行时错误视为非终止，则扫荡在引擎盖下的所有正确性问题。您仍然需要以某种方式证明该程序的正确性，但是如果您更喜欢其他形式主义，则不必处于Hoare逻辑中。

顺便说一句，请注意，表达当修改阵列之类的化合物变量时会发生什么，而不是您编写的内容。假设$ p $是$ mathrm {issorted}（a）$：替换$ a [i] leftarrow e $不会更改$ p $无效$ P $。即使您将谓词的语法限制为仅谈论原子，也要考虑分配$ a [a [0] -1]：= = a [0] $下的先决条件$ a [0] = 2 wedge a [1] = 3 $：您不能做一个简单的替代来获得正确的后条件$ a [0] = 1 wedge a [1] = 1 $，您需要评估$ a [0] $（这通常很难，由于先决条件可能无法指定$ a [0] $）的单个可能值。您需要在数组本身上执行替换：$ a leftarrow a [i leftarrow e] $。 迈克·戈登（Mike Gordon）的讲义 具有良好的演示文稿hoare逻辑，带有数组（但没有错误检查）。

Answer 2

正如吉尔斯（Gilles）提到的，有一个数组分配公理（请参阅 戈登笔记，第二秒。 2.1.10）：$$ dfrac {} { {q [a mapsto a.store（i，expr）] } ; ; a [i] = expr ; ; {q }} $$在单词中，如果您有数组分配，然后用数组替换原始数组 A.store(i,expr) 有位置 i 价值 expr。请注意，如果您已经有 A.store(i,vi) 在帖子上，分配 A[j]=vj, ，那你应该得到 A.store(j,vj).store(i,vi) 作为PRE（是的，按此顺序 - 最新更新首先执行！）。

此外，我们需要数组访问公理： A.store(i,v)[i] 可以取代 v （“如果您访问刚刚更新的$ i $ th元素，则返回分配的值”）。

我认为，为了证明具有数组的程序是正确的（“无界方访问”），上述公理就足够了。让我们考虑程序：

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

我们会注释该程序：

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

在哪里 A_length 是指定数组长度的变量。现在，尝试证明注释 - 即，将其向后处理（从下到顶部，“通常”在Hoare证明中）。如果最重要的话，你会得到 {false}, ，然后可能会发生限制访问，否则，您获得的表达式是不可能的前提条件。 （另外，我们需要确保创建数组时 int A=int[10]; 然后，在条件后我们有 {A_length==10}).