2

在尝试验证由数组支持的通用 FIFO 队列时，我遇到了一个令人困惑的错误。该队列是在这篇论文中找到的，由 Dafny 的创建者撰写。

有问题的错误是：

除非为数组元素提供了初始化程序，否则新的“数据”数组必须为空大小

new Data[whatever]这与在构造函数和 enqueue 方法中分配数组的两条线有关。

Dafny 版本：Dafny 2.0.0.00922 技术预览版 0

完整代码供参考。

class {:autocontracts} SimpleQueue<Data>
{
    ghost var Contents: seq<Data>;
    var a: array<Data>;
    var m: int, n: int;
    predicate Valid() {
        a != null && a.Length != 0 && 0 <= m <= n <= a.Length && Contents == a[m..n]
    }
    constructor ()
    ensures Contents == [];
    {
        a := new Data[10];
        m := 0;
        n := 0;
        Contents := [];
    }
    method Enqueue(d: Data)
    ensures Contents == old(Contents) + [d];
    {
        if n == a.Length {
            var b := a;
            if m == 0 {
                b := new Data[2 * a.Length];
            }
            forall (i | 0 <= i < n - m) {
                b[i] := a[m + i];
            }
            a, m, n := b, 0, n - m;
        }
        a[n], n, Contents := d, n + 1, Contents + [d];
    }

    method Dequeue() returns (d: Data)
    requires Contents != [];
    ensures d == old(Contents)[0] && Contents == old(Contents)[1..];
    {
        assert a[m] == a[m..n][0];
        d, m, Contents := a[m], m + 1, Contents[1..];
    }
}
method Main()
{
    var q := new SimpleQueue();
    q.Enqueue(5); q.Enqueue(12);
    var x := q.Dequeue();
    assert x == 5;
}
4

1 回答 1

1

自撰写那篇论文以来，Dafny 的类型系统已被推广到支持非“默认可初始化”的类型。这导致了一些向后的不兼容。

最简单的解决方法是更改

class SimpleQueue<Data>

至

class SimpleQueue<Data(0)>

这意味着类型变量Data只能用默认初始化类型来实例化。

另一个修复方法是更改​​构造函数以接受类型的默认值Data作为参数。然后您可以使用初始化函数分配一个数组，如

new Data[10] (_ => d)
于 2017-10-18T15:59:14.273 回答