如何理解该Prolog问题的执行逻辑与查询结果推导

首先给出问题涉及的完整Prolog代码：

a(1).
a(2).
b(a).
c(A,B,C) :- a(A),d(B,C).
c(A,B,C) :- b(A),d(B,C).
d(B,C) :- a(B),!,a(C).
d(B,_) :- b(B).

核心疑问说明 #

你看到的Y = Z, Z = 1这类输出不是特殊的变量约束推导，只是SWI-Prolog顶层的输出简写：当多个变量同时绑定到同一个基础值时，会用链式等号避免重复书写，本质等价于Y=1, Z=1。

先拆解d(B,C)的执行逻辑 #

d/2谓词里的!（剪枝）是执行流程的核心，先明确剪枝的生效规则：只有当剪枝被实际执行到时才会生效，生效后会做两件事：

• 丢弃当前谓词所有其他子句的备选分支，不会再尝试匹配其他子句
• 丢弃当前子句中、剪枝左侧所有目标产生的选择点，这些目标不能再回溯找其他解

单独查询d(B,C)时执行流程如下：

1. 匹配第一个d/2子句，首先调用左侧目标a(B)，第一个匹配事实a(1)，B绑定为1
2. 执行剪枝!：直接丢弃第二个d/2子句的匹配资格，同时丢弃a(B)剩余的备选（即B=2的匹配选项），B的值被固定为1
3. 执行剪枝右侧的a(C)，按顺序匹配两个事实：
   • 匹配a(1)：C绑定为1，此时B=1、C=1，对应第一个解，顶层输出Y = Z, Z = 1
   • 回溯匹配a(2)：C绑定为2，此时B=1、C=2，对应第二个解，顶层输出Y = 1, Z = 2
4. a(C)没有更多匹配项，d/2的所有可选分支已经被剪枝清空，查询结束，没有更多解。

注意：第二个d/2子句在这个查询里完全没有被触发——因为第一个子句的a(B)首次匹配就成功并触发了剪枝，直接切断了访问第二个子句的路径。只有当第一个子句的a(B)匹配失败（比如查询d(a, X)时，a(a)不成立，剪枝不会被执行），才会走到第二个子句。

再拆解c(X,Y,Z)的执行逻辑 #

c/3有两个独立子句，执行时会按子句顺序匹配，且每次调用d(B,C)都是全新的独立调用，之前调用产生的剪枝效果不会跨调用保留，流程如下：

1. 匹配第一个c/3子句，先调用a(A)：
   • 第一个匹配a(1)，A=1，调用d(B,C)，得到两个解：B=1,C=1、B=1,C=2，对应前两个总解：
     • X=1, Y=1, Z=1（顶层简写为X = Y, Y = Z, Z = 1）
     • X=1, Y=1, Z=2（顶层简写为X = Y, Y = 1, Z = 2）
   • 回溯a(A)，第二个匹配a(2)，A=2，重新调用d(B,C)，再次得到两个解：B=1,C=1、B=1,C=2，对应接下来两个总解：
     • X=2, Y=1, Z=1（顶层简写为X = 2, Y = Z, Z = 1）
     • X=2, Y=1, Z=2（顶层简写为X = Z, Z = 2, Y = 1）
2. a(A)没有更多匹配项，第一个c/3子句执行结束，回溯匹配第二个c/3子句，调用b(A)：
   • 匹配b(a)，A=a，第三次调用d(B,C)，同样得到两个解：B=1,C=1、B=1,C=2，对应最后两个总解：
     • X=a, Y=1, Z=1（顶层简写为X = a, Y = Z, Z = 1）
     • X=a, Y=1, Z=2（顶层简写为X = a, Y = 1, Z = 2）
3. b(A)没有更多匹配项，所有分支遍历完成，查询结束，总共6个解，和你在SWI-Prolog中运行的结果完全一致。

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