Что такое повтор в Прологе, когда вы отслеживаете? - PullRequest
Новая
       29

Что такое повтор в Прологе, когда вы отслеживаете?

0 голосов
/ 08 ноября 2018

У меня есть этот код (итеративное углубление, чтобы найти кратчайший путь): 

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

И когда я прослеживаю это, в одном из следов это дает мне: 

    2    2  Redo: length([],0) ?

Что здесь происходит? Кроме того, что 2 2 слева от линии?

Остальная часть трассировки: 

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

Ответы [ 2 ]

0 голосов
/ 09 ноября 2018

Это не комментарий, это ответ. 

Redo: length([],0) ?

Что здесь происходит?

Вот ваш вывод трассировки; Я добавил идентификатор и номер строки, чтобы точно идентифицировать Trace строк. 

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 строки. 

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 ниже, см. Длинный комментарий как другой ответ . 

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`

Я рассмотрел несколько шагов за пределами повтора, чтобы вы могли привести еще несколько примеров, чтобы вы могли закончить это самостоятельно, если захотите.

Хотя пример очень простой, для новичка в Прологе использование length/2 усложняет понимание.

0 голосов
/ 09 ноября 2018

Это комментарий в ответе, потому что он не вписывается в комментарий.

Использование length(Path,_) в этой программе предназначено для создания списка разной длины.

Если вы выполните запрос length(X,N) в SWI-Prolog, вы получите. 

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

Обратите внимание, как возвращается список увеличивающейся длины. Если вы хотите получить результаты в виде списка и не знаете длины списка или хотите возвращать списки разной длины, то это часто используется для этого.

Потратьте несколько часов и посмотрите на другой код в примерах Пролога на StackOverflow или других местах, и вы заметите использование length / 2 теперь, когда вы это знаете.

...