From jan@swi.psy.uva.nl  Mon Aug 21 10:55:06 2000
Received: from gollem.swi.psy.uva.nl (root@gollem [145.18.152.30])
	by swi.psy.uva.nl (8.9.3/8.9.3) with ESMTP id KAA29647;
	Mon, 21 Aug 2000 10:55:01 +0200 (MET DST)
Received: from localhost (localhost [[UNIX: localhost]])
	by gollem.swi.psy.uva.nl (8.9.3/8.9.3/SuSE Linux 8.9.3-0.1) id KAA02985;
	Mon, 21 Aug 2000 10:55:19 +0200
From: Jan Wielemaker <jan@swi.psy.uva.nl>
Organization: SWI, University of Amsterdam
To: "Richard A. O'Keefe" <ok@atlas.otago.ac.nz>, p.singleton@keele.ac.uk,
        prolog@swi.psy.uva.nl
Subject: Re: representing terms canonically
Date: Mon, 21 Aug 2000 10:40:49 +0200
X-Mailer: KMail [version 1.0.28]
Content-Type: text/plain
References: <200008202349.LAA21776@atlas.otago.ac.nz>
In-Reply-To: <200008202349.LAA21776@atlas.otago.ac.nz>
MIME-Version: 1.0
Message-Id: <00082110551903.02738@gollem>
Content-Transfer-Encoding: 8bit

On Mon, 21 Aug 2000, Richard A. O'Keefe wrote:
>Paul Singleton wrote:
>
>	I note (empirically) that ==/2 succeeds when comparing a cyclic term with
>	itself, which is half of what I need, but (understandably) it doesn't
>	terminate when comparing some cyclic terms which don't "match up", e.g.
>	
>	  T1 = f(f(T1)),
>	  T2 = f(T1),
>	  T1 == T2.
>	
>	T1 and T2, although identical, can never be found to be identical by ==/2,
>	as their f/2 nodes are forever out-of-step.
>	
>Surely that's a bug?  When I tried
>	?- T1 = f(f(T1)), T2 = f(T2), T1 == T2, write(yes), !, fail.
>at the top level loop of SWI 3.3.8, it didn't fail to terminate, it did
>	Segmentation Fault (core dumped)
>instead.
>
>If you do
>	T1 = f(f(T1)), T2 = f(T2), T1 = T2
>ISO Prolog is supposed to require that to succeed, and one way to
>implement (==)/2 is as (=)/2 with the ability to bind variables taken away.
>Instead it never came back with any kind of answer.

Not seen it in the ISO specs (which is backed up by the absence of a
test for it in the two test-sets for ISO I've played with).  I still
might have overlooked it or it might not be in `Prolog the Standard',
which is what I'm using.

>	What I think I need, is a (distinctly non-logical :-) term comparison which
>	immediately (without any recursive searching) reports whether two terms are
>	the same actual compound "cell" (or whatever Prolog implementors call it).
>	
>No, what you need is versions of (=)/2 and (==)/2 that work the way they
>did in SICStus Prolog back in the early 80s.  I was once told that the
>method went something like this:

Interesting thought.  It won't make it into the system quickly though
as I think it isn't very useful to have only partial support for these
things.  If any, the entire system (=, comparison, numbervars,
ground, recorded db, compilation, write, etc.) should be able to handle
this.  Otherwise, the sooner it crashes the better!

So, for now the issue is whether you can test two term-handles to point
to the same memory rather than just equal data.  At the moment you
can't.  Given the fact that cyclic terms aren't much good in SWI-Prolog
anyhow except for the few cases where they work without precautions I
wonder how useful it is?

If you want to add a test, have a look at src/pl-fli.c, defining most of
the term-reference handling functions.

	Regards --- Jan

