Common Lisp the Language, 2nd Edition


next up previous contents index
Next: Logical Operators Up: Predicates Previous: Specific Data Type

6.3. Equality Predicates

Common Lisp provides a spectrum of predicates for testing for equality of two objects: eq (the most specific), eql, equal, and equalp (the most general). eq and equal have the meanings traditional in Lisp. eql was added because it is frequently needed, and equalp was added primarily in order to have a version of equal that would ignore type differences when comparing numbers and case differences when comparing characters. If two objects satisfy any one of these equality predicates, then they also satisfy all those that are more general.


[Function]
eq x y

(eq x y) is true if and only if x and y are the same identical object. (Implementationally, x and y are usually eq if and only if they address the same identical memory location.)

It should be noted that things that print the same are not necessarily eq to each other. Symbols with the same print name usually are eq to each other because of the use of the intern function. However, numbers with the same value need not be eq, and two similar lists are usually not eq. For example:

(eq 'a 'b) is false. 
(eq 'a 'a) is true. 
(eq 3 3) might be true or false, depending on the implementation. 
(eq 3 3.0) is false. 
(eq 3.0 3.0) might be true or false, depending on the implementation. 
(eq #c(3 -4) #c(3 -4)) 
  might be true or false, depending on the implementation. 
(eq #c(3 -4.0) #c(3 -4)) is false. 
(eq (cons 'a 'b) (cons 'a 'c)) is false. 
(eq (cons 'a 'b) (cons 'a 'b)) is false. 
(eq '(a . b) '(a . b)) might be true or false. 
(progn (setq x (cons 'a 'b)) (eq x x)) is true. 
(progn (setq x '(a . b)) (eq x x)) is true. 
(eq #\A #\A) might be true or false, depending on the implementation. 
(eq "Foo" "Foo") might be true or false. 
(eq "Foo" (copy-seq "Foo")) is false. 
(eq "FOO" "foo") is false.

In Common Lisp, unlike some other Lisp dialects, the implementation is permitted to make ``copies'' of characters and numbers at any time. (This permission is granted because it allows tremendous performance improvements in many common situations.) The net effect is that Common Lisp makes no guarantee that eq will be true even when both its arguments are ``the same thing'' if that thing is a character or number. For example:

(let ((x 5)) (eq x x)) might be true or false.

The predicate eql is the same as eq, except that if the arguments are characters or numbers of the same type then their values are compared. Thus eql tells whether two objects are conceptually the same, whereas eq tells whether two objects are implementationally identical. It is for this reason that eql, not eq, is the default comparison predicate for the sequence functions defined in chapter 14.


Implementation note: eq simply compares the two given pointers, so any kind of object that is represented in an ``immediate'' fashion will indeed have like-valued instances satisfy eq. In some implementations, for example, fixnums and characters happen to ``work.'' However, no program should depend on this, as other implementations of Common Lisp might not use an immediate representation for these data types.

old_change_begin
An additional problem with eq is that the implementation is permitted to ``collapse'' constants (or portions thereof) appearing in code to be compiled if they are equal. An object is considered to be a constant in code to be compiled if it is a self-evaluating form or is contained in a quote form. This is why (eq "Foo" "Foo") might be true or false; in interpreted code it would normally be false, because reading in the form (eq "Foo" "Foo") would construct distinct strings for the two arguments to eq, but the compiler might choose to use the same identical string or two distinct copies as the two arguments in the call to eq. Similarly, (eq '(a . b) '(a . b)) might be true or false, depending on whether the constant conses appearing in the quote forms were collapsed by the compiler. However, (eq (cons 'a 'b) (cons 'a 'b)) is always false, because every distinct call to the cons function necessarily produces a new and distinct cons.
old_change_end

change_begin
X3J13 voted in March 1989 (QUOTE-SEMANTICS)   to clarify that eval and compile are not permitted either to copy or to coalesce (``collapse'') constants (see eq) appearing in the code they process; the resulting program behavior must refer to objects that are eql to the corresponding objects in the source code. Only the compile-file/load process is permitted to copy or coalesce constants (see section 25.1).
change_end


[Function]
eql x y

The eql predicate is true if its arguments are eq, or if they are numbers of the same type with the same value, or if they are character objects that represent the same character. For example:

(eql 'a 'b) is false. 
(eql 'a 'a) is true. 
(eql 3 3) is true. 
(eql 3 3.0) is false. 
(eql 3.0 3.0) is true. 
(eql #c(3 -4) #c(3 -4)) is true. 
(eql #c(3 -4.0) #c(3 -4)) is false. 
(eql (cons 'a 'b) (cons 'a 'c)) is false. 
(eql (cons 'a 'b) (cons 'a 'b)) is false. 
(eql '(a . b) '(a . b)) might be true or false. 
(progn (setq x (cons 'a 'b)) (eql x x)) is true. 
(progn (setq x '(a . b)) (eql x x)) is true. 
(eql #\A #\A) is true. 
(eql "Foo" "Foo") might be true or false. 
(eql "Foo" (copy-seq "Foo")) is false. 
(eql "FOO" "foo") is false.

Normally (eql 1.0s0 1.0d0) would be false, under the assumption that 1.0s0 and 1.0d0 are of distinct data types. However, implementations that do not provide four distinct floating-point formats are permitted to ``collapse'' the four formats into some smaller number of them; in such an implementation (eql 1.0s0 1.0d0) might be true. The predicate = will compare the values of two numbers even if the numbers are of different types.

If an implementation supports positive and negative zeros as distinct values (as in the IEEE proposed standard floating-point format), then (eql 0.0 -0.0) will be false. Otherwise, when the syntax -0.0 is read it will be interpreted as the value 0.0, and so (eql 0.0 -0.0) will be true. The predicate = differs from eql in that (= 0.0 -0.0) will always be true, because = compares the mathematical values of its operands, whereas eql compares the representational values, so to speak.

Two complex numbers are considered to be eql if their real parts are eql and their imaginary parts are eql. For example, (eql #C(4 5) #C(4 5)) is true and (eql #C(4 5) #C(4.0 5.0)) is false. Note that while (eql #C(5.0 0.0) 5.0) is false, (eql #C(5 0) 5) is true. In the case of (eql #C(5.0 0.0) 5.0) the two arguments are of different types and so cannot satisfy eql; that's all there is to it. In the case of (eql #C(5 0) 5), however, #C(5 0) is not a complex number but is always automatically reduced by the rule of complex canonicalization to the integer 5, just as the apparent ratio 20/4 is always simplified to 5.

The case of (eql "Foo" "Foo") is discussed above in the description of eq. While eql compares the values of numbers and characters, it does not compare the contents of strings. To compare the characters of two strings, one should use equal, equalp, string=, or string-equal.


Compatibility note: The Common Lisp function eql is similar to the Interlisp function eqp. However, eql considers 3 and 3.0 to be different, whereas eqp considers them to be the same; eqp behaves like the Common Lisp = function, not like eql, when both arguments are numbers.


[Function]
equal x y

The equal predicate is true if its arguments are structurally similar (isomorphic) objects. A rough rule of thumb is that two objects are equal if and only if their printed representations are the same.

Numbers and characters are compared as for eql. Symbols are compared as for eq. This method of comparing symbols can violate the rule of thumb for equal and printed representations, but only in the infrequently occurring case of two distinct symbols with the same print name.

Certain objects that have components are equal if they are of the same type and corresponding components are equal. This test is implemented in a recursive manner and may fail to terminate for circular structures.

For conses, equal is defined recursively as the two car's being equal and the two cdr's being equal.

Two arrays are equal only if they are eq, with one exception: strings and bit-vectors are compared element-by-element. If either argument has a fill pointer, the fill pointer limits the number of elements examined by equal. Uppercase and lowercase letters in strings are considered by equal to be distinct. (In contrast, equalp ignores case distinctions in strings.)


Compatibility note: In Lisp Machine Lisp, equal ignores the difference between uppercase and lowercase letters in strings. This violates the rule of thumb about printed representations, however, which is very useful, especially to novices. It is also inconsistent with the treatment of single characters, which in Lisp Machine Lisp are represented as fixnums.

Two pathname objects are equal if and only if all the corresponding components (host, device, and so on) are equivalent. (Whether or not uppercase and lowercase letters are considered equivalent in strings appearing in components depends on the file name conventions of the file system.) Pathnames that are equal should be functionally equivalent.

change_begin
X3J13 voted in June 1989 (EQUAL-STRUCTURE)   to clarify that equal never recursively descends any structure or data type other than the ones explicitly described above: conses, bit-vectors, strings, and pathnames. Numbers and characters are compared as if by eql, and all other data objects are compared as if by eq.
change_end

(equal 'a 'b) is false. 
(equal 'a 'a) is true. 
(equal 3 3) is true. 
(equal 3 3.0) is false. 
(equal 3.0 3.0) is true. 
(equal #c(3 -4) #c(3 -4)) is true. 
(equal #c(3 -4.0) #c(3 -4)) is false. 
(equal (cons 'a 'b) (cons 'a 'c)) is false. 
(equal (cons 'a 'b) (cons 'a 'b)) is true. 
(equal '(a . b) '(a . b)) is true. 
(progn (setq x (cons 'a 'b)) (equal x x)) is true. 
(progn (setq x '(a . b)) (equal x x)) is true. 
(equal #\A #\A) is true. 
(equal "Foo" "Foo") is true. 
(equal "Foo" (copy-seq "Foo")) is true. 
(equal "FOO" "foo") is false.

To compare a tree of conses using eql (or any other desired predicate) on the leaves, use tree-equal.


[Function]
equalp x y

Two objects are equalp if they are equal; if they are characters and satisfy char-equal, which ignores alphabetic case and certain other attributes of characters; if they are numbers and have the same numerical value, even if they are of different types; or if they have components that are all equalp.

Objects that have components are equalp if they are of the same type and corresponding components are equalp. This test is implemented in a recursive manner and may fail to terminate for circular structures. For conses, equalp is defined recursively as the two car's being equalp and the two cdr's being equalp.

Two arrays are equalp if and only if they have the same number of dimensions, the dimensions match, and the corresponding components are equalp. The specializations need not match; for example, a string and a general array that happens to contain the same characters will be equalp (though definitely not equal). If either argument has a fill pointer, the fill pointer limits the number of elements examined by equalp. Because equalp performs element-by-element comparisons of strings and ignores the alphabetic case of characters, case distinctions are therefore also ignored when equalp compares strings.

Two symbols can be equalp only if they are eq, that is, the same identical object.

change_begin
X3J13 voted in June 1989 (EQUAL-STRUCTURE)   to specify that equalp compares components of hash tables (see below), and to clarify that otherwise equalp never recursively descends any structure or data type other than the ones explicitly described above: conses, arrays (including bit-vectors and strings), and pathnames. Numbers are compared for numerical equality (see =), characters are compared as if by char-equal, and all other data objects are compared as if by eq.

Two hash tables are considered the same by equalp if and only if they satisfy a four-part test:

The four parts of this test are carried out in the order shown, and if some part of the test fails, equalp returns nil and the other parts of the test are not attempted.

If equalp must compare two structures and the defstruct definition for one used the :type option and the other did not, then equalp returns nil.

If equalp must compare two structures and neither defstruct definition used the :type option, then equalp returns t if and only if the structures have the same type (that is, the same defstruct name) and the values of all corresponding slots (slots having the same name) are equalp.

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.''

Note that one consequence of the vote to change the rules of floating-point contagion (CONTAGION-ON-NUMERICAL-COMPARISONS)   (described in section 12.1) is to make equalp a true equivalence relation on numbers.
change_end

(equalp 'a 'b) is false. 
(equalp 'a 'a) is true. 
(equalp 3 3) is true. 
(equalp 3 3.0) is true. 
(equalp 3.0 3.0) is true. 
(equalp #c(3 -4) #c(3 -4)) is true. 
(equalp #c(3 -4.0) #c(3 -4)) is true. 
(equalp (cons 'a 'b) (cons 'a 'c)) is false. 
(equalp (cons 'a 'b) (cons 'a 'b)) is true. 
(equalp '(a . b) '(a . b)) is true. 
(progn (setq x (cons 'a 'b)) (equalp x x)) is true. 
(progn (setq x '(a . b)) (equalp x x)) is true. 
(equalp #\A #\A) is true. 
(equalp "Foo" "Foo") is true. 
(equalp "Foo" (copy-seq "Foo")) is true. 
(equalp "FOO" "foo") is true.



next up previous contents index
Next: Logical Operators Up: Predicates Previous: Specific Data Type


AI.Repository@cs.cmu.edu