在 prolog 中表达 collat​​z 猜想的不同方式失败

Question

我正在使用 SWI Prolog 和此处的教程学习 prolog 。我发现，如果我像视频中那样表达科拉茨猜想，只要我将其替换#=为is我猜测的swipl差异，它就会起作用scryer-prolog。但如果我稍微调整这个定义，它似乎就会被破坏，要么出现错误，要么得出不正确的结论。为什么我的替代定义失败了？代码：

use_module(library(clpfd)).

%% Does work, collatz_next(A, 1) gives A=2
collatz_next(N0, N) :-
    N0 is 2*N.
collatz_next(N0, N) :-
   N0 is 2*_ + 1,
   N is 3*N0 + 1.

%% Doesn't work, collatz_next(A, 1) gives false
%% collatz_next(N0, N) :- ((N0 mod 2) is 0),((N0 / 2) is N).
%% collatz_next(N0, N) :- ((N0 mod 2) is 1),((N0 * 3 + 1) is N).

%% Doesn't work, collatz_next(A, 1) gives false
%% collatz_next(N0, N) :- ((N0 mod 2) is 0),(N0 is 2*N).
%% collatz_next(N0, N) :- ((N0 mod 2) is 1),((N0 * 3 + 1) is N).

%% Doesn't work
%% "Arguments are not sufficiently instantiated"
%% collatz_next(N0, N) :-
%%    N0 / 2 is N.
%% collatz_next(N0, N) :-
%%    N0 is 2*_ + 1,
%%    N is 3*N0 + 1.

Answer 1

:- use_module(library(clpfd)).正如 brebs 已经在评论中写的那样，如果您使用的是 SWI-Prolog，则必须包含该行。但是，如果您使用的是 Scryer Prolog，则该库称为 clpz，因此您必须包含行:- use_module(library(clpz)).. 如果您使用相应的库（我使用 Scryer Prolog 版本 0.9.0 和 SWI-Prolog 版本 8.4.2 进行了测试，两者都在 Linux 计算机上运行，​​均为 64 位），则谓词collatz_next/2（来自链接的视频）可与视频中描述的两个 Prolog 一起使用）。由于评论中还没有提到，我还建议您参考The Power of Prolog 中对 CLP(FD) 和 CLP(Z) 的描述。

现在回答你关于失败替代方案的问题。is/2如果右侧的表达式计算结果为左侧的数字，则内置表达式为 true。如果左侧是未实例化的变量，则该变量包含调用目标后右侧表达式的值。为了成功，右侧表达式中的所有变量都需要被初始化。考虑以下示例：

α-3是2+1。
真的。
   
?-X是2+1。
X = 3。
   
α-3是X+1。
错误：参数没有充分实例化
...

α-3是2+X。
错误：参数没有充分实例化
...

此外，如果左侧用浮点而不是整数实例化is/2将会失败：

?- 3.0 是2+1。
错误的。

现在我们已经介绍了一些基础知识，让我们看一下您的第一个谓词：

%% 有效，collat​​z_next(A, 1) 给出 A=2
collat​​z_next(N0, N) :-
   N0 为 2*N。
collat​​z_next(N0, N) :-
   N0 为 2*_ + 1，
   N 为 3*N0 + 1。

让我们观察一下，虽然您给定的示例产生了正确的答案，但在按 -;键后它会抛出实例化错误：

?- collat​​z_next(A, 1)。
A = 2 ;
错误：参数没有充分实例化
...

这里发生了什么？您正在发布查询，因此谓词头部的collatz_next(A, 1).变量与变量统一，变量与 统一。通过这些统一，第一条规则中的唯一目标 ，现在变为。这就得出了答案。Prolog 现在尝试第二条规则，其中第一个目标现在变为。这里右侧仍然包含一个变量 ( )，因此表达式没有充分实例化以进行计算，因此 Prolog 会抛出实例化错误。N0AN1N0 is 2*NA is 2*1A = 2collatz_next/2N0 is 2*_ + 1A is 2*_ + 1_

