[Re: EQUAL]

[Jon L White <edsel!jonl@labrea.stanford.edu>]

[Neil, I'm cc'ing my reply to the whole list, since I think you questions
are of general relevance.  Apologies in advance if you really didn't want
to "go public" with your question. -- JonL --]

    From: goldman@vaxa.isi.edu
    Date: Fri, 24 Jun 88 18:15:43 PDT
    . . . 

       (2) Descend defstructs, except possibly for "system" defstructs ...

    What are potential "system" defstructs?  Is the phrase limited to the list
    of types on page 13?  If so, then it sounds ok, since EQUAL is already
    (independently) appropriately defined on BIGNUMS and PATHNAMES.  But it
    just says "such as ..." on page 13, which leaves some doubt.

I was certainly thinking of those types on page 13, since they are the
ones addressed by the "cleanup" issue "type-hierarchy-underspecfied".

       (3) Require that EQUAL be a "generic" function, so that CLOS methods
	   can be written for it, likely, the "default" method for non-built-in
	   classes would be some sort of error, meaning that mindless descent
	   isn't a good default. 

    First, I would think that (OBJECT OBJECT) would have an EQUAL method
    that applied EQL, not ERROR, and that method would inherit to all standard
    classes under OBJECT.  I must misunderstand your intent -- you certainly
    would want EQUAL to be TRUE whenever EQ was true, not an error?

I'm not 100% certain that one would want this.  Perhaps the CLOS subcommittee
of x3j13 will tackle it.  Mostly, the default method is just to say that
you shouldn't be doing this (calling EQUAL) on an object of this type.  But 
just having no applicable method may in fact be a better kind of error.  Of 
course, a default method could check for EQ before causing any other kind of 
error.

    If programmers to extend EQUAL in CLOS style -- which means
    with arbitrary procedural definitions for their new classes -- could 
    EQUAL hash tables be implemented efficiently?  How would they hash 
    values belonging to the new classes?    

As you pointed out in subsequent discussion, a user-supplied EQUAL method,
whether for CLOS classes or as a defstruct option, leaves open the question
of mechanically verifying that the alleged predicate is reflexive, symmetric,
and transitive.  Another major problem with using hash-tables on objects
with non-default EQUAL methods is that the SXHASH function must be similarly
extended for these data types; SXHASH must obey the property that
    (equal x y)   imples   (= (sxhash x) (sxhash x))
See CLtL p285.  At one time, there was a suggestion that hash tables admit 
a user-supplied equivalence predicate; but it never got very far for just 
this reason, that the equivalence predicate must be *** paired up** with an
appropriate "numericalizer" function, and many implementors felt that users 
wouldn't understand these issues and wouldn't be able to construct up their 
own versions of sxhash to go with their alleged equivalence predicates. 
[SXHASH is required to be "good enough" for the EQUAL equivalence releation,
and for subsets of that relation such as STRING=, but it is unlikely that 
any vendor makes it "good enough" for, say, EQUALP.  Lucid has EQUALP hash
tables, but they don't use SXHASH.]

    . . . 
    [Pardon me if I am impuning more to your suggestion than you intended.
    This discussion that started on the meaning of DEFCONSTANT and QUOTE has
    spread out quite a bit, and maybe you are just suggesting this as
    an improvement to EQUAL with no implications about it clarifying
    defconstant/quote].

Yes, the Subject line of this interchange has been "EQUAL" -- not 
"constant folding/smashing" as before.  Jim MacDonald was simply
inspired by the defconstant/quote issue to open up the EQUAL one.


-- JonL --