constraint-programming - clp(Z) 与 Kiselyov 关系算术

Question

我正在努力理解 clp(Z) 和另一个 relational arithmetic system used in MiniKanren 之间的功能差异.

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

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

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

Answer 1

好问题!
有许多执行关系算术的方法，包括 CLP(Z)、CLP(FD)、“Kiselyov 算术”和关系皮亚诺算术。您还可以将算术限制为仅处理基本数(否则会发出错误信号)，或延迟对算术约束的评估，直到关系的参数变得足以确定性地解决该关系。

所有这些方法都是有用的，并且它们都有其权衡。

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

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

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

In particular, clp(Z) apparently applies to bounded fields while Kiselyov et al. is described to apply to unbounded fields.

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

Kiselyov 数字很有趣，因为一个数字可以代表无限组的具体数字。例如，

(0 1 1)

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

考虑这个 Kiselyov 数字:

`(1 . ,x)

哪里 x是一个“新鲜”的逻辑变量。此 Kiselyov 数字表示任何正奇数。这是 Kiselyov 算术的优势之一:可以对部分实例化的数字执行运算，表示可能无限多个具体的自然数，并且无需确定(可能无限多个)答案的基础。将无限多个自然数表示为单个数字有时可以让我们同时推理无限多个具体数字。唉，这只适用于我们想要表示的基础自然数集可以使用形式的 Kiselyov Numerals 表示的情况

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

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

other than Kiselyov et al. obviously not supporting intervals and negative numbers.

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

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

干杯，

- 将要