现在让我们尝试以相反的方式使用谓词。正如您在 Youtube 视频中看到的，如果N0=5那么预期的答案是N=16。但是，如果您使用谓词查询，您将得不到答案并出现实例化错误：

?- collat​​z_next(5, N)。
错误：参数没有充分实例化
...

查看您的定义，我们可以观察到规则头部的collatz_next/2变量与 统一，而第二个参数仍未实例化。第一个规则中的单个目标 ，因此由于右侧的变量而成为实例化错误。N05NN0 is 2*N5 is 2*N

请注意，视频还显示，:- collatz_next(N0,N).由于使用 CLP(FD)/CLP(Z)，最常见的查询仍在生成答案，而您的版本使用is/2，再次产生实例化错误。

您发布的接下来的两个版本collatz_next/2（带有评论的版本%% Doesn't work, collatz_next(A, 1) gives false）因规则中的第一个目标而失败。由于您查询规则头部的:- collatz_next(A, 1).变量与变量 统一，因此所有四个规则中的第一个目标分别变为和。如果您尝试将这些目标作为查询，答案是错误的：N0A((A mod 2) is 0)((A mod 2) is 1)

?- ((A mod 2) 为 0)。
错误的。

?- ((A mod 2) 为 1)。
错误的。

由于规则的第一个目标失败，Prolog 甚至不会尝试第二个目标，因为一旦你false在连词（链）中出现一个，它就不能产生 true。两个谓词的两个规则都是这种情况，因此您的查询的答案是错误的。另一方面，如果您尝试将左侧与is/2右侧交换，您将收到实例化错误：

?-（0 是（A mod 2））。
错误：参数没有充分实例化
...
   
?-（1 是（A mod 2））。
错误：参数没有充分实例化
...

也许可以这样想：如果您尝试对一个未实例化的变量取实际数字的模，您会期望发生什么？一种合理的期望是得到某种反馈，表明这是无法完成的。另一个合理的观点是期望 Prolog 将发布的目标作为约束传播，直到它可以（希望）稍后得到解决。这基本上就是 CLP(FD)/CLP(Z) 所做的事情（另请参阅The Power of Prolog 中有关 CLP(FD) 和 CLP(Z)中的约束传播的部分。只需尝试使用上述查询(#=)/2：

?- ((A mod 2) #= 0)。
模 2#=0。% 剩余目标
   
?- ((A mod 2) #= 1)。
模2#=1。% 剩余目标
   
?- (0 #= (A mod 2))。
模 2#=0。% 剩余目标
   
?- (1 #= (A mod 2))。
模2#=1。% 剩余目标

正如您所看到的，发布的约束现在已传播，并在推导结束时显示为剩余目标，因为在这些情况下，查询仅包含这些单个目标，无法进一步解析它们。

您发布的最后一个版本（标有评论%% Doesn't work）在第一条规则的单一目标中具有错误方式的左侧和右侧is/2，正如 TessellationHeckler 在评论中指出的那样。但即使你交换它们，除非变量N0被实例化，否则你也会得到实例化错误。但即便如此，一旦 Prolog 尝试第二条规则，您仍然会收到实例化错误，因为它的第一个目标N0 is 2*_ + 1包含一个始终未实例化的变量_：

?- N0 是 2*_ + 1。
错误：参数没有充分实例化
...
   
?- 1 是 2*_ + 1。
错误：参数没有充分实例化
...

底线是：如果您想使用低级谓词，则is/2必须了解它们的局限性。如果您想对整数进行声明式推理，则无法轻松绕过 CLP(FD)/CLP(Z)。而且，如果您决定使用视频中所示的谓词collatz_next/2，则无法将 CLP(FD)/CLP(Z) 约束一对一交换为低级谓词（例如）is/2并期望获得相同的结果。