clp(Z) 与 Kiselyov 关系算术

Question

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

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

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

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

Answer 1

好问题！执行关系算术的方法有很多，包括 CLP(Z)、CLP(FD)、“Kiselyov 算术”和关系 Peano 算术。您还可以将算术限制为仅适用于基本数字（否则会发出错误信号），或者延迟对算术约束的评估，直到关系的参数足够基本以确定性地求解该关系。

所有这些方法都很有用，并且都有其优缺点。

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

为了简要回答您的问题，我们应该记住 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域是有界的。在基谢廖夫算术中，域是无界的。

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

(0 1 1)

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

考虑这个 Kiselyov 数值：

`(1 . ,x)

其中x是“新鲜”逻辑变量。该 Kiselyov 数字表示任何正奇整数。这是基谢廖夫算术的优点之一：可以对部分实例化的数字执行运算，代表潜在无限多个具体自然数，并且无需为（可能无限多个）答案奠定基础。将无限多个自然数表示为单个数字有时可以让我们同时推理出无限多个具体数字。唉，这只适用于我们想要表示的基本自然数集可以使用以下形式的 Kiselyov Numerals 表示的情况

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

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

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

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

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

干杯，

- 将要