Dafny 中的 while 循环终止

Question

我正在尝试使用 Dafny 验证算法。我正在努力修复错误消息“decreases expression might not decrease (timed out)”。我的算法基本结构如下：

while (U != {})
    decreases |S| - |B - U|;  // S is a constant and |B| <= |S|
    invariant U < B;  // U is a subset of B
{
    var u :| u in U;  // pick an element of u
    U := U - {u};  // remove the element

    while (...)
        invariant U < B;  // U is a subset of B
    {
        // modifies B and U but does not modify |B - U|
    }
}

S、B、U都是集合。 S 在算法中根本没有被修改。我已经证明B的基数小于等于S的基数，所以decreases子句被0约束。

在每次分配给 B 或 U 之后（在内部 while 循环中），我可以证明 |B - U|保持不变。但是，这还不够，我需要内部 while 循环中的循环不变性来说明这一点，但我不知道如何在 Dafny 中表达这一点。我尝试了以下但没有解决问题：

invariant |old(B) - old(U)| == |B - U|;

(注：第一次使用Dafny，被这个问题卡了一个星期左右，大家多多指教。

Answer 1

为了表示内层循环对|B - U|的值没有影响，可以将|B - U|的值保存在内层循环之前的ghost变量中。然后，在内部循环不变量中提到那个幽灵变量。像这样：

ghost var previousCardinalityOfBminusU := |B - U|;
while (...)
  invariant |B - U| == previousCardinalityOfBminusU
{
  // ...
}

以下是一些其他评论：

如果内循环不向U添加任何元素，那么外循环的一个更简单的终止度量就是|U|。然后，您需要向内部循环添加一个循环不变量，例如 |U| <= prev，其中 prev 是您在内部循环之前设置为 |U| 的幽灵变量。
你也有证明内循环终止的方案吗？
表达式 U < B 表示 U 是 B 的正确子集，但也许这已经是您所说的评论“U 是 B 的子集”是什么意思？
您的错误消息还显示 "timed out"。有时，超时的原因可能不止一个，修复其中一个也可能解决另一个。为了确保其他一切都很好，我建议你暂时让验证者假设终止成功。

一种方法是（暂时）用 decreases * 标记每个循环，这告诉验证者您可以接受循环不终止。（这还需要您用 decreases * 标记任何封闭循环和封闭方法。）

另一种暂时让验证者假设终止成功的方法是使用assume语句。例如，对于外循环，你可以这样做：
```
while U != {}
  // as before
{
  ghost var prev := |S| - |B - U|;
  // as before
  // inner loop as before
  assume |S| - |B - U| < prev; // give verifier the (possibly incorrect) assumption that the termination metric has gone down
}
```
这可能会发现是否还有其他问题（之前被超时掩盖），而这些可能是超时的另一个原因。但是，如果您的程序使用这些假设进行了正确验证，那么确实是导致超时的终止证明。然后你需要尝试向验证者提供更多的正确性参数（我的直觉是内循环上的一些额外的不变量可以解决问题）。

Dafny 中的 while 循环终止

while loop termination in Dafny

termination

while-loop

dafny