在 Dafny 中修改另一个数组后断言失败

Question

我运行在达夫尼遇到了一个奇怪的问题。我试图在这里尽可能多地提取它：https://rise4fun.com/Dafny/F7sK

问题是，修改truthAssignment后，stack.valid即使stack.valid 不知道 truthAssignment。

assert stack.valid();
truthAssignment[variable] := 1;
assert stack.valid();  // assertion violation

Answer 1

以下为我验证：

assert stack.valid();
ghost var old_stack := stack.stack[..];
truthAssignment[variable] := 1;
assert stack.stack[..] == old_stack;
assert stack.valid();

我不太明白为什么会这样，但它属于 "extentional equality for sequences is hard for Dafny" 的一般类别。

Answer 2

Dafny 无法验证断言 assert stack.valid(); 的原因是 valid() 正文中的最后一个连词：

(forall c :: c in contents ==>
  exists i,j :: 0 <= i < stack.Length 
             && 0 <= j < |stack[i]| 
             && stack[i][j] == c)

它的形式是forall ... exists ...，证明这样的条件是不变的对于验证者来说是很困难的。一旦你弄清楚这是 valid() 中验证者无法证明的部分（你可以通过手动内联 valid() 的定义来代替你的断言来证明），那么解决方案是给验证者一些帮助。

当验证者——或人类，就此而言——试图证明形式 forall c :: P(c) 的东西时，它会组成一个任意的 c，然后尝试证明“ P(c)”。（逻辑学家称此规则为 "universal introduction"。）简单。然后，为了证明 exists i,j :: Q(i,j) 形式的东西，验证者寻找“Q(i,j)”的见证人。（这被称为"existential introduction"。）在这里，验证者不是特别有创意，经常需要帮助。有时，您必须自己弄清楚一些 i 和 j，然后断言 Q(i,j)。其他时候，只需提及所需 Q(i,j) 的某些组成部分，然后验证者就会找出其余部分。具体怎么做可以是一个反复试验的过程。

James 的上述补救措施之所以奏效，是因为它在更新 truthAssignment[variable] := 1; 之后提到了 stack.stack[..]。这以一种让验证者看到光的方式让验证者发痒。只需写下简单证明的断言：

assert 0 <= |stack.stack[..]|;  // mentioning stack.stack[..] helps the verifier in the next line

更新后也适用于这种情况。

鲁斯坦

在 Dafny 中修改另一个数组后断言失败

Assertion fails after modifying another array in Dafny

dafny