不变集可能会有所不同

Question

一种将整数数组的负元素复制到另一个数组的方法具有属性结果中的元素集是原始数组中元素的子集，保持不变复制过程中。

下面代码中的问题在于，一旦我们在结果数组中写入内容，Dafny 就会以某种方式忘记原始集合没有改变。如何解决这个问题？

method copy_neg (a: array<int>, b: array<int>)
  requires a != null && b != null && a != b
  requires a.Length == b.Length
  modifies b
{
  var i := 0;
  var r := 0;
  ghost var sa := set j | 0 <= j < a.Length :: a[j];
  while i < a.Length
    invariant 0 <= r <= i <= a.Length
    invariant sa == set j | 0 <= j < a.Length :: a[j]
  {
    if a[i] < 0 {
      assert sa == set j | 0 <= j < a.Length :: a[j]; // OK
      b[r] := a[i];
      assert sa == set j | 0 <= j < a.Length :: a[j]; // KO!
      r := r + 1;
    }
    i := i + 1;
  }
}

编辑

遵循，用序列上的谓词替换集合的包含是最有效的。

这是完整的规范（针对具有不同元素的数组）。 post-条件必须在循环不变量中详细说明一点，并且在循环中间保留了一个愚蠢的断言，但是所有的幽灵变量都消失了，这很好。

method copy_neg (a: array<int>, b: array<int>)
  returns (r: nat)
  requires a != null && b != null && a != b
  requires a.Length <= b.Length
  modifies b
  ensures 0 <= r <= a.Length
  ensures forall x | x in a[..] :: x < 0 <==> x in b[..r]
{
  r := 0;
  var i := 0;
  while i < a.Length
    invariant 0 <= r <= i <= a.Length
    invariant forall x | x in b[..r] :: x < 0
    invariant forall x | x in a[..i] && x < 0 :: x in b[..r]
  {
    if a[i] < 0 {
      b[r] := a[i];
      assert forall x | x in b[..r] :: x < 0;
      r := r + 1;
    }
    i := i + 1;
  }
}

Answer 1

这确实令人困惑。我将在下面解释为什么 Dafny 难以证明这一点，但首先让我给出一些让它通过的方法。

第一个解决方法

使证明通过的一种方法是在 b[r] := a[i]; 行之后插入以下 forall 语句。

forall x | x in sa
  ensures x in set j | 0 <= j < a.Length :: a[j]
{
  var j :| 0 <= j < a.Length && x == old(a[j]);
  assert x == a[j];
}

forall 陈述是 sa <= set j | 0 <= j < a.Length :: a[j] 的证明。我将在下面回过头来解释为什么这样做。

第二种解决方法

一般来说，在 Dafny 中推理数组时，最好使用 a[..] 语法将数组转换为数学序列，然后使用该序列。如果你真的需要使用set的元素，你可以使用set x | x in a[..]，而且你会比使用set j | 0 <= j < a.Length :: a[j].

系统地将 set j | 0 <= j < a.Length :: a[j] 替换为 set x | x in a[..] 会使您的程序进行验证。

第三种解决方案

弹出一个级别来指定你的方法，似乎你实际上并不需要提及所有元素的集合。相反，您可以说 "every element of b is an element of a" 之类的话。或者，更正式地说 forall x | x in b[..] :: x in a[..]。这不是您的方法的有效后置条件，因为您的方法可能不会填写所有 b。由于我不确定您的其他限制是什么，所以我会把它留给您。

解释

Dafny 的元素类型为 A 的集合被转换为 Boogie 映射 [A]Bool，其中元素映射为真，前提是它在集合中。 set j | 0 <= j < a.Length :: a[j] 等理解被翻译成 Boogie 地图，其定义涉及存在量词。这种特殊的理解转化为将 x 映射到

的地图

exists j | 0 <= j < a.Length :: x == read($Heap, a, IndexField(j))

其中 read 表达式是 a[j] 的 Boogie 翻译，特别是，它使堆显式化。

所以，要证明一个元素在推导定义的集合中，Z3需要证明一个存在量词，这很难。 Z3 使用 triggers 来证明这样的量词，Dafny 告诉 Z3 在尝试证明这个量词时使用触发器 read($Heap, a, IndexField(j))。结果证明这不是一个很好的触发器选择，因为它提到了堆的当前值。因此，当堆发生变化时（即更新 b[r] 之后），触发器可能不会触发，并且您会得到一个失败的证明。

Dafny 允许您使用 {:trigger} 属性自定义它用于集合理解的触发器。不幸的是，在 Dafny 级别没有很好的触发器选择。然而，这个程序在 Boogie/Z3 级别的合理触发器将只是 IndexField(j)（尽管对于一般的此类表达式，这可能是一个不好的触发器，因为它过于笼统）。如果 Dafny 没有另行通知，Z3 本身将推断出此触发器。你可以让 Dafny 说 {:autotriggers false}，像这样

invariant sa == set j {:autotriggers false} | 0 <= j < a.Length :: a[j]

此解决方案并不令人满意，需要对 Dafny 的内部结构有详细的了解。但是现在我们已经理解了它，我们也可以理解我提出的其他解决方法。

对于第一个解决方法，证明通过了，因为 forall 语句提到了 a[j]，这是触发器。这使得Z3成功证明存在。

对于第二种解决方法，我们简化了集合推导表达式，使其不再引入存在量词。相反，理解 set x | x in a[..] 被转换为映射 x 到

的映射

x in a[..]

（忽略 a[..] 是如何翻译的细节）。这意味着 Z3 永远不必证明存在性，因此通过其他方面非常相似的证明。

第三个解决方案出于类似的原因起作用，因为它不使用推导式，因此没有问题的存在量词/

不变集可能会有所不同

Invariant set may vary

dafny

编辑

第一个解决方法

第二种解决方法

第三种解决方案

解释