在 Dafny 中用另一张地图更新一张地图

Question

我想在 Dafny 中编写以下函数，它使用 m2 中的所有映射更新映射 m1，以便 m2 覆盖 m1：

function update_map<K, V>(m1: map<K, V>, m2: map<K, V>): map<K, V>
ensures
  (forall k :: k in m2 ==> update_map(m1, m2)[k] == m2[k]) &&
  (forall k :: !(k in m2) && k in m1 ==> update_map(m1, m2)[k] == m1[k]) &&
  (forall k :: !(k in m2) && !(k in m1) ==> !(k in update_map(m1, m2)))
{
  map k | (k in m1 || k in m2) :: if k in m2 then m2[k] else m1[k]
}

我收到以下错误：

Dafny 2.2.0.10923
stdin.dfy(7,2): Error: a map comprehension involved in a function definition is not allowed to depend on the set of allocated references; Dafny's heuristics can't figure out a bound for the values of 'k' (perhaps declare its type, 'K', as 'K(!new)')
stdin.dfy(7,2): Error: a map comprehension must produce a finite set, but Dafny's heuristics can't figure out how to produce a bounded set of values for 'k'
2 resolution/type errors detected in stdin.dfy

我不明白第一个错误，第二个错误，如果m1和m2都有有限域，那么它们的并集肯定也是有限的，但我该如何解释给达夫尼的？

更新：

应用 James 的修复后，它起作用了：

function update_map<K(!new), V>(m1: map<K, V>, m2: map<K, V>): map<K, V>
ensures
  (forall k :: k in m1 || k in m2 ==> k in update_map(m1, m2)) &&
  (forall k :: k in m2 ==> update_map(m1, m2)[k] == m2[k]) &&
  (forall k :: !(k in m2) && k in m1 ==> update_map(m1, m2)[k] == m1[k]) &&
  (forall k :: !(k in m2) && !(k in m1) ==> !(k in update_map(m1, m2)))
{
  map k | k in (m1.Keys + m2.Keys) :: if k in m2 then m2[k] else m1[k]
}

Answer 1

好问题！您运行跨越了 Dafny 中一些已知的尖锐边缘，这些边缘没有被记录下来。

在第一个错误中，Dafny 基本上是在说类型变量 K 需要被限制为不是引用类型。您可以通过将函数签名更改为以

开头来做到这一点

function update_map<K(!new), V>...

这里，(!new) 是 Dafny 语法，确切地说 K 只能用值类型实例化，不能用引用类型实例化。（不幸的是，!new 还没有记录，但是有一个 open issue 关于这个。）

在第二个错误中，您运行与 Dafny 用于证明有限性的有限句法启发法相冲突，如中所述。解决方法是使用 Dafny 的内置集合联合运算符而不是布尔析取，如下所示：

map k | k in m1.Keys + m2.Keys :: ...

（在这里，我使用 .Keys 将每个映射转换为其域中的键集，以便我可以应用 +，它适用于集合但不适用于映射。）

在修复了这两个类型检查时错误后，您现在会遇到两个新的验证时错误。耶！

stdin.dfy(3,45): Error: element may not be in domain
stdin.dfy(4,59): Error: element may not be in domain

这些告诉您后置条件语句本身的格式不正确，因为您正在使用键对映射进行索引，而没有正确假设这些键在映射的域中。您可以通过添加另一个后置条件（before 其他条件）来解决此问题，如下所示：

  (forall k :: k in m1 || k in m2 ==> k in update_map(m1, m2)) && ...

之后整个函数验证

在 Dafny 中用另一张地图更新一张地图

Updating a map with another map in Dafny

dafny