[comp.lang.prolog] Another question on pointers and Prolog.

turpin@cs.utexas.edu (Russell Turpin) (02/26/91)

-----
Some variants of Prolog support "infinite" data structures, that
is, non-tree-like data structures.  (In essence, an "infinite"
data structure is repetitive and there is a folding of it onto the
underlying finite, non-tree-like data structure.  Thus, the
following cyclic list:

	a --> b --> c -+
	      ^        |
	      +--------+

is equivalent to the "infinite" data structure abcbcbcbc ...)

A common problem given to undergraduates in a data structures
class is this: given a list, determine in linear time and constant
(pointer size) space whether the list terminates (ends in a null
pointer) or cycles.  The solution is to advance two pointers down
the list, one at twice the rate of the other, until either (1)
they are equal, indicating a cycle, or (2) the faster one falls
off the list.

Now suppose one is writing a Prolog program that deals with a
potentially infinite (cyclic) list, and one desires a predicate
that tests a list to determine whether it is infinite (cyclic).
How would one implement an efficient test such as the algorithm
described above? 

Alternatively, if one must either rely on built-in primitives or
a less efficient algorithm, should this be seen as a problem?

Russell

micha@ecrc.de (Micha Meier) (02/27/91)

In article <2142@n-kulcs.cs.kuleuven.ac.be> bimandre@icarus.cs.kuleuven.ac.be (Andre Marien) writes:
>In <18129@cs.utexas.edu> Russell Turpin asks :
>> How would one implement an efficient test such as the algorithm
>> described above? 
>(finding out whether a list is cyclic with pointers running at different speed)
...
>il([E|L]) :- il(L,[E|L]) .
>
>il(L,L) :- ! . % part of list unifies with list
>il([_,_|L1],[_|L2]) :-
>	il(L1,L2) .

	If your Prolog system does not treat cyclic terms, this program
	will loop with a cyclist list. Generally, if the Prolog system
	does not treat cyclic terms, there is no pure way to distinct
	a cyclic list from a non-cyclic one, precisely because
	there are no pointers in Prolog, and the term equality
	is not dictated by a von Neumann machine, but by logic.
	(You can of course find out how much space your program
	occupies and then go only that deep into the list :-))
	Note that some Prolog systems do compare the pointers
	deep in the unification Procedure, in order to save time
	when two identical terms are unified, so that the above program
	succeeds on lists like X=[a|X], but it still loops with X=[a, a|X].

--Micha
--
E-MAIL  micha@ecrc.de            	MAIL	Micha Meier
						ECRC, Arabellastr. 17
                     				8000 Munich 81
						Germany

mitsolid@acf5.NYU.EDU (Thanasis Mitsolides) (03/01/91)

/ micha@ecrc.de (Micha Meier) /  4:33 am  Feb 27, 1991 */
In article <2142@n-kulcs.cs.kuleuven.ac.be> bimandre@icarus.cs.kuleuven.ac.be (Andre Marien) writes:
>il([E|L]) :- il(L,[E|L]) .
>
>il(L,L) :- ! . % part of list unifies with list
>il([_,_|L1],[_|L2]) :-
>	il(L1,L2) .

	Note that some Prolog systems do compare the pointers
	deep in the unification Procedure, in order to save time
	when two identical terms are unified, so that the above program
	succeeds on lists like X=[a|X], but it still loops with X=[a, a|X].

What do you mean by "deep in the recursion"?
Most Prolog systems compare pointers immidiately and always.
The reason X=[a|X] or X[a, a, a|X] etc succeed
while X=[a,a|X] or X=[a,a,a,a|X] etc. fail is that
in the first case the unification operation eventually tries to unify
the same pointers while in the second case that never happens.

In other words, the reason "X=[a,a|X], il(X)" does not succeed
is the same for which "X=[a|X], Y=[a|Y], X=Y" does not succeed.

Thanasis

-------------------------------------------------------------------------------
Internet: mitsolid@cs.nyu.edu	             (mitsolid%cs.nyu.edu@relay.cs.net)
UUCP    : ...!uunet!cmcl2!cs!mitsolid
-------------------------------------------------------------------------------
--
-------------------------------------------------------------------------------
Internet: mitsolid@cs.nyu.edu	             (mitsolid%cs.nyu.edu@relay.cs.net)
UUCP    : ...!uunet!cmcl2!cs!mitsolid
-------------------------------------------------------------------------------

micha@ecrc.de (Micha Meier) (03/01/91)

In article <12600004@acf5.NYU.EDU> mitsolid@acf5.NYU.EDU (Thanasis Mitsolides) writes:
>
>	Note that some Prolog systems do compare the pointers
>	deep in the unification Procedure, in order to save time
>	when two identical terms are unified, so that the above program
>	succeeds on lists like X=[a|X], but it still loops with X=[a, a|X].
>
>What do you mean by "deep in the recursion"? (sic)

	By "deep in the unification procedure" I mean somewhere
	inside the unification procedure, which is used e.g. to implement
	the operation X = Y

>Most Prolog systems compare pointers immidiately and always.
>The reason X=[a|X] or X[a, a, a|X] etc succeed
>while X=[a,a|X] or X=[a,a,a,a|X] etc. fail is that
>in the first case the unification operation eventually tries to unify
>the same pointers while in the second case that never happens.

	You are missing the point. For Prolog systems which do not handle
	cyclic terms, the program succeeds only for a list whose tail
	points directly to its beginning.
	If the cycle is longer, e.g. X = [a, a, a|X], the program loops
	on the first clause il(L, L), because the unification always
	tries to unify adjacent list elements which are not
	located at the same memory address, it never comes to the second
	clause which applies the tortoise and hare technique.

>In other words, the reason "X=[a,a|X], il(X)" does not succeed
>is the same for which "X=[a|X], Y=[a|Y], X=Y" does not succeed.

	Yes, there are many other ways to say that a Prolog
	system which cannot handle cyclic terms can only handle
	unification of terms which are allocated at the same
	memory address.

--Micha
--
E-MAIL  micha@ecrc.de            	MAIL	Micha Meier
						ECRC, Arabellastr. 17
                     				8000 Munich 81
						Germany