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.

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) |

`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`

;; to determine whether two->boolean`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

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`

;; to determine whether two->boolean`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.

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 |

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