由于 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),假。
所以虽然这个片段仍然坚持第一个论点是[_|_]
它没有考虑剩余的术语。因此,目标不会终止。
如果您想了解更多信息,请查看failure-slice。同样,考虑使用 cTI。为了培养良好的直觉,您需要自己尝试一下。