2

I'm learning Prolog right now and have trouble understanding how Prolog uses these predicates to access the n-th element in the given list.

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

I use swi-prologs trace command to understand how the following expression is solved.

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

I understand parts of the trace but not everything, so I copied the trace with line numbers for easier reference. My question is below the trace output.

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

Line 1 to 5 is perfectly clear. The first rule matches which binds _6836 to 0. The N is N1 + 1 constraint fails and tries the elementAt([_|Tail], N, Element) predicate. This also means that _6836 is no longer bound to 0, right?

Line 7 is what I don't understand. Prolog tries to redo the

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

call which results in the call that's made in line 8 which is

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

I noted that _6836 which should be N in line 7 get's also used as N1 in line 8. Why does Prolog do that?

These are two completely different variables. The same pattern repeats in line 14-15, 25-26 and 39-40. Eventually it gets the correct element but I really don't understand how.

I think I don't quite understand how the redo works but I'm out of ideas.

Guy Coder
  • 24,501
  • 8
  • 71
  • 136
Chris
  • 661
  • 2
  • 7
  • 23

1 Answers1

1

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

Yes, it is the same variable. If you look at the trace you will see that at 

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

is source line

elementAt(Tail, N1, Element)

so _6836 is N1

then 

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

is source line

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

Notice the depth changed from (9) to (10)

so _6836 is N

thus N1 and N are unified but not yet bound. I don't know if that is the correct way to say it, but I am sure I will be corrected if not.

Personally I don't use trace much, I prefer to use these debugging predicates or gtrace when needed.

Community
  • 1
  • 1
Guy Coder
  • 24,501
  • 8
  • 71
  • 136
  • I didn't know about gstrace, thanks for that. Maybe I wasn't so clear about my problem. I do understand that the redo makes prolog use the next predicate which is source line 2. What I don't understand (and what I wasn't able to figure out from your post) is in trace line 6 (using your line numbers). Is the `N1` (_6044) in trace line 6 the same variable as the `N1`(_6044) in trace line 7? It doesn't make sense for me why Prolog just assume that N1 and N can be the same. Where does it take that information from? It takes the `N` from an earlier level (11) and passes it as `N1` to the next level – Chris Mar 25 '17 at 14:54
  • Neither Redo nor Call are variables. Yet, they are highlighted as if. – false Apr 01 '17 at 05:59