dafny 非别名内存奇怪的行为

Question

我有一个愚蠢的定义图 ADT（来自）为了完整性再次带到这里：

class Graph
{
    var adjList : seq<seq<int>>;
    constructor (adjListInput : seq<seq<int>>)
        ensures adjList == adjListInput
    {
        adjList := adjListInput;
    }
}
function ValidGraph(G : Graph) : bool
    reads G
{
    (forall u :: 0 <= u < |G.adjList| ==> forall v   :: 0 <= v <     |G.adjList[u]| ==> 0 <= G.adjList[u][v] < |G.adjList|) &&
    (forall u :: 0 <= u < |G.adjList| ==> forall v,w :: 0 <= v < w < |G.adjList[u]| ==> G.adjList[u][v] != G.adjList[u][w])
}
method main()
{
    var G : Graph := new Graph([[1,2],[0,2],[0,1]]);
    var nonRelatedArray := new int[8];
    var i := 0; while (i < 14)
    {
        // nonRelatedArray[3] := 55;
        i := i + 1;
    }
    assert (ValidGraph(G));
}

如果我在索引 3 处删除对 nonRelatedArray 的写评论，我会得到一个 断言违规 ，这有点奇怪，因为它看起来很合理内存模型将能够确定 nonRelatedArray 与 G.

（很好）无关

Answer 1

您可以通过将 modifies nonRelatedArray 添加到循环中来解决此问题。这个修改子句的关键是它没有提到G。所以 Dafny 知道 G 不会被循环修改，所以它仍然是一个有效的图。

如果您从循环中删除修改子句，会发生什么情况有点令人困惑。如果您不对堆执行任何写入操作（就像您注释掉上面的写入操作一样），那么 Dafny（实际上是 Boogie）能够自动看到根本没有任何更改。但是如果你对堆进行任何写入，Dafny 的默认修改子句突然变成“允许周围范围修改的任何内容”。如果您想要这两个默认值以外的其他内容，则需要通过提供修改子句来明确要求。

dafny 非别名内存奇怪的行为

dafny non aliased memory weird behavior

alias

memory-model

dafny