What is redo in Prolog when you trace?

问题:

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]) ? 

回答1:

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).

Explanation

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.

回答2:

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.

?- length(List,N).
List = [],
N = 0 ;
List = [_774],
N = 1 ;
List = [_774, _780],
N = 2 ;
List = [_774, _780, _786],
N = 3 ;
List = [_774, _780, _786, _792],
N = 4 ;
List = [_774, _780, _786, _792, _798],
N = 5 

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.