Issue: EQUAL-STRUCTURE (Version 1)

[Kent M Pitman <KMP@STONY-BROOK.SCRC.Symbolics.COM>]

This is somewhat sketchy, but I thought I'd get it on the table as is and people
could flesh it out as the discussion evolves...
 -kmp

-----
Issue:        EQUAL-STRUCTURE
References:   EQUAL (p80), EQUALP (p81)
Category:     CHANGE
Edit history: 18-Mar-88, Version 1 by Pitman
Status:	      For Internal Discussion

Problem Description:

  The behavior of EQUAL and EQUALP on structures is a subject of controversy.
  At issue are whether these functions should descend the slots of structures
  or use simply the structure's primitive identity (i.e., EQ) to test for
  equivalence.

Proposal (EQUAL-STRUCTURE:RADICAL):

  Remove EQUAL and EQUALP from the language. (Naturally, they could be retained
  as implementation-dependent extensions.)

  Rationale:

   The name "EQUAL" suggests something very generic. It conjures in the mind
   of the naive user the notion that there is a single, uniquely selected
   predicate which is always good for equality testing. In fact, there is a
   large space of useful equality predicates, each good for different
   applications, and the choice of the current definition of EQUAL is
   exceedingly arbitrary. Although the function chosen is sometimes quite
   useful and some work is occassionally saved by having it be defaultly
   available, confusion frequently results from its presence. Users for whom
   the operator is not appropriate are inclined to describe it as broken,
   rather than to recognize that it does a useful thing but that the
   application they have does not call for that useful thing. The thing which
   would be useful to them would not be useful in other situations. There is
   simply no unique solution. The absence of the operator EQUAL would cause
   people to think explicitly about what kind of equivalence is appropriate
   to their application, and to write something better suited to that
   application.

   As an aside, this same notion of uniqueness carries over to COPY. People
   have been observed to assert that a generic COPY function should be
   present for copying arbitrary objects. A single COPY function is not
   provided because there are many kinds of copying and no single function is
   entitled to the generic name COPY. This argument does not sit well with
   programmers who assert that if this is true, there should be no unique
   EQUAL operator. We could solve that problem two ways -- one by creating a
   COPY operator; another by eliminating the embarrassment of EQUAL and
   friends.

Proposal (EQUAL-STRUCTURE:STATUS-QUO):

  Leave things as is.

  Rationale:

   The intent of a structure is different than the intent of an array. A
   list is an anonymous entity which makes sense only in terms of its
   length and contents, and is not rightly compared just by object identity
   (EQ); a structure, on the other hand, has an identity of its own and is
   appropriately compared with EQ.

Proposal (EQUAL-STRUCTURE:DESCEND):

  Change EQUAL and EQUALP to descend structure slots.

  Rationale:

   A structure is a container and, like many other containers in Lisp,
   should be compared by recursing into the contents of that container.

Proposal (EQUAL-STRUCTURE:ADD-KEYWORDS):

  Add :TEST and :TEST-NOT keywords to EQUAL saying what comparison operator
  to use at the leaves.

  [This will need more details if anyone decides they want to push this line
   of reasoning. I don't claim to have done an adqeuate job of laying the
   issue out, though I could imagine someone doing so. -kmp]

  Rationale:

   There's ample precedent for resolving sticky situations like this in
   Common Lisp by just adding a keyword option. :-)

Proposal (EQUAL-STRUCTURE:ADD-OPERATOR)

  Introduce new operator(s) like EQUAL (and/or EQUALP) which descends
  structures.

  Rationale:

   If people don't want to make EQUAL more complicated, but still like
   the idea of a keyword-driven EQUAL, this is the only way to get it.

Current Practice:

  There is no particular ambiguity in CLtL right now, so presumably
  everyone agrees. The only question is whether what CLtL says is
  sufficiently useful in practice.

Cost to Implementors:

  The cost to implementors of most of these options is generally small.
  The exception is that the ADD-KEYWORDS option may require hairy compiler
  optimizations in order to get back the efficiency that a keyword would lose.

Cost to Users:

  Writing an EQUAL or EQUALP function which is like the one that Common Lisp
  now has would not be that hard to do as a compatibility measure in case
  EQUAL or EQUALP were changed or removed. So the cost to users is technically
  small.

Cost of Non-Adoption:

  Ongoing controversy about whether EQUAL and EQUALP "do the right thing".

Benefits:

  A feeling that EQUAL and EQUALP exist and/or do what they do because serious
  consideration was given and we consciously decided on a particular resolution
  to the numerous questions that have come up about them.

Aesthetics:

  Aesthetic considerations vary widely. Different people model structures
  differently. Sometimes the same person models structures differently in
  different situations. The question of which should be descended and which
  should not is a very personal one, and the aesthetic attractiveness of any
  of these options will vary from person to person or application to
  application.

  The ADD-KEYWORDS option will be the most controversial because some people
  don't like keywords and some compiler writers will not like having to
  optimize the keywords.

Discussion:

  Pitman strongly supports EQUAL-STRUCTURE:RADICAL as the correct choice from
  a purely language design standpoint, but acknowledges that it may not
  ultimately be deemed practical for pragmatic reasons.