难以理解重做和绑定

Question

我现在正在学习 Prolog，但无法理解 Prolog 如何使用这些谓词访问给定列表中的第 n 个元素。

elementAt([Element|_], 0, Element).
elementAt([_|Tail], N, Element) :-
    elementAt(Tail, N1, Element),
    N is N1 + 1.

我使用 swi-prologs trace 命令来理解下面的表达式是如何求解的。

elementAt([0,1,2,3,4,5,6,7], 5, E).

我理解部分轨迹但不是全部，所以我复制了带有行号的轨迹以便于参考。我的问题在跟踪输出下面。

1   Call: (8) elementAt([0, 1, 2, 3, 4, 5, 6, 7], 5, _6554) ? creep
2   Call: (9) elementAt([1, 2, 3, 4, 5, 6, 7], _6836, _6554) ? creep
3   Exit: (9) elementAt([1, 2, 3, 4, 5, 6, 7], 0, 1) ? creep
4   Call: (9) 5 is 0+1 ? creep
5   Fail: (9) 5 is 0+1 ? creep
6   Redo: (9) elementAt([1, 2, 3, 4, 5, 6, 7], _6836, _6554) ? creep
7   Call: (10) elementAt([2, 3, 4, 5, 6, 7], _6836, _6554) ? creep
8   Exit: (10) elementAt([2, 3, 4, 5, 6, 7], 0, 2) ? creep
9   Call: (10) _6840 is 0+1 ? creep
10  Exit: (10) 1 is 0+1 ? creep
11  Exit: (9) elementAt([1, 2, 3, 4, 5, 6, 7], 1, 2) ? creep
12  Call: (9) 5 is 1+1 ? creep
13  Fail: (9) 5 is 1+1 ? creep
14  Redo: (10) elementAt([2, 3, 4, 5, 6, 7], _6836, _6554) ? creep
15  Call: (11) elementAt([3, 4, 5, 6, 7], _6836, _6554) ? creep
16  Exit: (11) elementAt([3, 4, 5, 6, 7], 0, 3) ? creep
17  Call: (11) _6840 is 0+1 ? creep
18  Exit: (11) 1 is 0+1 ? creep
19  Exit: (10) elementAt([2, 3, 4, 5, 6, 7], 1, 3) ? creep
20  Call: (10) _6846 is 1+1 ? creep
21  Exit: (10) 2 is 1+1 ? creep
22  Exit: (9) elementAt([1, 2, 3, 4, 5, 6, 7], 2, 3) ? creep
23  Call: (9) 5 is 2+1 ? creep
24  Fail: (9) 5 is 2+1 ? creep
25  Redo: (11) elementAt([3, 4, 5, 6, 7], _6836, _6554) ? creep
26  Call: (12) elementAt([4, 5, 6, 7], _6836, _6554) ? creep
27  Exit: (12) elementAt([4, 5, 6, 7], 0, 4) ? creep
28  Call: (12) _6840 is 0+1 ? creep
29  Exit: (12) 1 is 0+1 ? creep
30  Exit: (11) elementAt([3, 4, 5, 6, 7], 1, 4) ? creep
31  Call: (11) _6846 is 1+1 ? creep
32  Exit: (11) 2 is 1+1 ? creep
33  Exit: (10) elementAt([2, 3, 4, 5, 6, 7], 2, 4) ? creep
34  Call: (10) _6852 is 2+1 ? creep
35  Exit: (10) 3 is 2+1 ? creep
36  Exit: (9) elementAt([1, 2, 3, 4, 5, 6, 7], 3, 4) ? creep
37  Call: (9) 5 is 3+1 ? creep
38  Fail: (9) 5 is 3+1 ? creep
39  Redo: (12) elementAt([4, 5, 6, 7], _6836, _6554) ? creep
40  Call: (13) elementAt([5, 6, 7], _6836, _6554) ? creep
41  Exit: (13) elementAt([5, 6, 7], 0, 5) ? creep
42  Call: (13) _6840 is 0+1 ? creep
43  Exit: (13) 1 is 0+1 ? creep
44  Exit: (12) elementAt([4, 5, 6, 7], 1, 5) ? creep
45  Call: (12) _6846 is 1+1 ? creep
46  Exit: (12) 2 is 1+1 ? creep
47  Exit: (11) elementAt([3, 4, 5, 6, 7], 2, 5) ? creep
48  Call: (11) _6852 is 2+1 ? creep
49  Exit: (11) 3 is 2+1 ? creep
50  Exit: (10) elementAt([2, 3, 4, 5, 6, 7], 3, 5) ? creep
51  Call: (10) _6858 is 3+1 ? creep
52  Exit: (10) 4 is 3+1 ? creep
53  Exit: (9) elementAt([1, 2, 3, 4, 5, 6, 7], 4, 5) ? creep
54  Call: (9) 5 is 4+1 ? creep
55  Exit: (9) 5 is 4+1 ? creep
56  Exit: (8) elementAt([0, 1, 2, 3, 4, 5, 6, 7], 5, 5) ? creep

第 1 到 5 行非常清楚。将 _6836 绑定到 0 的第一条规则匹配。N is N1 + 1 约束失败并尝试 elementAt([_|Tail], N, Element) 谓词。这也就意味着_6836不再绑定0了吧？

第7行我没看懂。 Prolog 尝试重做

elementAt([1, 2, 3, 4, 5, 6, 7], _6836, _6554)

调用导致第 8 行中的调用

elementAt([2, 3, 4, 5, 6, 7], _6836, _6554).

我注意到在第 7 行中应该是 N 的 _6836 在第 8 行中也被用作 N1。为什么 Prolog 会那样做？

这是两个完全不同的变量。在第 14-15、25-26 和 39-40 行重复相同的模式。最终它得到了正确的元素，但我真的不明白如何。

我想我不太明白重做是如何工作的，但我没有想法。

Answer 1

Is the N1 (_6836) in trace line 6 the same variable as the N1(_6836) in trace line 7?

是的，是同一个变量。如果您查看 trace，您会在

处看到

6  Redo: (9) elementAt([1, 2, 3, 4, 5, 6, 7], _6044, _5790) ? creep

是源代码行

elementAt(Tail, N1, Element)

所以 _6836 是 N1

然后

7  Call: (10) elementAt([2, 3, 4, 5, 6, 7], _6044, _5790) ? creep

是源代码行

elementAt([_|Tail], N, Element)

注意深度从 (9) 更改为 (10)

所以 _6836 是 N

因此N1和N是统一的，但尚未绑定。我不知道这样说是否正确，但我相信如果不正确我会得到纠正。

就我个人而言，我不太使用跟踪，我更喜欢在需要时使用这些或 gtrace。

难以理解重做和绑定

Trouble understanding redos and bindings

prolog

swi-prolog