使用 Dafny 反转堆栈

Question

我正在学习 Dafny，但还没有找到解决这个问题的方法。我有这种方法可以反转堆栈，从堆栈中弹出并推入另一个堆栈。但它不起作用，因为 dafny 指出“后置条件可能不适用于此 return 路径。”在方法 Reverse 上。

var arr: array<nat>;
var tail: nat;
const initialSize := 5;

ghost var Content: seq<nat>;


predicate Reversed(seq1:seq<nat>, seq2: seq<nat>)
    requires |seq1| > 0
    requires |seq1| == |seq2|
{
    forall j :: 0 <= j < |seq1| ==> seq1[j] == seq2[|seq1|-1-j]
}

此 return 路径可能不支持后置条件。验证者
Stack.dfy(88, 12)：这是可能不成立的后置条件。
Stack.dfy(10, 15): 相关位置 < 反向谓词

method Reverse()
    requires |Content| > 0
    ensures old(|Content|) == |Content|
    ensures Reversed(old(Content), Content)
{
    var newArray := new nat[arr.Length];
    var newTail := 0;
    ghost var newContent: seq<nat>;
    var element;
    while(tail>0)
        // invariant Content[|Content|-1] == newContent[|newContent|-1]
    {
        // Pop from old stack
        tail := tail - 1;
        element := arr[tail];
        Content := arr[0..tail];
        // Push into new stack
        newArray[newTail] := element;
        newTail := newTail + 1;
        newContent := newContent + [element];
    }

    arr := newArray;
    tail:= newTail;
    Content := newContent;
}

我已经尝试找出一些循环不变量但没有成功。

编辑：我正在使用自动合约

Answer 1

我使用 forall 而不是 while 解决了这个问题，因为它不需要不变量：

method Reverse()
    requires |Content| > 0
    ensures old(|Content|) == |Content|
    ensures Reversed(old(Content), Content)
{
    var newArray := new nat[arr.Length];

    forall i | 0 <= i < tail
    {
        newArray[i] := arr[tail - i - 1];
    }

    arr := newArray;
    Content := arr[..tail];
}

使用 Dafny 反转堆栈

Reverse a stack using Dafny

dafny