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

SICP Exercise 2.78: Using Primitive Types

The internal procedures in the scheme-number package are essentially nothing more than calls to the primitive procedures +, -, etc. It was not possible to use the primitives of the language directly because our type-tag system requires that each data object have a type attached to it. In fact, however, all Lisp implementations do have a type system, which they use internally. Primitive predicates such as symbol? and number? determine whether data objects have particular types. Modify the definitions of type-tag, contents, and attach-tag from section 2.4.2 so that our generic system takes advantage of Scheme's internal type system. That is to say, the system should work as before except that ordinary numbers should be represented simply as Scheme numbers rather than as pairs whose car is the symbol scheme-number.

To recap, here are the original implementations of the three procedures in question:

(define (attach-tag type-tag contents)
  (cons type-tag contents))
(define (type-tag datum)
  (if (pair? datum)
      (car datum)
      (error "Bad tagged datum -- TYPE-TAG" datum)))
(define (contents datum)
  (if (pair? datum)
      (cdr datum)
      (error "Bad tagged datum -- CONTENTS" datum)))

What we want to do is to modify these so that they treat any contents or datum that is a primitive number specially.

The changes to type-tag and contents are straightforward. We simply extend them both so that, in addition to checking whether datum is a pair and handling that as is currently done, they also check whether it's a number. If a number is encountered then, rather than raise an error as would currently happen, type-tag should return 'scheme-number while contents should return the datum directly.

attach-tag raises an interesting issue. Now the obvious solution is simply to modify it so that it tests whether the passed contents is a number or not. If it is then simply return the number; if it isn't then return a tagged pair (i.e. the current behaviour). However, this is not necessarily the correct behaviour.

Our system is supposed to be additive, supporting new number representations. What if I decide to add a new package for representing transfinite cardinal numbers, with the tag 'transfinite-cardinal, and the representation being a non-negative primitive Scheme integer such that 0 represents ℵ₀, 1 represents ℵ₁, and so on? If I make the obvious modification to attach-tag then attach-tag will ignore my type-tag, spot that the contents are a primitive Scheme number, return the untagged contents and break my transfinite cardinals package!

No, for attach-tag to work correctly, it really needs to check if type-tag is 'scheme-number rather than checking whether contents is a primitive Scheme number.

Given all that, here's how we can express this programmatically:

