避免无限递归但仍仅使用未绑定参数传递
Avoiding infinite recursion but still using unbound parameter passing only
我有以下工作程序：（可以在这个网站上测试：http://swish.swi-prolog.org，我已经删除了直接 link 到一个保存的程序，因为我注意到任何人都可以编辑它。）
它在无向图中搜索两点之间的路径。重要的部分是结果在 "main" 谓词的范围内返回。 （在跟踪变量中）
edge(a, b).
edge(b, c).
edge(d, b).
edge(d, e).
edge(v, w).
connected(Y, X) :-
(
edge(X, Y);
edge(Y, X)
).
path(X, X, _, []) :-
connected(X, _).
path(X, Y, _, [X, Y]) :-
connected(Y, X).
path(X, Z, Visited, [X|Track]) :-
connected(X, Y),
not(member(X, Visited)),
path(Y, Z, [X|Visited], Track).
main(X, Y) :-
path(X, Y, [], Track),
print(Track),
!.
结果：
?- main(a, e).
[a, b, d, e]
true
?- main(c, c).
[]
true
?- main(b, w).
false
我的问题：
访问过的节点列表以两种不同的方式传递给谓词。在绑定的 Visited 变量和未绑定的 Track 变量中。这两种不同形式的参数传递的名称是什么？
通常我只想使用未绑定参数传递（Track 变量），让结果在主谓词的范围内。但是我也必须添加 Visited 变量，因为成员检查对 Track 变量不起作用（我不知道为什么）。是否可以仅以未绑定的方式通过 Track 使其工作？ （没有 Visited 变量）
非常感谢！
简短的回答：不，你不能避免额外的争论而不让一切变得更加混乱。这是因为这种用于寻找路径的特定算法需要保持状态；基本上，你的额外参数是你的状态。
可能还有其他方法来保持状态，例如使用全局可变变量或动态更改 Prolog 数据库，但这两种方法都更难正确使用，并且会涉及更多代码。
这个额外的参数通常被称为 累加器 ，因为它会在您向下 proof tree 时累积一些东西。最简单的例子是遍历一个列表：
foo([]).
foo([X|Xs]) :-
foo(Xs).
这很好，除非你需要知道在到达这里之前你已经看到了哪些元素：
bar(List) :-
bar_(List, []).
bar_([], _).
bar_([X|Xs], Acc) :-
/* Acc is a list of all elements so far */
bar_(Xs, [X|Acc]).
这与您在代码中所做的大致相同。如果你特别看一下这个：
path(X, Z, Visited, /* here */[X|Track]) :-
connected(X, Y),
not(member(X, Visited)),
path(Y, Z, [X|Visited], /* and here */Track).
path/4 的最后一个参数在证明树中 少一个 的 深度处多 一个元素 ！而且，当然，第三个参数更长（它随着证明树的向下而增长）。
例如，您可以通过向上面的愚蠢 bar 谓词添加另一个参数来反转列表：
list_reverse(L, R) :-
list_reverse_(L, [], R).
list_reverse_([], R, R).
list_reverse_([X|Xs], R0, R) :-
list_reverse_(Xs, [X|R0], R).
我不知道最后一个参数有什么特殊的名字，那个在开始时是自由的，在最后是解决方案。在某些情况下，它可能是一个 输出参数 ，因为它意味着在以某种方式转换输入之后捕获输出。在许多情况下，最好避免将参数视为严格的输入或输出参数。例如，length/2:
?- length([a,b], N).
N = 2.
?- length(L, 3).
L = [_2092, _2098, _2104].
?- length(L, N).
L = [],
N = 0 ;
L = [_2122],
N = 1 ;
L = [_2122, _2128],
N = 2 . % and so on
注意：您的代码中有很多不重要的小问题，在 Whosebug 上提供那么多建议并不是一个好主意。如果您愿意，可以将此作为问题提交到 Code Review。
编辑：你一定要学习this question。
我还提供了一个更简单的解决方案here。请注意在编译时使用 term_expansion/2 从无向边生成有向边。更重要的是：您不需要 main，只需从顶层调用您想要的谓词即可。当您放弃切割时，当您的 From 和 To 参数中的一个或两个是自由变量时，您将获得所有可能的解决方案。
我有以下工作程序：（可以在这个网站上测试：http://swish.swi-prolog.org，我已经删除了直接 link 到一个保存的程序，因为我注意到任何人都可以编辑它。）
它在无向图中搜索两点之间的路径。重要的部分是结果在 "main" 谓词的范围内返回。 （在跟踪变量中）
edge(a, b).
edge(b, c).
edge(d, b).
edge(d, e).
edge(v, w).
connected(Y, X) :-
(
edge(X, Y);
edge(Y, X)
).
path(X, X, _, []) :-
connected(X, _).
path(X, Y, _, [X, Y]) :-
connected(Y, X).
path(X, Z, Visited, [X|Track]) :-
connected(X, Y),
not(member(X, Visited)),
path(Y, Z, [X|Visited], Track).
main(X, Y) :-
path(X, Y, [], Track),
print(Track),
!.
结果：
?- main(a, e).
[a, b, d, e]
true
?- main(c, c).
[]
true
?- main(b, w).
false
我的问题：
访问过的节点列表以两种不同的方式传递给谓词。在绑定的 Visited 变量和未绑定的 Track 变量中。这两种不同形式的参数传递的名称是什么？
通常我只想使用未绑定参数传递（Track 变量），让结果在主谓词的范围内。但是我也必须添加 Visited 变量，因为成员检查对 Track 变量不起作用（我不知道为什么）。是否可以仅以未绑定的方式通过 Track 使其工作？ （没有 Visited 变量）
非常感谢！
简短的回答：不，你不能避免额外的争论而不让一切变得更加混乱。这是因为这种用于寻找路径的特定算法需要保持状态；基本上，你的额外参数是你的状态。
可能还有其他方法来保持状态，例如使用全局可变变量或动态更改 Prolog 数据库，但这两种方法都更难正确使用，并且会涉及更多代码。
这个额外的参数通常被称为 累加器 ，因为它会在您向下 proof tree 时累积一些东西。最简单的例子是遍历一个列表：
foo([]).
foo([X|Xs]) :-
foo(Xs).
这很好，除非你需要知道在到达这里之前你已经看到了哪些元素：
bar(List) :-
bar_(List, []).
bar_([], _).
bar_([X|Xs], Acc) :-
/* Acc is a list of all elements so far */
bar_(Xs, [X|Acc]).
这与您在代码中所做的大致相同。如果你特别看一下这个：
path(X, Z, Visited, /* here */[X|Track]) :-
connected(X, Y),
not(member(X, Visited)),
path(Y, Z, [X|Visited], /* and here */Track).
path/4 的最后一个参数在证明树中 少一个 的 深度处多 一个元素 ！而且，当然，第三个参数更长（它随着证明树的向下而增长）。
例如，您可以通过向上面的愚蠢 bar 谓词添加另一个参数来反转列表：
list_reverse(L, R) :-
list_reverse_(L, [], R).
list_reverse_([], R, R).
list_reverse_([X|Xs], R0, R) :-
list_reverse_(Xs, [X|R0], R).
我不知道最后一个参数有什么特殊的名字，那个在开始时是自由的，在最后是解决方案。在某些情况下，它可能是一个 输出参数 ，因为它意味着在以某种方式转换输入之后捕获输出。在许多情况下，最好避免将参数视为严格的输入或输出参数。例如，length/2:
?- length([a,b], N).
N = 2.
?- length(L, 3).
L = [_2092, _2098, _2104].
?- length(L, N).
L = [],
N = 0 ;
L = [_2122],
N = 1 ;
L = [_2122, _2128],
N = 2 . % and so on
注意：您的代码中有很多不重要的小问题，在 Whosebug 上提供那么多建议并不是一个好主意。如果您愿意，可以将此作为问题提交到 Code Review。
编辑：你一定要学习this question。
我还提供了一个更简单的解决方案here。请注意在编译时使用 term_expansion/2 从无向边生成有向边。更重要的是：您不需要 main，只需从顶层调用您想要的谓词即可。当您放弃切割时，当您的 From 和 To 参数中的一个或两个是自由变量时，您将获得所有可能的解决方案。