Alloy

Question

下午好，

我在处理无界通用量词时遇到了 Alloy 的问题。正如 Daniel Jackson 的书 'Software Abstractions'（第 5.3 节 'Unbounded Universal Quantifiers'）中所解释的，Alloy 在通用量词和断言检查方面有一个微妙的限制。 Alloy 在某些情况下会产生虚假的反例，例如下一个检查集合是否在并集下闭合（如上述书中所示）：

sig Set {
  elements: set Element
}
sig Element {}

assert Closed {
  all s0, s1: Set | some s2: Set |
    s2.elements = s0.elements + s1.elements
}
check Closed for 3

产生一个反例，例如：

Set = {(S0),(S1)}
Element = {(E0),(E1)}
s0 = {(S0)}
s1 = {(S1)}
elements = {(S0,E0), (S1,E1)}

分析器没有用足够的值填充 Set（缺少 Set 原子 S2，包含 S0 和 S1 的并集）。

书中提出了解决这个普遍问题的两种方法：

1) 声明生成器公理以强制Alloy生成所有可能的实例。例如：

fact SetGenerator{
  some s: Set | no s.elements
  all s: Set, e: Element |
    some s': Set | s'.elements = s.elements + e
}

但是，此解决方案会产生范围爆炸并且还可能导致不一致。

2) 省略生成器公理并使用有界通用形式进行约束。也就是说，量化变量的边界表达式没有提到生成的签名的名称。然而，并不是每一个断言都可以用这样的形式来表达。

我的问题是：是否有特定的规则来选择这些解决方案？书上看不清楚。

谢谢。

Answer 1

不，没有具体的规则（或者至少 none 我想出了）。在实践中，这种情况并不经常出现，所以我会在每个案例出现时进行处理。您有具体的例子吗？

此外，请记住，有时您可以使用高阶量词（即集合或关系上的量词）来表述您的问题，在这种情况下，您可以使用 Alloy*，Alloy 支持高阶分析。

Alloy - 处理无界通用量词

Alloy - Dealing with unbounded universal quantifiers

scope

assertion

universal

quantifiers