University of Washington
Department of Computer Science and Engineering

CSE573–Artificial Intelligence

Winter 1998

 

Some Notes on Equality Testing in LISP

 

Testing whether two objects are "equal" in LISP can be somewhat complicated, as there are several things the statement "two objects are equal" can mean in the first place.

 

There are two senses in which two objects can be equal:

  1. In the strongest sense two objects are equal if and only if they occupy the same area of memory.
  2. In a weaker sense, two objects can be "similar" in some type-specific way. For example, two numbers are said to be equal if they have the same numeric value, two characters are said to be equal if they have the same ASCII value, two strings are said to be equal if they are the same character for character, and so on.

 

The first sense is stronger than the second in that any two objects that are equal in the first sense are also equal in the second sense, but the converse is not necessarily true.

 

The EQ Predicate

 

There is one predicate in LISP that tests equality in the strong sense, and several that test equality in the weak sense, since weak equality depends on the objects' data types.

 

Strong equality is tested using the predicate EQ. For any two objects o1 and o2, (EQ o1 o2) is true if and only if o1 and o2 occupy the same area of memory. The following cases demonstrate this form of equality.

 

(setf v1 '(any list or other object))

(setf v2 v1) ; Now v1 and v2 point to the same list

 

(defun eq-to-v1-p (input-argument)

(eq input-argument v1))

 

(eq v1 v2) => T

(eq-to-v1-p v1) => T

(eq-to-v1-p v2) => T

 

Two lists can look alike but not be EQ, however, because whenever a list is constructed, new memory is allocated to store it.

 

(setf v3 '(any list or other object)) ; v3 looks just like v1

(eq v1 v3) => NIL

 

Equality of Symbols

 

Suppose now that v1 and v2 were bound to symbols, not to lists. How would we test whether they were equal? The answer is that you use EQ, but it's not clear why that should work. After all, I just said that two lists can look just the same but be stored separately. This is not the case for symbols, however. Two symbols with the same print name are guaranteed to be EQ. So the example above when applied to symbols looks like this:

 

(setf v1 'any-symbol-at-all)

(setf v2 v1)

(setf v3 'any-symbol-at-all)

 

(eq v1 v2) => T

(eq v1 v3) => T

 

The first example is expected: once again, v1 and v2 point to exactly the same object. The second example behaves differently for symbols than it does for lists. Since v1 and v3 are bound to symbols with the same name, they must be EQ.

 

Therefore if you want to know whether two symbols are equal, use (EQ symbol1 symbol2).

 

The EQL Predicate

 

The predicate (EQL object1 object2) is slightly weaker than EQ. It is defined as follows:

  1. If (EQ object1 object2) is true, then (EQL object1 object2) is true as well.
  2. (EQL char1 char2) is true if char1 and char2 are identical characters (this is case sensitive)
  3. (EQL num1 num2) is true is num1 and num2 are numbers of the same type, and are numerically equal.

 

Here are some examples:

 

(EQL 'A 'A) => T

(EQL 'A 'B) => NIL

(EQL #\a #\a) => T

(EQL #\a #\A) => NIL

(EQL 4 4) => T

(EQL 4.2 4.2) => T

(EQL 4 4.0) => NIL

 

Notice the last example, where the two objects are not EQL even though they are numerically equal. One is an integer and one is a real number, so they do not have the same data type. This means that EQL is probably not a good predicate to use to test whether two numbers are equal. But it is good for symbols and characters.

 

The = Predicate

 

As you might imagine, the function = is appropriate for testing whether two numbers are numerically equal. It does not require that the numbers be the of the same type; it will convert the numbers to the most specific common numeric type, then compare them using EQL.

 

(= 4 4.0) => T

(= 4 'A) => Generates an error.

 

Notice the last example sets = apart from EQ and EQL. The last two predicates will never cause an error, regardless of what object appears as their arguments. The = predicate complains if either of its arguments are non-numeric, so it should only be used when the arguments are guaranteed to be numbers.

 

The EQUAL Predicate

 

EQUAL is a weaker predicate than EQ or EQL: any two objects that are EQL are also EQUAL. EQUAL is specifically intended to compare sequences, particularly lists and strings.

Recall that two lists of symbols are not EQ or EQL if they do not share memory. So,

 

(EQ '(A B C) '(A B C)) => NIL

(EQL "abc" "abc") => NIL

 

But these two lists and two strings are equal in the sense that (1) they have the same data type, and (2) they have the same number of elements, and (3) corresponding elements in the two sequences are equal (in this case EQ).

 

So (EQUAL obj1 obj2) is true if and only if:

 

  1. obj1 and obj2 are EQ, or
  2. obj1 and obj2 are EQL, or
  3. obj1 and obj2 are sequences, have the same length, and the corresponding elements are EQUAL.

 

Notice that the definition of EQUAL is recursive: EQUAL is defined in terms of itself. That means that two nested lists can be EQUAL:

 

(setf v1 '(1 (2 3) 4))

(setf v2 '(1 (2 3) 4))

 

(EQL v1 v2) => NIL

(EQUAL v1 v2) => T

(EQUAL "abc" "abc") => T

(EQUAL "abc" "ABC") => NIL ; EQUAL is case sensitive

 

Notice that v1 and v2 are not EQ or EQL, but they are both lists of length 3, and

 

(EQUAL (first v1) (first v2)) => T

(EQUAL (second v1) (second v2)) => T

(EQUAL (third v1) (third v2)) => T

 

The EQUALP Predicate

 

The final, and weakest equality predicate, is most often used to compare user-defined structures.

For example,

 

(defstruct foo x y)

(setf foo1 (make-foo :x 1 :y 'Y))

(setf foo2 (make-foo :x 1 :y 'Y))

 

(eql foo1 foo2) => NIL

(equal foo1 foo2) => NIL

 

but these two structures are similar in the sense that they are structures of the same type, and corresponding components of the two structures are equal (in this case they are EQL).

 

So EQUALP is defined as follows. Two objects object1 and object2 are EQUALP if an only if:

  1. object1 and object2 are EQUAL, or
  2. object1 and object2 are structures of the same type, and corresponding components are EQUALP.

 

Again notice that EQUALP is defined recursively, so nested structures can be EQUALP too. (To be honest, this isn't the precise definition of EQUALP. If you're curious about the real definition, you can find it in the CommonLisp manual which is available in the Allegro program.

 

Summary

 

It really isn't as complicated as it sounds. In most cases, when you need to compare two objects equal, they will be the same type and you will know what that type is. In that case you know the preferred equality test: