如何在 Dafny 中描述这个简单算法的不变量？

Question

正在尝试正式验证以下问题。 https://leetcode.com/problems/count-equal-and-divisible-pairs-in-an-array/

给定一个长度为 n 的 0 索引整数数组 nums 和一个整数 k，return 对数 (i, j) 其中 0 <= i < j < n，这样 nums[i] == nums[j] 和 (i * j) 可以被 k.

整除

function countPairs(nums: number[], k: number): number {
    let count = 0;
    for(let i = 0; i < nums.length-1; i++) {
        for(let j = i+1; j < nums.length; j++) {
            if(nums[i] == nums[j] && (i*j) % k == 0) {
                count++;
            }
        }
    }
    return count;
};

我不知道如何验证这个愚蠢的东西。也许我错过了对问题的超级简单描述，而且我太专注于不相关的细节。

我的策略开始于尝试将结果与匹配集的基数进行比较。然而，让愚蠢的人相信两个循环中集合匹配的基数似乎是不可能的。

function method satPairs(nums: seq<nat>, k: nat, a: nat, b: nat): bool
    requires k > 0
    requires a <= b < |nums| 
{
    nums[a] == nums[b] && (a*b) % k == 0
}

function matchPairs(nums: seq<nat>, k: nat): nat 
    requires k > 0
{
    |set x,y | 0 <= x < y < |nums| && nums[x] == nums[y] && (x*y) % k == 0 :: (x,y)|
}

function method pairsI(nums: seq<nat>, k: nat, i: nat): set<(nat, nat)> 
    requires k > 0
    requires 0 <= i < |nums|
    ensures forall x,y :: 0 <= x < i && x <= y < |nums| && satPairs(nums, k, x, y) ==> (x,y) in pairsI(nums, k, i)
{
    set x: nat,y:nat | 0 <= x < i && x <= y < |nums| && satPairs(nums, k, x, y) :: (x,y)
}

我还尝试使用可以一次使用一列计算匹配对的方法来设置基于计数的不变量。但是，我运行陷入了不兼容的情况，在 while 循环之前和之后维护不变量。我希望可以递归地定义这些辅助函数，允许对每个不变量的两个循环内使用的结果进行一些归纳，但它没有用。

function countSeqPairs(nums: seq<nat>, k: nat, start: nat,  stop: nat): nat 
    requires k > 0
    requires start <= stop <= |nums|
    decreases |nums|-start, |nums|-stop
{
    if start > stop || stop >= |nums| || start >= |nums| then 0 else 
    if stop < |nums| then (if satPairs(nums, k, start, stop) then 1 + countSeqPairs(nums, k, start, stop+1) else countSeqPairs(nums, k, start, stop+1)) else countSeqPairs(nums, k, start+1, stop+2)

}

function countSeqSlice(nums: seq<nat>, k: nat, start: nat, stop: nat): nat 
    requires k > 0
    requires start <= stop <= |nums|
    decreases |nums| - stop
{
    if start > stop || stop >= |nums| then 0
    else if satPairs(nums, k, start, stop) then 1 + countSeqSlice(nums, k, start, stop+1) else countSeqSlice(nums, k, start, stop+1)
}

这是主要方法，对不变量进行了各种无效尝试。

method countPairs(nums: seq<nat>, k: nat) returns (count: nat) 
    requires k > 0
    requires |nums| >= 2;
{
    count := 0;
    //ghost var cpairs: set<(nat, nat)> := {};
    for i : nat := 0 to |nums|-2 
        invariant count >= 0
        //invariant cpairs == pairsI(nums, k, i)
    {
        // ghost var occount := count;
        // ghost var increment := 0;
        for j : nat := i+1 to |nums|-1 
            invariant count >= 0
            // invariant count == occount + increment
            // invariant satPairs(nums, k, i, j) ==> increment == increment + 1 
            // invariant count == 0 || satPairs(nums, k, i, j) ==> count == count + 1
            //invariant cpairs == pairsI(nums, k, i) + set z: nat | i+1 <= z <= j && satPairs(nums, k, i, z) :: (i, z)
        {
            // ghost var currcount := count;
            // if nums[i] == nums[j] && (i*j)% k == 0 {
            if  i+1 <= j <= j && satPairs(nums, k, i, j) {
                // increment := increment + 1;
                //cpairs := {(i,j)}+cpairs;
                count := count + 1;
            }
        }
    }
}

