为什么不推断出这个愚蠢的post-条件?

Why this dafny post-condition is not inferred?

我已经以类似的建设性方式证明了一些纯粹存在的引理(没有结果):

https://rise4fun.com/Dafny/Wvly

lemma DivModExistsUnique_Lemma (x:nat, y:nat)  
requires y != 0
ensures exists q:nat, r:nat :: x == y*q + r &&  r < y 
{
var q:nat, r:nat := 0, x;
while r >= y 
  invariant x == y*q + r
  {
  q := q + 1;
  r := r - y;
  }
assert x == y*q + r &&  r < y;
}

我不明白为什么这个post-条件不是从证明中的最后一个断言中推断出来的。

有一些额外的提示可以给 Dafny 吗?

很好的证明!问题在于后置条件中的量词没有涉及 r 的“匹配模式”(也称为“触发器”)。 Dafny 对此发出了警告。那么这是什么意思?

为了证明存在量词,验证者试图找到一个证人。在寻找见证人时,验证者不会尝试数学中的每一个可能的术语,甚至不会尝试出现在程序其他地方的每一个术语。相反,验证者将其注意力限制在 both 出现在证明上下文中其他地方的术语 and 具有量词的“匹配模式”的形状.在 Dafny IDE(VS Code 或 Emacs)中,您可以将光标放在量词上,IDE 将向您显示 Dafny select 编辑的触发器。 (同样,在您的情况下,它会显示“无触发器”。)

关于什么是触发器,什么是触发器,有一些规则(请参阅 Dafny FAQ 或 Whosebug 上的许多已回答问题)。对于 q,验证者将 select 术语 y*q 作为触发器。这是允许的,因为 Dafny 允许 * 出现在触发器中。但是,r 唯一可能有用的触发器是 ... + rr < ...,这两个都不被允许,因为触发器不允许提及 +< .因此,Dafny 找不到量词的触发器,这实质上意味着它永远不会找到证明存在量词的证人。

要解决此问题,您可以引入一个涉及量化变量的函数。例如,

function MulAdd(a: nat, b: nat, c: nat): nat {
  a*b + c
}

lemma DivModExistsUnique_Lemma(x:nat, y:nat)  
  requires y != 0
  ensures exists q:nat, r:nat :: x == MulAdd(y, q, r) && r < y
{
  var q:nat, r:nat := 0, x;
  while r >= y 
    invariant x == MulAdd(y, q, r)
  {
    q := q + 1;
    r := r - y;
  }
}

将证明你的程序。然后 IDE 还会向您显示 Mul(y, q, r) 被 select 编辑为触发器。

没有触发器的量词往往是只使用“built-in 符号”的量词,例如 +<&&。当你的问题有其他功能时,验证者通常可以找到触发器。

为了证明,最符合我口味的解决方案是使用引理 out-parameters。这意味着引理可以只是“return”它计算的 qr。它还使引理更易于使用,因为引理的调用者通常需要对量词进行 Skolemize(您在 Dafny 中使用 assign-such-that 运算符 :| 进行 - 这也涉及触发器,通过方式)。但是你说你(出于某种原因)试图避免 out-parameters。如果是这样,那么 MulAdd 函数就可以解决问题。