简单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).

使用simple，特别是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)

令我困惑的是prolog似乎要重做：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.

..。这改善了决定论。