是无数个健全的名单吗? [英] Is an infinite list of ones sane?

问题描述

在Prolog中，统一X = [1|X]是获取无限列表的明智方法吗? SWI-Prolog没问题，但是GNU Prolog只是挂起.

In Prolog, is the unification X = [1|X] a sane way to get an infinite list of ones? SWI-Prolog does not have any problem with it, but GNU Prolog simply hangs.

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

I know that in most cases I could replace the list with

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

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

but my question is explicitly if one may use the expression X = [1|X], member(Y, X), Y = 1 in a "sane" Prolog implementation.

推荐答案

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

In Prolog, is the unification X = [1|X] a sane way to get an infinite list of ones?

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

It depends on whether or not you consider it sane to produce an infinite list at all. In ISO-Prolog a unification like X = [1|X] is subject to occurs check (STO) and thus is undefined. That is, a standard-conforming program must not execute such a goal. To avoid this from happening, there is unify_with_occurs_check/2, subsumes_term/2. And to guard interfaces against receiving infinite terms, there is acyclic_term/1.

所有当前实现都以X = [1|X]终止. GNU Prolog也会终止:

All current implementations terminate for X = [1|X]. Also GNU Prolog terminates:

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

no

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

But for more complex cases, rational tree unification is needed. Compare this to Haskell where repeat 1 == repeat 1 causes ghci to freeze.

至于在常规的Prolog程序中使用有理树，这在开始时就很有趣，但扩展得并不好.举个例子，在1980年代初的一段时间里，人们相信语法将使用有理树来实现. las，人们对DCG感到很满意. 之所以没有离开研究的原因之一是因为Prolog程序员认为存在许多概念，而对于理性树却不存在.以字典词典术语排序为例，该词典排序没有对有理树的扩展.也就是说，存在无法使用标准术语顺序进行比较的有理树. (实际上，这意味着您将获得准随机结果.)这意味着您将无法生成包含此类术语的排序列表.同样，这意味着bagof/3之类的许多内置函数不再可以无限地可靠地工作.

As for using rational trees in regular Prolog programs, this is quite interesting in the beginning but does not extend very well. As an example, it was believed for some time in the beginning 1980s that grammars will be implemented using rational trees. Alas, people are happy enough with DCGs alone. One reason why this isn't leaving research, is, because many notions Prolog programmers assume to exist, do not exist for rational trees. Take as an example the lexicographic term ordering which has no extension for rational trees. That is, there are rational trees that cannot be compared using standard term order. (Practically this means that you get quasi random results.) Which means that you cannot produce a sorted list containing such terms. Which again means that many built-ins like bagof/3 no longer work reliably with infinite terms.

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

For your example query, consider the following definition:

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.

因此，有时有一些简单的方法可以避免未终止.但是，经常没有这种情况.

So sometimes there are simple ways to escape non-termination. But more often than not there are none.

这篇关于是无数个健全的名单吗?的文章就介绍到这了，希望我们推荐的答案对大家有所帮助，也希望大家多多支持IT屋！