SICP Exercise 2.87: Testing Zero for Polynomials

Install =zero? for polynomials in the generic arithmetic package. This will allow adjoin-term to work for polynomials with coefficients that are themselves polynomials.

The polynomial Package

In section 2.5.3 the authors provide us with various operations for manipulating polynomials and their terms, along with the skeleton of a polynomial package. Before we can start into the exercise we need to put all this together so that we have a package we can install into the system we've been building from section 2.5.1.

To save you the hassle of doing it yourself, here's the basic polynomial package:

(define (install-polynomial-package)
  ;; internal procedures
  ;; representation of poly
  (define (make-poly variable term-list)
    (cons variable term-list))
  (define (variable p) (car p))
  (define (term-list p) (cdr p))
  
  ;; procedures same-variable? and variable? from section 2.3.2
  (define (variable? x) (symbol? x))
  (define (same-variable? v1 v2)
    (and (variable? v1) (variable? v2) (eq? v1 v2)))

  ;; representation of terms and term lists
  (define (adjoin-term term term-list)
    (if (=zero? (coeff term))
        term-list
        (cons term term-list)))
  (define (the-empty-termlist) '())
  (define (first-term term-list) (car term-list))
  (define (rest-terms term-list) (cdr term-list))
  (define (empty-termlist? term-list) (null? term-list))
  (define (make-term order coeff) (list order coeff))
  (define (order term) (car term))
  (define (coeff term) (cadr term))

  ;; procedures used by add-poly
  (define (add-poly p1 p2)
    (if (same-variable? (variable p1) (variable p2))
        (make-poly (variable p1)
                   (add-terms (term-list p1)
                              (term-list p2)))
        (error "Polys not in same var -- ADD-POLY"
               (list p1 p2))))
  (define (add-terms L1 L2)
    (cond ((empty-termlist? L1) L2)
          ((empty-termlist? L2) L1)
          (else
           (let ((t1 (first-term L1)) (t2 (first-term L2)))
             (cond ((> (order t1) (order t2))
                    (adjoin-term
                     t1 (add-terms (rest-terms L1) L2)))
                   ((< (order t1) (order t2))
                    (adjoin-term
                     t2 (add-terms L1 (rest-terms L2))))
                   (else
                    (adjoin-term
                     (make-term (order t1)
                                (add (coeff t1) (coeff t2)))
                     (add-terms (rest-terms L1)
                                (rest-terms L2)))))))))

  ;; procedures used by mul-poly
  (define (mul-poly p1 p2)
    (if (same-variable? (variable p1) (variable p2))
        (make-poly (variable p1)
                   (mul-terms (term-list p1)
                              (term-list p2)))
        (error "Polys not in same var -- MUL-POLY"
               (list p1 p2))))
  (define (mul-terms L1 L2)
    (if (empty-termlist? L1)
        (the-empty-termlist)
        (add-terms (mul-term-by-all-terms (first-term L1) L2)
                   (mul-terms (rest-terms L1) L2))))
  (define (mul-term-by-all-terms t1 L)
    (if (empty-termlist? L)
        (the-empty-termlist)
        (let ((t2 (first-term L)))
          (adjoin-term
           (make-term (+ (order t1) (order t2))
                      (mul (coeff t1) (coeff t2)))
           (mul-term-by-all-terms t1 (rest-terms L))))))
  
  ;; interface to rest of the system
  (define (tag p) (attach-tag 'polynomial p))
  (put 'add '(polynomial polynomial) 
       (lambda (p1 p2) (tag (add-poly p1 p2))))
  (put 'mul '(polynomial polynomial) 
       (lambda (p1 p2) (tag (mul-poly p1 p2))))
  (put 'make 'polynomial
       (lambda (var terms) (tag (make-poly var terms))))
  'done)

(define (make-polynomial var terms)
  ((get 'make 'polynomial) var terms))

Don't forget to install this by evaluating (install-polynomial-package) of course, or you won't get very far!

Zero Testing for Polynomials

Now onto the exercise itself!

In order to implement =zero? for the polynomial package we need to ask ourselves how we can test whether a polynomial is zero or not. We can't determine equality with zero by looking at the indeterminate itself. However, we can determine it from the coefficients.

If there are no coefficients then the polynomial is equal to zero. On the other hand, when there are coefficients, we can only say that the polynomial is equal to zero iff all of the coefficients are equal to zero. As soon as one of them is non-zero we're unable to tell whether or not the polynomial is equal to zero until we bind the indeterminate to a particular value. Of course, as the coefficients are types from our generic arithmetic system we can test these for equality with zero by recursively evaluating =zero? on each of them.

So we have a recursive approach. If the list of coefficients is empty then the polynomial is equal to zero. Otherwise, we test whether or not the first coefficient is equal to zero. If it is then the polynomial may be equal to zero, but we need to test the remaining coefficients for equality with zero before we can confirm this; if it isn't then the polynomial isn't equal to zero.

Let's put this into code:

(define (install-polynomial-package)
  …
  (define (=zero-all-terms? L)
    (cond ((empty-termlist? L) #t)
          ((not (=zero? (coeff (first-term L)))) #f)
          (else (=zero-all-terms? (rest-terms L)))))
  (define (=zero-poly? p)
    (=zero-all-terms? (term-list p)))
  …
  (put '=zero? '(polynomial) =zero-poly?)
  …
  'done)

...and let's give it a spin:

> (=zero? (make-polynomial 'x '()))
#t
> (=zero? (make-polynomial 'x (list (list 4 (make-integer 3))
                                    (list 2 (make-integer 1))
                                    (list 0 (make-real 2.3)))))
#f
> (=zero? (make-polynomial 'x (list (list 3 (make-real 0))
                                    (list 2 (make-rational 0 4))
                                    (list 1 (make-integer 0)))))
#t