# Section 42Equality

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) ```
They are obviously distinct. In contrast, the following two
 ```(make-posn 12 1) ``` ```(make-posn 12 1) ```
are equal. They both contain `12` in the `x`-field and `1` in the `y`-field.

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 `posn`s 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)) ``` Figure 125:  Determining the intensional equality of two structures

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.

 Guideline on Testing Use `eq?` for testing when comparing the identity of objects matters. Use `equal?` for testing otherwise.

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