Dafny 中的 multiset(a[..a.Length]) 和 multiset(a[..]) 之间的区别
Difference between multiset(a[..a.Length]) and multiset(a[..]) in Dafny
我正在努力想出一些愚蠢的东西。
给定 2 个数组 a 和 b，我的断言、不变量、post 条件等形式为：
multiset(a[..]) == multiset(b[..]);
失败但是
multiset(a[..a.Length]) == multiset(b[..b.Length])
成功。
我对此很困惑，因为我认为 a[..] 和 a[..a.Length] 是完全相同的东西。不过，我发现了一些有趣的事情。如果我在方法末尾添加：
assert a[..a.Length] == a[..];
assert b[..b.Length] == b[..];
然后我可以获得不变量、post 条件、涉及我的第一个示例的断言。
这表明 a[..] 和 a[..a.Length] 实际上是不同的。
有人可以解释为什么会这样吗？这里发生了什么？
您说得对，a[..] 和 [..a.Length]（就此而言，a[0..] 和 a[0..a.Length]）是同一回事。然而，可能验证者对待这些略有不同。这有所不同，因为 Dafny 中缺少（注意：即将出现的技术词）extensionality。
外延性意味着，如果您知道两个事物具有相同的元素，那么它们就是同一事物。在您的示例中，扩展性意味着，如果您知道 a[..] 和 a[..a.Length] 具有相同的元素，那么 a[..] 和 a[..a.Length] 是相同的。
Dafny 缺乏外延性意味着验证者有时知道两个事物具有相同的元素，但仍然没有得出这两个事物相同的结论。当这两件事被传递给一个函数时，这往往会很明显。在您的示例中，该函数是 multiset(...)，它将序列转换为多重集。
虽然 Dafny 不自动支持可扩展性，但它确实提供了一种简单的技术来“提醒”验证者有关可扩展性的信息。技巧是assert 使两者相等。特别地，当你为两个序列A和B写assert A == B;时，那么验证者首先会证明A和B具有相同的元素，并且那么它将得出结论A实际上等于B。换句话说，当验证者被明确要求验证两个序列值表达式如 A 和 B 是否相等时，那么它 而不是 只是证明它们在元素方面是相等的，之后得出结论 A == B.
所以，你上面的补救措施是完全正确的。当你assert a[..a.Length] 和a[..] 相等时，验证者证明它们具有相同的元素。之后，它“记住”这也意味着 a[..a.Length] 和 a[..] 相等。一旦意识到这两个序列是相同的，它就会立即知道它们的函数，如 multiset(a[..a.Length]) 和 multiset(a[..])，是相同的。
更一般地说，外延性不仅与序列相关，而且与集合、多重集和映射相关。因此，如果您正在使用这些集合类型中的任何一种，您可能需要编写有关序列相等性、集合相等性等的断言，以“提醒”验证者有关可扩展性的信息。
更一般地说，有很多事情是真实的，但验证者不会立即验证。要了解可能遗漏的内容，常用技术是开始自己分解证明义务，就像您在 assert 语句中所做的那样。通过将更复杂的证明义务分解为更简单的证明义务（通常使用 assert 语句或 calc 语句来完成），您实质上向验证者提供了有关如何证明更复杂事物的提示。
我正在努力想出一些愚蠢的东西。
给定 2 个数组 a 和 b，我的断言、不变量、post 条件等形式为：
multiset(a[..]) == multiset(b[..]);
失败但是
multiset(a[..a.Length]) == multiset(b[..b.Length])
成功。
我对此很困惑，因为我认为 a[..] 和 a[..a.Length] 是完全相同的东西。不过，我发现了一些有趣的事情。如果我在方法末尾添加：
assert a[..a.Length] == a[..];
assert b[..b.Length] == b[..];
然后我可以获得不变量、post 条件、涉及我的第一个示例的断言。
这表明 a[..] 和 a[..a.Length] 实际上是不同的。
有人可以解释为什么会这样吗？这里发生了什么？
您说得对，a[..] 和 [..a.Length]（就此而言，a[0..] 和 a[0..a.Length]）是同一回事。然而，可能验证者对待这些略有不同。这有所不同，因为 Dafny 中缺少（注意：即将出现的技术词）extensionality。
外延性意味着，如果您知道两个事物具有相同的元素，那么它们就是同一事物。在您的示例中，扩展性意味着，如果您知道 a[..] 和 a[..a.Length] 具有相同的元素，那么 a[..] 和 a[..a.Length] 是相同的。
Dafny 缺乏外延性意味着验证者有时知道两个事物具有相同的元素，但仍然没有得出这两个事物相同的结论。当这两件事被传递给一个函数时，这往往会很明显。在您的示例中，该函数是 multiset(...)，它将序列转换为多重集。
虽然 Dafny 不自动支持可扩展性，但它确实提供了一种简单的技术来“提醒”验证者有关可扩展性的信息。技巧是assert 使两者相等。特别地，当你为两个序列A和B写assert A == B;时，那么验证者首先会证明A和B具有相同的元素，并且那么它将得出结论A实际上等于B。换句话说，当验证者被明确要求验证两个序列值表达式如 A 和 B 是否相等时，那么它 而不是 只是证明它们在元素方面是相等的，之后得出结论 A == B.
所以，你上面的补救措施是完全正确的。当你assert a[..a.Length] 和a[..] 相等时，验证者证明它们具有相同的元素。之后，它“记住”这也意味着 a[..a.Length] 和 a[..] 相等。一旦意识到这两个序列是相同的，它就会立即知道它们的函数，如 multiset(a[..a.Length]) 和 multiset(a[..])，是相同的。
更一般地说，外延性不仅与序列相关，而且与集合、多重集和映射相关。因此，如果您正在使用这些集合类型中的任何一种，您可能需要编写有关序列相等性、集合相等性等的断言，以“提醒”验证者有关可扩展性的信息。
更一般地说，有很多事情是真实的，但验证者不会立即验证。要了解可能遗漏的内容，常用技术是开始自己分解证明义务，就像您在 assert 语句中所做的那样。通过将更复杂的证明义务分解为更简单的证明义务（通常使用 assert 语句或 calc 语句来完成），您实质上向验证者提供了有关如何证明更复杂事物的提示。