Subject: Re: representing terms canonically

From: Jan Wielemaker <[email-masked]>
Date: Mon, 21 Aug 2000 10:40:49 +0200

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