2

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]) ?
false
  • 10,264
  • 13
  • 101
  • 209
John Sall
  • 1,027
  • 1
  • 12
  • 25
  • 3
    "Redo" means Prolog is [*backtracking*](https://www.doc.gold.ac.uk/~mas02gw/prolog_tutorial/prologpages/search.html). – lurker Nov 08 '18 at 20:08
  • A better keyword to search on instead of `redo` is [choice-point](https://en.wikipedia.org/wiki/Prolog#Execution) – Guy Coder Nov 08 '18 at 20:17
  • You gave us the predicates, but what was the query you started? – Guy Coder Nov 08 '18 at 20:19
  • If you can read OCaml then [this](https://github.com/andrejbauer/plzoo/blob/master/src/miniprolog/solve.ml) shows how it works in OCaml. – Guy Coder Nov 08 '18 at 20:26
  • @GuyCoder query is : path(a, g, P). – John Sall Nov 09 '18 at 05:29
  • @GuyCoder Why would there be a choice point at : length(Path, _) ? that was inside a predicate and I left that predicate and went to the other predicate path _r(X, Z [X|Path]). I will add the rest of the tracing. – John Sall Nov 09 '18 at 05:33
  • I take it that you copied the code from somewhere but that it doesn't really explain how the code works and you are confused. When I was learning Prolog seeing the use of `length(Path,_)` confused me at first then here they helped me understand it. – Guy Coder Nov 09 '18 at 12:50
  • Of interest: [When is the Redo-port called with new variables in Trace/0 and when not?](https://stackoverflow.com/q/45391973/1243762) – Guy Coder Nov 09 '18 at 13:12
  • The reason there is a choice-point for `length(Path,_)` is that there can be many choices made at that time. Since the variables `Path` and `_` are unbound at that time, there are choices. In this case what the code is trying to do is create a path of size length which is the second parameter of `length(Path,_)`. So there are choices here, e.g. `length(Path,0)`, `length(Path,1)`, `length(Path,2)`, and so on. – Guy Coder Nov 09 '18 at 13:24
  • In order to answer what the numbers on the left are we need to know what Prolog implementation you used, the app you used to run the debugger, and the way you configured and ran the trace. I don't see the numbers when I use SWI-Prolog. – Guy Coder Nov 09 '18 at 14:06
  • If answers are posted and you don't accept them then you should post a reply comment for the answer explaining why you are not accepting the answer. Also an up-vote and an and accept vote are two different votes. If people regularly answer your questions and you don't give them accept votes or feed back they tend to stop answering your questions or giving you help. – Guy Coder Nov 10 '18 at 13:30

2 Answers2

1

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.

Guy Coder
  • 24,501
  • 8
  • 71
  • 136
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.

Guy Coder
  • 24,501
  • 8
  • 71
  • 136