16 Extensional Equality

One of the most useful notions of equality is that of extensional equality, which means that two values are equal if and only if one can be substituted for the other in all possible contexts without affecting the meaning of a program. So for example 5 is extensionally equal to 5, even though in some sense there are two different 5s: the one written first and one written second. Likewise, if we have the following data representation of Cartesian points:

;; A Posn is a (new posn% Number Number)

(define-class posn%

(fields x y))

For some kinds of values such as numbers, strings, and positions, it’s easy to determine if two values of that kind are equal. But it’s not possible to compare all kinds of values for extensional equality. For example, two functions are extensionally equal when for all equal inputs they produce equal outputs. Suppose we have two Number -> Number functions, f and g; how can determine if f is substitutable for g? We’ll have to apply f to all possible numbers n and then ask if (= (f n) (g n)). But there are an infinite number of numbers, so we’ll have to apply f and g an infinite number of times before being sure that f and g are the same.

By exactly the same reasoning, it follows that some kinds of objects cannot be compared for extensional equality since comparing two [Fun Number Number] objects involves checking (= (f . apply n) (g . apply n)) for all numbers n.

16.1 Structural equality for recursive unions

It’s fairly simple to define an equality method for simple compound structures such as posn%, however matters are complicated when dealing with the equality of a recursive union data representation. For example, suppose we define lists of positions:

;; A ListPosn is one of

;; - (new mt%)

;; - (new cons% Posn ListPosn)

;; and implements

;; - =? : ListPosn -> Boolean

;; - Is this list the same as given list?

(define-class mt%)

(define-class cons%

(fields first rest))

To see the problem consider implementing =? in the mt% class:

mt%

;; Is this empty list the same as given list?

(define (=? that) ...)

While it’s clear that when evaluating the ellided ... code that this is a mt% object, it not at all clear what kind of object that. All that is known is that is a ListPosn. Unfortunately the answer the method should produce is entirely dependent on the kind of object that is. If that is a mt%, the answer is true; otherwise it is false.

At this point we have a couple options for how to proceed. One is to add to the ListPosn interface methods that tell compute whether an object is a mt% object. The solution, then is simple:

mt%

;; Is this empty list the same as given list?

;; ListPosn -> Boolean

(define (=? that)

(cond [(that . mt?) true]

[(that . cons?) false]))

We could do likewise for the case of a cons%:

cons%

;; Is this empty list the same as given list?

;; ListPosn -> Boolean

(define (=? that)

(cond [(that . mt?) false]

[(that . cons?)

(and (this . first . =? (that . first))

(this . rest . =? (that . rest)))]))

Notice here that we first check that the given list is a cons, then and only then do we access the first and second part of the cons to determine if they are the same. In the case of the first, we use the posn% =? method to determine if the two positions are equal; for the rest, we use the ListPosn =? method to determine if the rest of the lists are equal recursively.

This approach is simple, but leaks some details about the representation of lists could cause difficulties if we tried to extend the set of implementations of ListPosn. That’s because we are mixing our style of programming; while we are using the class dispatch mechanism to carry out case analysis on this, we are using a type-predicate and an explicit cond to analyze the cases of that. To employ a consistent object-oriented style, we should use the dispatch mechanism to analyze that and eliminate the need for the cond expressions in this program.

Here’s an alternative that makes use of a common pattern for writing methods that follow the “cross product of inputs” recipe, such as =?. First, observe that it’s easy to write object specific equality methods. In other words, writing a method to determine if two empty lists are equal is easy; so is writing a method to determine if two cons lists are equal is easy:

mt%

;; Is this empty list the same as given empty?

;; Empty -> Boolean

(define (=-empty? that) true)

cons%

;; Is this cons list the same as given cons?

;; Cons -> Boolean

(define (=-cons? that)

(and (this . first . =? (that . first))

(this . rest . =? (that . rest))))

Currently these methods are variant specific—we can’t send the =-empty? to a cons% object, but that’s an easy restriction to lift: we simply need to lift =-empty? and =-cons? to the ListPosn interface and then implement =-cons? in the mt% class and =-empty? in the cons% class:

