I have this code(iterative deepening to find shortest path) :
arc(a, g).
arc(a, b).
arc(b, g).
path(X, Z, Path) :-
length(Path, _),
path_r(X, Z, Path).
path_r(Z, Z, []).
path_r(X, Z, [X|Path]) :-
arc(X, Y),
path(Y, Z, Path).
And when I trace it, in one of the traces it gives me :
2 2 Redo: length([],0) ?
What's happening here? Also, what is 2 2 in the left of the line?
The rest of the tracing:
1 1 Call: path(a,g,_23) ?
2 2 Call: length(_23,_55) ?
2 2 Exit: length([],0) ?
3 2 Call: path_r(a,g,[]) ?
3 2 Fail: path_r(a,g,[]) ?
2 2 Redo: length([],0) ?
2 2 Exit: length([_80],1) ?
3 2 Call: path_r(a,g,[_80]) ?
4 3 Call: arc(a,_146) ?
4 3 Exit: arc(a,g) ?
5 3 Call: path(g,g,[]) ?
6 4 Call: length([],_158) ?
6 4 Exit: length([],0) ?
7 4 Call: path_r(g,g,[]) ?
7 4 Exit: path_r(g,g,[]) ?
5 3 Exit: path(g,g,[]) ?
3 2 Exit: path_r(a,g,[a]) ?
1 1 Exit: path(a,g,[a]) ?
This is not a comment, it is an answer.
Redo: length([],0) ?
What's happening here?
Here is your trace output; I added an identifier and line number to accurately identify Trace lines.
Trace 1 1 1 Call: path(a,g,_23) ?
Trace 2 2 2 Call: length(_23,_55) ?
Trace 3 2 2 Exit: length([],0) ?
Trace 4 3 2 Call: path_r(a,g,[]) ?
Trace 5 3 2 Fail: path_r(a,g,[]) ?
Trace 6 2 2 Redo: length([],0) ?
Trace 7 2 2 Exit: length([_80],1) ?
Trace 8 3 2 Call: path_r(a,g,[_80]) ?
Trace 9 4 3 Call: arc(a,_146) ?
Trace 10 4 3 Exit: arc(a,g) ?
Trace 11 5 3 Call: path(g,g,[]) ?
Trace 12 6 4 Call: length([],_158) ?
Trace 13 6 4 Exit: length([],0) ?
Trace 14 7 4 Call: path_r(g,g,[]) ?
Trace 15 7 4 Exit: path_r(g,g,[]) ?
Trace 16 5 3 Exit: path(g,g,[]) ?
Trace 17 3 2 Exit: path_r(a,g,[a]) ?
Trace 18 1 1 Exit: path(a,g,[a]) ?
And here is your source code; I added an identifier and line number to accurately identify Fact and Predicate lines.
Fact 1 arc(a, g).
Fact 2 arc(a, b).
Fact 3 arc(b, g).
Predicate 1,1 path(X, Z, Path) :-
Predicate 1,2 length(Path, _),
Predicate 1,3 path_r(X, Z, Path).
Predicate 2,1 path_r(Z, Z, []).
Predicate 3,1 path_r(X, Z, [X|Path]) :-
Predicate 3,2 arc(X, Y),
Predicate 3,3 path(Y, Z, Path).
To understand the calls to length/2 below, see long comment as other answer.
Trace 1 is your initial query `path(a,g,X)`
Prolog unifies this with Predicate 1,1 `path(X, Z, Path)`
Prolog unifies `a` with `X`, `g` with `Z`, and `X` with `Path`
Trace 2 is Predicate 1,2 `length(Path,_)`
Prolog unifies `_23` with `Path` and `_` with `_55`
Prolog then calls `length/2` and upon return
`Path` is unified with `[]` and `_` is unified with `0`
Trace 3 `length(_23,_55)` is unified to `length([],0)`
Trace 4 is Predicate 1,3 `path_r(X, Z, Path).
Prolog unifies `a` with `X`, `g` with `Z`, and `Path` with `[]`
Prolog calls Predicate 2,1
Trace 5 is Predicate 2,1 `path_r(Z, Z, [])`
Prolog unifies `a` with `Z`
Prolog can not unify `g` with `Z` because `Z` is `a` and fails.
Trace 6 is Predicate 1,2 `length(Path,_)`
Prolog knows `length([],0)` failed
Prolog redoes (REDO) the call to `length/2`
Trace 7 is Predicate 1,2 `length(Path,_)`
`Path` is unified with `[_80]` and `_` is unified with `1`
Trace 8 is Predicate 1,3 `path_r(X, Z, Path)`
Prolog unifies `a` with `X`, `g` with `Z`, and `Path` with `[_80]`
Prolog calls Predicate 3,1 it can not call Predicate 2,1 because `Path` which is `[_80]` can not unify with `[]`.
Trace 9 is Predicate 3,2 `arc(X,Y)`
Prolog unifies 'a` with `X` and `_146` with `Y`
Prolog calls Fact 1
Trace 10 is Fact 1 `arc(a, g).`
Prolog unifies `a` with `a` and `g` with `Y`
I covered a few steps beyond the redo so that you would a few more example lines so that you can finish this on your own if you choose.
While the example is a very simple example, for student new to Prolog the use of length/2 does make it harder to understand.