EQUAL

["Robert W. Kerns" <RWK@AI.AI.MIT.EDU>]

    Date: Fri, 10 Jun 88 18:27:18 PDT
    From: Jim McDonald <edsel!jlm at labrea.stanford.edu>

    Thus EQUAL is (in some historical sense) defined to make it easy to do
    pattern matching on code.  Since code traditionally becomes read-only,
    this is more-or-less consistent with collapsing EQUAL structures to be
    EQ.  I claim that the traditional explanation for EQUAL's semantics
    (that EQUAL means roughly HAVE-THE-SAME-PRINT-REPRESENTATION-P) is
    actually just an observation based on this more fundamental reason. 

    When people try to move beyond manipulation of code, the whole basis
    for the semantics of EQUAL is removed, so the result is somewhat
    chaotic. 

While this all sounds very nice, I'm afraid you're engaging in
a bit of historical revisionism.

Originally, LISP didn't have all these nice hairy datatypes.
Those of us who were there (Not me!) can tell about what McCarthy
wrought, but I know I've seen Lisp's without arrays at all.  I know
people have been using EQUAL to compare data more often than to compare
code for a very long time.

In fact, EQUAL doesn't work on code, plain and simple.  To compare
code, you must first recognize that it is not computable to compare
two functions which contain quoted data, unless that quoted data is
EQ.  You also have to place constraints on macros to not be pathological
(i.e. sick).

To illustrate a couple examples:

(defvar *call-registry* (make-hash-table :test 'eq))

(defvar *macro-registry* (make-hash-table :test 'eq))

(defun register-macro-marker (marker)
  (let ((marker (gethash *macro-registry* marker)))
     (unless marker
	(setf marker `',(gensym))
	(setf (gethash *macro-registry* marker) marker))
     marker))

(defun register-call (marker result)
  (push result (gethash *call-registry* marker)))

(defmacro register (&whole marker)
  `(register-call ,(register-macro-marker marker) ,(second marker)))

(defun confound (flag)
  (if flag (register '(MARKER)) (register '(MARKER))))

Are the two branches of the IF equivalent?  EQUAL says yes.
I leave it as an exercise for the reader to count how many
ways and on how many levels those two branches differ.

[I apologize in advance for any spazzes in the code; I have to
type it in by hand; I don't have any way of transfering files
to or from arpanetland for testing, and editing directly on ITS
doesn't work well for me either].

In short, what EQUAL is good for is comparing "old-style" data
(that is, data structures like are used in such venerable programs
as Macsyma -- and there are some exceptions there, too).

I do think it would be reasonable to define an extremely limited set
of new predicates.  I would suggest limiting it to two new ones that
do the two pieces of EQUALP -- descend other structures, and merge
case in strings and characters.

I would strongly discourage any attempt to "solve the problem of
comparisons", on the grounds that it will require more hair, additions
to the language, and discussion than it could possibly be worth.