Section 42

Equality

As we mutate structures or vectors, we use words such as ``the vector now contains false in its first field'' to describe what happens. Behind those words is the idea that the vector itself stays the same -- even though its properties change. What this observation suggests is that there are really two notions of equality: the one we have used so far and a new one based on effects on a structure or vector. Understanding these two notions of equality is critically important for a programmer. We therefore discuss them in detail in the following two subsections.

42.1  Extensional Equality

Recall the class of posn structures from part I. A posn combines two numbers; its fields are called x and y. Here are two examples:

(make-posn 3 4)

(make-posn 8 6)

(make-posn 12 1)

(make-posn 12 1)

More generally, we consider two structures to be equal if they contain equal components. This assumes that we know how to compare the components, but that's not surprising. It just reminds us that processing structures follows the data definition that comes with the structure definition. Philosophers refer to this notion of equality as EXTENSIONAL EQUALITY.

Section 17.8 introduced extensional equality and discussed its use for building tests. As a reminder, let's consider a function for determining the extensional equality of posn structures:

;; equal-posn : posn posn  ->  boolean
;; to determine whether two posns are extensionally equal 
(define (equal-posn p1 p2)
  (and (= (posn-x p1) (posn-x p2))
       (= (posn-y p1) (posn-y p2))))

The function consumes two posn structures, extracts their field values, and then compares the corresponding field values using =, the predicate for comparing numbers. Its organization matches that of the data definition for posn structures; its design is standard. This implies that for recursive classes of data, we naturally need recursive equality functions.

Exercise 42.1.1.   Develop an extensional equality function for the class of child structures from exercise 41.3.3. If ft1 and ft2 are family tree nodes, how long is the maximal abstract running time of the function?    Solution

Exercise 42.1.2.   Use exercise 42.1.1 to abstract equal-posn so that its instances can test the extensional equality of any given class of structures.    Solution

42.2  Intensional Equality

Consider the following toy program:

(define a (make-posn 12 1))
(define b (make-posn 12 1))

(begin
  (set-posn-x! a 1)
  (equal-posn a b))

It defines two posn structures. The two structures are initially equal in the sense of the preceding subsection. Yet when we evaluate the begin-expression, the result is false.

Even though the two structures initially consist of the same values, they are different because the structure mutation in the begin-expression changes the x-field of the first structure and leaves the second one alone. More generally, the expression has an effect on one structure but not the other. Now take a look at a slightly different program:

(define a (make-posn 12 1))
(define b a)

(begin
  (set-posn-x! a 1)
  (equal-posn a b))

Here a and b are two different names for the same structure. Therefore, the evaluation of (set-posn-x! a 1) affects both a and b, which means that (equal-posn a b) is going to yield true this time.

The two observations have a general moral. If the evaluation of an expression affects one structure and simultaneously some other structure, the two structures are equal in a deeper sense than equal-posn can determine. Philosophers refer to this notion of equality as INTENSIONAL EQUALITY. In contrast to extensional equality, this notion of equality requires not only that two structures consist of equal parts, but that they also simultaneously react to structure mutations. It is a direct consequence that two intensionally equal structures are also extensionally equal.

Designing a function for determining the intensional equality of structures is more work than designing one for determining their extensional equality. We start with a precise description:

;; eq-posn : posn posn  ->  boolean
;; to determine whether two posn structures 
;; are affected by the same mutation 
(define (eq-posn p1 p2) ...)

We already have an example, so we move on to a discussion of the template:

(define (eq-posn p1 p2)
  ... (posn-x p1) ... (posn-x p2) ...
  ... (posn-y p1) ... (posn-y p2) ... )

The template contains four expressions, each one reminding us of the available information and which structure fields we can mutate.

Translating the above observations into a full definition yields the following draft:

(define (eq-posn p1 p2)
  (begin
    (set-posn-x! p1 5)
    (= (posn-x p2) 5)))

This function sets p1's x-field to 5 and then checks whether p2's x-field also became 5. If so, both structures reacted to the mutation and are, by definition, intensionally equal.

Unfortunately, our reasoning has a problem. Consider the following application:

(eq-posn (make-posn 1 2) (make-posn 5 6))

The two posn's aren't even extensionally equivalent, so they should not be intensionally equivalent. But our first version of eq-posn would produce true, and that is a problem.

We can improve the first version with a second mutation:

(define (eq-posn p1 p2)
  (begin
    (set-posn-x! p1 5)
    (set-posn-x! p2 6)
    (= (posn-x p1) 6)))

This function changes p1 and then p2. If the structures are intensionally equal, then the mutation of p2 must affect p1. Furthermore, we know that p1's x-field can't coincidentally contain 6, because we first changed it to 5. Thus, when (eq-posn a b) produces true, a changes when b changes and vice versa, and the structures are intensionally equal.

The only problem left now is that eq-posn has effects on the two structures that it consumes but has no effect statement. Indeed, it should not have a visible effect because its only purpose is to determine whether two structures are intensionally equal. We can avoid this effect by first saving the old values in p1's and p2's x fields, mutating the fields, and then restoring the old values. Figure 125 contains a function definition that performs an intensional equality check without any visible effects.

;; eq-posn : posn posn  ->  boolean
;; to determine whether two posn structures 
;; are affected by the same mutation 
(define (eq-posn p1 p2)
  (local (;; save old x values of p1 and p2
	  (define old-x1 (posn-x p1))
	  (define old-x2 (posn-x p2))
	  ;; modify both x fields of p1 and p2
	  (define effect1 (set-posn-x! p1 5))
	  (define effect2 (set-posn-x! p2 6))
	  ;; now compare the two fields
	  (define same (= (posn-x p1) (posn-x p2)))
	  ;; restore old values
	  (define effect3 (set-posn-x! p1 old-x1))
	  (define effect4 (set-posn-x! p2 old-x2)))
    same))

The existence of eq-posn says that all structures have a unique ``fingerprint.'' We can inspect two structures (of the same class) for this fingerprint if we have access to the mutators. Scheme and many other languages typically provide built-in functions for comparing two structural values extensionally and intensionally. The corresponding Scheme functions are equal? and eq?. In Scheme, both functions are applicable to all values, whether mutators and selectors are accessible or hidden. The existence of eq? suggests a revision for our guideline on testing.

The guideline is general. Still, programmers should use equality functions that indicate what kind of values they expect to compare, such as symbol=?, boolean?, or =, because the additional information helps readers understand the purpose of the program more easily.

Exercise 42.2.1.   Evaluate the following expressions by hand:

1. (eq-posn (make-posn 1 2) (make-posn 1 2))

2. (local ((define p (make-posn 1 2)))
	(eq-posn p p))

3. (local ((define p (make-posn 1 2))
	     (define a (list p)))
	(eq-posn (first a) p))

Check the answers with DrScheme.    Solution

Exercise 42.2.2.   Develop an intensional equality function for the class of child structures from exercise 41.3.3. If ft1 and ft2 are family tree nodes, how long is the maximal abstract running time of the function?    Solution

Exercise 42.2.3.   Use exercise 42.2.2 to abstract eq-posn so that its instances can test the intensional equality of any given class of structures.    Solution