简单prolog示例中的意外回溯

Question

下面是一个简单的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，特别是swish.SWI-Prolog.org，下面的简单查询会产生正确的答案true，但也会出现回溯，然后说false。

?- ancestor(john, jane).
true
false

这让我很困惑，而且出乎意料。

我尝试过追踪：

trace, ancestor(john, jane).
Call:ancestor(john,jane)
Call:parent(john,jane)
Exit:parent(john,jane)
Exit:ancestor(john,jane)
1true
Redo:parent(john,jane)
Fail:parent(john,jane)
Redo:ancestor(john,jane)
Call:parent(john,_696)
Exit:parent(john,jane)
Call:ancestor(jane,jane)
Call:parent(jane,jane)
Fail:parent(jane,jane)
Redo:ancestor(jane,jane)
Call:parent(jane,_698)
Fail:parent(jane,_698)
Fail:ancestor(jane,jane)
Redo:parent(john,_696)
Exit:parent(john,james)
Call:ancestor(james,jane)
Call:parent(james,jane)
Fail:parent(james,jane)
Redo:ancestor(james,jane)
Call:parent(james,_698)
Fail:parent(james,_698)
Fail:ancestor(james,jane)
Fail:ancestor(john,jane)

令我困惑的是，序言似乎在重做：parent(john, jane)问题：为什么会这样

我自己(公认的学生(的理解是，prolog只会回溯，为查询时未绑定的变量尝试附加值。这里，递归定义的第一条规则中没有在查询时未绑定的变量：ancestor(X,Y) :- parent(X,Y)。

我可以理解prolog在递归定义的第二条规则中为变量尝试新值：ancestor(X,Y) :- parent(X,A), ancestor(A,Y).这里prolog可以为A.尝试新值

---

UPDATE-我尝试删除定义的递归部分：

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

查询仍然会导致回溯。

?- ancestor(john, jane).
true
false

尽管轨迹较短。

trace, ancestor(john, jane).
Call:ancestor(john,jane)
Call:parent(john,jane)
Exit:parent(john,jane)
Exit:ancestor(john,jane)
1true
Redo:parent(john,jane)
Fail:parent(john,jane)
Fail:ancestor(john,jane)
false

这更加尖锐地集中在意外行为上。为什么prolog回溯到没有未绑定变量的点？

Answer 1

这可以归结为：

parent(john, jane).
parent(john, james).
parent(sally, jane).

?- parent(john, jane).
true ;
false.

choicepoint之所以发生，是因为两个参数的组合都没有索引。

解决这个问题的最简单方法是使用制表，方法是在代码中添加：

:- table parent/2.
:- table ancestor/2.

这提高了决定论。