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.
Here is your trace output; I added an identifier and line number to accurately identify
Trace
lines.And here is your source code; I added an identifier and line number to accurately identify
Fact
andPredicate
lines.Explanation
To understand the calls to
length/2
below, see long comment as other answer.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.This is a comment in an answer because it doesn't fit in a comment.
The use of
length(Path,_)
in this program is for the use of generating list of different lengths.If you run the query
length(X,N)
in SWI-Prolog you get.Notice how a list of increasing length is returned. When you want to generate results that are list and you don't know the length of the list or want to return lists of different lengths then this often used trick does that.
Take a few hours and look at other code in Prolog examples on StackOverflow or other places and you notice the use of length/2 now that you are aware of it.