Prolog 查询未终止

Question

这是一个非常基本的查询，但我是 prolog 的新手，无法找到此查询不终止的原因：

% fact 
progeny(dexter, mark).
progeny(mark, bill).
progeny(bill, lisa).


% rule
progeny(X, Y) :- progeny(X, Z), progeny(Z, Y).

查询progeny(dexter, X)给出了mark、bill和lisa，但没有终止。
而查询 progeny(Y, lisa) 给出了 bill 和 dexter 并且没有终止（这个查询答案也没有提到标记）。
应该注意的是，我对事实和规则使用相同的名称来测试某些值。
非常感谢对此问题的任何帮助或澄清。

Answer 1

您需要定义另一个谓词作为传递关系。下面的代码工作得很好（注意谓词 progenyt 是实际的传递关系）。

progeny(dexter, mark).
progeny(mark, bill).
progeny(bill, lisa).

progenyt(X, Y) :- progeny(X, Y).
progenyt(X, Y) :- progeny(X, Z), progenyt(Z, Y).

澄清

当你写 progeny(X, Y) :- progeny(X, Z), progeny(Z, Y). 时，你会在某个时候让 prolog 尝试匹配 progeny(dexter, Y) :- progeny(dexter, lisa), progeny(lisa, Y).，这是 prolog 得到 'confused'.

的时刻

即，它将尝试将 progeny(lisa, Y) 与某些事实匹配，这对所有条目都将失败。然后，prolog 将尝试规则 progeny(lisa, Y) :- progeny(lisa, Z), progeny(Z, Y).，它要求评估 progeny(lisa, Z)。在这里你会遇到 stack overflow，因为要让 progeny(lisa, Y) 成功，progeny(lisa, Z) 也必须成功，这会导致某种无限循环，这就是为什么您的查询永远不会终止。

在我发布的解决方案中，这永远不会发生，因为 progenyt(lisa, Y) 要成功，progeny(lisa, Z) 必须成功，而这永远不会发生（所有事实都失败了）。因此，它只会产生这三个结果，然后会立即终止。

请注意，如果在最后一行交换 progeny 和 progenyt，查询也会运行进入与之前相同的问题（对于 progenyt(lisa, Y)要成功，progenyt(lisa, Z)也必须先成功，会导致无限循环）。

Answer 2

您也可以使用tabling。阅读我链接的文档以了解背景、解释和详细信息。

要修复程序，只需为谓词 progeny/2 添加一个 table 指令。

:- table progeny/2.

% fact
progeny(dexter, mark).
progeny(mark, bill).
progeny(bill, lisa).


% rule
progeny(X, Y) :- progeny(X, Z), progeny(Z, Y).

您现在应该得到：

?- [progeny].
true.

?- progeny(dexter, X).
X = bill ;
X = mark ;
X = lisa. % query terminates

?- progeny(Y, lisa).
Y = bill ;
Y = dexter ;
Y = mark. % no missing solutions, query terminates.

Prolog 查询未终止

Prolog query not terminating

prolog

transitive-closure