为何Prolog中jealous谓词子句顺序会导致jealous(1,4)查询栈溢出

Prolog的消解执行没有自动逻辑等价优化，完全遵循固定顺序的深度优先搜索机制，规则和子目标的书写顺序直接决定执行路径，和纯逻辑层面的等价性无关。

Prolog消解的核心执行原则 #

Prolog运行时永远遵守两个固定规则，没有例外：

• 子句匹配：从上到下遍历代码中的所有事实和规则，优先匹配位置最靠上的条目，匹配成功就进入对应分支，不会提前查看下方的子句。
• 子目标求解：规则体中的目标从左到右依次求解，左侧目标未完成求解前，不会触达右侧的任何子目标。

栈溢出版本的死循环执行推演 #

栈溢出版本的代码中，递归规则排在边界终止规则之前，执行jealous(1,4)的流程为：

1. 首次调用jealous(1,4)时，Prolog从上到下匹配，最先命中排在第一的递归规则jealous(A, B) :- jealous(A, C), jealous(C,B).，绑定A=1、B=4。
2. 按照从左到右的顺序先求解规则体的第一个子目标jealous(1, C)，此时完全不会执行右侧的jealous(C,4)。
3. 求解jealous(1, C)时，Prolog依旧从上到下匹配，再次优先命中最上方的同一条递归规则，绑定A=1、B=C1，递归进入下一层调用，依然优先求解左侧子目标jealous(1, C2)。
4. 这个过程会无限重复，属于典型的左递归死循环：每一层调用都优先匹配最上方的递归规则，永远不会触达排在下方的、基于hates的终止边界规则。递归栈会不断压入新的jealous(1, 变量)调用，最终耗尽栈空间触发溢出，全程没有机会打通关系链路。

顺序调整后的正常执行逻辑 #

将基于hates的边界终止规则放到所有递归规则的最上方后，执行流程会发生本质变化：

1. 调用jealous(1,4)时，Prolog首先匹配最上方的边界规则，检查是否存在hates(1,4)的事实——确认不存在后，才会跳去匹配下方的递归规则。
2. 进入递归规则后，依然优先求解左侧子目标jealous(1, C)，此时因为边界规则在最上方，求解该目标会快速匹配到hates(1,2)的事实，得到确定的C=2。
3. 拿到C的确定值后，再求解右侧子目标jealous(2,4)，重复同样的逻辑：先检查直接的hates关系，没有的话进入递归得到C=3，再求解jealous(3,4)，匹配到hates(3,4)的事实，整个关系链路打通，最终返回正确结果。

常见认知误区 #

• 纯逻辑层面的规则等价性，不代表Prolog执行层面的行为等价。Prolog本质是按固定顺序遍历搜索的解释器，不是自动定理证明器，不会主动优化规则的执行顺序。
• 只要递归调用的优先级高于终止边界规则，无论递归逻辑本身是否自洽，都会触发无限栈压入。
• 即使调整了规则的上下顺序，如果规则体的子目标顺序不合理，依然可能触发其他路径的死循环——因为子目标从左到右优先求解的机制始终不变。

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