为什么 Prolog 在一种情况下会自动回溯，但在另一种情况下不会？

Question

我有一个带有两个谓词

rr

和

p

的 Prolog 程序，每个谓词都有自己的一组规则和事实。当使用特定输入查询这些谓词时，我注意到 Prolog 在一种情况下会自动回溯，但在另一种情况下则不会。

rr(f(X,Y),g(Z)) :- rr(Y,Z).
rr(a,a).

p(X,Y,f(a)) :- p(X,X,Y).
p(X,X,X).

查询：

?- rr(f(a,f(b,a)),X).
X = g(g(a)).
?- p(X,a,f(X)).
X = a ;
false.

如您所见，第一个查询不执行任何回溯，而第二个查询会自动让您在第一个解决方案之间进行选择或手动执行回溯。

[trace]  ?- rr(f(a,f(b,a)),X).
   Call: (10) rr(f(a, f(b, a)), _27336) ? creep
   Call: (11) rr(f(b, a), _28554) ? creep
   Call: (12) rr(a, _29312) ? creep
   Exit: (12) rr(a, a) ? creep
   Exit: (11) rr(f(b, a), g(a)) ? creep
   Exit: (10) rr(f(a, f(b, a)), g(g(a))) ? creep
X = g(g(a)).

[trace]  ?- p(X,a,f(X)).
   Call: (10) p(_33908, a, f(_33908)) ? creep
   Call: (11) p(a, a, a) ? creep
   Exit: (11) p(a, a, a) ? creep
   Exit: (10) p(a, a, f(a)) ? creep
X = a ;
   Redo: (10) p(_33908, a, f(_33908)) ? creep
   Fail: (10) p(_33908, a, f(_33908)) ? creep
false.

打印跟踪时，两个程序都选择了一条以空语句结尾的路径，但第二个程序自动检测回溯，为什么 Prolog 会这样？是否能够在第一种情况下预先检测到其他可能的解决方案无效？

Answer 1

当 Prolog 引擎在代码中选择一条路径，并留下一个选择点以返回并尝试其他可能的路径时，就会发生回溯。如果系统可以快速判断出一条路径无法得出答案，那么它可以忽略该路径并且永远不会回来尝试。这不会改变答案（回溯提示本身不是答案），它是一种性能优化 - 做更少的工作意味着更快完成。在

rr/2

上留下选择点是有效的，但没有用。

一个策略是第一个参数索引：在

rr/2

中，第一个参数的形状是不同的：

rr(f(X,Y), ...
rr(     a, ...

查询

?- rr(f(..,..), ..

无法将第一个参数与

a

统一，并且可以在离开选择点并回溯以稍后尝试完整调用之前快速识别。在

p/2

：

p(X, ...
p(X, ...

第一个参数是相同的，没有快速的方法来排除其中一个，所以它留下一个选择点并尝试第一个，如果需要的话可以稍后返回并尝试第二个子句。

SWI Prolog 有多种索引，如下所述：

• 即时 (JIT) 索引
  • 可以在

    [_|_]

    和

    []

    之间进行选择的静态代码，用于快速递归列表到末尾。
  • 对第一个参数进行线性扫描，寻找确定性（无选择点）结果。
  • 满足某些重要条件的谓词的哈希表查找。
• 索引数据库
  • 使用

    term_hash/2

    和

    term_hash/4

    自定义某些谓词的索引。

其他 Prolog 系统有其他策略，可能会导致不同类型代码的性能优势和劣势；我认为第一个参数索引在许多系统中都实现了。