对于要确保什么，似乎没有比方法本身更短的描述了。除了帮助解决上述问题外，我还有三个问题，通常您如何描述像这样明显任意的事物的不变量？

其次，可以使用什么策略来处理在循环运行之前不为真但之后为真的循环不变量？它往往是初始条件设置为 0 或其他一些空值，但是在循环的第 0 次迭代之后它将设置为某个值，然后不变量失败。我一直运行关注这种情况，感觉应该有某种标准的保护措施。

最后，可以或应该在方法 ensure 语句中使用幽灵变量吗？

Answer 1

这是一种方法。

function method satPairs(nums: seq<nat>, k: nat, a: nat, b: nat): bool
    requires k > 0
    requires a <= b < |nums| 
{
    nums[a] == nums[b] && (a*b) % k == 0
}

function matchPairsHelper(nums: seq<nat>, k: nat, bound: int): set<(int, int)>
  requires k > 0
  requires bound <= |nums|
{
    set x,y | 0 <= x < bound && x < y < |nums| && satPairs(nums, k, x, y) :: (x,y)
}

function matchPairs(nums: seq<nat>, k: nat): set<(int, int)>
  requires k > 0
{
  matchPairsHelper(nums, k, |nums|)
}

function innerMatchPairsHelper(nums: seq<nat>, k: nat, outer: int, inner_bound: int): set<(int, int)>
  requires k > 0
  requires inner_bound <= |nums|
{
    set y | 0 <= outer < y < inner_bound && satPairs(nums, k, outer, y) :: (outer,y)
}

method countPairs(nums: seq<nat>, k: nat) returns (count: nat) 
    requires k > 0
    requires |nums| >= 2
    ensures count == |matchPairs(nums, k)|
{
  count := 0;
  for i : nat := 0 to |nums|
    invariant count == |matchPairsHelper(nums, k, i)|
  {
    for j : nat := i+1 to |nums|
      invariant count == |matchPairsHelper(nums, k, i)| + |innerMatchPairsHelper(nums, k, i, j)|
    {
      assert innerMatchPairsHelper(nums, k, i, j+1) ==
        (if satPairs(nums, k, i, j) then {(i, j)} else {}) + innerMatchPairsHelper(nums, k, i, j);
      if satPairs(nums, k, i, j) {
        count := count + 1;
      } 
    }
    assert matchPairsHelper(nums, k, i+1) == matchPairsHelper(nums, k, i) + innerMatchPairsHelper(nums, k, i, |nums|);
  }
}

一些注意事项：

James 的集合推导规则：永远不要将集合推导用作任何较大表达式的一部分，而只能作为 return 设置的函数的主体。这有助于在断言中多次引用该集合，而不会混淆 Dafny。
James 的基数规则：Dafny 永远不会证明两个基数相等。您必须手动要求它证明两个集合相等，然后它会得出基数相等的结论。
我没有真正看你的不变量。我只是想写下循环在做什么。外部循环是 x 坐标上的循环。所以不变量是所有“正确的”对都被计算为所有小于 i 的 x 坐标（对于 y 的所有值）。然后对于内层循环，不变量是精确的 x 坐标 i 的所有对都已计数到 j。我为这些概念定义了两个函数。
除此之外，只需要在几个地方声明一些集合等式。

关于您的其他问题：

how do you describe an invariant for something which is sort of manifestly arbitrary like this?

我不确定我是否理解问题。您是在问“我如何为这个后置条件发现正确的循环不变量？”或者“当它看起来和代码本身一样长时，我该如何声明后置条件？”
what strategy can be used to handle loop invariants which are not true before the loop is run but are afterwards?

我的解决方案中不需要这个，但如果您确实需要它，那么最简单的方法就是 i == 0 || <invariant that is true only after loop starts>。一般来说，我认为这样的不变量有“难闻的气味”，并试图通过重构来避免它们。但有时它们是不可避免的。
can or should ghost variables be used in method ensure statements?

我也不确定我是否理解这一点。您不能在 ensures 子句 中引用方法的任何局部变量， 那些被该方法 return 编辑的除外。如果需要，您可以 return 一个幽灵变量，如
```
method Foo() returns (bar: int, ghost baz: int)
  ensures ... mentions bar and baz just fine ...
```
回答这个问题吗？

如何在 Dafny 中描述这个简单算法的不变量？

How do I describe the invariants for this simple algorithm in Dafny?

loop-invariant

dafny