(Dafny) Добавление элементов массива в другой - инвариант цикла

У меня есть функция sum, которая принимает два массива a и b в качестве входных данных и изменяет b таким образом, чтобы b[i] = a[0] + a[1] + ... + a[i]. Я написал эту функцию и хочу проверить ее с Дафни. Однако Дафни говорит мне, что мой инвариант цикла может не поддерживаться циклом. Вот код:

function sumTo(a:array<int>, n:int) : int
  requires a != null;
  requires 0 <= n < a.Length;
  decreases n;
  reads a;
{
    if (n == 0) then a[0] else sumTo(a, n-1) + a[n]
}

method sum(a:array<int>, b:array<int>)
    requires a != null && b != null
    requires a.Length >= 1
    requires a.Length == b.Length
    modifies b
    ensures forall x | 0 <= x < b.Length :: b[x] == sumTo(a,x)
{
    b[0] := a[0];
    var i := 1;

    while i < b.Length
        invariant b[0] == sumTo(a,0)
        invariant 1 <= i <= b.Length

        //ERROR : invariant might not be maintained by the loop.
        invariant forall x | 1 <= x < i :: b[x] == sumTo(a,x)

        decreases b.Length - i
    {
        b[i] := a[i] + b[i-1];
        i := i + 1;
    }
}

Как я могу исправить эту ошибку?


person Dory    schedule 27.05.2017    source источник


Ответы (1)


Ваша программа будет неправильной, если a и b ссылаются на один и тот же массив. Вам нужно предварительное условие a != b. (Если вы добавите его, Дафни проверит вашу программу.)

Рустан

person Rustan Leino    schedule 31.05.2017