What is redo in Prolog when you trace?











up vote
2
down vote

favorite












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









share|improve this question




















  • 2




    "Redo" means Prolog is backtracking.
    – lurker
    Nov 8 at 20:08












  • A better keyword to search on instead of redo is choice-point
    – Guy Coder
    Nov 8 at 20:17










  • You gave us the predicates, but what was the query you started?
    – Guy Coder
    Nov 8 at 20:19










  • If you can read OCaml then this shows how it works in OCaml.
    – Guy Coder
    Nov 8 at 20:26










  • @GuyCoder query is : path(a, g, P).
    – sosscs
    Nov 9 at 5:29

















up vote
2
down vote

favorite












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









share|improve this question




















  • 2




    "Redo" means Prolog is backtracking.
    – lurker
    Nov 8 at 20:08












  • A better keyword to search on instead of redo is choice-point
    – Guy Coder
    Nov 8 at 20:17










  • You gave us the predicates, but what was the query you started?
    – Guy Coder
    Nov 8 at 20:19










  • If you can read OCaml then this shows how it works in OCaml.
    – Guy Coder
    Nov 8 at 20:26










  • @GuyCoder query is : path(a, g, P).
    – sosscs
    Nov 9 at 5:29















up vote
2
down vote

favorite









up vote
2
down vote

favorite











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









share|improve this question















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






debugging prolog tracing






share|improve this question















share|improve this question













share|improve this question




share|improve this question








edited Nov 9 at 5:30

























asked Nov 8 at 18:37









sosscs

696




696








  • 2




    "Redo" means Prolog is backtracking.
    – lurker
    Nov 8 at 20:08












  • A better keyword to search on instead of redo is choice-point
    – Guy Coder
    Nov 8 at 20:17










  • You gave us the predicates, but what was the query you started?
    – Guy Coder
    Nov 8 at 20:19










  • If you can read OCaml then this shows how it works in OCaml.
    – Guy Coder
    Nov 8 at 20:26










  • @GuyCoder query is : path(a, g, P).
    – sosscs
    Nov 9 at 5:29
















  • 2




    "Redo" means Prolog is backtracking.
    – lurker
    Nov 8 at 20:08












  • A better keyword to search on instead of redo is choice-point
    – Guy Coder
    Nov 8 at 20:17










  • You gave us the predicates, but what was the query you started?
    – Guy Coder
    Nov 8 at 20:19










  • If you can read OCaml then this shows how it works in OCaml.
    – Guy Coder
    Nov 8 at 20:26










  • @GuyCoder query is : path(a, g, P).
    – sosscs
    Nov 9 at 5:29










2




2




"Redo" means Prolog is backtracking.
– lurker
Nov 8 at 20:08






"Redo" means Prolog is backtracking.
– lurker
Nov 8 at 20:08














A better keyword to search on instead of redo is choice-point
– Guy Coder
Nov 8 at 20:17




A better keyword to search on instead of redo is choice-point
– Guy Coder
Nov 8 at 20:17












You gave us the predicates, but what was the query you started?
– Guy Coder
Nov 8 at 20:19




You gave us the predicates, but what was the query you started?
– Guy Coder
Nov 8 at 20:19












If you can read OCaml then this shows how it works in OCaml.
– Guy Coder
Nov 8 at 20:26




If you can read OCaml then this shows how it works in OCaml.
– Guy Coder
Nov 8 at 20:26












@GuyCoder query is : path(a, g, P).
– sosscs
Nov 9 at 5:29






@GuyCoder query is : path(a, g, P).
– sosscs
Nov 9 at 5:29














2 Answers
2






active

oldest

votes

















up vote
1
down vote



accepted










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.






