Dafny 泛型类型数组错误

Question

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

有问题的错误是：

unless an initializer is provided for the array elements, a new array of 'Data' must have empty size

这与在构造函数和入队方法中通过 new Data[whatever] 分配数组的两行有关。

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;
}

Answer 1

自撰写该论文以来，Dafny 的类型系统已被推广以支持 "default initializable" 以外的类型。这导致了一些向后的不兼容性。

最简单的解决方法是更改

class SimpleQueue<Data>

至

class SimpleQueue<Data(0)>

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

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

new Data[10] (_ => d)

Dafny 泛型类型数组错误

Dafny generic type array error

dafny