解释为什么 append/3 在这些情况下产生无限数量的解决方案

Question

我无法理解这个关于 Prolog 的问题。题目如下：

Select all of the following goals that have an infinite number of solutions.

以下是可能的答案：

append([a,b,c,d], Y, Z)
append(X, Y, X)
append(X, [a,b,c,d], Z)
append(X, Y, [a,b,c,d])

显然正确答案是 2 和 3，但我不明白为什么 1 也不正确 - Z 和 Y 不会有无限的可能性吗？另外，为什么 2 是正确的，因为第一个参数和第三个参数（“结果”）是相同的？听起来 Y 可能只是 [].

非常感谢！

Answer 1

append(X, Y, X) 只能对 Y == [] 成立（这是 Wadler 的“免费定理”），但在该约束下，X 可以是无限种可能性中的任何一种:

SWI-Prolog 发现了 Y == [] 并且对 X 列表的内容不置可否，仅将其作为未绑定变量的列表给出：

?- append(X,Y,X).
X = Y, Y = [] ;   % alternative writing of X = [], Y = []
X = [_6696],
Y = [] ;
X = [_6696, _7824],
Y = [] ;
X = [_6696, _7824, _8952],
Y = [] ;
X = [_6696, _7824, _8952, _10080],
Y = [] ;
X = [_6696, _7824, _8952, _10080, _11208],
Y = [] 
...

你是对的 append([a,b,c,d], Y, Z) 应该被列为承认无限多的解决方案。

有趣的是，SWI-Prolog 在这种情况下没有枚举模板/占位符变量/候选者列表，而是吐出本质上是对约束 append([a,b,c,d], Y, Z) 的重写，即它的行为更 theorem-proverish 比案例 1:

?- append([a,b,c,d],Y,Z).
Z = [a, b, c, d|Y].

(这是 Prolog 的歧义：它什么时候枚举，什么时候不枚举？如果有 Prolog 表示法 “未指定内容的 N 值列表， N 0 到 +oo 之间的整数 这样的符号可以用作 append(X,Y,X) 的输出。）

这里没有选择的备选方案是：

?- append([a,b,c,d],Y,Z).
Y = [], 
Z = [a,b,c,d] ;
Y = [_1], 
Z = [a,b,c,d,_1] ;
Y = [_1,_2], 
Z = [a,b,c,d,_1,_2] ;
...

是否有执行上述操作的 Prolog？可能会有。

Answer 2

如果您想准确地谈论 Prolog，有必要（至少）区分 answers 和 solutions询问。 answer 是一个过程概念，它是 Prolog 每次查询成功时生成的变量的替换。 解决方案是查询成功的变量替换。每个答案替换都是一个解决方案，但这并不能使这些概念成为同义词。

考虑这个谓词：

foo(a).
foo(a).

这有两个答案（恰好看起来一样）：

?- foo(X).
X = a ;
X = a.

它只有一个解：只有替换X = a才能成功，Prolog甚至可以证明这一点：

?- X = a, foo(X).
X = a ;
X = a.

?- dif(X, a), foo(X).
false.

在这种情况下，答案多于解决方案。相反的也可以：

bar(f(_X)).

这里的查询bar(T)只有一个答案，但有多个解（实际上是无穷多个）：

?- bar(T).
T = f(_708).

?- T = f(1), bar(T).
T = f(1).

?- T = f(2), bar(T).
T = f(2).

现在让我们看一下问题的第一个查询：

?- append([a, b, c, d], Y, Z).
Z = [a, b, c, d|Y].

根据上面的定义，这只有一个答案。但是正如您所指出的，我们可以用无限多个不同的值替换变量，得到无限多个 解决方案 ，例如：

?- Y = [1], append([a, b, c, d], Y, Z).
Y = [1],
Z = [a, b, c, d, 1].

?- Y = [1, 2], append([a, b, c, d], Y, Z).
Y = [1, 2],
Z = [a, b, c, d, 1, 2].

现在，坏消息是你的老师似乎没有使用与我在这里使用的相同的约定。使用上面定义的术语，老师问的是答案，而你在思考解决方案。很想知道他们是否理解这种区别，以及他们使用什么术语来表示这些不同的概念。如果他们的意思真的是 answers，那么他们认为这个查询没有无限多是正确的。如果他们真的是指 解决方案 ，那么你是对的，它确实有无限多的解决方案。

至于第二个查询：

?- append(X, Y, X).
X = Y, Y = [] ;
X = [_818],
Y = [] ;
X = [_818, _824],
Y = [] ;
X = [_818, _824, _830],
Y = [] .

你是对的，Y 只能是 []，但这仍然为 X 留下无限数量的 解决方案 。在这里 Prolog 还产生了无限多的 answers 来描述这些解决方案。

解释为什么 append/3 在这些情况下产生无限数量的解决方案

Explanation for why append/3 produces infinite number of solutions in these cases

list

append

prolog

infinite