为什么不能将空字段中的值计数与整数进行比较？

Question

我创建了一个测试来比较空字段中值的数量与数字。我对结果感到惊讶。

首先，我创建了一个带有字段 f 的签名，可选择将一个 A 原子映射到另一个 A 原子：

sig A {f: lone A}

然后我创建了这个表达式：如果f为空，则f映射的A原子数小于8：

check {
    no A.f =>
        # A.f < 8 
}

我运行检查命令和Alloy分析器找到了一个反例。这让我大吃一惊。

我打开了 Evaluator 工具并输入了这个：

我输入了：A

评估员回复：{}

我输入了：no A.f

评估员回复：true

我输入了：# A.f

评估员回复：0

我输入了：# A.f < 8

评估员回复：false

嗯？

为什么 0 < 8 是假的？

Answer 1

Alloy 只有一组有限的整数，因为每个整数在寻找解决方案时都相对昂贵。默认情况下，此集合为：

Int
  ┌──┬──┬──┬──┬──┬──┬──┬──┬─┬─┬─┬─┬─┬─┬─┬─┐⁻¹
  │-8│-7│-6│-5│-4│-3│-2│-1│0│1│2│3│4│5│6│7│  
  └──┴──┴──┴──┴──┴──┴──┴──┴─┴─┴─┴─┴─┴─┴─┴─┘

当你做 7+1 时，你实际上得到 -8！

试一试...只需在计算器中输入 8:

 8
   -8

这实际上不限于 Alloy、C、C++、Java，大多数其他语言也做同样的事情，您通常没有注意到它的原因是因为环绕点是高得多。对于 Java int，它超过 20 亿。原因是整数存储为一组位。一旦达到最大值，添加将需要额外的位。由于该位不存在，因此它会被默默地忽略。（实际上，意识到到目前为止我从未见过任何处理此溢出的代码是一个非常可怕的想法。）

因此，当你的最大数量是7时，默认在Alloy，而你使用8实际是-8!

  # A.f < -8

我们有这种恐惧的原因是在 Alloy 中，当将 Int 提供给 SAT 求解器时，它也被打包在一个位集中。

Alloy 一直在努力解决这个问题，并且有一个选项可以防止溢出。最初我以为这是天赐的礼物，但自从我意识到它是如何工作后我就禁用了它。问题是它删除了可能有效的解决方案。找到解决方案并不算太糟糕，因为当什么都没有时你会注意到，但它对断言来说非常糟糕，因为断言可能会说没有解决方案，而模型实际上有。这让我不寒而栗，因为我想依赖一个断言。查看实际用例，我决定我宁愿在我的模型中明确处理溢出，因为它们实际上也是最终产品中的一个问题。许多已知的错误是由意外溢出引起的。所以隐藏它们的模型是恕我直言，不是很有用。

那你是怎么处理的呢？这个语法有点奇怪。您必须指定整数编码的 bitwidth。因此，您可以将模型更改为：

sig A {f: 孤独的 A}

check {
    no A.f =>
        # A.f < 8 
} for 5 int

for 5 int设置SAT编码的位宽为5位。 5 位 = 5^2=32。那么你就有了整数 -16..15.

这显然是一条巨大的绊线。幸运的是，在 SMT 求解器上制作 Alloy 运行的工作非常出色。 SMT 求解器将具有比 Alloy 更自然的数字处理能力，这不会让您失望。

就是说，如果您使用不适合可用 Int 集的常量整数，我可以尝试至少生成一个错误。也许您可以提交错误？

为什么不能将空字段中的值计数与整数进行比较？

Why can't a count of the values in an empty field be compared against an integer?

alloy