Path: utzoo!utgpu!news-server.csri.toronto.edu!bonnie.concordia.ca!clyde.concordia.ca!nstn.ns.ca!news.cs.indiana.edu!samsung!crackers!m2c!umvlsi!dime!cs.umass.edu!pop
From: pop@cs.umass.edu
Newsgroups: comp.lang.prolog
Subject: Cycles in Prolog Data Structures.
Keywords: Unification occurs check
Message-ID: <26637@dime.cs.umass.edu>
Date: 14 Feb 91 15:23:59 GMT
References: <17853@cs.utexas.edu>
Sender: news@dime.cs.umass.edu
Reply-To: pop@cs.umass.edu ()
Organization: University of Massachusetts, Amherst
Lines: 16

While purists would consider it an error, the fact that Prolog implementations
do not include an occurs check in unification makes it possible to create
cyclic data-structures, e.g.

    :-  X =  [a|X].

will succeed, creating an infinite list of a's. Whethere there is a breed of
Prolog programmers who happily knit up tangled webs in this way, I don't 
know, nor is it entirely obvious to me how to program up the example that
Russell Turpin refers to. The spouse "slot" could be put in a tree by having
a unique unbound variable at each node, which is no great problem. However
any attempt at a recursive traversal of the tree to fill in the spice would
not work, since the variables would be unbound as soon as each recursive
sub-goal succeeded. I think that one would have to write a tail-recursive
predicate, which explored the tree by maintaining an explicit stack.
At the end of all the binding, it could only be preserved by using an assert..