2

我正在努力理解 clp(Z) 和MiniKanren 中使用的另一个关系算术系统之间的功能差异。

特别是，clp(Z) 显然适用于有界场，而 Kiselyov等人。被描述为适用于无界字段。

我尝试使用与无穷大和不确定性相关的各种边缘情况，但除了 Kiselyov等人之外，我无法找到明显的差异。显然不支持区间和负数。

Kiselyov 系统的要点/优势是什么？主要是实现更简单，还是有更多？

4

1 回答 1

4

好问题！执行关系算术的方法有很多，包括 CLP(Z)、CLP(FD)、“Kiselyov Arithmetic”和关系 Peano Arithmetic。您还可以将算术限制为仅在基础数字上工作（否则会发出错误信号），或延迟算术约束的评估，直到关系的参数变得足以确定地解决关系。

所有这些方法都是有用的，它们都有自己的权衡取舍。

我一直在考虑写一篇关于这个主题的短文。如果你有兴趣，也许我们可以一起写出来。

为了简要回答您的问题，我们应该记住 CLP(Z) 和 CLP(FD) 之间的区别。'CLP(X)' 代表“域'X'上的约束逻辑编程”。CLP(FD) 在整数的有限域 (FD) 上运行。在 CLP(Z) 中，域是所有整数的集合，因此大小是无限的。

显然 FD 域包含在 Z 域中，那么为什么还要有一个单独的 CLP(FD) 域/求解器呢？因为在受限域内解决问题可能更快或更容易。事实上，一些在一个域中不可判定的问题可能在受限域内变得可判定。

特别是，clp(Z) 显然适用于有界场，而 Kiselyov 等人。被描述为适用于无界字段。

CLP(Z) 中的 Z 域实际上是无界的。CLP(FD) 中的 FD 域是有界的。在 Kiselyov 算术中，域是无界的。

Kiselyov 数字的有趣之处在于一个数字可以代表无限组的具体数字。例如，

(0 1 1)

是表示 6 的 Kiselyov 数字。（Kiselyov 数字是按小端顺序排列的二进制数字列表，这就是为什么 6 用前导“0”而不是前导“1”表示的原因。）

考虑这个 Kiselyov 数词：

`(1 . ,x)

其中x是一个“新鲜”的逻辑变量。这个 Kiselyov 数字表示任何正奇数。这是 Kiselyov Arithmetic 的一个优点：可以对部分实例化的数字执行运算，表示可能无限多的具体自然数，而不需要（可能无限多）答案的基础。将无限多个自然数表示为单个数字有时可以让我们一次推理出无限多个具体数字。唉，这仅适用于我们想要表示的基础自然数集可以使用形式的 Kiselyov 数字表示的情况

`(<bit sequence that doesn't end in 0> . ,x)

Kiselyov 算术的一个缺点是每个算术关系都会立即“解决”：如果我们想将两个 Kiselyov 数相加，然后将结果乘以另一个 Kiselyov 数，我们必须先执行完全加法或完全乘法，然后再执行另一个操作。相比之下，CLP(Z) 或 CLP(FD) 求解器可以累积约束，检查每一步的可满足性，并且只有在所有约束都累积后才在计算结束时执行完整求解。这种方法可以更有效，并且还可以在一组约束中发现不一致，在这些约束中，天真地使用 Kiselyov Arithmetic 会产生分歧。

除了 Kiselyov 等人。显然不支持区间和负数。

Kiselyov Arithmetic 可以扩展为支持负数，也可以支持分数/有理数。我怀疑支持间隔也是可行的。唉，我不知道任何包含这些扩展的库。

关系算术的不同方法之间还有许多其他权衡，至少值得写一篇简短的论文！不过，我希望这能给你一些想法。

干杯，

- 将要

于 2020-05-22T15:44:41.883 回答