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