寻找一个简单循环的不变量

Question

当我试图向 Dafny 证明我的程序是正确的时，我从未感到如此严重的不足，所以我需要你的帮助：给定的程序如下所示：

method doingMath(N: int, M: int) returns (s: int)
requires N <= M //given precondition
ensures 2*s == M*(M+1)-N*(N+1) //given postcondition
{
    var a: int := N;
    var r: int := 0;

    while a < M 
    invariant FIND ME!
    {
        a := a+1;
        r := r+a;
    }
    return r;
}

作为第一步，我想弄清楚循环的作用，所以我做了一个 table:

据此我计算出 r:

的循环不变量

invariant r == (a-N)*N + (a-N)*((a-N)+1)/2

在 (0==0) 之前和循环的每次迭代之后都成立（遵循公式）。显然它不满足终止条件

When the loop terminates, the loop invariant along with the reason that the loop terminated gives us a useful property.

由于循环守卫足够简单，我认为完整的不变量应该是

invariant a<=M && r == (a-N)*N + (a-N)*((a-N)+1)/2

因此我的不变量满足初始化、维护和终止。然而 Dafny 抱怨

Error: This loop invariant might not be maintained by the loop.

我怎样才能让 Dafny 开心？

Answer 1

您运行与非线性算术的诅咒相冲突。任何时候你依赖乘法的重要属性，Dafny 都会遇到你的程序的困难。

这是修复特定证明的一种方法。抱歉，它太乱了。我确信它可以被清理干净，但我只是把一些东西拼凑在一起来向你展示这个想法。

function {:opaque} mul(a: int, b: int): int
{
  a * b
}

lemma MulZero1(a: int)
  ensures mul(0, a) == 0
{
  reveal mul();
}

lemma MulNeg1(a: int, b: int)
  ensures mul(-a, b) == -mul(a, b)
{
  reveal mul();
}

lemma MulNeg2(a: int, b: int)
  ensures mul(a, -b) == -mul(a, b)
{
  reveal mul();
}

lemma MulInd(a: nat, b: int)
  ensures mul(a, b) == if a == 0 then 0 else mul(a-1, b) + b
{
  reveal mul();
}

lemma MulEven(a: int, b: int)
  requires b % 2 == 0
  decreases if a < 0 then -a + 1 else a
  ensures mul(a, b) % 2 == 0
{
  if a < 0 {
    MulNeg1(a, b);
    MulEven(-a, b);
  } else if a == 0 {
    MulZero1(b);
  } else {
    calc {
      mul(a, b) % 2;
      { MulInd(a, b); }
      (mul(a-1, b) + b) % 2;
      mul(a-1, b) % 2;
      { MulEven(a-1, b); }
      0;
    }
  }
}

lemma MulComm(a: int, b: int)
  ensures mul(a, b) == mul(b, a)
{
  reveal mul();
}

lemma MulAdjEven(a: int)
  ensures mul(a, a + 1) % 2 == 0
{
  var m := a % 2;

  if m == 0 {
    MulComm(a, a+1);
    MulEven(a+1, a);
  } else {
    assert m == 1;
    assert (a + 1) % 2 == 0;
    MulEven(a, a+1);
  }
}

method doingMath(N: int, M: int) returns (s: int)
requires N <= M //given precondition
ensures 2*s == mul(M,M+1) - mul(N,N+1) //given postcondition
{
    var a: int := N;
    var r: int := 0;

    assert mul(a-N, N) + mul(a-N, (a-N)+1)/2 == 0 by {
      reveal mul();
    }

    while a < M 
      invariant a <= M
      invariant r == mul(a-N, N) + mul(a-N, (a-N)+1)/2
    {
        a := a+1;
        r := r+a;
        assert r == mul(a-N, N) + mul(a-N, (a-N)+1)/2 by {
          reveal mul();
        }
    }

    calc {
      2*r;
      2* (mul(M-N, N) + mul(M-N, (M-N)+1)/2);
      { MulAdjEven(M-N); }
      2*mul(M-N, N) + mul(M-N, (M-N)+1);
      { reveal mul(); }
      mul(M,M+1) - mul(N,N+1);
    }
    return r;
}

乘法对 Dafny 来说很难，所以我们手动将它包装在一个不透明的函数中。这让我们可以细粒度地控制 Dafny 何时被允许“知道”该函数实际上是乘法。

然后我们可以通过调用 mul 来替换您的方法中所有出现的乘法。这让达夫尼很快就失败了。（与超时相比，这是一个很大的改进！）然后我们可以在需要的地方有选择地揭示 mul 的定义，或者我们可以证明关于 mul.

的引理

最难的引理是MulEven。尝试将其 body/proof 替换为 reveal mul();，您将看到 Dafny 超时。相反，我必须通过归纳来证明它。这个证明本身需要其他几个关于乘法的引理。幸运的是，他们都很容易。

