为何简单Prolog程序中会出现意外回溯现象？

示例程序 #

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

现象描述 #

执行查询 ?- parent(john, jane). 时，Prolog会先返回 true，但当触发获取更多答案的操作时，会返回 false。该现象在SWI-Prolog、Swish和GNU Prolog中均存在。

原因解释 #

这是Prolog回溯机制与索引实现逻辑共同作用的结果：

• 多数Prolog系统会基于谓词的参数（比如第一个参数）建立索引。查询 parent(john, jane) 时，系统会先定位到所有第一个参数为john的事实，也就是parent(john,jane)和parent(john,james)两条。
• 匹配到第一条符合的事实后，Prolog不会直接判定没有其他匹配项，而是会记录一个选择点（标记同索引组内还有未检查的事实），先返回true。
• 当请求更多答案时，Prolog回溯到该选择点，检查剩余的同组事实。发现parent(john,james)与查询目标不匹配，且无其他待检查事实，于是返回false，表示没有更多符合条件的答案。

简言之，哪怕查询和事实中都没有变量，只要当前索引分组内还有未检查的条目，Prolog就会保留选择点，不会在第一次匹配时直接确认“无更多答案”。

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