在 Dafny 中用于表现奇怪的序列的运算符

Question

我如何帮助 Dafny 证明以下两个断言是相同的：

method foo(xs : seq<int>)
  requires forall x :: x in xs ==> 0 <= x < 5;
{
  assert forall x :: x in xs ==> 0 <= x < 5;
  assert forall i :: 0 <= i < |xs| ==> 0 <= xs[i] < 5;
}

另外，Dafny 似乎可以证明以下是相同的。这是为什么？


predicate test(value : int) {
  0 <= value < 5
}

method foo'(xs : seq<int>)
  requires forall x :: x in xs ==> test(x);
{
  assert forall i :: 0 <= i < |xs| ==> test(xs[i]);
}

Example on Rise4Fun

Answer 1

这与量词触发器有关。您可以在 Dafny FAQ.

中阅读有关触发器的更多信息

在这种情况下，第一个示例中最终断言失败的原因是 requires 子句和第一个断言中的 forall 量词在 x in xs 上触发。¹ 这意味着这个量化事实 将不会在值 v 处使用 除非 v in xs 是 "in scope"对于验证者。为了证明第二个断言，验证者需要使用更早的量化事实，其值为 xs[i]，但 xs[i] in xs 不是 "in scope"。这听起来可能很奇怪，因为 xs[i] in xs 总是正确的，但事实证明，如果没有你的帮助，验证者无法解决这个问题。

所以要证明第二个断言，您需要以某种方式在范围内得到事实 xs[i] in xs。一种方法是将断言更改为

assert forall i :: 0 <= i < |xs| ==> xs[i] in xs && 0 <= xs[i] < 5;

（在结论中添加 xs[i] in xs）。事实上，一旦这个新的断言被证明，Dafny 就可以然后证明你之后的第二个断言，因为这个新的断言是在 xs[i] 上触发的，它也是 "in scope"在你的第二个断言中。

最后，你的第二个例子验证的原因是因为引入谓词test改变了可用的触发器。现在 requires 子句中的 forall 在 x in xs 和 test(x) 上触发。新触发器与 foo 正文中断言的新版本相匹配，因为 test(xs[i]) 已经出现。这会导致第一个 forall 被正确实例化，这意味着断言通过。像这样引入 otherwise-useless 命名谓词是按摩触发器以使它们执行您想要的操作时的常用技巧。

1. 您可以通过将鼠标悬停在 IDE 中的 forall 上，或通过运行在命令行上使用选项 /printTooltips 来查看正在使用的触发器。对于第一个示例中的第一个断言，您应该会看到类似 Selected triggers: {x in xs} 的内容。

在 Dafny 中用于表现奇怪的序列的运算符

in operator for sequences comporting weird in Dafny

seq

dafny