Path: utzoo!attcan!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: <1991Feb27.093326.16330@ecrc.de>
Date: 27 Feb 91 09:33:26 GMT
References: <18129@cs.utexas.edu> <2142@n-kulcs.cs.kuleuven.ac.be>
Sender: news@ecrc.de
Reply-To: micha@ecrc.de (Micha Meier)
Organization: European Computer-Industry Research Centre
Lines: 31

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