SWI-Prolog中简单查询出现意外回溯的原因咨询

示例Prolog程序 #

% parent facts
parent(john, jane).
parent(john, james).
parent(sally, jane).
parent(martha, sally).
parent(deirdre, martha).

% ancestor recursive definition
ancestor(X,Y) :- parent(X,Y).
ancestor(X,Y) :- parent(X,A), ancestor(A,Y).

问题现象 #

在SWI-Prolog中执行查询?- ancestor(john, jane).，返回正确结果true后，会触发回溯并最终返回false。追踪发现Prolog会重新执行parent(john, jane)，即使移除递归规则，该现象依然存在。

原认知是Prolog仅会为查询中未绑定的变量回溯尝试新值，但此场景中第一条规则没有未绑定变量，为何会出现这种回溯行为？

解答 #

这是因为Prolog的回溯机制本质是穷尽所有可能解，哪怕当前已经找到一个确定的解，它依然会尝试检查是否存在其他潜在的解，这是语言的固有设计。

具体到这个场景：

• 执行ancestor(john, jane)时，首先匹配第一条规则ancestor(X,Y) :- parent(X,Y)，找到parent(john, jane)事实，返回true。
• 但Prolog会记录当前的「选择点」：一是还有第二条ancestor规则未尝试，二是parent事实中是否存在其他能匹配parent(john, jane)的条目（尽管这里没有，但Prolog仍会回溯检查）。
• 当触发继续查询（比如在SWI-Prolog中按分号），Prolog就会回溯：先尝试第二条规则，X=john时先找parent(john,A)的可能值，第一个是A=jane，调用ancestor(jane,jane)无匹配事实，递归失败；接着回溯到parent(john,A)的下一个值A=james，调用ancestor(james,jane)同样失败。所有选择点尝试完毕后，返回false。

哪怕移除递归规则，只保留ancestor(X,Y) :- parent(X,Y)，Prolog依然会在返回true后，检查是否有其他parent(john, jane)事实，确认没有后返回false——这种行为和是否存在未绑定变量无关，只要存在未尝试的选择点，就会触发回溯。

内容的提问来源于stack exchange，提问作者Prolog ByExample