是一个无限的清单？

Question

在Prolog中,统一X = [1|X]是一种获得无限列表的理智方式吗？SWI-Prolog没有任何问题,但GNU Prolog只是挂起.

我知道在大多数情况下我可以替换列表

one(1).
one(X) :- one(X).

但我的问题是明确是否可以X = [1|X], member(Y, X), Y = 1在"理智"的Prolog实现中使用该表达式.

Answer 1

在 Prolog 中，统一X = [1|X]是获取无限列表的明智方法吗？

这取决于您是否认为生成无限列表是明智的。在 ISO-Prolog 中，类似的统一X = [1|X]会受到发生检查 (STO) 的影响，因此是未定义的。也就是说，符合标准的程序不得执行这样的目标。为了避免这种情况发生，有unify_with_occurs_check/2, subsumes_term/2。为了防止接口接收无限项，有acyclic_term/1.

所有当前的实现都终止于X = [1|X]。GNU Prolog 也终止：

| ?- X = [1|X], acyclic_term(X).

no

但是对于更复杂的情况，需要合理的树统一。将此与repeat 1 == repeat 1导致ghci冻结的Haskell 进行比较 。

至于在常规 Prolog 程序中使用有理树，这在开始时很有趣，但并没有很好地扩展。例如，在 20 世纪 80 年代初期，人们相信语法将使用有理树来实现。唉，人们对 DCG 已经足够满意了。这不离开研究的一个原因是，因为 Prolog 程序员假设存在的许多概念对于有理树来说并不存在。以字典术语排序为例，它没有对有理树进行扩展。也就是说，存在无法使用标准术语顺序进行比较的有理树。（实际上，这意味着您会获得准随机结果。）这意味着您无法生成包含此类术语的排序列表。这再次意味着许多内置程序喜欢bagof/3 不再以无限项可靠地工作。

对于示例查询，请考虑以下定义：

memberd(X, [X|_Xs]).
memberd(E, [X|Xs]) :-
   dif(E,X),
   memberd(E, Xs).

?- X = 1, Xs=[1|Xs], memberd(X,Xs).
X = 1,
Xs = [1|Xs] ;
false.

所以有时有一些简单的方法可以避免非终止。但通常情况下没有。