Dafny 无法在 while 循环中验证多个迭代器

Question

我想要一个分配两个迭代器的函数，然后进入一个循环，只要 MoveNext() returns 为真，就会在迭代器上重复调用 MoveNext()。但是，在迭代器违反（或阻止 Dafny 验证）另一个迭代器所需的不变量时调用 MoveNext()：

iterator Iter1()
{ yield; }

iterator Iter2()
{ yield; }

method main()
    decreases *
{
    var iter1 := new Iter1();
    var iter2 := new Iter2();
    var iter1More := true;
    var iter2More := true;

    while (iter1More || iter2More)
        invariant iter1More ==> iter1.Valid() && fresh(iter1._new)
        // The following invariant is not verified
        invariant iter2More ==> iter2.Valid() && fresh(iter2._new)
        decreases *
    {
        if (iter1More) {
            iter1More := iter1.MoveNext();
        }
    }
}

Dafny 无法验证 iter2More ==> iter2.Valid() && fresh(iter2._new)，即使 Iter1 有一个空的修改子句。我需要添加循环不变量吗？

Answer 1

好的，这个很有趣 :)

这是您需要验证的额外不变量

invariant {iter1} + iter1._new !! {iter2} + iter2._new

这个不变量也足以证明调用两个迭代器的更复杂的循环，如下所示：

    if (iterMore1) {
        iterMore1 := iter1.MoveNext();
    }
    if (iterMore2) {
        iterMore2 := iter2.MoveNext();
    }

我发现这个问题的方式是 Dafny 抱怨 iter2.Valid() 在调用 iter1.MoveNext() 后可能无法保持。任何时候在调用之前为真的谓词在调用之后可能不为真，你知道问题是 Dafny 无法证明函数的读取子句没有与方法的修改子句重叠。不幸的是，迭代器的 Valid() 谓词的 reads 子句和迭代器的 MoveNext() 方法的修改子句都没有记录。我深入研究了 Dafny 的 Boogie 输出，并能够按如下方式对它们进行逆向工程

predicate Valid()
  reads this, this._reads, this._new

method MoveNext()
  modifies this, this._modifies, old(this._new)

我还看到 Dafny 可以证明 Iter1 和 Iter2 都有空的 _reads 和 _modifies 集合。所以实际上它只是引用本身，以及它们的 _new 集。这解释了不变量。

Dafny 无法在 while 循环中验证多个迭代器

Dafny can't verify multiple iterators in while loop

dafny