Ошибка массива универсального типа Dafny

При попытке проверить общую очередь FIFO, поддерживаемую массивом, я столкнулся с запутанной ошибкой. Очередь была найдена в этом статья, автором которой является создатель Dafny.

Рассматриваемая ошибка:

если для элементов массива не указан инициализатор, новый массив «Данные» должен иметь пустой размер

который относится к обеим строкам, выделяющим массив через 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;
}

person DaKellyFella    schedule 18.10.2017    source источник


Ответы (1)


Со времени написания этой статьи система типов Дафни была обобщена для поддержки типов, которые не являются «инициализируемыми по умолчанию». Это привело к некоторой обратной несовместимости.

Самый простой способ это изменить

class SimpleQueue<Data>

to

class SimpleQueue<Data(0)>

это означает, что переменная типа Data может быть создана только с типами, инициализируемыми по умолчанию.

Еще одно исправление — изменить конструктор, чтобы он принимал значение по умолчанию для типа Data в качестве аргумента. Затем вы можете выделить массив с помощью функции инициализации, как в

new Data[10] (_ => d)
person James Wilcox    schedule 18.10.2017