"Mathematicians often say that to understand something you must first
read it, then write it down in your own words, then teach it so someone
else " - from "How to read mathematics".
I came back to playing with Lisp recently, and naturally I discovered
that I forgot how Lisp's equality operators - eq, eql, equal and equalp
differ. To completely understand it,
I referred to the Hyperspec and two Lisp books. To avoid
this experience in the future, I summarized my "understanding"
in a short article:
http://www.geocities.com/spur4444/prog/equality_in_lisp.html
I think it will be quite useful to beginners, both to understand
and to serve as a reference. But I'll be glad to get some feedback from
the experienced Lisp programmers here. Are there
any obvious flops ?
Disclaimer: the article is not complete. There are other comparison
operators in Lisp (e.g. char=). For a full reference, the Hyperspec is
required. However, the article should be useful for initial "getting
it" stage.
Kind regards,
Eli
In article <··········@odak26.prod.google.com>,
"Eli Bendersky" <······@gmail.com> wrote:
> Disclaimer: the article is not complete. There are other comparison
> operators in Lisp (e.g. char=). For a full reference, the Hyperspec is
> required. However, the article should be useful for initial "getting
> it" stage.
I would at least mention the existence of string= and string-equal, and
also mention that notwithstanding their names they also work on symbols.
RG
Eli Bendersky wrote:
> "Mathematicians often say that to understand something you must first
> read it, then write it down in your own words, then teach it so someone
> else " - from "How to read mathematics".
>
> I came back to playing with Lisp recently, and naturally I discovered
> that I forgot how Lisp's equality operators - eq, eql, equal and equalp
> differ. To completely understand it,
> I referred to the Hyperspec and two Lisp books. To avoid
> this experience in the future, I summarized my "understanding"
> in a short article:
>
> http://www.geocities.com/spur4444/prog/equality_in_lisp.html
>
> I think it will be quite useful to beginners, both to understand
> and to serve as a reference. But I'll be glad to get some feedback from
> the experienced Lisp programmers here. Are there
> any obvious flops ?
>
> Disclaimer: the article is not complete. There are other comparison
> operators in Lisp (e.g. char=). For a full reference, the Hyperspec is
> required. However, the article should be useful for initial "getting
> it" stage.
Nice. What about contributing it to the CL cookbook
(http://cl-cookbook.sourceforge.net)? There doesn't seem to be an
article covering this issue.
Alberto
From: Mark Carter
Subject: Re: a short article about equality in Lisp (for beginners)
Date:
Message-ID: <2nho7eF139acU1@uni-berlin.de>
Eli Bendersky wrote:
> "Mathematicians often say that to understand something you must first
> read it, then write it down in your own words, then teach it so someone
> else " - from "How to read mathematics".
I heard one respected mathematician (maybe Warner) say: unless you can
think of 5 different ways to solve a problem, then you don't really
fully understand it.
From: Antonio Menezes Leitao
Subject: Re: a short article about equality in Lisp (for beginners)
Date:
Message-ID: <87d6248bt3.fsf@evaluator.pt>
"Eli Bendersky" <······@gmail.com> writes:
> "Mathematicians often say that to understand something you must first
> read it, then write it down in your own words, then teach it so someone
> else " - from "How to read mathematics".
>
> I came back to playing with Lisp recently, and naturally I discovered
> that I forgot how Lisp's equality operators - eq, eql, equal and equalp
> differ. To completely understand it,
> I referred to the Hyperspec and two Lisp books. To avoid
> this experience in the future, I summarized my "understanding"
> in a short article:
>
> http://www.geocities.com/spur4444/prog/equality_in_lisp.html
>
> I think it will be quite useful to beginners, both to understand
> and to serve as a reference. But I'll be glad to get some feedback from
> the experienced Lisp programmers here. Are there
> any obvious flops ?
I don't agree with the following sentence:
On the other hand, you probably don't want to use eq on anything
other than symbols.
In don't think that's correct. Identity is a fundamental concept in
object-oriented languages (such as Common Lisp) and, except for
numbers and characters, 'eq' is the operator that checks it.
I know that 'eql' does the same and also deals with numbers and
characters but, in most cases, these should be tested with '=' and
'char='. In fact, when we know that we are not dealing with numbers
and characters, 'eq' seems much more informative to me than 'eql'.
The Summary also doesn't seems OK.
# eq compares symbols. Two objects are eq iff they are actually the
same object in memory. Don't use it for numbers and characters.
# eql compares symbols similarly to eq, numbers (type sensitive) and
characters (case sensitive)
As I said above, when you are looking for identity, these operators
are perfectly OK (and essential, in fact) to compare a lot more
datatypes.
Ant�nio Leit�o.
From: Peter Seibel
Subject: Re: a short article about equality in Lisp (for beginners)
Date:
Message-ID: <m3pt64409y.fsf@javamonkey.com>
"Eli Bendersky" <······@gmail.com> writes:
> I think it will be quite useful to beginners, both to understand and
> to serve as a reference. But I'll be glad to get some feedback from
> the experienced Lisp programmers here. Are there any obvious flops ?
One nit. EQUAL consides non-EQL bit vectors with the same contents to
be equivalent; you say it only works for strings.
Also, I belive the case with EQ when applied to numbers and characters
is even worse than you let on. For instance,
(let ((x 10)) (eq x x)) ==> NIL
is a legal result which is somewhat at odds with how I imagine most
folks would understand your model of "EQ compares addresses". When you
say:
As a rule of thumb don't use eq on numbers and characters, unless
you really know what you're doing.
you imply that there are some situations where you might want to use
EQ to compare numbers or characters. It's not clear to me that that's
ever the case. I can see that if you're *really* concerned about speed
you might use EQ in a place where you know you will never be comparing
numbers and/or characters but that's different. (Or some folks argue
for using EQ when applicable to emphasize that there are no numbers or
characters involved--e.g. somewhere where only symbols are being
compared.)
-Peter
--
Peter Seibel ·····@javamonkey.com
Lisp is the red pill. -- John Fraser, comp.lang.lisp
From: Coby Beck
Subject: Re: a short article about equality in Lisp (for beginners)
Date:
Message-ID: <l0dRc.69976$T_6.22049@edtnps89>
"Peter Seibel" <·····@javamonkey.com> wrote in message
···················@javamonkey.com...
> "Eli Bendersky" <······@gmail.com> writes:
>
> folks would understand your model of "EQ compares addresses". When you
> say:
>
> As a rule of thumb don't use eq on numbers and characters, unless
> you really know what you're doing.
>
> you imply that there are some situations where you might want to use
> EQ to compare numbers or characters. It's not clear to me that that's
> ever the case.
The best rule of thumb is never use EQ.
When you are in a situation where rules of thumb (rule of thumbs??) don't
apply, then rarely use EQ.
--
Coby Beck
(remove #\Space "coby 101 @ big pond . com")
In article <·····················@edtnps89>, Coby Beck wrote:
>
> "Peter Seibel" <·····@javamonkey.com> wrote in message
> ···················@javamonkey.com...
>> "Eli Bendersky" <······@gmail.com> writes:
>>
>> folks would understand your model of "EQ compares addresses". When you
>> say:
>>
>> As a rule of thumb don't use eq on numbers and characters, unless
>> you really know what you're doing.
>>
>> you imply that there are some situations where you might want to use
>> EQ to compare numbers or characters. It's not clear to me that that's
>> ever the case.
>
> The best rule of thumb is never use EQ.
>
> When you are in a situation where rules of thumb (rule of thumbs??) don't
> apply, then rarely use EQ.
>
I have found that EQ is suprisingly little used. About the only times use
it is when creating #'eq hashtables for looking up by symbols or by object
identity when I have a different data structure, and is looking up additional
information with the object.
--
--
Gisle S�lensminde
Computational biology unit, University of Bergen, Norway
Email: ·····@cbu.uib.no
Eli Bendersky wrote:
> I think it will be quite useful to beginners, both to understand
> and to serve as a reference. But I'll be glad to get some feedback from
> the experienced Lisp programmers here. Are there
> any obvious flops ?
It's a very nice article and I think I will recommend it. However, a
minor note: The last section before the Summary might lead some newbies
to try too hard to figure out when they should use eq instead of eql.
It's possibly a good idea to say that eql is generally fast enough, and
that's why it is usually the default (and should be in one's own code).
Pascal
--
Tyler: "How's that working out for you?"
Jack: "Great."
Tyler: "Keep it up, then."
Eli Bendersky wrote:
[...]
> I referred to the Hyperspec and two Lisp books. To avoid
> this experience in the future, I summarized my "understanding"
> in a short article:
>
> http://www.geocities.com/spur4444/prog/equality_in_lisp.html
[...]
> Disclaimer: the article is not complete. There are other comparison
> operators in Lisp (e.g. char=). For a full reference, the Hyperspec is
> required. However, the article should be useful for initial "getting
> it" stage.
You may also want to read this famous article, in case you haven't done
so already:
<http://www.nhplace.com/kent/PS/EQUAL.html>
Alberto
From: Robert Strandh
Subject: Re: a short article about equality in Lisp (for beginners)
Date:
Message-ID: <6wacx7tx90.fsf@serveur5.labri.fr>
Alberto Riva <···@nospam.chip.org> writes:
> You may also want to read this famous article, in case you haven't
> done so already:
>
> <http://www.nhplace.com/kent/PS/EQUAL.html>
Perhaps this is the moment to submit my modest proposal for a new
equality predicate + hash function. I am not entirely happy with the
name "key-situation", but aside from that, the proposal has been read
and fixed by a few LSM attendees. Anyway, let me know what you think.
Background
----------
The standard specifies only four types of hash tables possible,
according to whether the equality function is eq, eql, equal or
equalp. Many applications need to define their own key hashing
functions and key equality tests. This often becomes an exercise
in transforming the desired key into something that is acceptable to
one of these equality function.
This proposal is for extending the concepts of hashing and equality so
that the user can define application-specific extensions.
Proposal
--------
The idea is to introduce two new generic functions:
hash object situation [generic function]
eqv object1 object2 situation [generic function]
The crucial idea (perhaps not original) is the last argument, a
`key situation' which is an object that determines how objects are
compared or hashed. Client code will typically write methods on these
functions.
The hash function must return a nonnegative fixnum[1].
Client code must respect the following invariant:
(eqv object1 object2 situation)
implies
(= (hash object1 situation) (hash object2 situation))
There would be a number of predefined key situations, and methods to
compare objects in these situations.
For that, situations are organized into a hierarchy of CLOS classes.
key-situation [protocol class]
The base class for all key situations.
builtin-key-situation [class]
This class is a subclass of key-situation. All predefined situations
are subclasses of builtin-key-situation.
Client code is not allowed to alter or override the predefined methods
for hash and eqv. The reason is that an implementation should be able
to assume that it deals with the predefined methods and optimize
compiled code by inlining them.
eq-key-situation [class]
This class is a subclass of builtin-key-situation. When eqv is called
with an instance of this class as its third argument, it behaves like
eq with respect to the first two arguments.
+eq-key-situation+ [constant]
This constant contains an instance of the class eq-key-situation.
eql-key-situation [class]
This class is a subclass of builtin-key-situation. When eqv is called
with an instance of this class as its third argument, it behaves like
eql with respect to the first two arguments.
+eql-key-situation+ [constant]
This constant contains an instance of the class eql-key-situation.
equal-key-situation [class]
This class is a subclass of builtin-key-situation. When eqv is called
with an instance of this class as its third argument, it behaves like
equal with respect to the first two arguments.
+equal-key-situation+ [constant]
This constant contains an instance of the class equal-key-situation.
equalp-key-situation [class]
This class is a subclass of builtin-key-situation. When eqv is called
with an instance of this class as its third argument, it behaves like
equalp with respect to the first two arguments.
+equalp-key-situation+ [constant]
This constant contains an instance of the class equalp-key-situation.
case-sensitive-key-situation [class]
This class is a subclass of builtin-key-situation. It is defined only
when both object arguments are string designators. When eqv is called
with an instance of this class, then it behaves like string=.
+case-sensitive-key-situation+ [constant]
This constant contains an instance of the class
case-sensitive-key-situation.
case-insensitive-key-situation [class]
This class is a subclass of builtin-key-situation. It is defined only
when both object arguments string designators. When eqv is called
with an instance of this class, then it behaves like string-equal.
+case-insensitive-key-situation+ [constant]
This constant contains an instance of the class
case-insensitive-key-situation.
The proposal calls for a new type of hash table to be introduced:
make-generalized-hash-table situation [function]
returns a hash table that will call the `hash' generic function to
hash the keys that are inserted in the table, and `eqv' to compare
them. The situation that was passed to make-generalized-hash-table is
used as the last argument to these functions.
Two new functions are needed to access elements in the table, say:
htref table key [function]
(setf htref) object table key [function]
Acknowledgments
---------------
Thanks to Bruno Haible, Christophe Rhodes, Rudi Schlatte, and
Aleksandar Bakic for their invaluable comments about many aspects of
this proposal.
Notes
-----
[1] In most cases, the size of a fixnum is the size of a native
integer minus 2 or 3 bits, and a native integer is usually capable of
expressing the entire address space. It is therefore unlikely that
we would need more different hash codes that the number of objects
that will fit in the address space of the machine. And it is handy to
be able to assume that a nonnegative fixnum is returned for
performance reasons.
--
Robert Strandh
---------------------------------------------------------------------
Greenspun's Tenth Rule of Programming: any sufficiently complicated C
or Fortran program contains an ad hoc informally-specified bug-ridden
slow implementation of half of Common Lisp.
---------------------------------------------------------------------
Robert Strandh wrote:
> Perhaps this is the moment to submit my modest proposal for a new
> equality predicate + hash function. I am not entirely happy with the
> name "key-situation", but aside from that, the proposal has been read
> and fixed by a few LSM attendees. Anyway, let me know what you think.
[SNIP]
Looks good.
Like you I'm uneasy about "key-situation". What you have here
isn't really any sort of "situation", and isn't only for "keys";
it's a general notion of equivalence, which might have many
applications. Also, "situation" has another technical meaning
(in connection with conditions) which might be best avoided here.
How about a bit of mathematical terminology? Call your protocol
class "equivalence-relation" or maybe even just "equivalence".
Some other suggestions: "discriminator", "equality-context",
"key-context".
I think you should require some other invariants for the
"eqv" generic function: symmetry, reflexivity and transitivity.
I don't know whether this will actually make the hash-table
code any neater or more correct -- probably not -- but these
properties seem fundamental for anything that deserves to be
called a notion of equality or equivalence.
I have some concerns about efficiency, which probably aren't
very well founded. Consider an alternative proposal, where
a "notion of equivalence" is defined not by an object used
to adjust the behaviour of generic functions, but by a pair
of functions -- generic if need be -- implementing comparison
and hashing. In lesser languages, this would be the only way
to do it. It seems (though I've not benchmarked anything)
that your approach loses some speed for the sake of flexibility
(via subclassing situation classes) and namespace non-pollution
(because you have just two generic functions and no need to
define lots of others). I don't think the namespace pollution
is a real issue, so this is primarily about speed versus
flexibility. I bet you've thought carefully about this, so
could you make some comments about why your proposal needn't
be as slow as I'm worried it might be, and why the flexibility
it offers is useful?
(I don't mean to imply that there aren't any other advantages
of your proposal. I can see, e.g., that having equivalence
testing and hashing attached to a single object is more
convenient and less error-prone than separating them. And
maybe there's some benefit from being able to specialize
*other* generic functions on a key-situation, though right
now I can't think of any examples.)
CLOS method dispatch gives priority to earlier arguments.
Is there an efficiency gain to be had from making the
situation the *first* rather than the *last* argument to
HASH and EQV?
--
Gareth McCaughan
.sig under construc
From: Robert Strandh
Subject: Re: a short article about equality in Lisp (for beginners)
Date:
Message-ID: <6w4qnetj8i.fsf@serveur5.labri.fr>
Gareth McCaughan <················@pobox.com> writes:
> Looks good.
Thanks.
> Like you I'm uneasy about "key-situation". What you have here
> isn't really any sort of "situation", and isn't only for "keys";
Precisely.
> it's a general notion of equivalence, which might have many
> applications. Also, "situation" has another technical meaning
> (in connection with conditions) which might be best avoided here.
Ouch! I didn't catch that.
> How about a bit of mathematical terminology? Call your protocol
> class "equivalence-relation" or maybe even just "equivalence".
> Some other suggestions: "discriminator", "equality-context",
> "key-context".
I like "discriminator" the most. Thanks.
>
> I think you should require some other invariants for the
> "eqv" generic function: symmetry, reflexivity and transitivity.
> I don't know whether this will actually make the hash-table
> code any neater or more correct -- probably not -- but these
> properties seem fundamental for anything that deserves to be
> called a notion of equality or equivalence.
You are right, of course. Does the Common Lisp standard say anything
similar for "eq", "eql", etc.?
> I have some concerns about efficiency, which probably aren't
> very well founded.
I think they might be well founded. I do not propose to do away with
existing functions, especially "eq", "eql", and "=" which would still
have to be used when performance is an issue.
> Consider an alternative proposal, where
> a "notion of equivalence" is defined not by an object used
> to adjust the behaviour of generic functions, but by a pair
> of functions -- generic if need be -- implementing comparison
> and hashing. In lesser languages, this would be the only way
> to do it. It seems (though I've not benchmarked anything)
> that your approach loses some speed for the sake of flexibility
> (via subclassing situation classes) and namespace non-pollution
> (because you have just two generic functions and no need to
> define lots of others). I don't think the namespace pollution
> is a real issue, so this is primarily about speed versus
> flexibility. I bet you've thought carefully about this, so
> could you make some comments about why your proposal needn't
> be as slow as I'm worried it might be, and why the flexibility
> it offers is useful?
I am not too worried about performance as I pointed out before. I
consider the flexibility an advantage, especially since "eqv" is a
generic function and can use method combinations for things like
caching, etc.
> (I don't mean to imply that there aren't any other advantages
> of your proposal. I can see, e.g., that having equivalence
> testing and hashing attached to a single object is more
> convenient and less error-prone than separating them. And
> maybe there's some benefit from being able to specialize
> *other* generic functions on a key-situation, though right
> now I can't think of any examples.)
I agree. It *feels* like it could be useful in other situations.
Perhaps object copying and so called "serialization" would be
candidates.
> CLOS method dispatch gives priority to earlier arguments.
> Is there an efficiency gain to be had from making the
> situation the *first* rather than the *last* argument to
> HASH and EQV?
That's a thought. I don't know about that. Perhaps someone else
could comment on that.
Thanks for your comments.
--
Robert Strandh
---------------------------------------------------------------------
Greenspun's Tenth Rule of Programming: any sufficiently complicated C
or Fortran program contains an ad hoc informally-specified bug-ridden
slow implementation of half of Common Lisp.
---------------------------------------------------------------------
From: Christophe Rhodes
Subject: Re: a short article about equality in Lisp (for beginners)
Date:
Message-ID: <sqoelmovy4.fsf@cam.ac.uk>
Robert Strandh <·······@labri.fr> writes:
> Gareth McCaughan <················@pobox.com> writes:
>> CLOS method dispatch gives priority to earlier arguments.
>> Is there an efficiency gain to be had from making the
>> situation the *first* rather than the *last* argument to
>> HASH and EQV?
>
> That's a thought. I don't know about that. Perhaps someone else
> could comment on that.
If there's any such efficiency gain (which I'm not sure about), it
should also be achieved without changing the "API" by specifying the
argument-precedence-order of the generic functions in question.
Christophe
--
http://www-jcsu.jesus.cam.ac.uk/~csr21/ +44 1223 510 299/+44 7729 383 757
(set-pprint-dispatch 'number (lambda (s o) (declare (special b)) (format s b)))
(defvar b "~&Just another Lisp hacker~%") (pprint #36rJesusCollegeCambridge)
Robert Strandh <·······@labri.fr> wrote:
+---------------
| Perhaps this is the moment to submit my modest proposal for a new
| equality predicate + hash function.
...
| The standard specifies only four types of hash tables possible,
| according to whether the equality function is eq, eql, equal or equalp.
+---------------
Are you familiar with EXTENSIONS:DEFINE-HASH-TABLE-TEST in CMUCL?
(...and presumably in SBCL as well?)
The hash-tables defined by Common Lisp have limited utility
because they are limited to testing their keys using the equality
predicates provided by (pre-CLOS) Common Lisp. CMUCL overcomes
this limitation by allowing its users to specify new hash table
tests and hashing methods. The hashing method must also be
specified, since the compiler is unable to determine a good
hashing function for an arbitrary equality (equivalence) predicate.
[Function]
define-hash-table-test hash-table-test-name test-function hash-function
The hash-table-test-name must be a symbol. The test-function takes
two objects and returns true iff they are the same. The hash-function
takes one object and returns two values: the (positive fixnum) hash
value and true if the hashing depends on pointer values and will
have to be redone if the object moves.
To create a hash-table using this new ``test''
(really, a test/hash-function pair), use
(MAKE-HASH-TABLE :TEST hash-table-test-name ...).
I believe that this is a simpler protocol that does not require
introducing the notion of "situations" or the generic functions
they depend on.
As usual with CMUCL/SBCL, the code is available for perusal and/or
re-use in other implementations.
-Rob
-----
Rob Warnock <····@rpw3.org>
627 26th Avenue <URL:http://rpw3.org/>
San Mateo, CA 94403 (650)572-2607
From: Robert Strandh
Subject: Re: a short article about equality in Lisp (for beginners)
Date:
Message-ID: <6w8ycqtkgr.fsf@serveur5.labri.fr>
····@rpw3.org (Rob Warnock) writes:
> Are you familiar with EXTENSIONS:DEFINE-HASH-TABLE-TEST in CMUCL?
> (...and presumably in SBCL as well?)
Yes, I am familiar with that extension.
> I believe that this is a simpler protocol that does not require
> introducing the notion of "situations" or the generic functions
> they depend on.
Well, actually I saw using a generic fuction as a feature.
--
Robert Strandh
---------------------------------------------------------------------
Greenspun's Tenth Rule of Programming: any sufficiently complicated C
or Fortran program contains an ad hoc informally-specified bug-ridden
slow implementation of half of Common Lisp.
---------------------------------------------------------------------
Robert Strandh wrote:
> Perhaps this is the moment to submit my modest proposal for a new
> equality predicate + hash function. I am not entirely happy with the
> name "key-situation", but aside from that, the proposal has been read
> and fixed by a few LSM attendees. Anyway, let me know what you think.
Your proposal seems too complicated for my taste, but maybe there is
some hidden complexity I am missing. However, as far as I understand,
what make-hash-table already does is to determine the hash function
according to the equivalence predicate that is passed to it. What about
just offering a way to "register" more of those, for example via a
generic function?
(defgeneric hash-function (equivalence-predicate))
(defmethod hash-function ((ep (eql #'my-equal)))
#'my-hash-function))
And then of course, make-hash-table has to call this function in order
to determine the hash function. Wouldn't that be good enough?
Pascal
--
Tyler: "How's that working out for you?"
Jack: "Great."
Tyler: "Keep it up, then."
From: Marco Antoniotti
Subject: Re: a short article about equality in Lisp (for beginners)
Date:
Message-ID: <tYqSc.10$D5.6227@typhoon.nyu.edu>
This seems like a nice solution. It seems to me that it is less
invasive. Of course you always have to specify what a "good" hash
function is.
Cheers
Marco
Pascal Costanza wrote:
>
> Robert Strandh wrote:
>
>> Perhaps this is the moment to submit my modest proposal for a new
>> equality predicate + hash function. I am not entirely happy with the
>> name "key-situation", but aside from that, the proposal has been read
>> and fixed by a few LSM attendees. Anyway, let me know what you think.
>
>
> Your proposal seems too complicated for my taste, but maybe there is
> some hidden complexity I am missing. However, as far as I understand,
> what make-hash-table already does is to determine the hash function
> according to the equivalence predicate that is passed to it. What about
> just offering a way to "register" more of those, for example via a
> generic function?
>
> (defgeneric hash-function (equivalence-predicate))
>
> (defmethod hash-function ((ep (eql #'my-equal)))
> #'my-hash-function))
>
> And then of course, make-hash-table has to call this function in order
> to determine the hash function. Wouldn't that be good enough?
>
>
> Pascal
>
>
On Fri, 06 Aug 2004 20:04:54 -0400, Alberto Riva wrote:
> You may also want to read this famous article, in case you haven't done
> so already:
>
> <http://www.nhplace.com/kent/PS/EQUAL.html>
And this one:
http://home.pipeline.com/~hbaker1/ObjectIdentity.html
--
__("< Marcin Kowalczyk
\__/ ······@knm.org.pl
^^ http://qrnik.knm.org.pl/~qrczak/
Eli Bendersky's webpage
http://www.geocities.com/spur4444/prog/equality_in_lisp.html
proposes a context for understanding CL's equality tests:
What all this plethora of comparison options is good
for, you may ask. The answer is - flexibility. Other
than differing in their abilities, the Lisp equality
operators differ in their efficiency. As you can guess,
eq is the fastest. It's only a pointer comparison:
nothing smart. The other operators have special cases,
hence they are slower. On the other hand, you probably
don't want to use eq on anything other than symbols.
Common Lisp the Language, Second Edition, pp 109, (CLtL2),
makes a different point.
As part of the X3J13 discussion of this issue the
following observations were made. Object equality is
not a concept for which there is a uniquely determined
correct algorithm. The appropriateness of an equality
predicate can be judged only in the context of the needs
of some particular program. Although these functions
take any type of argument and their names sound very
generic, EQUAL and EQUALP are not appropriate for every
application. Any decision to use or not use them should
be determined by what they are documented to do rather
than by any abstract characterization of their
function. If neither EQUAL nor EQUALP is found to be
appropriate in a particular situation, programmers are
encouraged to create another operator that is
appropriate rather than blame EQUAL or EQUALP for
"doing the wrong thing."
Hmm, I think I see what they are getting at. For example
(defvar a1 '((a . 5)(b . 7)))
(defvar a2 '((b . 7)(a . 5)))
(equal a1 a2) => NIL
(equalp a1 a2) => NIL
if we think of a1 and a2 as association lists we might want
them to be considered to be equal, so we roll our own
(defun assoc-keys (al)
(remove-duplicates
(mapcar (function car) al)))
(defun assoc-subsume-p (inferior superior)
(every (lambda(key)
(equal (assoc key inferior)
(assoc key superior)))
(assoc-keys inferior)))
(defun assoc-equal (x y)
(and (assoc-subsume-p x y)
(assoc-subsume-p y x)))
(assoc-equal a1 a2) => T
But what about
(defvar a3 '((a . 5)(b . 7)(a . 3)))
(defvar a4 '((a . 5)(b . 7)(c . 3)))
(assoc-equal a1 a3) => T
(assoc-equal a1 a4) => NIL
My assoc-equal treats the assoc-list as a stack of bindings,
so a=3 is shadowed and a1 = a3, but c=3 is an extra binding so
a1 =/= a4.
Is that right? Perhaps the assoc-equal in your program
must check that the shadowed bindings exist and agree.
When X3J13 say
The appropriateness of an equality predicate can be
judged only in the context of the needs of some
particular program.
I think they have code such as assoc-equal in mind. The five
built-in predicates (=, eq, eql, equal, equalp) are intended
as a basic tool kit to get you started. The details of how
equal and equalp recursively descend into substructure
strike me as the first words on the issue, not the last.
Alan Crowe
Edinburgh
Scotland
From: Kalle Olavi Niemitalo
Subject: Re: a short article about equality in Lisp (for beginners)
Date:
Message-ID: <87ekmjykam.fsf@Astalo.kon.iki.fi>
Alan Crowe <····@cawtech.freeserve.co.uk> writes:
> Perhaps the assoc-equal in your program
> must check that the shadowed bindings exist and agree.
I don't see why it should. The shadowed bindings matter only if
one is allowed to pop conses off the head of the alist. But if
you allow that, then (assoc-equal a1 a2) should return false too,
because (assoc-equal (cdr a1) (cdr a2)) is false. And then one
can just use EQUAL.
In article <··········@odak26.prod.google.com>, Eli Bendersky wrote:
> I came back to playing with Lisp recently, and naturally I discovered
> that I forgot how Lisp's equality operators - eq, eql, equal and equalp
> differ. To completely understand it,
> I referred to the Hyperspec and two Lisp books. To avoid
> this experience in the future, I summarized my "understanding"
> in a short article:
>
> http://www.geocities.com/spur4444/prog/equality_in_lisp.html
You say
Additionally, eq ignores the types of numbers (unlike =).
I would say that eq *doesn't* ignore the type of numbers, whereas =
*does*: two numbers of different types can still be =. So, on some
implementations (eq 4 4), and (eq 4.0 4.0), and some not[1], but on no
implementation is it true that (eq 4 4.0), whereas on every
implementation it should be true that (= 4 4.0)
-- Larry
[1] And on some implementations (eq 4.0 4.0) and (not (eq 4.0 4.0)) at
different times, e.g. cmucl:
USER> (eq 1.0 1.0)
NIL
USER> (defun foo () (eq 1.0 1.0))
FOO
USER> (foo)
T
In the case of cmucl (as I understand it), this happens because it
interprets the (eq 1.0 1.0), whereas it compiles (slightly; not to
machine code) the function FOO.
>>>>> "Larry" == Larry Clapp <·····@theclapp.org> writes:
Larry> [1] And on some implementations (eq 4.0 4.0) and (not (eq 4.0
Larry> 4.0)) at different times, e.g. cmucl:
USER> (eq 1.0 1.0)
Larry> NIL
USER> (defun foo () (eq 1.0 1.0))
Larry> FOO
USER> (foo)
Larry> T
Larry> In the case of cmucl (as I understand it), this happens
Larry> because it interprets the (eq 1.0 1.0), whereas it compiles
Larry> (slightly; not to machine code) the function FOO.
I guess such a thing could make people wonder if they should ever use
Lisp (or at least cmucl). One simple expression (eq 1.0 1.0) evaluating
to different results depending on where in the code you use it. Creepy.
--
lrnr
lrnr <··@nospam.com> writes:
> I guess such a thing could make people wonder if they should ever use
> Lisp (or at least cmucl). One simple expression (eq 1.0 1.0) evaluating
> to different results depending on where in the code you use it. Creepy.
Well, if languages were rejeted for their creepiness factor, I doubt
so many people would use C.
--
__Pascal Bourguignon__ http://www.informatimago.com/
Our enemies are innovative and resourceful, and so are we. They never
stop thinking about new ways to harm our country and our people, and
neither do we.
>>>>> "Pascal" == Pascal Bourguignon <····@mouse-potato.com> writes:
Pascal> lrnr <··@nospam.com> writes:
>> I guess such a thing could make people wonder if they should ever
>> use Lisp (or at least cmucl). One simple expression (eq 1.0 1.0)
>> evaluating to different results depending on where in the code
>> you use it. Creepy.
Pascal> Well, if languages were rejeted for their creepiness factor,
Pascal> I doubt so many people would use C.
I agree. I've been learning Lisp for the last couple of years. I like it
and one single quirk in a particular implementation wouldn't make me
reject it. I am just saying that such quirks can lead to very
unpleasant surprises, which could push people to give up on Lisp.
--
lrnr
lrnr wrote:
>>>>>>"Pascal" == Pascal Bourguignon <····@mouse-potato.com> writes:
>
> Pascal> lrnr <··@nospam.com> writes:
> >> I guess such a thing could make people wonder if they should ever
> >> use Lisp (or at least cmucl). One simple expression (eq 1.0 1.0)
> >> evaluating to different results depending on where in the code
> >> you use it. Creepy.
>
> Pascal> Well, if languages were rejeted for their creepiness factor,
> Pascal> I doubt so many people would use C.
>
> I agree. I've been learning Lisp for the last couple of years. I like it
> and one single quirk in a particular implementation wouldn't make me
> reject it. I am just saying that such quirks can lead to very
> unpleasant surprises, which could push people to give up on Lisp.
It's important to note that almost every language has issues wrt
equality / equivalence. C-based languages usually get 1.0 == 1.0 right
just because they restrict the possible representation of numbers from
the outset. A fair comparison would be with so-called "boxed" values in
those languages, and then you have exactly the same issues there. It's
just that the language specs don't talk about it.
See for example http://citeseer.ist.psu.edu/grogono00copying.html for
some insights.
Pascal
--
Tyler: "How's that working out for you?"
Jack: "Great."
Tyler: "Keep it up, then."
From: Karl A. Krueger
Subject: Re: a short article about equality in Lisp (for beginners)
Date:
Message-ID: <cf6prl$1ko$1@baldur.whoi.edu>
Pascal Costanza <········@web.de> wrote:
> It's important to note that almost every language has issues wrt
> equality / equivalence. C-based languages usually get 1.0 == 1.0 right
> just because they restrict the possible representation of numbers from
> the outset. A fair comparison would be with so-called "boxed" values in
> those languages, and then you have exactly the same issues there. It's
> just that the language specs don't talk about it.
Consider Python, which has integers, long integers, and floats ... and
allows you to specify which representation you want when you enter a
literal number. "1" yields the integer 1, "1L" yields the long integer
1. Overflowing integers gets you longs just as overflowing fixnums in
CL gets you bignums.
Python also has equality and identity predicates, and they behave as
such:
>>> 1 is 1L
False
>>> 1 == 1L
True
>>> 1 is 1.0
False
>>> 1 == 1.0
True
--
Karl A. Krueger <········@example.edu>
Woods Hole Oceanographic Institution
Email address is spamtrapped. s/example/whoi/
"Outlook not so good." -- Magic 8-Ball Software Reviews
From: Peter Seibel
Subject: Re: a short article about equality in Lisp (for beginners)
Date:
Message-ID: <m3wu0a3dkv.fsf@javamonkey.com>
lrnr <··@nospam.com> writes:
>>>>>> "Larry" == Larry Clapp <·····@theclapp.org> writes:
>
>
> Larry> [1] And on some implementations (eq 4.0 4.0) and (not (eq 4.0
> Larry> 4.0)) at different times, e.g. cmucl:
>
> USER> (eq 1.0 1.0)
> Larry> NIL
>
> USER> (defun foo () (eq 1.0 1.0))
> Larry> FOO
>
> USER> (foo)
> Larry> T
>
> Larry> In the case of cmucl (as I understand it), this happens
> Larry> because it interprets the (eq 1.0 1.0), whereas it compiles
> Larry> (slightly; not to machine code) the function FOO.
>
> I guess such a thing could make people wonder if they should ever use
> Lisp (or at least cmucl). One simple expression (eq 1.0 1.0) evaluating
> to different results depending on where in the code you use it. Creepy.
So the real problem here is that folks think expressions that use EQ
are "simple". But EQ is really quite a strange beast that is the way
it is in order to allow certain optimizations when you *know* you're
not dealing with numbers or characters. If everyone just forgot about
EQ and used EQL all the time then we wouldn't have these problems.
-Peter
--
Peter Seibel ·····@javamonkey.com
Lisp is the red pill. -- John Fraser, comp.lang.lisp
From: Coby Beck
Subject: Re: a short article about equality in Lisp (for beginners)
Date:
Message-ID: <ySfRc.45345$hw6.5614@edtnps84>
"lrnr" <··@nospam.com> wrote in message
···················@localhost.localdomain...
> >>>>> "Larry" == Larry Clapp <·····@theclapp.org> writes:
Larry> In the case of cmucl (as I understand it), this happens
> Larry> because it interprets the (eq 1.0 1.0), whereas it compiles
> Larry> (slightly; not to machine code) the function FOO.
>
> I guess such a thing could make people wonder if they should ever use
> Lisp (or at least cmucl). One simple expression (eq 1.0 1.0) evaluating
> to different results depending on where in the code you use it. Creepy.
A couple of steps to consider before concluding Lisp is creepy:
1. Wonder, investigate and then understand why. OR...
2. Read the spec, it is very clear that EQ comparisons of numbers has some
undefined consequences. OR...
3. Accept the common knowledge that EQ is not meant for numbers. OR...
4. Follow standard advice and don't ever use EQ unless you know you really
want to.
I remember seeing (or 0 0) => t and being surprised bordering on outraged
but that was a while ago when I still knew everything.
--
Coby Beck
(remove #\Space "coby 101 @ big pond . com")
From: Kalle Olavi Niemitalo
Subject: Re: a short article about equality in Lisp (for beginners)
Date:
Message-ID: <87u0vep4jx.fsf@Astalo.kon.iki.fi>
"Coby Beck" <·····@mercury.bc.ca> writes:
> I remember seeing (or 0 0) => t and being surprised bordering on outraged
> but that was a while ago when I still knew everything.
Which Lisp was that? My guess is Linj.
Kalle Olavi Niemitalo <···@iki.fi> wrote:
+---------------
| "Coby Beck" <·····@mercury.bc.ca> writes:
| > I remember seeing (or 0 0) => t and being surprised bordering on outraged
| > but that was a while ago when I still knew everything.
|
| Which Lisp was that? My guess is Linj.
+---------------
For any real Lisp, of course, (OR 0 0) => 0, but maybe he just meant
that (IF 0 T NIL) => T is initially surprising to C programmers.
-Rob
-----
Rob Warnock <····@rpw3.org>
627 26th Avenue <URL:http://rpw3.org/>
San Mateo, CA 94403 (650)572-2607
From: Kalle Olavi Niemitalo
Subject: Re: a short article about equality in Lisp (for beginners)
Date:
Message-ID: <87oellpk60.fsf@Astalo.kon.iki.fi>
····@rpw3.org (Rob Warnock) writes:
> For any real Lisp, of course, (OR 0 0) => 0
Apparently not AutoLISP, though.
<http://xarch.tu-graz.ac.at/autocad/docs/and-bug.html>
Kalle Olavi Niemitalo <···@iki.fi> wrote in message news:<··············@Astalo.kon.iki.fi>...
> ····@rpw3.org (Rob Warnock) writes:
>
> > For any real Lisp, of course, (OR 0 0) => 0
>
> Apparently not AutoLISP, though.
> <http://xarch.tu-graz.ac.at/autocad/docs/and-bug.html>
AutoLISP: (OR 0 0) => nil
even "without short-circuit evaluation" (aka "and-bug").
From: Coby Beck
Subject: Re: a short article about equality in Lisp (for beginners)
Date:
Message-ID: <aPwRc.50323$hw6.25938@edtnps84>
"Rob Warnock" <····@rpw3.org> wrote in message
···························@speakeasy.net...
> Kalle Olavi Niemitalo <···@iki.fi> wrote:
> +---------------
> | "Coby Beck" <·····@mercury.bc.ca> writes:
> | > I remember seeing (or 0 0) => t and being surprised bordering on
outraged
> | > but that was a while ago when I still knew everything.
> |
> | Which Lisp was that? My guess is Linj.
> +---------------
>
> For any real Lisp, of course, (OR 0 0) => 0, but maybe he just meant
> that (IF 0 T NIL) => T is initially surprising to C programmers.
Sorry for that...Rob guessed my point. The Lisp was ACL 3.0 and it probably
was (OR 0 0) => 0 my only point being I had expected a NIL.
--
Coby Beck
(remove #\Space "coby 101 @ big pond . com")
From: Alain Picard
Subject: Re: a short article about equality in Lisp (for beginners)
Date:
Message-ID: <87k6w9j4y0.fsf@memetrics.com>
lrnr <··@nospam.com> writes:
> I guess such a thing could make people wonder if they should ever use
> Lisp (or at least cmucl). One simple expression (eq 1.0 1.0) evaluating
> to different results depending on where in the code you use it. Creepy.
Seems to me the only thing creepy about (eq 1 1) => NIL is
a misunderstanding about the intended semantic of the EQ
function. Someone coming to lisp for the first time might
be forgiven for associating EQ with the "mathematical equal" (i.e. `=')
but a perusal of the spec should dispel that notion fairly quickly.
From: Marco Antoniotti
Subject: Re: a short article about equality in Lisp (for beginners)
Date:
Message-ID: <sZqSc.11$D5.6227@typhoon.nyu.edu>
lrnr wrote:
>>>>>>"Larry" == Larry Clapp <·····@theclapp.org> writes:
>
>
>
> Larry> [1] And on some implementations (eq 4.0 4.0) and (not (eq 4.0
> Larry> 4.0)) at different times, e.g. cmucl:
>
> USER> (eq 1.0 1.0)
> Larry> NIL
>
> USER> (defun foo () (eq 1.0 1.0))
> Larry> FOO
>
> USER> (foo)
> Larry> T
>
> Larry> In the case of cmucl (as I understand it), this happens
> Larry> because it interprets the (eq 1.0 1.0), whereas it compiles
> Larry> (slightly; not to machine code) the function FOO.
>
> I guess such a thing could make people wonder if they should ever use
> Lisp (or at least cmucl). One simple expression (eq 1.0 1.0) evaluating
> to different results depending on where in the code you use it. Creepy.
Are we in need of a bit of RTFM here? :)
Cheers
--
Marco