SICP Exercise 2.79: Generic Equality Testing

Define a generic equality predicate equ? that tests the equality of two numbers, and install it in the generic arithmetic package. This operation should work for ordinary numbers, rational numbers, and complex numbers.

Before we start on figuring out how to test for equality, we should first note a couple of things:

• We're going to build a generic equality predicate here. Predicate is defined in section 1.1.6 as: "used for procedures that return true or false, as well as for expressions that evaluate to true or false." So, unlike all of the procedures defined so far in the packages, a package's implementation of equ? will not be returning a data object of the package's type. As a result we won't need to tag the result of the predicate. This means we can install these procedures directly into the operations table, rather than wrapping it in a λ-function that performs the tagging.
• We're not going to deal with coercion until the next section. As a result we can assume that "This operation should work for ordinary numbers, rational numbers, and complex numbers" means that the operation should work for any pair of numbers of the same type, but that it doesn't need to work for pairs of numbers of different types. This is identical to the behaviour of the existing generic operations.

Okay, so onto the exercise itself...

Firstly, the generic operation itself is straightforward, following the same pattern as the other generic operations:

(define (equ? x y) (apply-generic 'equ? x y))

Next, let's deal with the scheme-number package. This package uses primitive Scheme numbers as its untagged representation and, as the internal procedure we need here will be dealing with the untagged representation, this means that we can use the primitive = procedure to perform the equality test. This can be installed directly into the operations table without a surrounding λ-function because, as noted above, we don't need to mutate the result of this.

Onto the rational package... The set of rational numbers can be formally defined as sets of equivalence classes where each equivalence class is of infinite size. This means that testing for rational number equality normally takes a little bit more than simply checking that the numerators are equal and the denominators are equal; you need to cope with mathematically equal numbers that have different numerators and denominators (such as 1/2 and 2/4). The usual way of achieving this is, for any given pair of rational numbers, n₁/d₁ and n₂/d₂, testing for equality by testing that n₁d₂ = n₂d₁ holds. However, as make-rat reduces any rational number to its canonical representation we can ignore this necessity and do the simple check.

Finally, let's consider the complex package. We have two internal representations we can use for complex numbers: rectangular and polar form. In order to test for equality here it is enough to pick one of the forms and compare the components of that form for equality. So we can either pick rectangular form and so compare the real and imaginary components for equality, or we can pick polar form and so compare the magnitude and angle components for equality. Let's pick the rectangular form.

Okay, so we know how we're going to do it... Here's the changes we make:

(define (install-scheme-number-package)
  …
  (put 'equ? '(scheme-number scheme-number) =)
  …
  'done)

(define (install-rational-package)
  ;; internal procedures
  …
  (define (equ? x y)
    (and (= (numer x) (numer y))
         (= (denom x) (denom y))))
  …
  ;; interface to rest of the system
  …
  (put 'equ? '(rational rational) equ?)
  …
  'done)

(define (install-complex-package)
  ;; imported procedures from rectangular and polar packages
  …
  ;; internal procedures
  …
  (define (equ? z1 z2)
    (and (= (complex-real-part z1) (complex-real-part z2))
         (= (complex-imag-part z1) (complex-imag-part z2))))
  …
  ;; interface to rest of the system
  …
  (put 'equ? '(complex complex) equ?)
  …
  'done)

If you're wondering about the complex- prefix to real-part and imag-part, then have a read of my solution to exercise 2.77 - there's a name clash with the R6RS complex number support.

Okay, so let's see this in action:

> (equ? (make-scheme-number 3) (make-scheme-number 4))
#f
> (equ? (make-scheme-number 5) (make-scheme-number 5))
#t
> (equ? (make-rational 2 3) (make-rational 3 5))
#f
> (equ? (make-rational 1 2) (make-rational 2 4))
#t
> (equ? (make-complex-from-real-imag 1 2) (make-complex-from-real-imag 3 4))
#f
> (equ? (make-complex-from-real-imag 5 6) (make-complex-from-real-imag 5 6))
#t
> (equ? (make-complex-from-mag-ang 2 4) (make-complex-from-mag-ang 6 8))
#f
> (equ? (make-complex-from-mag-ang 1 3) (make-complex-from-mag-ang 1 3))
#t
> (equ? (make-complex-from-real-imag 3 0) (make-complex-from-mag-ang 3 0))
#t