涉及序列的愚蠢代码中缺少不变量

Question

我想知道 dafny 无法验证我的程序是否有原因？

我是否遗漏了一些额外的不变量？

Answer 1

问题是您对 s 的定义和对 o 的构造进入了 "different directions"。 s 的递归情况根据以下定义 s(i) i[0]以及s(i[1..])定义的"previously"是什么。相反，循环迭代根据 i[n] 和 o 的先前值定义新的 o。在你当前的程序中建立证明义务需要一个归纳证明的引理，而 Dafny 并没有自己发明这样的引理。

为了记录本回答，以下是您的开头：

function s(i: seq<int>): seq<int> {
  if |i| == 0 then [] else 
    if i[0] == 42 then [i[0]] + s(i[1..])
    else s(i[1..])
}

method q (i: seq<int>) returns (o: seq<int>)
  ensures o == s(i)
{
  var n := 0;
  o := [];

  while n < |i|
    invariant n <= |i| && o == s(i[..n])   
  {
    if i[n] == 42 {
      o := o + [i[n]];
    } 
    n := n + 1;
  } 
}

有四种出路。

一种解决方法是定义 s 的不同版本，称之为 s'，它从给定序列的另一端递归。然后，在您的方法规范和循环不变式中将 s 替换为 s'。这是一个很好的解决方案，除非出于某种原因你真的更喜欢 s，而不是 s'，在你的方法规范中。

第二个出路是定义这样一个s'并证明一个引理s(i)和s'(i)return相同的值。这将使您在方法规范中保留 s，代价是有两个函数定义并且必须编写（并证明和使用）引理。

第三种出路是将循环更改为迭代 "downward" 而不是 "upward"。即在|i|处开始n，在循环体中递减n。（和往常一样，n 的递增通常最好在循环体的末尾完成（post-递增），而 n 的递减通常最好在循环体的开头完成循环体（预递减）。）

第四个出路是改变关于 o 的循环不变量的编写方式。目前，不变量表示您已经计算出的内容，即 o == s(i[..n])。您可以根据尚未计算的内容编写不变量，如 o + s(i[n..]) == s(i)，您可以将其读作 "once I have added s(i[n..]) to o, I will have s(i)"。这是 q 的那个版本：

method q(i: seq<int>) returns (o: seq<int>)
  ensures o == s(i)
{  
  var n := 0;
  o := [];

  while n < |i|
    invariant n <= |i| && o + s(i[n..]) == s(i)
  {
    if i[n] == 42 {
      o := o + [i[n]];
    } 
    n := n + 1;
  } 
}

您可能也有兴趣观看有关此主题的 this episode of Verification Corner。

鲁斯坦

涉及序列的愚蠢代码中缺少不变量

missing invariant in dafny code involving sequences

dafny