跟踪时 Prolog 中的重做是什么?
What is redo in Prolog when you trace?
我有这段代码(迭代加深寻找最短路径):
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]) ?
这是答案中的评论,因为它不适合评论。
本程序中length(Path,_)
的使用是为了生成不同长度的list。
如果你 运行 在 SWI-Prolog 中查询 length(X,N)
你会得到。
?- 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
注意如何return编辑长度递增的列表。当您想要生成列表结果并且您不知道列表的长度或想要 return 不同长度的列表时,这个常用的技巧就可以做到这一点。
花几个小时看看 Whosebug or other places and you notice the use of length/2 上 Prolog 示例中的其他代码,现在您已经知道了。
这不是评论,这是一个答案。
Redo: length([],0) ?
What's happening here?
这是您的跟踪输出;我添加了标识符和行号以准确识别 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`
我介绍了重做之外的几个步骤,以便您可以添加更多示例行,以便您可以根据需要自行完成此操作。
虽然该示例是一个非常简单的示例,但对于刚接触 Prolog 的学生来说,length/2
的使用确实使其更难理解。
我有这段代码(迭代加深寻找最短路径):
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]) ?
这是答案中的评论,因为它不适合评论。
本程序中length(Path,_)
的使用是为了生成不同长度的list。
如果你 运行 在 SWI-Prolog 中查询 length(X,N)
你会得到。
?- 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
注意如何return编辑长度递增的列表。当您想要生成列表结果并且您不知道列表的长度或想要 return 不同长度的列表时,这个常用的技巧就可以做到这一点。
花几个小时看看 Whosebug or other places and you notice the use of length/2 上 Prolog 示例中的其他代码,现在您已经知道了。
这不是评论,这是一个答案。
Redo: length([],0) ?
What's happening here?
这是您的跟踪输出;我添加了标识符和行号以准确识别 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`
我介绍了重做之外的几个步骤,以便您可以添加更多示例行,以便您可以根据需要自行完成此操作。
虽然该示例是一个非常简单的示例,但对于刚接触 Prolog 的学生来说,length/2
的使用确实使其更难理解。