;; A ListPosn ... and implements:

;; - =-empty? : Empty -> Boolean

;;   Is this list the same as given empty list?

;; - =-cons? : Cons -> Boolean

;;   Is this list the same as given cons list?

mt%

;; =-cons? : Cons -> Boolean

;; Is this empty list the same as given cons list?

(define (=-cons? that) false)

cons%

;; =-empty? : Empty -> Boolean

;; Is this cons list the same as given empty list?

(define (=-empty? that) false)

Since an empty lists and a cons lists are never the same, the implementation of both of these methods is just false.

Of all these possibilities, only one is possible or computes anything interesting and that’s (that . =-empty? Empty). So what does it do? Since it’s a method invoked on that, the object system will dispach to the appropriate method based on what kind of object that is. If it’s a cons%, we’re going to invoke the =-empty? method that always returns false, but since that is a cons% and this is a mt%, that is the desired result. On the other hand, if that is a mt%, the =-empty? method that always returns true is invoked. But in that case, both this and that are mt%, so again we’ve produced the desired result. By similar reasoning, we can define the correct implementation of =? for cons%. Putting it all together, we get:

(define-class mt%

(define (=? that) (that . =-empty? this))

(define (=-empty? that) true)

(define (=-cons? that) false))

(define-class cons%

(fields first rest)

(define (=? that) (that . =-cons? this))

(define (=-empty? that) false)

(define (=-cons? that)

(and (this . first . =? (that . first))

(this . rest . =? (that . rest)))))

Notice that this correctly defines equality for lists of positions and achieves our goal of programming in an interface-oriented style that has no explicit cond expressions performing case analysis on the kind of an object.

This technique which is generally applicable to methods of a recursive union that take arguments of that same recursive union and that needs to consider all possible scenarios for what this and that could be. The technique is often called double-dispatch since it does dispatch twice, once on the receiver and once on the argument, in order to achieve a complete case analysis.

Where for each Vi, you write:

Vi

;; =? : U -> Boolean

(define (=? that) (that . =-Vi? this))

;; =-Vi? : Vi -> Boolean

;; Is this Vi same as that Vi?

(define (=-Vi? that)

;; structural recur on each component,

;; equal if all parts are equal.

...)

;; One method for each Vj where j≠i.

;; Is this Vi same as that Vj?  No.

(define (=-Vj? that) false)

...

While this approach is mechanical, it’s involves writing a lot of methods (can you construct a formulae for determining the number of method definitions you need if there are i variants in a union?) and can quickly become unwieldy. Luckily we can combat the problem throug the use of inheritence and overriding.

16.2 Abstracting equality with double dispatch

If you have a union with i variants, each variant will need to define i-1 =-Vj? methods for each j≠i, and each of these methods will produce false. Instead of defining all of these methods in the variant, we can lift all i =-Vi? methods to an abstract class and in each case, return false. That behavior is close to the right thing, but not totally correct. In particular, for each of the Vi, the method specific to that variant, =-Vi? will be wrong since we want to structurally recur, not just return false blindly. To fix things up is easy though: simply override the =-Vi? method in the Vi implementation.

To make an example concrete, here is how to abstract the structural equality method of ListPosn using this approach:

(define-class alist%

(define (=-empty? that) false)

(define (=-cons? that) false))

(define-class mt%

(super alist%)

(define (=? that) (that . =-empty? this))

(define (=-empty? that) true))

(define-class cons%

(super alist%)

(fields first rest)

(define (=? that) (that . =-cons? this))

(define (=-cons? that)

(and (this . first . =? (that . first))

(this . rest . =? (that . rest)))))

Because there are only two variants for a list, the overall size of the code didn’t shrink (in fact it grew slightly longer), however the approach pays off when more variants are invovled. Each class now only defines behavior specific to that kind of object. If we had 100 variants, adding a 101th invaraint would only involving adding one method to alist% and two methods to the 101th variant. That’s it. (Compare this to what’s required if you can’t use inheritance and overriding.) Importantly, such a design is extensible: to add new variants we have to modify the abstract class and the new variant; we don’t have to edit the one hundred existing implementations.

