终止条件序言

Question

我的老师给我们提供了一些关于 Prolog 的幻灯片，我发现有些奇怪。

reverse([],[]).
reverse([X|Xs],Zs) :- reverse(Xs,Ys), append(Ys, [X], Zs).

据他说，当第一个参数 reverse([],..) 是一个完整列表时程序终止。此外，如果将谓词中的目标切换为 reverse([X|Xs],Zs) :- append(Ys, [X], Zs), reverse(Xs,Ys).，则当第二个参数是完整列表 reverse(..,[]).

时程序应该终止

这与我目前所学的有所不同。我认为这两个论点都影响了程序的终止条件，显然根据我老师的例子，它们并没有。谁能给我一些意见？

Answer 1

Prolog程序的终止属性由于Prolog相对复杂的控制流程，有点难以掌握。有一些方法可以降低复杂性。一是通过在程序中插入额外的目标 false 来仅考虑程序的一部分。您可以将它们放在任何地方。并且无论您将它们放置在何处，以下内容都成立：如果这个名为 failure-slice 的新程序没有终止，那么您的原始程序也不会终止。注意 "if"。这是您的程序：

reverse([],[]) :- false.
reverse([X|Xs],Zs) :-
   reverse(Xs,Ys), false,
   append(Ys, [X], Zs).

这个失败片段对于理解什么你的关系描述是完全没用的。它永远不会成功。但是，它可以帮助我们更好地理解终止的方式。

请注意，事实已完全消除。事实上，无论事实看起来如何，它都无法改善 reverse/2 的这个失败片段的终止。（虽然它可能会恶化终止）。

还要注意第二个参数，Zs：没有进一步提及这个 Zs。因此： reverse/2 的第二个参数可以是任何它想要的。它也不会改善终止。

要使 reverse/2 终止，必须实例化第一个参数，以便该片段终止。因此[]、[X|[]]会终止，甚至[X|nonlist]也会终止。但是 部分列表 例如 Xs、[a|Xs] 等将不会终止。

如果你想改进 reverse(Xs,[]) 的终止，你需要改变可见的剩余部分。一种方法是交换目标。现在，Zs 可能有助于终止。但是——唉——第一个论点现在不再像以前那样具有影响力了。考虑 reverse([a], Zs) 和：

reverse([],[]) :- false.
reverse([X|Xs],Zs) :-
   append(Ys, [X], Zs), false,
   reverse(Xs,Ys).

append([], Zs, Zs) :- false.
append([X|Xs], Ys, [X|Zs]) :-
   append(Xs, Ys, Zs), false.

所以虽然这个片段仍然坚持第一个参数是 [_|_]，但它没有考虑剩余的术语。因此，目标不会终止。

如果您想了解更多信息，请查看 failure-slice. Equally, consider using cTI。要培养良好的直觉，您需要亲自尝试一下。

终止条件序言

Termination condition prolog

termination

prolog

failure-slice