CLPFD 和无限可数域
CLPFD and infinite countable domains
I #> 0, I #< 10, indomain(I).
前面的代码显然做了以下事情：
I = 1 ;
I = 2 ;
I = 3 ;
I = 4 ;
I = 5 ;
I = 6 ;
I = 7 ;
I = 8 ;
I = 9.
以下代码不起作用（参数未充分实例化）：
I #> 0, indomain(I).
现在我了解到，在这种情况下，I 有无数种可能的绑定，而且 CLPFD 正如其名称所暗示的那样适用于有限域。
但是我不明白为什么在这种特殊情况下存在这种限制。是不是可以从最小范数到最大范数枚举可能的解，得到如下：
I = 1 ;
I = 2 ;
I = 3 ;
.
.
.
即使对于有多个变量的问题，也可以说：
0 #< I, I #< J, label([I,J]).
为什么不能实现它以致出现以下行为：
I = 1,
J = 2 ;
I = 1,
J = 3 ;
I = 2,
J = 3 ;
I = 1,
J = 4 ;
.
.
.
简而言之：为什么 CLPFD 仍然不能用于无限域，如果这些域很容易使用振幅来计算？
这是因为 CLP(FD) 保留了以下重要的 属性：
If a predicate p(Vs) terminates universally, then ?- p(Vs), label(Vs). also terminates universally.
一个目标G 普遍终止 iff ?- G, false. 终止.
为什么这如此重要？因为一个 CLP(FD) 程序通常由两部分组成：
- 发布所有约束
- 寻找解决方案。
通常很容易通过简单的检查表明建模部分 (1) 普遍终止。但是 (2) 是最困难的部分，通常会占用大部分计算时间，而且我们通常 a priori 甚至不知道是否存在单一解决方案。搜索部分可能 运行 几天、几个月或几年都没有结果。
许多 Prolog 初学者描述了一个搜索任务，运行 它，几秒钟后抱怨 Prolog 很慢。事实上，事实证明，他们经常不小心编写了 不会终止 的程序，并且 永远不会 找到解决方案。
出于这些原因，令人鼓舞的是，如果您只能（通常可以，而且相当容易）显示第 (1) 部分终止，那么您的整个程序 — 第 (1) 部分 并且第(2)部分——也终止。
你是完全正确的，任何可数的无限搜索 space 都可以用你描述的方式之一系统地覆盖到任何有限的范围。然而，这样做会破坏这个基本不变量。您必须能够依靠以下 属性 才能应用上述推理：
label/1, labeling/2 and indomain/1 always terminate.
在 SWI-Prolog 和 YAP 中，这是由设计确保的。在其他系统中，它在不同程度上成立。
没有理由不允许在 CLP(FD) 中枚举无限域。自从
由于 user:mat 已正确观察到约束本身终止，如果存在解决方案，无限枚举可能会找到解决方案。
所以基本上我们有：
The constraints terminate universally, i.e. (#=)/2, (#=<)/2, etc.. give
true or false when completely instantiated, and don't diverge.
然后我们观察：
The labeling of constraints terminates existentially, i.e. it finds
a solution to a problem after some time if we can also enumerate multiple
infinite domains in a fair way.
所以主要的问题是如何以公平的方式枚举多个无限域，因为当我们不以公平的方式枚举时，我们可能会在域的子集中误入歧途，即使有也找不到解决方案存在一个。想到以下枚举多个无限域的方法：
1) 取消配对功能
使用函数取消配对：N -> NxN，并仅枚举此函数的参数。这是此处描述的旧 Mathematica 技术：An Elegant Pairing Function。缺点每次都需要计算平方根。
2) 公平合取
使用公平连词来组合无限枚举数。这是一种应用于函数式编程的技术，请参见此处的示例：Backtracking, Interleaving, and Terminating Monad Transformers。连接词在常量内存中不起作用的缺点 space，您会生成越来越多的右侧枚举器实例。
3) 额外变量
使用额外的变量 H 和额外的约束，例如 H=abs(X1)+..+abs(Xn) 用于 cantor 配对。然后您可以枚举这个变量并让约束求解器完成剩下的工作。对于某些值的优势，您可能会提前修剪。
在 Jekejeke Minlog 中，我们最近选择了变体 3。这是一个示例 运行 枚举毕达哥拉斯三元组：
?- use_module(library(finite/clpfd)).
?- [X,Y,Z] ins 1..sup, X*X+Y*Y #= Z*Z, label([X,Y,Z]).
X = 3,
Y = 4,
Z = 5 ;
X = 4,
Y = 3,
Z = 5 ;
X = 6,
Y = 8,
Z = 10 ;
X = 8,
Y = 6,
Z = 10
一般来说，当使用无限标签时，人们会尝试解决一个 Diophantine Equation，它并不总是有解决方案，这甚至是不可判定的，我们在希尔伯特第十问题出现后就知道了。所以保证通用终止甚至是不可能的。
另一方面，如果有解决方案，您可能会在一段时间后找到它，前提是解决方案不是太大并且会超过计算机在内存 space 和计算时间方面的限制。但这不应该让你的计算机崩溃，一个体面的 Prolog 系统实现应该优雅地 return 到顶层。您也可以打断翻译或停止要求进一步的解决方案。
再见
I #> 0, I #< 10, indomain(I).
前面的代码显然做了以下事情：
I = 1 ;
I = 2 ;
I = 3 ;
I = 4 ;
I = 5 ;
I = 6 ;
I = 7 ;
I = 8 ;
I = 9.
以下代码不起作用（参数未充分实例化）：
I #> 0, indomain(I).
现在我了解到，在这种情况下，I 有无数种可能的绑定，而且 CLPFD 正如其名称所暗示的那样适用于有限域。
但是我不明白为什么在这种特殊情况下存在这种限制。是不是可以从最小范数到最大范数枚举可能的解，得到如下：
I = 1 ;
I = 2 ;
I = 3 ;
.
.
.
即使对于有多个变量的问题，也可以说：
0 #< I, I #< J, label([I,J]).
为什么不能实现它以致出现以下行为：
I = 1,
J = 2 ;
I = 1,
J = 3 ;
I = 2,
J = 3 ;
I = 1,
J = 4 ;
.
.
.
简而言之：为什么 CLPFD 仍然不能用于无限域，如果这些域很容易使用振幅来计算？
这是因为 CLP(FD) 保留了以下重要的 属性：
If a predicate
p(Vs)terminates universally, then?- p(Vs), label(Vs).also terminates universally.
一个目标G 普遍终止 iff ?- G, false. 终止.
为什么这如此重要？因为一个 CLP(FD) 程序通常由两部分组成：
- 发布所有约束
- 寻找解决方案。
通常很容易通过简单的检查表明建模部分 (1) 普遍终止。但是 (2) 是最困难的部分，通常会占用大部分计算时间，而且我们通常 a priori 甚至不知道是否存在单一解决方案。搜索部分可能 运行 几天、几个月或几年都没有结果。
许多 Prolog 初学者描述了一个搜索任务，运行 它，几秒钟后抱怨 Prolog 很慢。事实上，事实证明，他们经常不小心编写了 不会终止 的程序，并且 永远不会 找到解决方案。
出于这些原因，令人鼓舞的是，如果您只能（通常可以，而且相当容易）显示第 (1) 部分终止，那么您的整个程序 — 第 (1) 部分 并且第(2)部分——也终止。
你是完全正确的，任何可数的无限搜索 space 都可以用你描述的方式之一系统地覆盖到任何有限的范围。然而，这样做会破坏这个基本不变量。您必须能够依靠以下 属性 才能应用上述推理：
label/1,labeling/2andindomain/1always terminate.
在 SWI-Prolog 和 YAP 中，这是由设计确保的。在其他系统中，它在不同程度上成立。
没有理由不允许在 CLP(FD) 中枚举无限域。自从 由于 user:mat 已正确观察到约束本身终止，如果存在解决方案，无限枚举可能会找到解决方案。
所以基本上我们有：
The constraints terminate universally, i.e. (#=)/2, (#=<)/2, etc.. give true or false when completely instantiated, and don't diverge.
然后我们观察：
The labeling of constraints terminates existentially, i.e. it finds a solution to a problem after some time if we can also enumerate multiple infinite domains in a fair way.
所以主要的问题是如何以公平的方式枚举多个无限域，因为当我们不以公平的方式枚举时，我们可能会在域的子集中误入歧途，即使有也找不到解决方案存在一个。想到以下枚举多个无限域的方法：
1) 取消配对功能
使用函数取消配对：N -> NxN，并仅枚举此函数的参数。这是此处描述的旧 Mathematica 技术：An Elegant Pairing Function。缺点每次都需要计算平方根。
2) 公平合取
使用公平连词来组合无限枚举数。这是一种应用于函数式编程的技术，请参见此处的示例：Backtracking, Interleaving, and Terminating Monad Transformers。连接词在常量内存中不起作用的缺点 space，您会生成越来越多的右侧枚举器实例。
3) 额外变量
使用额外的变量 H 和额外的约束，例如 H=abs(X1)+..+abs(Xn) 用于 cantor 配对。然后您可以枚举这个变量并让约束求解器完成剩下的工作。对于某些值的优势，您可能会提前修剪。
在 Jekejeke Minlog 中，我们最近选择了变体 3。这是一个示例 运行 枚举毕达哥拉斯三元组：
?- use_module(library(finite/clpfd)).
?- [X,Y,Z] ins 1..sup, X*X+Y*Y #= Z*Z, label([X,Y,Z]).
X = 3,
Y = 4,
Z = 5 ;
X = 4,
Y = 3,
Z = 5 ;
X = 6,
Y = 8,
Z = 10 ;
X = 8,
Y = 6,
Z = 10
一般来说，当使用无限标签时，人们会尝试解决一个 Diophantine Equation，它并不总是有解决方案，这甚至是不可判定的，我们在希尔伯特第十问题出现后就知道了。所以保证通用终止甚至是不可能的。
另一方面，如果有解决方案，您可能会在一段时间后找到它，前提是解决方案不是太大并且会超过计算机在内存 space 和计算时间方面的限制。但这不应该让你的计算机崩溃，一个体面的 Prolog 系统实现应该优雅地 return 到顶层。您也可以打断翻译或停止要求进一步的解决方案。
再见