Изменение массива в Dafny с помощью постусловий

Пытаемся реализовать довольно простой метод, когда вы передаете пустой массив и помещаете в него значения (натуральные числа).

Код работает нормально, но простое постусловие, которое должно пройти в моей голове, выдает мне ошибки.

method Main() {
  var a := new int[5];
  initialise(a);

}

method initialise(a: array<int>) 
modifies a
requires a.Length > 0
ensures forall i :: 0 <= i < a.Length ==> a[i] == i
{
    var i := 0;
    while i < a.Length
    invariant 0 <= i <= a.Length
    decreases  a.Length - i
  {
        a[i] := i;
        i := i + 1;
    }
}

Ошибка:

A postcondition might not hold on this return path. Related location 1: Line: 10, Col: 8


person alexsurelee    schedule 09.08.2019    source источник


Ответы (1)


Вам нужно рассказать Дафни об инварианте, поддерживаемом циклом.

Как только вы добавите

invariant forall j :: 0 <= j < i ==> a[j] == j

доказательство проходит.

person Matthias Schlaipfer    schedule 09.08.2019
comment
При желании вы также можете опустить предварительное условие a.Length > 0, потому что ваш метод initialise работает и для пустого массива. - person Rustan Leino; 09.08.2019
comment
Спасибо за это! Один вопрос - я думал, что инвариант должен сохраняться до выполнения цикла, и в этом случае я бы не подумал, что он будет правильно проверен. Проверяет ли инвариант только после повторения цикла? - person alexsurelee; 11.08.2019
comment
Он должен удерживать перед циклом, и он это делает. i равен 0 перед циклом, поэтому предшествующая импликация ложна, а импликация истинна для всех j. - person Matthias Schlaipfer; 12.08.2019