Subject: Re: representing terms canonically

From: "Richard A. O'Keefe" <[email-masked]>
Date: Thu, 24 Aug 2000 08:34:52 +1200 (NZST)

concerning the handling of cyclic terms,
Paul Singleton wrote:

	OK, I think I understand the constructive part of your reply,
	but I'm having trouble with "No" :-)

	I'm worried that the (==)/2 you suggest has a cost which depends
	(somehow) upon the size of the terms being compared, whereas my

	  int PL_same_compound(term_t t1, term_t t2)
	
Why the restriction to compound terms?  Why not just for a version of EQ?

	has a size-independent cost, and lets me detect cyclic terms
	more cheaply.
	
I must have misunderstood your problem.

In the case where the two terms to be compared are the same copy
(live at the same address) or are non-variables with different
principal functors, the SICStus (==)/2 takes constant time.  The
expensive case is when they are isomorphic as rational trees but
live at different addresses.  In that case, it will take time
linear in the stored size of the terms.

As I understood your problem, determining whether a term was cyclic
(and a fortiori, whether two terms are the same copy of one term)
was only a means to an end:  converting possibly cyclic terms to
a minimal form.  For that, the SICStus (==)/2 really is the tool
you want; it does the whole job of safely deciding when two terms
can be identified without leaving the bulk of the work to you.

Consider as an example
	T0 = boom,
	T1 = and(T0,T0),
	...,
	T20 = and(T19,T19)
There aren't actually any cycles here, but if you want to convert
this term to a compact output format, you had *better* notice the
equal subtrees, which the SICStus (==)/2 will do cheaply.