Dafny：没有找到触发条件和随之而来的断言错误

Question

这是我为 returns 两个整数中的最大值的方法编写的代码：

predicate greater(x: int, a: int, b: int){
    (x >= a) && (x >= b)
}

method Max(a: int, b: int) returns (max: int)
    ensures max >= a
    ensures max >= b
    ensures forall x /*{:trigger greater(x,a,b)}*/ :: (greater(x,a,b)) ==> x >= max
{
    if (a > b){
        max := a;
    }else{
        max := b;
    }
//  assert greater(max, a, b); - trivial assertion
}

method Main(){
    var res:= Max(4, 5);

    assert res == 5;
}

如您所见，我已经尝试了 Wiki page 中提及的两种技术（手动触发分配并在方法主体中添加了一个微不足道的无用断言。但是，我仍然得到一个断言错误。

我不知道还能做什么。我已经阅读了 this, this and 等其他答案，但到目前为止 none 对我有所帮助。

PS：我知道有一种更简单的方法可以为这个特定的方法编写后置条件，但是，我真的希望仅根据 forall 量词对后置条件建模。

Answer 1

让我们暂时忘记 greater，看看您要实现的目标。在 Main 中调用 Max 后，您知道以下内容（来自 Max 的后置条件）：

res >= 4
res >= 5
forall x :: x >= 4 && x >= 5 ==> x >= res

你正试图从中证明 res == 5。这三件事中的第二件立即给你一半的平等，所以你需要做的就是获得 5 >= res。如果用 5 为 x 实例化量词，您将得到

5 >= 4 && 5 >= 4 ==> 5 >= res

简化为5 >= res，这是你需要的，所以你的证明到此结束。

总而言之，证明归结为用 5 为 x 实例化量词。接下来，您需要了解一下 Dafny 验证器如何实例化量词。本质上，它通过查看量词的 "shape" 并在您要证明的内容的上下文中寻找类似的东西来做到这一点。 "shape"，我的意思是 "the functions and predicates it uses"。通常，这种技术效果很好，但在您的情况下，量词非常简单，没有任何 "shape" 可言。因此，验证者无法提出所需的实例化。

如果我们能直接说"hey, try instantiating that quantifier with 5 for x"就好了。好吧，我们可以，如果我们给量词一些我们可以参考的"shape"。这就是那些 wiki 和其他指南试图表达的意思。这是引入谓词 greater 的用武之地。（不要尝试手动编写触发器注释。）

好的，在引入 greater 之后，您的规格说明

ensures greater(max, a, b)
ensures forall x :: greater(x, a, b) ==> x >= max

这表示“max 满足 greater(max, a, b)” 和 "among all values x that satisfy greater(x, a, b), max is the smallest"。在 Main 中调用 Max 之后，我们有：

greater(res, 4, 5)
forall x :: greater(x, 4, 5) ==> x >= res

回想一下，我说过验证者试图通过查看量词和查看断言周围的上下文来找出量词实例化，而您正在尝试使用 5 实例化量词 [=23] =].因此，如果您可以在诱使验证者执行该实例化的断言之前向上下文添加一些内容，那么您就完成了。

答案如下：您想引入术语greater(5, 4, 5)。它的形状很像量词中的 greater(x, 4, 5)。由于这种相似性，验证者会将 x 实例化为 5，从而得到

greater(5, 4, 5) ==> 5 >= res

并且由于 greater(5, 4, 5) 很容易证明是 true，因此需要的事实 5 >= res 紧随其后。

因此，将 Main 的正文更改为

var res := Max(4, 5);
assert greater(5, 4, 5);
assert res == 5;

大功告成。验证者将证明这两个断言。第一个是微不足道的，在证明它之后，验证者可以在第二个断言的证明中使用术语 greater(5, 4, 5)。该术语触发量词，产生事实 5 >= res，证明第二个断言。

我想指出，我们试图证明的大多数量词已经具有某种形状。在您的例子中，引入谓词 greater 是为了给量词赋予某种形状。添加额外断言（这里，assert greater(5, 4, 5)）的技术是相同的，无论 greater 是否已经定义或作为提供形状的普通谓词引入。

Dafny：没有找到触发条件和随之而来的断言错误

Dafny: no terms found to trigger on and a consequent assertion error

dafny