SICP Exercise 2.87 Addendum: Making Polynomials

If you were paying close attention at the end of exercise 2.87 you would have noticed that I created polynomials for testing =zero? as follows:

(make-polynomial 'x '())
(make-polynomial 'x (list (list 4 (make-integer 3))
                          (list 2 (make-integer 1))
                          (list 0 (make-real 2.3))))
(make-polynomial 'x (list (list 3 (make-real 0))
                          (list 2 (make-rational 0 4))
                          (list 1 (make-integer 0))))

Do you notice anything about the term list?

Yep, I had to create the term list representation directly as the operations within the polynomial package for doing so are not exposed externally. This means that I, and anyone using the system, needs to have knowledge of the internal representation used for terms and term lists in order to create polynomials. They would need to know that a term is a list consisting of the order of the indeterminate that the term is for and the coefficient to apply. They would also need to know that a term list is a list of such terms, ordered in decreasing value of the order of the terms.

Exposing the internal representation in this manner has a further implication. It means that once our system is in use we will be unable to change the internal representation without having to find all clients of the system and update them to use the new representation.

Yuck.

We can address these issues by encapsulating the internal representation of terms. To do this we'll need a way for clients to create valid term representations for passing to make-polynomial. We'll also want to update make-polynomial so that clients can pass us in any list of terms and we'll reorganize them into our desired internal representation.

The first of these steps is straightforward. The polynomial package already has an internal operation, make-term for constructing polynomial terms. We just need to expose this externally in the normal manner.

As for accepting any list of polynomials and converting them into a valid representation, let's consider what we'll have to do. We'll need to go through the passed-in list of terms and build up the valid internal representation as we go. To do this we'll need to start with a valid internal representation of an empty term list (which we can get by evaluating (the-empty-termlist)). We then need to iterate through the passed-in terms and, for each one, insert it into the correct position in the term list we're building up. We should also cope with the situation where there are two or more terms passed in with the same order. We could either raise an error in this case, or add the terms together. I chose the latter.

Here's the updates required to do all this:

(define (install-polynomial-package)
  …
  (define (make-poly variable term-list)
    (cons variable (build-term-list term-list (the-empty-termlist))))
  …
  (define (insert-term term terms)
    (if (empty-termlist? terms)
        (adjoin-term term (the-empty-termlist))
        (let* ((head (first-term terms))
               (head-order (order head))
               (term-order (order term)))
          (cond ((> term-order head-order) (adjoin-term term terms))
                ((= term-order head-order)
                 (adjoin-term (make-term term-order (add (coeff term) (coeff head)))
                              (rest-terms terms)))
                (else (adjoin-term head (insert-term term (rest-terms terms))))))))
  (define (build-term-list terms result)
    (if (null? terms)
        result
        (build-term-list (cdr terms) (insert-term (car terms) result))))
  …
  (put 'make 'polynomial-term make-term)
  …
  'done)

(define (make-polynomial-term order coeff)
  ((get 'make 'polynomial-term) order coeff))

We can then make polynomials as follows:

> (make-polynomial 'x
                   (list (make-polynomial-term 4 (make-integer 3))
                         (make-polynomial-term 2 (make-integer 1))
                         (make-polynomial-term 0 (make-real 2.3))))
(polynomial x (4 (integer . 3)) (2 (integer . 1)) (0 (real . 2.3)))
> (make-polynomial 'y
                   (list (make-polynomial-term 2 (make-integer 1))
                         (make-polynomial-term 0 (make-real 2.3))
                         (make-polynomial-term 4 (make-integer 3))))
(polynomial y (4 (integer . 3)) (2 (integer . 1)) (0 (real . 2.3)))
> (make-polynomial 'z
                   (list (make-polynomial-term 0 (make-integer 0))
                         (make-polynomial-term 3 (make-real 0.0))
                         (make-polynomial-term 2 (make-rational 1 2))))
(polynomial z (2 (rational 1 . 2)))
> (make-polynomial 'a
                   (list (make-polynomial-term 2 (make-integer 1))
                         (make-polynomial-term 3 (make-real 3.5))
                         (make-polynomial-term 2 (make-rational 1 2))))
(polynomial a (3 (real . 3.5)) (2 (rational 3 . 2)))