Дафни: как использовать оба квантификатора вместе

Я пытаюсь использовать Dafny для проверки очень простого кода. Кулачный блок — обычная версия. И я просто не могу найти способ установить постусловие

"существует для всех j ~~~~~~"

Я не знаю, как использовать 2 квантификатора вместе в Dafny, помогите, пожалуйста. Спасибо.

//this is a c++ version of the code
for (int lastNot0 = 0, cur = 0; cur < nums.length; cur++) {
    if (nums[cur] != 0) {
        swap(nums[lastNot0 ++], nums[cur]);
    }
}

//Dafny code
method moveZero(a: array<int>)
  requires a != null && a.Length > 0;
  modifies a;
  ensures exists i :: forall j :: 0 <= j < i < a.Length && a[j] != 0;
//  ensures forall k :: 0 <= k < a.Length && k != i && k != j ==> a[k] == old(a[k]);
{
  var lastNot0 := 0;
  var cur := 0;
  while(cur < a.Length)
  invariant 0 <= lastNot0 <= cur < a.Length
  {
    if(a[cur] != 0){
      swap(a, lastNot0, cur);
      lastNot0 := lastNot0 + 1;
    }
    cur := cur + 1;

  }
}

method swap(a: array<int>, i: int, j: int)
  requires a != null && 0 <= i < j < a.Length;
  modifies a;
  ensures a[i] == old(a[j]);
  ensures a[j] == old(a[i]);
  ensures forall k :: 0 <= k < a.Length && k != i && k != j ==> a[k] == old(a[k]);
{
  var temp := a[i];
  a[i] := a[j];
  a[j] := temp;
}

person Tony    schedule 24.02.2017    source источник
comment
Можете ли вы объяснить, какое постусловие вы пытаетесь добавить? Насколько я понимаю, вы пытаетесь сказать, что существует i для всех j таких, что j<i и a[i]==0. Это правильно?   -  person deLta    schedule 24.02.2017
comment
Да, я пытаюсь что-то вроде «обеспечивает существование i :: forall j :: 0 ‹= j ‹ i ‹ a.Length && a[j] != 0;' но я не работаю: '/!\ Не найдено условий для срабатывания.'   -  person Tony    schedule 24.02.2017
comment
Итак, во-первых, на мой взгляд, этот предикат не будет работать, потому что возможно, что в массиве a нет элемента со значением 0. В этом случае предикат не будет работать.   -  person deLta    schedule 24.02.2017
comment
Мой вопрос здесь в том, как поставить 2 квантификатора, что я должен поставить между «существует i» и «forall j». Должен ли я использовать '(' или ',' или ':' или '::' или что-то еще. Я думаю, что это синтаксическая ошибка.   -  person Tony    schedule 24.02.2017


Ответы (2)


Ваш синтаксис правильный. Проблема в том, что в кванторе нет условия, включающего i. Он просто говорит, что i > j, но не относится к значениям массива a. Поэтому вам нужно добавить еще одно условие, например a[i] == 0, к квантификатору.

ensures exists i :: forall j :: 0 <= j < i < a.Length && a[j] != 0 && a[i] == 0;

Это не даст вам предупреждения о том, что термины не найдены для срабатывания.

person deLta    schedule 24.02.2017
comment
но что, если я ничего не знаю об i, так как я мог бы быть a.Length, а a[i] даже не будет существовать - person Tony; 25.02.2017
comment
Кроме того, я столкнулся с другой проблемой. есть ли способ использовать метод в постусловии. Например, у меня есть метод count(seq a), который считает нули в a, а в условиях поста ensures count(a) < 5. Я хочу, чтобы в постусловии было меньше 5 нулей в a. Но дафни не разрешала мне использовать мето. Я получил это сообщение об ошибке method call is not allowed to be used in an expression context (count) - person Tony; 25.02.2017
comment
Чтобы это было правдой, должно выйти целое число i такое, что каждое целое число меньше i. Таким образом, постусловие невыполнимо. По крайней мере, это мое понимание. - person Theodore Norvell; 02.03.2017

Я думаю, что вы пытаетесь сказать,

ensures exists i | 0 <= i <= a.length ::
            forall j | 0 <= j < i ::  a[j] != 0 ;

Но тогда это тривиально верно (считайте, что i == 0), так что, возможно, вы имеете в виду не это.

Из вашего кода вы перемещаете все ненулевые значения вперед. Таким образом, вам также нужно, чтобы элементы в i и далее были равны 0, поэтому

ensures exists i | 0 <= i <= a.length ::
               (forall j | 0 <= j < i ::  a[j] != 0)
            && (forall j | i <= j < a.length ::  a[j] == 0);

или более кратко

ensures exists i | 0 <= i <= a.length ::
            forall j | 0 <= j < a.length ::  a[j] != 0 <==> j < i ;
person Theodore Norvell    schedule 02.03.2017