将 Dafny 中的两个整数与不变量相乘的简单方法

Question

此 Q3 方法通过将 m0 添加到 res |n0| 来交换 n0 * m0次。如果 n0 为负，我们将 n0 和 m0 都反转，因为 n0*m0 = -n0* -m0 成立。

我的问题是我不完全知道我的不变量应该是什么样子，因为不变量必须是布尔类型。谁能告诉我不变的布尔条件是什么样子的？我想过 Abs((n0)-n)*m == res，但那行不通。

method Q3(n0 : int, m0 : int) returns (res : int)
  ensures n0*m0 == res
{

  var n, m : int;
  res := 0;
  if (n0 >= 0) 
     {n,m := n0, m0;} 
  else 
     {n,m := -n0, -m0;}

  while (0 < n) 
  invariant Abs((n0)-n)*m
  { 
    res := res + m; 
    n := n - 1; 
  }
}

function Abs(x: int): int
{
  if x < 0 then -x else x
}

Answer 1

在尝试设计循环不变量时，先逆向工作会很有帮助。循环终止后你需要知道什么？

对于此方法，一旦循环终止，您将需要建立后置条件n0 * m0 == res，因此这是我们循环不变量的起点。

因为 res 被循环改变了，所以 n0 * m0 == res 本身不是不变量。相反，我们要考虑如何循环 "makes progress" 这个目标。这个循环通过将 m 添加到 res 来取得进展，粗略地说，这样做总共 n 次。当n为0时，循环终止。

一个常见的模式在这里很有用：不变量应该谈论已经完成的事情 "so far" 和正在做的事情 "left to do"。在这种情况下，到目前为止已经完成的是 res，剩下要做的是 m 的剩余 n 添加。循环的每次迭代都需要完成一项工作，并在保持不变性的情况下完成。

换句话说，这个循环的一个好的不变量是res + n * m == n0 * m0。

另外，Dafny Tutorial 有一个关于循环不变量的部分，这可能会有所帮助。

将 Dafny 中的两个整数与不变量相乘的简单方法

Simple method to multiply two ints in Dafny with invariant

methods

dafny