Issue EQUALP-GENERIC

[Kim A. Barrett <IIM@ECLA.USC.EDU>]

In response to JonL's complaint that a proposal to make EQUALP a generic
function did not seem to be forthcoming ...

-----
Forum:		Cleanup
Issue:		EQUALP-GENERIC
References:	EQUALP, p81
Related issues: EQUAL-STRUCTURE
		HASH-TABLE-STABILITY
		HASH-TABLE-TESTS
Category:	CHANGE ADDITION
Edit history:	Version 1, 02-28-89, Kim A. Barrett

Problem description:

 The recent acceptance of Issue EQUAL-STRUCTURE (as ammended) has generated
 some complaints about its specified behavior on objects with metaclass
 STRUCTURE-CLASS.  Some programs which depend on EQUALP comparing the
 components of structures are now broken.

 There are some who feel that EQUALP could be made much more useful than it
 currently is by making it user extensible, but there are potential
 difficulties due to the recent acceptance of Issue HASH-TABLE-TESTS, which
 added EQUALP as a valid hash-table test.

Proposal (EQUALP-GENERIC:YES):

 Specify that EQUALP is a generic function, and define the new generic function
 EQUALP-HASH.  Specify that a necessary requirement on all methods for these
 functions is that (EQUALP x y) => (= (EQUALP-HASH x t) (EQUALP-HASH y t)).
 Add a discussion of the constraints on equivelence predicates and their
 corresponding hash functions, similar to that presented in Issue
 HASH-TABLE-STABILITY.

 EQUALP object1 object2					[Generic Function]

  The generic function EQUALP is a predicate which can be called to compare two
  objects for equivelence.  The precise definition of equivelence is specified
  by the methods defined on this function.  The result is either true or false,
  depending on whether the objects are equivelent.

 Method Signatures:

  EQUALP (object1 NUMBER) (object2 NUMBER)		[Primary Method]
   Defines equality as being =.

  EQUALP (object1 CHARACTER) (object2 CHARACTER)	[Primary Method]
   Defines equality as being CHAR-EQUAL.

  EQUALP (object1 CONS) (object2 CONS)			[Primary Method]
   Defines equality as having EQUALP CAR's and EQUALP CDR's.

  EQUALP (object1 PATHNAME) (object2 PATHNAME)		[Primary Method]
   Defines equality as being EQUAL.

  EQUALP (object1 VECTOR) (object2 VECTOR)		[Primary Method]
   Defines equality as having the same length (observing fill-pointers when
   present), and every pair of corresponding components are EQUALP. 

  EQUALP (object1 ARRAY) (object2 ARRAY)		[Primary Method]
   Defines equality as having the same rank and dimensions, and every pair of
   corresponding components are EQUALP.

  EQUALP (object1 HASH-TABLE) (object2 HASH-TABLE)	[Primary Method]
   Defines equality as satisfying the following conditions:
   1. Each hash-table uses the same test function.
   2. Each hash-table contains entries for the same set of keys, where the test
      function is used to determine the equivelence of keys.
   3. For each key, the associated values from the two tables are EQUALP.

  EQUALP (object1 T) (object2 T)			[Primary Method]
   The default method defines equality as being EQ.

 Remarks:
  An error is signaled on an attempt to add a method on any built-in class.
  Adding a method on a class after ALLOCATE-INSTANCE has been called on the
  class has undefined consequences.  Implementations may be extended in this
  case.

  An implementation may specify additional methods on this function.

 EQUALP-HASH object &optional use-pointer depth		[Generic Function]

  The generic function EQUALP-HASH is a called to compute a hash code for the
  Object.  Use-Pointer is a flag.  If true, the memory location of the object
  may be used to generate the hash code.  The default is false.

  Depth is used to control the depth of recursion, allowing cuttoff.  This
  prevents infinite recursion in the case of circular references.  Callers of
  this function should not explicitely specify a value for this argument.
  Methods on this function which need to make recursive calls should simply
  pass the Depth argument along unchanged.

  This function returns two values.  The first value is the hash code, which is
  a non-negative fixnum.  The second value is a flag indicating whether the
  memory location of the object (or any component) was used in generating the
  hash code.  A caller who specifies NIL for the Use-Pointer argument may
  reliably depend on the second value being false.

  This function is used by the implementation to compute hash codes for EQUALP
  hash-tables.  By specifying a NIL value for the second argument, it may also
  be used to compute a code which is independent of the particular
  "incarnation" or "core image", just as for SXHASH.

 Method Signatures:

  EQUALP-HASH (object NUMBER) &optional use-pointer depth     [Primary Method]
  EQUALP-HASH (object CHARACTER) &optional use-pointer depth  [Primary Method]
  EQUALP-HASH (object CONS) &optional use-pointer depth	      [Primary Method]
  EQUALP-HASH (object PATHNAME) &optional use-pointer depth   [Primary Method]
  EQUALP-HASH (object VECTOR) &optional use-pointer depth     [Primary Method]
  EQUALP-HASH (object ARRAY) &optional use-pointer depth      [Primary Method]
  EQUALP-HASH (object HASH-TABLE) &optional use-pointer	depth [Primary Method]
  EQUALP-HASH (object T) &optional use-pointer depth	      [Primary Method]

   The manner in which the hash code is computed by the standard methods on
   this function is implementation dependent.

 Remarks:
  An error is signaled on an attempt to add a method on any built-in class.
  Adding a method on a class after ALLOCATE-INSTANCE has been called on the
  class has undefined consequences.  Implementations may be extended in this
  case.

  An implementation may specify additional methods on this function.

Examples:

Test Cases:

Rationale:

 It is not possible to determine in a general way what components of
 user-defined classes should be examined when computing equality of instances.
 By specifying EQUALP to be a generic function which the user can extend, we
 allow the user to specify the algorithm for determining equivelence.

 The restrictions on adding additional methods are due to the possiblity of
 existing data structures having been built up using the previous set of
 methods.  One way an implementation could be extended would be to provide a
 mechanism for marking potentially invalid data structures when new methods are
 added.

Current practice:

 Probably no current implementation already does this.

Cost to Implementors:

 Probably small.  An implementation must already support the described
 functionality for EQUALP, and must have a function similar to EQUALP-HASH in
 order to implement hash-tables with an EQUALP test function.  This proposal
 merely exposes the hashing function and makes both of these functions
 user-specializable. 

Cost to Users:

 Users who were depending on EQUALP descending into structures will have to
 write methods for both functions for the classes they wish to continue to have
 this behavior.

Cost of non-adoption:

Performance impact:

 Probably small overall, though programs which rely heavily on EQUALP or EQUALP
 hash-tables may be affected due to the differing performance of generic
 functions compared with normal functions doing type analysis.  Presumably the
 performance can only be worse than what would be the case if this proposal
 were not adopted, since if defining these functions as generic produced better
 performance, then the implementation may have already made them generic,
 possibly without advertising the fact.

Benefits:

 Allows users to specify the proper method for comparing instances of user
 defined classes.

Aesthetics:

Discussion:

 Other mechanisms for doing the recursion cuttoff in EQUALP-HASH are possible.
 The one offered in the proposal is simple and trivial to implement.  It is
 also kind of ugly, and it is possible that some users might want more than is
 offered for this.  Maybe some better alternative can be developed.
-------