Relay-Version: version B 2.10 5/3/83; site utzoo.UUCP
Path: utzoo!mnetor!uunet!seismo!mcvax!ukc!its63b!aiva!jeff
From: jeff@aiva.ed.ac.uk (Jeff Dalton,                          JANET: J.Dalton@uk.ac.ed             )
Newsgroups: comp.lang.lisp
Subject: Re: EQ and EQUAL
Message-ID: <127@aiva.ed.ac.uk>
Date: Wed, 31-Dec-69 18:59:59 EDT
Article-I.D.: aiva.127
Posted: Wed Dec 31 18:59:59 1969
Date-Received: Sat, 8-Aug-87 09:02:17 EDT
References: <22@citcom.UUCP> <13278@topaz.rutgers.edu> <6601@reed.UUCP> <3927@spool.WISC.EDU> <6638@reed.UUCP> <290@nysernic> <1205@cognos.UUCP>
Reply-To: jeff@uk.ac.ed.aiva (Jeff Dalton)
Organization: Dept. of AI, Univ. of Edinburgh, UK
Lines: 68
Summary: EQ's not an unsafe EQUAL


The discussion of EQ vs. EQUAL seems to be assuming that

   -- EQ on lists is just an efficiency hack.

   -- EQ is unreliable and implementation-dependent.

So EQ gets classed with goto as something that we'd be better off
without.  However, EQ is not just a fast-but-unreliable EQUAL.

It is right to say that EQ is implementation-dependent, but it still
has certain properties that allow it to be used in portable ways.
Whether it is still useful to use EQ depends on other properties of
the Lisp systems in question.

In the "usual" Lisps, there is a ordering of equality predicates.  In
Common Lisp, the order from most to least strict is: EQ, EQL, EQUAL,
EQUALP.  (I'm leaving out type- specific tests like = and CHAR=.)  If
a more strict predicate returns true for some arguments, all less
strict predicates will also return true.  So, if EQ returns true, this
result is no more unreliable or implementation-dependent that one from
EQUAL -- because EQUAL will always return true as well.

But, one might argue, EQUAL calls EQ first: if you trust EQ only when
it returns true, you might as well use EQUAL instead.  Here I agree.
So the question is: is it ever useful to make the kind of distinction
made by EQ?  The answer to this question will depend on what other
operations are available in your Lisp.

In a sense, EQ tests whether two objects are the same identical object.
But how, apart from using EQ (or EQL), would one know whether objects
were identical?

One method would be to modify one of the objects and see whether the
other changes too.  If your Lisp includes RPLACA or RPLACD, two EQUAL
conses can be distinguished by this means, and so it is possible to
define a CONS-EQ that is stricter than EQUAL.  CONS-EQ would be a
useful test for "operational equivalence", not a fast-but-unreliable
EQUAL.

In the "usual" Lisps RPLACA and RPLACD *are* available, EQ returns true
for conses that are the same under destructive modification (and false
for conses that are different), and CONS always returns a new, EQ-unique,
object each time it's called.  Using EQ in this way works in all of these
Lisps.  You do not need to understand internals of the implementation,
only that EQ, CONS, etc. have certain properties.

Now, there are some who would like to get rid of RPLACA and RPLACD as
well as EQ.  And if you do so, it is not longer necessary for CONS to
create a new object each time.  It might ("hashed cons") quickly look
to see if the right (EQUAL) thing already existed.  And if CONS always
did this, EQUAL for conses could just be a pointer comparison, as EQ
is in more standard Lisps.

So the remaining question is to ask why anyone would want to keep
the operations for destructive modification.

One answer is that having objects that can change over time is an
effective technique for modeling real-world objects that change over
time.  For example, if we represent an person as a Lisp object, and the
person's address changes, we can follow the change by changing the Lisp
object instead of making a new object with a different address (but
otherwise the same) and then doing everything else required to give
the new object the same role in the database that the old one had.
-- 
Jeff Dalton,                          JANET: J.Dalton@uk.ac.ed             
AI Applications Institute,            ARPA:  J.Dalton%uk.ac.ed@cs.ucl.ac.uk
Edinburgh University.                 UUCP:  ...!ukc!ed.ac.uk!J.Dalton