跟踪时，Prolog中的重做是什么? [英] 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) ? 

这是怎么回事?另外，该行左边的2 2是什么?

What's happening here? Also, what is 2 2 in the left of the line?

其余跟踪:

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

这是怎么回事?

这是您的跟踪输出；我添加了一个标识符和行号以准确识别 Trace 行.

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

这是您的源代码；我添加了一个标识符和行号，以准确识别 Fact 和 Predicate 行.

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

说明

要了解下面对 length/2 的调用，请与其他 answer 一起查看长注释.

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.

尽管该示例是一个非常简单的示例，但对于刚接触Prolog的学生来说，使用 length/2 确实使它更难理解.

While the example is a very simple example, for student new to Prolog the use of length/2 does make it harder to understand.

这篇关于跟踪时，Prolog中的重做是什么?的文章就介绍到这了，希望我们推荐的答案对大家有所帮助，也希望大家多多支持IT屋！