为什么我的 Dafny 断言在 x == y 和 x != y 上都失败了？

Question

我正在学习教程 here，代码似乎是正确的，但是当我使用断言进行测试时，出现错误！

运行程序打印出正确答案，但断言似乎自相矛盾。当显示反例时，似乎 -1 被考虑，即使它不应该被考虑。

method binarySearch(a:array<int>, key:int) returns (r:int) 
    requires forall i,j :: 0 <= i <= j < a.Length ==> a[i] <= a[j]
    ensures 0 <= r ==> r < a.Length && a[r] == key 
    ensures r < 0 ==> forall i :: 0 <= i < a.Length ==> a[i] != key
{

    var lo, hi := 0, a.Length;

    while (lo < hi) 
        invariant 0 <= lo <= hi <= a.Length
        invariant forall i :: 0 <= i < lo ==> a[i] < key
        invariant forall i :: hi <= i < a.Length ==> a[i] > key
        decreases hi - lo;
    {
        var mid := (lo + hi) / 2;
        if key < a[mid] 
        {
            hi := mid;
        }
        else if key > a[mid]
        {
            lo := mid + 1;
        }
        else 
        {
            return mid;
        }
    }

    return -1;
}


// tests
method Main() 
{
    var a := new int[6][1,2,3,4,5,6];
    var r := binarySearch(a, 5);

    assert r == 4;  // fails
    assert r != 4;  // also fails
}

这是一个错误还是我遗漏了什么？

Answer 1

Dafny 使用 post-condition 方法来推理方法调用的结果。

这里post-condition是

如果 r 在 0 到数组长度之间，则 r 处的元素等于键
如果r小于0，则不在数组中。

Dafny 不知道其中哪些是空洞的，但你可以暗示一下。用 if r >= 0 && r < a.Length 保护 assert r == 4 将使其验证。

或者在assert r == 4之前添加assert a[4] == 5之后，验证将通过。

出现奇怪错误的原因是在调用二进制搜索之后，这些是 dafny 已知的事实

assert (r < 0) || (0 <= r < 6)
assert (r < 0) ==> forall i :: 0 <= i < a.Length ==> a[i] != 5
assert (0 <= r < 6) ==> a[r] == 5

用这些既不能证明r == 4也不能证明r != 4。默认情况下，Dafny 似乎不会向证明者传播 assert a[0] == 1 等信息，您必须明确要求它。

为什么我的 Dafny 断言在 x == y 和 x != y 上都失败了？

Why is my Dafny assertion failing on both x == y and x != y?

dafny