序言推导在此查询中如何工作？

Question

我尝试使用以下规则集编写一个简单的 Prolog 程序。

conc([],L,L).
conc([X|L1],L2,[X|L3]):- conc(L1,L2,L3).

然后我将其加载到 SWI-Prolog shell 并在跟踪模式下执行以下查询。

 ?-conc([2,3],[p,q],[2,3,p,q]).

输出如下。

[trace]  ?- conc([2,3],[p,q],[2,3,p,q]).
   Call: (8) conc([2, 3], [p, q], [2, 3, p, q]) ? creep
   Call: (9) conc([3], [p, q], [3, p, q]) ? creep
   Call: (10) conc([], [p, q], [p, q]) ? creep
   Exit: (10) conc([], [p, q], [p, q]) ? creep
   Exit: (9) conc([3], [p, q], [3, p, q]) ? creep
   Exit: (8) conc([2, 3], [p, q], [2, 3, p, q]) ? creep
true.

现在的问题是画出这个目标的推导树，但我无法完全理解prolog是如何做到这一点的，即使查看上面的trace输出也是如此。

有人可以根据上述规则集解释上述查询的派生树吗？非常感谢有用的答案。

Answer 1

?- conc([2,3],[p,q],[2,3,p,q]).

Call: (8) conc([2, 3], [p, q], [2, 3, p, q]) ? creep

当前目标就是题目。

由于[2,3]不匹配[]，所以规则1没有选择，所以尝试规则2。为了匹配规则 2 的头部，进行了以下替换：X/2, L1/[3], L2/[p,q], L3/[3,p,q].

我们的新目标现在是规则 2 的主体，conc(L1,L2,L3)，经过上述替换后，即 conc([3],[p,q],[3,p,q])。

Call: (9) conc([3], [p, q], [3, p, q]) ? creep

由于[3]不匹配[]，所以规则1没有选择，所以尝试规则2。替换：X/3、L1/[]、L2/[p,q]、L3/[p,q] 我们的新目标现在是 conc(L1,L2,L3) 在适当的解决方案之后，相当于 conc([],[p,q],[p,q]).

Call: (10) conc([], [p, q], [p, q]) ? creep

匹配规则 1 => 证明成功

因此，目标 10 的待办事项清单得到证明，因此目标 10 得到证明：

Exit: (10) conc([], [p, q], [p, q]) ? creep

因此，目标 9 的待办事项清单得到证明，因此目标 9 得到证明：

Exit: (9) conc([3], [p, q], [3, p, q]) ? creep

因此，目标 8 的待办事项清单得到证明，因此目标 8 得到证明：

Exit: (8) conc([2, 3], [p, q], [2, 3, p, q]) ? creep

既然目标 8 是问题，我们就完成了，证明也完成了：

true.

Answer 2

我觉得使用示踪剂通常是没有帮助的，除非你已经知道你在做什么并且知道在精确的位置有问题，即使那样它也是一个 hard-to-disentangle一团糟.

最好仔细查看程序，并将其作为递归调用的定义（或者作为归纳定义）阅读：

空列表[]和其他一些列表L的串联是同一个列表L:

    conc( [], L, L ).

第一个元素为 X 的非空列表与其他列表 L2 的串联是一个以相同 X 并继续列表 L3 这样：
- L3 是列表 L1 和 L2:

    conc( [X | L1], L2, [X | L3] ) :- 
        conc(  L1,  L2,      L3 ).

这是一个很好的串联定义：

每当 conc(A1,A2,R) 成功时，我们肯定会得到 A1 的所有元素，后面跟着 A2 的所有元素，形式为 R（因此定义作为“串联”有意义）。
每当 conc“引用自身”（递归地）第一个列表参数小一个，所以我们有一个单调递减的“变体”并且正在到达某个地方（我们也会自动停止因为列表长度始终 >= 0)。
当第一个列表参数的长度为 0 时，有一个“基本情况”的非递归定义，所以当我们停止时，我们可以成功地做到这一点（如果第一个子句 conc([],L,L). 丢失我们会停止但由于缺少空列表的匹配子句而失败）。

“推导树”相当线性（与您在函数式语言中找到的推导没有什么不同），即递归地应用第二个子句直到它不再适用，然后应用他的第一个子句。

因此我们看到：

Call: (8) conc([2, 3], [p, q], [2, 3, p, q])
   Call: (9) conc([3], [p, q], [3, p, q])
      Call: (10) conc([], [p, q], [p, q])
      Exit: (10) conc([], [p, q], [p, q])
   Exit: (9) conc([3], [p, q], [3, p, q])
Exit: (8) conc([2, 3], [p, q], [2, 3, p, q])

注意“出口”的传统名称。正确的名称是而且应该一直是“成功”，即使在 1980 年代也是如此。它从未改变。

Answer 3

推导树如下（考虑重命名变量的子句）：

序言推导在此查询中如何工作？

How prolog derivation works in this query?

trace

list

concatenation

prolog