您可能还想看看作为 IronFleet 项目的一部分开发的数学库 here。（首先阅读名称中包含“非线性”一词的文件；这些是最接近公理的最低级证明。）他们使用类似的方法来建立大量关于乘法（以及除法和模数）的事实)，这样这些函数就可以在代码库的其他地方保持不透明，从而提高 Dafny 的性能。

Answer 2

我设法避免了任何非线性算术问题。以下是我对这个问题的看法：

你试图建立一个后置条件，为了清楚起见，我将写成 P(s, N, M)，即 s、N 和 N 的某些函数M。提出执行此操作的循环的一种技术是“用变量替换常量”。这意味着您选择所需后置条件的常量之一（此处，您可以选择 N 或 M，因为 s 不是常量）并将其替换为将在每次循环迭代中更改的变量。让我们选择 M 作为常量，然后引入（就像您在程序中所做的那样）a 作为变量。由于我们选择 M 作为常量，我们希望 a 的最终值为 M，因此我们将从 N 开始 a。然后我们有：

method doingMath(N: int, M: int) returns (s: int)
  requires N <= M
  ensures P(s, N, M)
{
  var a := N;

  while a < M
    invariant N <= a <= M
    invariant P(s, N, a)  // postcondition, but with variable a instead of constant M
}

如果您输入此程序（但将 P(s, N, a) 展开为实际条件），那么您会发现 Dafny 证明了后置条件。换句话说，验证器给你的信息是如果你可以建立并保持这个循环不变量，那么程序将正确建立后置条件。

你自己也可以看到这个。循环守卫的否定给你 M <= a，结合循环不变量 a <= M 给你 a == M。当您组合 a == M 和循环不变量 P(s, N, a) 时，您会得到后置条件 P(s, N, M).

太好了。但是验证者发出一个抱怨，说循环不变量在输入时不成立。这是因为我们没有为 s 提供任何初始值。由于a的初始值为N，我们需要为s找到一个满足P(s, N, N)的值。该值为 0，因此我们将程序更新为

method doingMath(N: int, M: int) returns (s: int)
  requires N <= M
  ensures P(s, N, M)
{
  var a := N;
  s := 0;

  while a < M
    invariant N <= a <= M
    invariant P(s, N, a)
}

接下来我们来写循环体。（注意我是如何开始循环不变量的，而不是从循环体开始然后试图找出一个不变量。对于这类程序，我发现这是最简单的方法。）我们已经决定要将 a 从初始值 N 变为最终值 M，因此我们添加赋值 a := a + 1;:

method doingMath(N: int, M: int) returns (s: int)
  requires N <= M
  ensures 2*s == M*(M+1) - N*(N+1)
{
  var a := N;
  s := 0;

  while a < M
    invariant N <= a <= M
    invariant P(s, N, a)
  {
    a := a + 1;
  }
}

这解决了终止问题。我们需要做的最后一件事是在循环内更新 s 以保持不变量。这主要是以目标为导向的方式 backward 很容易完成的。方法如下：在循环体的末尾，我们要确保 P(s, N, a) 成立。这意味着我们希望条件 P(s, N, a + 1) 在赋值给 a 之前保持 。通过将 desired 条件中的 a 替换为（赋值的右侧）a + 1.

好的，所以在赋值给a之前，我们想要P(s, N, a + 1)，而我们在循环体内得到的是不变量P(s, N, a)。现在，我要根据你的实际情况展开P(...)。好的，我们有

2*s == a*(a+1) - N*(N+1) (*)

我们想要

2*s == (a+1)*(a+2) - N*(N+1) (**)

让我们将 (**) 中的 (a+1)*(a+2) 重写为 2*(a+1) + a*(a+1)。所以，(**) 可以等效地写成

2*s == 2*(a+1) + a*(a+1) - N*(N+1) (***)

如果将 (***)（这是我们想要的）与 (*)（这是我们已经得到的）进行比较，那么您会注意到 [=63= 的右侧] 比 (*) 的右侧多 2*(a+1)。所以，我们必须安排增加相同数量的左侧。

如果将 s 增加 a+1，则左侧 2*s 增加 2*(a+1)，这就是我们想要的。所以，我们的最终方案是

method doingMath(N: int, M: int) returns (s: int) requires N <= M ensures 2*s == M*(M+1) - N*(N+1) { var a := N; s := 0; while a < M invariant N <= a <= M invariant 2*s == a*(a+1) - N*(N+1) { s := s + a + 1; a := a + 1; } }

如果需要，您可以将分配的顺序交换为 s 和 a。这会给你

method doingMath(N: int, M: int) returns (s: int) requires N <= M ensures 2*s == M*(M+1) - N*(N+1) { var a := N; s := 0; while a < M invariant N <= a <= M invariant 2*s == a*(a+1) - N*(N+1) { a := a + 1; s := s + a; } }

综上所述，我们已经从循环不变量构建了循环体，我们通过在后置条件中“用变量替换常量”来设计这个循环不变量。

鲁斯坦

寻找一个简单循环的不变量

Finding an invariant for a simple loop

loop-invariant

dafny