4

我的老师为我们提供了一些关于 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(..,[]).

这与我迄今为止所学到的有点背道而驰。我认为这两个论点都影响了程序的终止条件,显然他们没有按照我老师的例子。谁能给我一些意见?

4

1 回答 1

4

由于 Prolog 相对复杂的控制流程,Prolog 程序的终止属性有点难以掌握。有一些方法可以降低复杂性。一是通过在程序中插入额外的目标来仅考虑false程序的一部分。你可以把它们放在任何地方。并且无论您将它们放在哪里,以下内容都成立:如果这个称为故障切片的新程序没有终止,那么您的原始程序也不会终止。注意“如果”。这是你的程序:

反向([],[]):-。
反向([X|Xs],Zs):-
   反向(Xs,Ys),追加(Ys,[X],Zs)

此故障片对于理解您的关系描述的内容完全没有。它永远不会成功。但是,它有助于我们更好地理解终止将如何进行。

请注意,该事实已完全消除。事实上,无论事实如何,它都不能改善这个故障片的终止reverse/2。(不过,它可能会恶化终止)。

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

reverse/2终止,必须实例化第一个参数,以便该片段将终止。因此[][X|[]]将终止,甚至[X|nonlist]将终止。但是诸如, etc 之类的部分列表不会终止。Xs[a|Xs]

如果您想改进终止,例如,reverse(Xs,[])您需要更改可见的剩余部分中的某些内容。一种方法是交换目标。现在,Zs可能有助于终止。但是——唉——第一个论点现在不再像以前那样有影响力了。考虑reverse([a], Zs)并:

反向([],[]):-。
反向([X|Xs],Zs):-
   追加(Ys,[X],Zs),反向(Xs,Ys)附加([],Zs,Zs):-。
附加([X|Xs],Ys,[X|Zs]):-
   追加(Xs,Ys,Zs),

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

如果您想了解更多信息,请查看。同样,考虑使用 cTI。为了培养良好的直觉,您需要自己尝试一下。

于 2015-01-14T13:48:50.257 回答