Дафни, вызов может нарушать условие изменения контекста

В моей программе (полная версия на rise4fun) я хочу разделить массив, отсортировать каждый фрагмент и затем объедините их вместе.

Я решил использовать последовательности, потому что это упрощает нарезку и слияние. Затем, чтобы повторно использовать некоторый существующий код, я преобразовываю каждый фрагмент в массив и вызываю свою реализацию сортировки вставками. Но вызов сообщает об ошибке call may violate context's modifies clause. Почему это?

Вот основная часть моего кода.

method MySort(input:array?<int>)
modifies input;
requires input != null;
requires input.Length > 0;
requires input.Length%2==0;
{
if(input.Length%2!=0){return;}
 var mid:int := input.Length/2; 
 var subOne := input[0..mid];
 var subTwo := input[mid..input.Length];
 var arrSubOne := toArrayConvert(subOne);
 var arrSubTwo := toArrayConvert(subTwo);
 insertionSort(arrSubOne); //call may violate context's modifies clause
 insertionSort(arrSubTwo); //call may violate context's modifies clause
} 

method toArrayConvert(s:seq<int>) returns(a:array<int>)
requires |s|>0;
ensures |s| == a.Length;
ensures multiset(s[..]) == multiset(old(s[..]))
ensures forall i::0<=i<a.Length ==> s[i] == a[i];
{ /* ... */ }

method insertionSort(input:array?<int>)
modifies input
requires input != null
requires input.Length > 0
ensures perm(input,old(input))
ensures sortedBetween(input, 0, input.Length) // 0 to input.Length = whole input
{ /* ... */ }

person Amir-Mousavi    schedule 22.05.2018    source источник
comment
Имейте в виду, что вы с большей вероятностью получите исчерпывающие ответы, если не будете задавать несколько вопросов в одном сообщении.   -  person Malte Schwerhoff    schedule 22.05.2018


Ответы (2)


Вы пропустили постусловие на toArrayConvert

ensures fresh(res)

Затем проверяется вся ваша программа.

Это постусловие гарантирует, что массив, возвращаемый этим методом, является «свежим», т. е. заново выделенным. Это позволяет Дафни сделать вывод, что вы не изменяете ничего, чего не должны были делать: вам разрешено изменять массив, потому что вы его выделили!

Пожалуйста, задайте отдельный вопрос о замене последовательности или обновите свой старый вопрос по этой теме, если вы считаете, что ответа недостаточно.

person James Wilcox    schedule 22.05.2018
comment
Спасибо, долго не мог понять :) - person Amir-Mousavi; 23.05.2018

На этот вопрос сложно ответить, поскольку вы не предоставили контракт insertionSort. Я предполагаю, что insertionSort изменяет больше, чем вызывающий, то есть insertionSort перечисляет некоторые данные в своих modifies предложениях, которые MySort не перечисляет в своих modifies предложениях.

Если бы это было разрешено, то вызывающий MySort "пропустил бы" потенциальные модификации, т. е. контракт MySort был бы просто заниженным приближением, что было бы несостоятельным.

person Malte Schwerhoff    schedule 22.05.2018
comment
очень жаль, что там была опечатка. новая ссылка: rise4fun.com/Dafny/Yplso - person Amir-Mousavi; 22.05.2018
comment
это из-за локальных переменных, которые передаются методу? - person Amir-Mousavi; 22.05.2018