share|improve this answer






























    up vote
    1
    down vote













    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.






    share|improve this answer





















      Your Answer






      StackExchange.ifUsing("editor", function () {
      StackExchange.using("externalEditor", function () {
      StackExchange.using("snippets", function () {
      StackExchange.snippets.init();
      });
      });
      }, "code-snippets");

      StackExchange.ready(function() {
      var channelOptions = {
      tags: "".split(" "),
      id: "1"
      };
      initTagRenderer("".split(" "), "".split(" "), channelOptions);

      StackExchange.using("externalEditor", function() {
      // Have to fire editor after snippets, if snippets enabled
      if (StackExchange.settings.snippets.snippetsEnabled) {
      StackExchange.using("snippets", function() {
      createEditor();
      });
      }
      else {
      createEditor();
      }
      });

      function createEditor() {
      StackExchange.prepareEditor({
      heartbeatType: 'answer',
      convertImagesToLinks: true,
      noModals: true,
      showLowRepImageUploadWarning: true,
      reputationToPostImages: 10,
      bindNavPrevention: true,
      postfix: "",
      imageUploader: {
      brandingHtml: "Powered by u003ca class="icon-imgur-white" href="https://imgur.com/"u003eu003c/au003e",
      contentPolicyHtml: "User contributions licensed under u003ca href="https://creativecommons.org/licenses/by-sa/3.0/"u003ecc by-sa 3.0 with attribution requiredu003c/au003e u003ca href="https://stackoverflow.com/legal/content-policy"u003e(content policy)u003c/au003e",
      allowUrls: true
      },
      onDemand: true,
      discardSelector: ".discard-answer"
      ,immediatelyShowMarkdownHelp:true
      });


      }
      });














      draft saved

      draft discarded


















      StackExchange.ready(
      function () {
      StackExchange.openid.initPostLogin('.new-post-login', 'https%3a%2f%2fstackoverflow.com%2fquestions%2f53214129%2fwhat-is-redo-in-prolog-when-you-trace%23new-answer', 'question_page');
      }
      );

      Post as a guest















      Required, but never shown

























      2 Answers
      2






      active

      oldest

      votes








      2 Answers
      2






      active

      oldest

      votes









      active

      oldest

      votes






      active

      oldest

      votes








      up vote
      1
      down vote



      accepted










      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.






      share|improve this answer



























        up vote
        1
        down vote



        accepted










        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.






        share|improve this answer

























          up vote
          1
          down vote



          accepted







          up vote
          1
          down vote



          accepted






          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.






          share|improve this answer














          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.







          share|improve this answer














          share|improve this answer



          share|improve this answer








          edited Nov 9 at 15:22

























          answered Nov 9 at 14:48









          Guy Coder

          14.5k43781




          14.5k43781
























              up vote
              1
              down vote













              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.






              share|improve this answer

























                up vote
                1
                down vote













                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.






                share|improve this answer























                  up vote
                  1
                  down vote










                  up vote
                  1
                  down vote









                  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.






                  share|improve this answer












                  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.







                  share|improve this answer












                  share|improve this answer



                  share|improve this answer










                  answered Nov 9 at 13:02









                  Guy Coder

                  14.5k43781




                  14.5k43781






























                      draft saved

                      draft discarded




















































                      Thanks for contributing an answer to Stack Overflow!


                      • Please be sure to answer the question. Provide details and share your research!

                      But avoid



                      • Asking for help, clarification, or responding to other answers.

                      • Making statements based on opinion; back them up with references or personal experience.


                      To learn more, see our tips on writing great answers.





                      Some of your past answers have not been well-received, and you're in danger of being blocked from answering.


                      Please pay close attention to the following guidance:


                      • Please be sure to answer the question. Provide details and share your research!

                      But avoid



                      • Asking for help, clarification, or responding to other answers.

                      • Making statements based on opinion; back them up with references or personal experience.


                      To learn more, see our tips on writing great answers.




                      draft saved


                      draft discarded














                      StackExchange.ready(
                      function () {
                      StackExchange.openid.initPostLogin('.new-post-login', 'https%3a%2f%2fstackoverflow.com%2fquestions%2f53214129%2fwhat-is-redo-in-prolog-when-you-trace%23new-answer', 'question_page');
                      }
                      );

                      Post as a guest















                      Required, but never shown





















































                      Required, but never shown














                      Required, but never shown












                      Required, but never shown







                      Required, but never shown

































                      Required, but never shown














                      Required, but never shown












                      Required, but never shown







                      Required, but never shown







                      這個網誌中的熱門文章

                      Xamarin.form Move up view when keyboard appear

                      Post-Redirect-Get with Spring WebFlux and Thymeleaf

                      Anylogic : not able to use stopDelay()