Issue: EQUAL-STRUCTURE (Version 1)

[Jon L White <edsel!jonl@labrea.Stanford.EDU>]

Generally ok write-up of the issues.  You left out the option of adding
a jillion-skillion new functions -- one for each conceivable kind of 
equivalence relation between s-expressions.  But that's ok; I want to
focus on just one of your proposals.

re: Proposal (EQUAL-STRUCTURE:DESCEND):
    Change EQUAL and EQUALP to descend structure slots.

EQUALP is already documented to descend structures (CLtL, p81).  So this
proposal should just say "Change EQUAL ...".

Had all the negative arguments against this particular proposal -- the one 
you call (EQUAL-STRUCTURE:DESCEND) -- been thought of 6 years ago, CL could
not even have an EQUALP function.  The logical conclusion of these 
"technical details" arguments is that EQUAL cannot be defined either.
These arguments go roughly as follows:
   (1) The equivalence which EQUAL implements is not graph-isomorphism --
       which *is* uniquely defined -- but rather an ill-defined one
       making reference to the underspecified notion of "printing".
       Attempts to make it more precise are merely arbitrary.
   (2) EQUAL is not a total function since it is permitted to run amok 
       on circular structures.  In fact, it is much more "likely" that 
       defstruct instances will contain ultimately circular links than 
       that cons cells will; hence one will "probably" lose more much 
       often if EQUAL were to descend structures.

The more "wizard", or "theorist" one is, the more compelling the above
arguments seem.  On the other hand, the more a "user" one is, the more
likely he will argue as follows:

  I've used the EQUAL function for over 15 years, and have almost never
  been dissatisfied with it, as the Doctors of Technology say I should be; 
  and every instance of dissatisfaction was due to its failue to descend 
  through pointer vectors.  I keep my house in order, and know exactly
  how my data pyramids are built up; so why should I be punished just
  because some Conehead somewhere got lost playing around with his
  Klein bottles and Moebius strips?


All the problems alleged for EQUALP's descent into structures also apply
to EQUAL's descent into lists; it's only a matter of probabilities.  Hence,
I don't believe this issue can be settled by technical discussion.  

The only non-time-wasting effort I can see to do from now on is to look for 
some way to present our dilemma to a broad "user" community.  We could try 
to tell them, in cursory terms and few words, of the technical arguments 
that show EQUAL (and EQUALP) to be ill-behaved functions.  Then let them 
decide (by straw vote?) if the extra functionality provided by this proposal
is worth the extra risk.



Related Issues:

  -- Are DEFSTRUCT-defined types and CONS, ARRAY, HASH-TABLE, PACKAGE, 
     READTABLE, STREAM, etc.  pairwise disjoint?

  -- Will CLOS require EQUAL to be "generic"?  Also, what about COPY?



-- JonL --