PROLOG【手算】

Question

我正在尝试在 prolog 中练习手算，能否请您向我解释并演示这个特定问题的手算，以便我获得更多的理解。

在涉及文本处理的 Prolog 项目中（此处未进一步讨论），已实现谓词 duplicate/2 以复制列表的每个条目。下面是 duplicate/2 的一个例子：

?- duplicate([w,o,r,d], D).

D = [w,w,o,o,r,r,d,d] .

?- duplicate([], D).

D = [].

下面显示了 duplicate/2 的定义。写下 duplicate/2

的手算

duplicate(L, D) :- duplicate(L,[], D). % clause 0

duplicate([], Acc, D) :- reverse(Acc, D). % clause 1

duplicate([H|T], Acc, D) :- duplicate(T, [H, H|Acc], D). % clause 2

（涉及辅助谓词 duplicate/3 ）使得三个中的每一个子句（编号为 0、1、2）在手算中执行。

Answer 1

好吧，让我们使用示例查询的简化版本 duplicate([w], D).。只有一个规则头，它有两个参数：子句 0 中的一个，其中 L=[w] 和 D1=D。(1) 正文告诉我们，我们应该推导 duplicate([w],[],D)。第1条的head不匹配，因为[]和[w]不能统一。这留下了条款 2：[w] = [H|T] 与 H=w 和 T=[] (2) 统一，Acc = [] 和 D2=D。现在我们的新目标是 duplicate([], [w,w], D)，它只匹配条款 1 (3)。我们的目标是 reverse([w,w],D)，这是内置的 reverse/2 谓词。如果 D 与 [w,w] 的反向列表统一，则为真，因此 D=[w,w]。现在我们没有任何目标可以推导，已经找到了一个完整的推导。由于我们总是重命名规则的变量，因此 D 仍然是我们原始查询中的变量，这意味着 D = [w,w] 是查询的正确答案替代。

我承认我有点懒，只有一个重复的字母，累加器Acc的反转似乎有点无意义。要了解为什么有必要，您可以尝试对 duplicate([x,y],D) 进行相同的推导，其中累加器应为 [y,y,x,x]，因为元素始终在前面。

另一个有趣的练习也是 duplicate(X,[w,w]) 并检查 duplicate(X,[w]) 失败的原因（提示：查看统一问题 [w] = [H,H|Acc] ）。到目前为止还没有包含的是回溯：在查询 duplicate(X, Y) 的情况下，你的目标匹配多个头并且你得到不止一个解决方案（实际上是无限多个）。

玩的开心！

(1) 规则为真与其变量的命名方式无关。当我们有两个来自不同规则的同名变量 D 时，我们需要将其中一个规则中的 D 重命名为其他名称，比如 D1。

(2) 您可以通过输入统一作为查询来在提示中进行检查：

1 ?- [w] = [H|T].
H = w,
T = [].

(3) 原因是列表 [H|T] 至少有一个元素，而 [] 没有。您可以在提示中再次检查：

2 ?- [] = [H|T].
false.

Answer 2

duplicate(L, D) :- duplicate(L,[], D). % clause 0

duplicate([], Acc, D) :- reverse(Acc, D). % clause 1

duplicate([H|T], Acc, D) :- duplicate(T, [H, H|Acc], D). % clause 2

为了我的理解下面的快速手算如果我错了请纠正我并告诉我我是否正确因为我是序言新手。

duplicate[w,o,r,d], D) clause 0 --> duplicate ([w,o,r,d],[].D). clause 2 --> duplicate[w,o,r,d],Acc,D) --> clause 2 duplicate([o,r,d],[w,w],[],D),

我可以继续执行第 2 条以继续复制列表的头部，我可以这样做直到列表为空 []。然后我可以转到第 1 条。

然后我可以将我的列表放入累加器然后反转它以产生 [d,d,r,r,o,o,w,w]

下面是第1条的手算

clause 1 duplicate[w,w,o,o,r,r,d,d],D) ---> clause 1 reverse([w,w,o,o,r,r,d,d],D).

D = [d,d,r,r,o,o,w,w]

Answer 3

如果您允许计算机帮助您进行手算，有两种经典方法可以做到这一点：

1) 使用调试器：大多数Prolog调试器使用Byrd盒模型，这意味着它只显示你在解决证明过程中选择的目标。这是针对更简单程序的更小查询的运行。通常可以通过 trace:

打开调试器

?- [user].
duplicate([], []).
duplicate([X|Y], [X,X|Z]) :- duplicate(Y,Z).
^D
Yes
?- duplicate([w,o],X).
X = [w,w,o,o]
?- trace.
Yes 
?- duplicate([w,o],X).
    0 Call duplicate([w,o], X) ?
    1 Call duplicate([o], _C) ?
    2 Call duplicate([], _F) ?
    2 Exit duplicate([], []) ?
    1 Exit duplicate([o], [o,o]) ?
    0 Exit duplicate([w,o], [w,w,o,o]) ?
X = [w,w,o,o] ;
    0 Redo duplicate([w,o], [w,w,o,o]) ?
    1 Redo duplicate([o], [o,o]) ?
    2 Redo duplicate([], []) ?
    2 Fail duplicate([], _F) ?
    1 Fail duplicate([o], _C) ?
    0 Fail duplicate([w,o], X) ?
No

2) 编写元解释器：您可以编写提供跟踪的元解释器，可以在运行之后进行检查，并给出 Prolog 系统找到的证明证书：

这是普通的普通解释器：

solve(true) :- !.
solve((A,B)) :- !, solve(A), solve(B).
solve(A) :- rule(A,B), solve(B).

这是一个解释器，它给出了应用程序的踪迹子句，它在 DCG 中实现：

solve(true) --> [].
solve((A,B)) --> !, solve(A), solve(B).
solve(A) --> {rule(A,B)}, [(A :- B)], solve(B).

这里是一个示例运行，用于简化重复查询和再次编程：

rule(duplicate([], []), true).
rule(duplicate([X|Y], [X,X|Z]), duplicate(Y,Z)).

?- solve(duplicate([w,o],X),L,[]).
X = [w,w,o,o],
L = [(duplicate([w,o],[w,w,o,o]) :- duplicate([o],[o,o])),
     (duplicate([o],[o,o]) :- duplicate([],[])),
     (duplicate([],[]) :- true)]

再见

PROLOG【手算】

PROLOG [hand computation]

prolog