(define (attach-tag type-tag contents)
  (if (= type-tag 'scheme-number)
      contents
      (cons type-tag contents)))
(define (type-tag datum)
  (cond ((number? datum) 'scheme-number)
        ((pair? datum) (car datum))
        (else (error "Bad tagged datum -- TYPE-TAG" datum))))
(define (contents datum)
  (cond ((number? datum) datum)
        ((pair? datum) (cdr datum))
        (else (error "Bad tagged datum -- CONTENTS" datum))))

If we swap these in for our original three procedures then we can give it all a spin:

> (attach-tag 'scheme-number 5)
5
> (attach-tag 'transfinite-cardinal 2)
(mcons 'transfinite-cardinal 2)
> (type-tag 4)
'scheme-number
> (contents 3)
3
> (type-tag (attach-tag 'transfinite-cardinal 2))
'transfinite-cardinal
> (contents (make-rational 5 4))
(mcons 5 4)
> (add (make-scheme-number 5) (make-scheme-number 4))
9
> (add (make-rational 1 3) (make-rational 1 4))
(mcons 'rational (mcons 7 12))

All seems to be in order... If you're wondering about the mcons then you should read part (b) of my solution to exercise 2.73.

SICP Exercise 2.77: Tracing magnitude

Louis Reasoner tries to evaluate the expression (magnitude z) where z is the object shown in figure 2.24. To his surprise, instead of the answer 5 he gets an error message from apply-generic, saying there is no method for the operation magnitude on the types (complex). He shows this interaction to Alyssa P. Hacker, who says "The problem is that the complex-number selectors were never defined for complex numbers, just for polar and rectangular numbers. All you have to do to make this work is add the following to the complex package:"

(put 'real-part '(complex) real-part)
(put 'imag-part '(complex) imag-part)
(put 'magnitude '(complex) magnitude)
(put 'angle '(complex) angle)

Describe in detail why this works. As an example, trace through all the procedures called in evaluating the expression (magnitude z) where z is the object shown in figure 2.24. In particular, how many times is apply-generic invoked? What procedure is dispatched to in each case?

A couple of things first:

1. It's not explicitly stated in the book (at least in my reading of it), but you not only need to install the rectangular and polar packages for the generic arithmetic operations system - you need to include the generic complex-number selectors real-part, imag-part, magnitude and angle defined in section 2.4.3.
2. In exercise 2.73 I listed the code from section 3.3.3 that provides the put and get procedures we need for implementing data-directed systems in the style presented. I also noted that, under DrRacket, I'd had to include a couple of packages to get this to work. One of them, rnrs/base-6, includes its own complex-number support, which clashes with the generic complex-number selectors we need to include. I got around this by simply prefixing these selectors with complex-.

Anyway.

The important parts of install-rectangular-package and install-polar-package are as follows:

(define (install-rectangular-package)
  ;; internal procedures
  …
  (define (magnitude z)
    (sqrt (+ (square (real-part z))
             (square (imag-part z)))))
  …
  ;; interface to the rest of the system
  …
  (put 'magnitude '(rectangular) magnitude)
  …
  'done)

(define (install-polar-package)
  ;; internal procedures
  (define (magnitude z) (car z))
  …
  ;; interface to the rest of the system
  …
  (put 'magnitude '(polar) magnitude)
  …
  'done)

You'll note from the highlighted portion that both packages install procedures under the operation key 'magnitude, but for the type lists '(rectangular) and '(polar).

Let's also refresh our minds on how the generic magnitude operation is implemented:

(define (magnitude z) (apply-generic 'magnitude z))

Simple, really.

Prior to following Alyssa's suggestion there is no procedure installed under the operation key 'magnitude for the type list '(complex). So when Louis tries to evaluate (magnitude z) the call to apply-generic fails to get a 'magnitude operation for the complex number and so it raises an error.

When Louis extends the complex package as Alyssa suggests this is no longer the case. Now apply-generic does get a 'magnitude operation for the complex number. It's the one we've just installed for the complex package. And this is the generic magnitude operation itself!

So how does this work then?

Well, remember that when apply-generic invokes the procedure it has retrieved using get, it strips the outer-most type tag of the data before passing it to the procedure. When we evaluate (magnitude z) it gets the procedure magnitude from the table and then effectively evaluates (magnitude (contents z)). Now z has an outer tag of 'complex with an inner tag of 'rectangular on the pair (3 4), so the second (recursive) invocation of magnitude is now dealing with a different type, 'rectangular. This time around it gets the inner procedure, magnitude, defined in the rectangular package that handles the rectangular representation appropriately.

So there are two invocations of apply-generic. The first invocation dispatches to the generic magnitude operation, while the second dispatches to the inner procedure magnitude defined in the rectangular package.

Let's trace this through. First let's define z:

(define z (make-complex-from-real-imag 3 4))

And now let's evaluate (magnitude z)... For brevity's sake I've not expanded out map or get, and to make it clear which magnitude procedure is which, I've referred to the inner procedure magnitude from the rectangular package as rectangular->magnitude below.

  (magnitude z)
= (apply-generic 'magnitude z)
= (let ((type-tags (map type-tag (z))))
    (let ((proc (get 'magnitude type-tags)))
      (if proc
          (apply proc (map contents (z)))
          (error
            "No method for these types -- APPLY-GENERIC"
            (list 'magnitude type-tags))))))
= (let ((type-tags '(complex)))
    (let ((proc (get 'magnitude type-tags)))
      (if proc
          (apply proc (map contents (z)))
          (error
            "No method for these types -- APPLY-GENERIC"
            (list 'magnitude type-tags))))))
= (let ((proc (get 'magnitude '(complex))))
    (if proc
        (apply proc (map contents (z)))
        (error
          "No method for these types -- APPLY-GENERIC"
          (list 'magnitude '(complex)))))))
= (let ((proc magnitude))
    (if proc
        (apply proc (map contents (z)))
        (error
          "No method for these types -- APPLY-GENERIC"
          (list 'magnitude '(complex)))))))
= (if magnitude
      (apply magnitude (map contents (z)))
      (error
        "No method for these types -- APPLY-GENERIC"
        (list 'magnitude '(complex)))))))
= (apply magnitude (map contents (z)))
= (apply magnitude (('rectangular (3 4))))
≡ (magnitude ('rectangular (3 4)))
= (apply-generic 'magnitude ('rectangular (3 4)))
= (let ((type-tags (map type-tag (('rectangular (3 4))))))
    (let ((proc (get 'magnitude type-tags)))
      (if proc
          (apply proc (map contents (('rectangular (3 4)))))
          (error
            "No method for these types -- APPLY-GENERIC"
            (list 'magnitude type-tags))))))
= (let ((type-tags '(rectangular)))
    (let ((proc (get 'magnitude type-tags)))
      (if proc
          (apply proc (map contents (('rectangular (3 4)))))
          (error
            "No method for these types -- APPLY-GENERIC"
            (list 'magnitude type-tags))))))
= (let ((proc (get 'magnitude '(rectangular))))
    (if proc
        (apply proc (map contents (('rectangular (3 4)))))
        (error
          "No method for these types -- APPLY-GENERIC"
          (list 'magnitude '(rectangular)))))))
= (let ((proc rectangular->magnitude))
    (if proc
        (apply proc (map contents (('rectangular (3 4)))))
        (error
          "No method for these types -- APPLY-GENERIC"
          (list 'magnitude '(rectangular)))))))
= (if rectangular->magnitude
      (apply rectangular->magnitude (map contents (('rectangular (3 4)))))
      (error
        "No method for these types -- APPLY-GENERIC"
        (list 'magnitude '(rectangular)))))))
= (apply rectangular->magnitude (map contents (('rectangular (3 4)))))
= (apply rectangular->magnitude ((3 4)))
≡ (rectangular->magnitude (3 4))
= (sqrt (+ (square (real-part (3 4)))
           (square (imag-part (3 4))))))
= (sqrt (+ (square (car (3 4))) (square (cdr (3 4))))))
= (sqrt (+ (square 3) (square 4)))
= (sqrt (+ (* 3 3) (* 4 4)))
= (sqrt (+ 9 16))
= (sqrt 25)
= 5