From ok@atlas.otago.ac.nz  Wed Aug 23 22:34:44 2000
Received: from atlas.otago.ac.nz (atlas.otago.ac.nz [139.80.32.250])
	by swi.psy.uva.nl (8.9.3/8.9.3) with ESMTP id WAA08238
	for <prolog@swi.psy.uva.nl>; Wed, 23 Aug 2000 22:34:42 +0200 (MET DST)
Received: (from ok@localhost)
	by atlas.otago.ac.nz (8.9.3/8.9.3) id IAA12270;
	Thu, 24 Aug 2000 08:34:52 +1200 (NZST)
Date: Thu, 24 Aug 2000 08:34:52 +1200 (NZST)
From: "Richard A. O'Keefe" <ok@atlas.otago.ac.nz>
Message-Id: <200008232034.IAA12270@atlas.otago.ac.nz>
To: ok@atlas.otago.ac.nz, p.singleton@keele.ac.uk
Subject: Re: representing terms canonically
Cc: prolog@swi.psy.uva.nl

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.