16.3 Equality over interpretation

It is often the case that two peices of data are considered equal if and only if they are structurally equal, i.e. the data is comprised of the same thing. However, that is not the case when there are multiple representations of the same information. For example, consider the following data definition for a set of numbers, represented as a list of potentially non-unique elements:

;; A [SetNumber X] is one of:

;; - (new mt-set%)

;; - (new cons-set% Number SetNumber)

;; Interp: as the unordered, unique elements of this list.

So if we had instead used cons% and mt%, the =? method would produce false for these objects.

How can we define an equality method for sets that respects the interpretation of sets so that two sets are equal if and only if they represent the same information?

Let’s start by defining set equality the way a mathematician would, which is that two sets are equal if one is a subset of the other and vice versa. This definition can be lifted to an abstract class for sets:

(define-class aset%

(define (=? that)

(and (this . ⊆ that)

(that . ⊆ this))))

Now we need to define ⊆:

mt-set%

;; ⊆ : SetNumber -> Boolean

;; Is this empty set a subset of that?

;; The empty set is a subset of all sets.

(define (⊆ that) true)

cons-set%

;; ⊆ : SetNumber -> Boolean

;; Is this non-empty set a subset of that?

;; A non-empty set is a subset if that contains the first element

;; and the rest is a subset of that.

(define (⊆ that)

(and (that . ∋ (this . first))

(this . rest . ⊆ that)))

Finally, all that remains is ∋, pronounced “contains”:

mt-set%

;; ∋ : Number -> Boolean

;; Does this empty set contain given number?

(define (∋ n) false)

cons-set%

;; ∋ : Number -> Boolean

;; Does this non-empty set contain given number?

(define (∋ n)

(or (= n (this . first))

(this . rest . ∋ n)))

16.4 Detatching objects from interpretation

In the previous section, we defined a =? method for sets that respected the set intpretation of objects. Since the set and list interpretation of equality is different, we needed different classes of objects to represent lists and sets. But fundamentally, we chose the same representation (namely lists) and our methods interpreted this representation differently. Is it possible to instead have a single representation that could be interpreted both as a list or a set? If we are to accomplish this, it cannot be through the use of =? method, since there can only be one =? method per object. Instead what we would like to do is define, external to the list classes, a notion of equivalence:

;; An [Equiv X] implements

;; - apply X X -> Boolean

;;   Are given Xs equal?

Moreover, an [Equiv X] needs to be reflexive, transitive, and symmetric, i.e. if ≡ is an [Equiv X], it must be the case that:

• (≡ . apply x x) is true.

• (≡ . apply x y) and (≡ . apply y z) implies (≡ . apply x z)

• (≡ . apply x y) implies (≡ . apply y x),

For example, here is the implementation of the usual equivalence relation on numbers:

;; A (new eqv-number%) implements [Equiv Number].

(define-class eqv-number%

(define (apply n m) (= n m)))

Here is another equivalence relation, but it equates 5 with 10:

;; A (new eqv-number-mod-5%) implements [Equiv Number].

(define-class eqv-number-mod-5%

(define (apply n m) (= (modulo n 5) (modulo m 5))))

16.5 Multiple Representations

;; A Posn implements IPosn

;; An IPosn implements

;; x : -> Number

;; y : -> Number

;; =? : IPosn -> Bool

;; is the given posn the same as this one?

;; A Posn2 is a (posn2% Number Number)

(define-class posn2%

(fields ls)

(constructor (x y)

(fields (list x y)))

(define (x) (first (field ls)))

(define (y) (second (field ls)))

(define (=? p)

(and (= (x) (send p x))

(= (y) (send p y)))))

Now we can compare the two different kinds of posns and everything works properly.

What about multiple representations for lists of posns?

#lang class/3

;; A Posn implements IPosn.

;; An IPosn implements:

;;

;; x : -> Number

;; y : -> Number

;; =? : IPosn -> Boolean

;; A Posn2 is a (posn2% Number Number).

;; implement IPosn.

