Is an infinite list of ones sane?

Question

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).

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

Upbringing

Answer 1

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

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.

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

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

no

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

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.

Deepfreeze

Answer 2

You don't get an infinite number of ones, of course, but what's called a rational or cyclic term. Not all Prolog systems support cyclic terms, however. Systems that provide some support for rational terms include CxProlog, ECLiPSe, SICStus, SWI-Prolog, and YAP. But be aware that there are differences between them regarding the computations that you can perform with rational terms.

A query such as:

X = [1|X], member(Y, X), Y = 1.

requires support for coinduction. You have a portable implementation of coinduction in Logtalk, which you can use with all the systems mentioned above. Coinduction requires that the Prolog system can create rational terms (using a query such as X = [1|X]), that can unify rational terms, and that can print bindings with rational terms in a non-ambigouos way.

For an example about enumerating (or testing) the elements of a rational list, see:

https://github.com/LogtalkDotOrg/logtalk3/blob/master/examples/coinduction/lists.lgt

Two sample queries for this example:

?- {coinduction(loader)}.
...
% (0 warnings)
true.
?- X = [1|X], lists::comember(Y, X), Y = 1.
X = [1|X],
Y = 1 ;
false.

?- X = [1, 2, 3| X], lists::comember(Y, X).
X = [1, 2, 3|X],
Y = 1 ;
X = [1, 2, 3|X],
Y = 2 ;
X = [1, 2, 3|X],
Y = 3 ;
false.

If you're interested in rational terms and coinduction, Logtalk's coinduction example includes several individual examples and bibliographic references.

Proterozoic

Answer 3

If you want to work with infinite lists, you can alternatively also revert to lazy lists. They have also a coinductive reading. Here is a simple Haskell like take predicate in Prolog that will evaluate an initial segment of a lazy list [Head|TailClosure]:

take(0, _, R) :- !, R = [].
take(N, C, [H|R]) :-
  call(C, [H|T]),
  M is N-1,
  take(M, T, R).

And here is a definition of the list of ones in this framework:

 one([1|one]).

As you can see you can expand the coinductive definition:

 Welcome to SWI-Prolog (threaded, 64 bits, version 7.7.1)
 SWI-Prolog comes with ABSOLUTELY NO WARRANTY. This is free software.

 ?- take(5,one,L).
 L = [1, 1, 1, 1, 1]. 

The requirements to make this work are much lower than in the case of rational terms. You only need a Prolog system that supports call/n which is required by ISO core standard, in its corrigendum 2. On the other hand rational terms are not required.

Its possible to define irrational lists this way and also to code stream processors that combine different streams. There is a growing literature about certain applications as for example exact reals and theorem provers like Coq, HOL/Isabelle, .. can reason about such streams.

Further reading:

Markus Triska - Prolog Streams
https://www.metalevel.at/various/prost

Dexter Kozen & Alexandra Silva - Practical Coinduction
https://www.cs.cornell.edu/~kozen/Papers/Structural.pdf

Edit 14.08.2018:
It must be said that neither prost from Markus Triska nor my post here did invent lazy lists via higher order calls. We find a 1983 Richard O'Keefe snippet here lazy.pl, where apply/2, the precursor of call/n is used. So I guess it pretty much belongs to Prolog folklore.

Phosphorate

... and even without the call/n, by fixing a special name for all lazy list-defining predicates (i.e., with an "extra level of indirection"). – Hilda

we would have to write G =.. [.....], G., correct? so it's just a syntactic difference. Using special name (building a kind of interpreter, in effect) was just something I came up with, at the time. Maybe I didn't yet know about call/N then, or fell comfortable with. :) – Hilda

huh, I was just thinking about the freeze. :) --- good to know, about the GC. – Hilda

looking at prost.pl, this seems like a typo (the args are swapped): shouldn't it be seq_take(Seq, N, Ts) :- phrase(seq_take_(N, Seq), Ts).? Also, looks like seq_take_ makes the classic mistake of forcing one-too-many elements in the stream: seq_take(Seq, 1, Ts) shouldn't call seq_next/2 at all. --- and lastly, primes are the classic non-postponed sieve of Turner (trial division), running in ~ n^2 instead of the postponed ~ n^1.5 (approximately; a proper sieve of E. should be even better, of course). – Hilda

e.g. rosettacode.org/wiki/Sieve_of_Eratosthenes#Optimized_approach – Hilda

@WillNess There are papers that discuss the co-inductive "purity", or simpler checkable as co-inductively guarded. It could be that a sieve can be better implemented less pure. Similarly the Hamming numbers exampe is discussed in this respect here: lorentzcenter.nl/lc/web/2014/603/presentations/Geuvers.pdf (See Page 39 ff) – Phosphorate

Let us continue this discussion in chat. – Hilda

@Will: G =.. [.....], G. is not a full replacement of call(C, ...) since with =.. you have n arguments, whereas with call/N you have >= n arguments – Deepfreeze