在我的程序(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
{ /* ... */ }
发布于 2018-05-22 08:23:56
您在toArrayConvert
上缺少一个后置条件
ensures fresh(res)
然后你的整个程序验证。
这个后置条件保证该方法返回的数组是“新的”,这意味着它是新分配的。这允许Dafny得出结论,您没有修改任何不应该修改的内容:您可以修改数组,因为您分配了它!
如果你觉得答案不够的话,请另外问一个关于序列交换的问题,或者更新你以前关于这个话题的问题。
发布于 2018-05-22 04:00:06
这个问题很难回答,因为你没有提供insertionSort
的合同。我的猜测是,insertionSort
修改的次数比调用者多,也就是说,insertionSort
在其modifies
子句中列出了一些MySort
在modifies
子句中没有列出的数据。
如果允许这样做,那么MySort
的调用方将“错过”潜在的修改,因为,即MySort
的合同只是一个欠近似的,这将是不健全的。
https://stackoverflow.com/questions/50466383
复制