Unification, comparison

[Raphael Collet]

David Hopwood wrote:
> Hmm. I believe the following optimization is worth considering: when two
> variables are either bound together or successfully tested for structural
> equality, set both to point to the structure with the lower address.
> 
> (Note that this only incurs extra overhead in the slow path where the
> full unification or structural equality algorithms are needed, not in the
> fast paths where they either already have the same address, or one was
> unbound.)

Your suggestion implies that the memory representation of a record could 
be turned into an indirection to another representation of the same 
record.  This makes the traversal of data quite complex, and makes the 
memory representation quite error-prone.  Currently only a variable can 
become an indirection to something else.

In most programs, something like 99% of unifications are simple variable 
bindings.  Very few actually require recursive unification.  Your idea 
implies an overhead on *every* operation, even if you don't use the full 
power of unification!  The current implementation provides a better 
tradeoff for most cases.

> The main advantage is for memory usage -- it tends to reduce the number of
> copies of identical structures, as the ones that are no longer referenced
> are garbage collected. I don't remember where I first heard about this idea
> (maybe on the C2 wiki?), but some Lisp implementations used it, I think.

I am not sure this is worth the effort.  My experience tells me that 
this kind of tricks potentially brings more problems than solutions.

> Is System.eq supposed to be guaranteed to distinguish between structurally
> equal values that have been bound together? If so then this would prevent
> the above optimization -- but perhaps its specification is too strong in
> that case.

Yes.  System.eq just tests whether its arguments, which actually are 
memory references, are identical.  It does not take into account 
structual equality.

Cheers,
raph