Prolog在实施反向列表时不会停止

Question

这是我的实现：

popped_last_el([], [_]).
popped_last_el([F | R], [F | X]) :- popped_last_el(R, X).

last_el(X, [X]).
last_el(X, [_ | L]) :- last_el(X, L).

reverse_list([], []).
reverse_list([F | R], L2) :- last_el(F, L2), popped_last_el(L, L2), reverse_list(R, L).

当我查询 reverse_list([a, b], X) 时，它按预期输出 X = [b, a]。但是当我使用 ; 寻求另一个解决方案时，prolog 会无限期地运行。为什么？

Answer 1

Why?

这里有一个failure-slice来解释为什么程序还是循环。您的程序中只有这个非常小的部分 对 non-termination 负责。您必须在该部分修复 某些内容 才能使 non-termination 消失。

last_el(X, [X]) :- false.
last_el(X, [_ | L]) :- last_el(X, L), false.

reverse_list([], []) :- false.
reverse_list([F | R], L2) :-
   last_el(F, L2), false,
   popped_last_el(L, L2),
   reverse_list(R, L).

?- reverse_list([a, b], X), false.
   loops.

从这里你可以看出failure-slice：

L2 需要知道 ('instantiated') 才能使 last_el/2 终止。但事实并非如此。

Prolog在实施反向列表时不会停止

Prolog not halting when implementing reverse list

prolog

failure-slice