Issue: EQUAL-STRUCTURE (Version 2)

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

I thought you were going to incorporate my comments into this issue, which
I sent in reply to its first presentation:

  Date: Fri, 18 Mar 88 21:21:51 PST
  From: Jon L White <edsel!jonl@labrea.Stanford.EDU>
  To: KMP@stony-brook.scrc.symbolics.com
  Cc: CL-Cleanup@sail.stanford.edu
  In-Reply-To: Kent M Pitman's message of Fri, 18 Mar 88 17:39 EST <880318173922.6.KMP@RIO-DE-JANEIRO.SCRC.Symbolics.COM>
  Subject: Issue: EQUAL-STRUCTURE (Version 1)

  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 --