如何手动追踪Prolog查询?- r([1,2,6], [], L)的求解过程

给定规则说明 #

定义r/3谓词的两个子句：

• 边界事实：r([], X, X). 当第一个输入参数为空列表时，第二个参数与第三个输出参数直接统一
• 递归子句：r([X|Y], X2, X3) :- r(Y, [X|X2], X3). 拆分第一个列表的头元素X，将X拼接至第二个参数列表头部作为新的累加值，递归处理第一个列表剩余的尾元素Y

逐步推导过程 #

第1层调用（初始查询） #

当前目标：r([1,2,6], [], L)

• 第一个参数为非空列表，匹配递归子句
• 变量绑定：X=1, Y=[2,6], X2=[], X3=L
• 生成下一层递归目标：r([2,6], [1], L)

第2层调用 #

当前目标：r([2,6], [1], L)

• 第一个参数为非空列表，匹配递归子句
• 变量绑定：X=2, Y=[6], X2=[1], X3=L
• 生成下一层递归目标：r([6], [2,1], L)

第3层调用 #

当前目标：r([6], [2,1], L)

• 第一个参数为非空列表，匹配递归子句
• 变量绑定：X=6, Y=[], X2=[2,1], X3=L
• 生成下一层递归目标：r([], [6,2,1], L)

第4层调用（触发边界条件） #

当前目标：r([], [6,2,1], L)

• 第一个参数为空列表，匹配边界事实
• 变量绑定：X=[6,2,1]，根据事实要求第三个参数等于第二个参数，因此L=[6,2,1]
• 无剩余待满足目标，递归回溯完成，推导结束

最终查询结果 #

L = [6,2,1]
注：该谓词本质是带累加器的列表反转实现，第二个参数为累加器，初始传空列表即可得到第一个参数的反转结果

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