Prolog合一算法运行机制及事实顺序影响查询结果原因

Prolog的合一不是孤立的项匹配逻辑，是和深度优先搜索+顺序匹配+回溯机制绑定运行的，核心执行规则如下：

• 复合查询的子目标严格从左到右依次执行
• 匹配事实/规则时，严格按照代码中书写的从上到下顺序尝试匹配
• 每遇到一个有多个匹配可能的位置就会生成选择点，记录当前的变量绑定状态，留待回溯时使用
• 找到一组能满足所有子目标的变量绑定后，会立刻返回结果，如果此时还有未探索的选择点，会等待用户输入;触发回溯查找下一个解；如果没有剩余选择点，就直接结束查询
• 回溯时会撤销最近一次的变量绑定，回到上一个选择点，尝试下一个可匹配的选项，所有选择点都探索完仍找不到合理解时，返回false

第一个查询场景的执行逻辑 #

对应知识库代码：

bar(b).
bar(c).
baz(c).

执行查询bar(X), baz(X).的流程：

1. 先执行第一个子目标bar(X)，按顺序匹配到第一条事实bar(b)，绑定X = b，此时记录选择点：bar(X)还有第二条事实bar(c)未探索
2. 执行第二个子目标baz(X)即baz(b)，知识库中只有baz(c)，匹配失败，触发回溯
3. 撤销X = b的绑定，回到bar(X)的选择点，匹配第二条事实bar(c)，绑定X = c，此时bar(X)已经没有剩余未探索的事实，不存在未处理的选择点
4. 执行第二个子目标baz(c)，匹配成功，所有子目标满足，直接返回结果X = c，因为没有剩余选择点，查询直接结束，不会提示查找下一个解。

第二个查询场景的执行逻辑 #

调整事实顺序后的知识库代码：

bar(c).
bar(b).
baz(c).

执行相同查询bar(X), baz(X).的流程：

1. 先执行第一个子目标bar(X)，按顺序匹配到第一条事实bar(c)，绑定X = c，此时记录选择点：bar(X)还有第二条事实bar(b)未探索
2. 执行第二个子目标baz(c)，匹配成功，所有子目标满足，返回结果X = c。因为此时还存在未探索的选择点，Prolog会等待用户输入;确认是否查找下一个解
3. 用户输入;触发回溯，撤销X = c的绑定，回到bar(X)的选择点，匹配第二条事实bar(b)，绑定X = b，此时bar(X)没有剩余未探索的事实
4. 执行第二个子目标baz(b)，匹配失败，所有选择点已全部探索完毕，没有其他可满足条件的解，因此返回false。

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