Path: utzoo!censor!geac!torsqnt!news-server.csri.toronto.edu!cs.utexas.edu!uunet!mcsun!unido!ecrc!micha
From: micha@ecrc.de (Micha Meier)
Newsgroups: comp.lang.prolog
Subject: Re: Another question on pointers and Prolog.
Message-ID: <1991Mar1.124315.827@ecrc.de>
Date: 1 Mar 91 12:43:15 GMT
References: <18129@cs.utexas.edu> <12600004@acf5.NYU.EDU>
Sender: news@ecrc.de
Reply-To: micha@ecrc.de (Micha Meier)
Organization: European Computer-Industry Research Centre
Lines: 42

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