(define-class posn2%

(fields ls)

(constructor (x0 y0)

(fields (list x0 y0)))

(define (x)

(first (field ls)))

(define (y)

(second (field ls)))

(check-expect (send (posn2% 3 4) =? (posn2% 3 4)) true)

(check-expect (send (posn2% 3 4) =? (posn2% 3 5)) false)

(define (=? p)

(and (= (send this x) (send p x))

(= (send this y) (send p y)))))

(check-expect (send (posn% 1 2) =? (posn2% 1 2)) true)

(check-expect (send (posn% 1 2) =? (posn2% 1 1)) false)

;; A Posn1 is a (posn% Number Number).

;; implements IPosn.

(define-class posn%

(fields x y)

;; Posn -> Boolean

;; Is the given posn the same as this?

(check-expect (send (posn% 3 4) =? (posn% 3 4)) true)

(check-expect (send (posn% 3 4) =? (posn% 3 5)) false)

(define (=? p)

(and (equal? (field x) (send p x))

(equal? (field y) (send p y)))))

;; A LoP is one of:

;; - (mt%)

;; - (cons% Posn LoP)

;; implements ILoP

;; An ILoP implements:

;;

;; first : -> Posn

;; rest : -> ILoP

;; empty? : -> Boolean

(define the-real-empty? empty?)

(define the-real-first first)

(define the-real-rest rest)

(define-class list%

(fields ls)

(define (empty?)

(the-real-empty? (field ls)))

(define (first)

(the-real-first (field ls)))

(define (rest)

(list% (the-real-rest (field ls))))

(define (=? lop)

(cond [(send this empty?) (send lop empty?)]

[else

(and (not (send lop empty?))

(send (send this first) =? (send lop first))

(send (send this rest) =? (send lop rest)))])))

;; A [Listof X] is one of:

;; - (mt%)

;; - (cons% X [Listof X])

;; where X implements

;; =? : X -> Boolean

(define-class mt%

;; [Listof X] -> Boolean

;; Is the given list of posns the same as this?

(define (=? lop)

(send lop empty?))

(define (empty?)

true))

(define-class cons%

(fields first rest)

(define (=? lop)

(and (not (send lop empty?))

(send (field first) =? (send lop first))

(send (field rest) =? (send lop rest))))

(define (empty?)

false))

(check-expect (send (mt%) =? (mt%)) true)

(check-expect (send (cons% (posn% 3 4) (mt%)) =? (cons% (posn% 3 4) (mt%)))

true)

(check-expect (send (cons% (posn% 3 4) (mt%)) =?  (mt%))

false)

(check-expect (send (cons% (posn% 3 4) (mt%)) =? (cons% (posn% 3 5) (mt%)))

false)

(check-expect (send (list% empty) =? (list% empty)) true)

(check-expect (send (list% (list (posn% 3 4))) =? (list% (list (posn% 3 4))))

true)

(check-expect (send (list% (list (posn% 3 4))) =? (list% (list)))

false)

(check-expect (send (list% (list (posn% 3 4))) =? (list% (list (posn% 3 5))))

false)

(check-expect (send (list% (list (posn% 3 4))) =? (cons% (posn2% 3 4) (mt%)))

true)

Now we can make all of the appropriate combinations work together: different kinds of lists with the same kind of posns, the same kind of lists with different kinds of posns, and different kinds of lists with different kinds of posns.

16.6 Parameterized Data Defintions and Equality

Generalizing LoP to [Listof X].

;; A [Listof X] is one of:

;; - (mt%)

;; - (cons% X [Listof X])

But we have to change one more thing. Our =? method assumes that X implements an =? method themselves.

;; A [Listof X] is one of:

;; - (mt%)

;; - (cons% X [Listof X])

;; where X implements

;; =? : X -> Boolean

We could also change the signature of =? to take a comparison. But then we’d have to change all of our code. We’ve lifted a restriction, but only to things that can be compared for equality.

16.7 Exercises

16.7.1 Extensional equality JSON

Revisit your solution to the JSON representation problem (JSON) and develop a method for determining if a given JSON value is extensionally equal to another. Note that this method must respect the set interpretation of JSON objects.