2.5.3 · Generic symbolic algebra

A polynomial package turns algebra into operations on tagged data.

Sparse term lists keep powers and coefficients explicit, while generic add and multiply merge equal orders and preserve the polynomial variable.

Guiding question

How can a generic arithmetic system manipulate polynomial structure without scattering term-list details through client code?

Represent a sparse polynomial as a variable plus descending terms
Merge equal powers while adding two term lists
Distribute one term across a polynomial during multiplication
Remove zero-coefficient terms at the representation boundary
Dispatch polynomial add and multiply through type-tagged methods
Reject operations whose polynomial variables do not match

The first program represents each term as an order and coefficient and stores terms from highest order to lowest. add-terms performs the same ordered merge used earlier for sets: the larger order is copied, equal orders are combined, and adjoin-term omits a zero result. The polynomial package owns that representation and exposes one tagged add method. Adding x² + 2x + 1 to x² − 1 therefore produces 2x² + 2x without leaving an explicit zero constant term. A y polynomial returns different-variables instead of silently combining unrelated indeterminates.

The second program multiplies one term by every term in the other polynomial, shifts orders by addition, multiplies coefficients, and merges the partial products through add-terms. Multiplying x + 1 by x − 1 creates two middle terms that cancel, leaving x² − 1. A separate evaluator uses the package selectors and reports 8 at x = 3. This lesson models sparse univariate integer-coefficient polynomials with tagged addition, multiplication, normalization, and evaluation.

SICP code2,685 of 1,048,576 UTF-8 bytes

(begin
  (define (attach-tag type contents) (cons type contents))
  (define (type-tag object) (car object))
  (define (contents object) (cdr object))
  (define (make-term order coefficient)
    (list order coefficient))
  (define (order term) (car term))
  (define (coefficient term) (cadr term))
  (define (adjoin-term term terms)
    (if (= (coefficient term) 0)
        terms
        (cons term terms)))
  (define (add-terms left right)
    (cond ((null? left) right)
          ((null? right) left)
          (else
           (let ((left-term (car left))
                 (right-term (car right)))
             (cond ((> (order left-term) (order right-term))
                    (adjoin-term
                      left-term
                      (add-terms (cdr left) right)))
                   ((< (order left-term) (order right-term))
                    (adjoin-term
                      right-term
                      (add-terms left (cdr right))))
                   (else
                    (adjoin-term
                      (make-term
                        (order left-term)
                        (+ (coefficient left-term)
                           (coefficient right-term)))
                      (add-terms (cdr left) (cdr right)))))))))
  (define (make-polynomial variable terms)
    (attach-tag 'polynomial (cons variable terms)))
  (define (variable polynomial-contents)
    (car polynomial-contents))
  (define (term-list polynomial-contents)
    (cdr polynomial-contents))
  (define (add-polynomial-contents left right)
    (if (eq? (variable left) (variable right))
        (make-polynomial
          (variable left)
          (add-terms (term-list left) (term-list right)))
        'different-variables))
  (define operation-table
    (list
      (cons (list 'add 'polynomial 'polynomial)
            add-polynomial-contents)))
  (define (lookup-entry key table)
    (cond ((null? table) #f)
          ((equal? key (car (car table)))
           (cdr (car table)))
          (else (lookup-entry key (cdr table)))))
  (define (apply-generic operation left right)
    (let ((method
            (lookup-entry
              (list operation (type-tag left) (type-tag right))
              operation-table)))
      (if method
          (method (contents left) (contents right))
          'no-method)))
  (define p
    (make-polynomial
      'x
      (list (make-term 2 1)
            (make-term 1 2)
            (make-term 0 1))))
  (define q
    (make-polynomial
      'x
      (list (make-term 2 1)
            (make-term 0 -1))))
  (define y
    (make-polynomial 'y (list (make-term 1 1))))
  (list (apply-generic 'add p q)
        (apply-generic 'add p y)))

(begin
  (define (attach-tag type contents) (cons type contents))
  (define (type-tag object) (car object))
  (define (contents object) (cdr object))
  (define (make-term order coefficient)
    (list order coefficient))
  (define (order term) (car term))
  (define (coefficient term) (cadr term))
  (define (adjoin-term term terms)
    (if (= (coefficient term) 0)
        terms
        (cons term terms)))
  (define (add-terms left right)
    (cond ((null? left) right)
          ((null? right) left)
          (else
           (let ((left-term (car left))
                 (right-term (car right)))
             (cond ((> (order left-term) (order right-term))
                    (adjoin-term
                      left-term
                      (add-terms (cdr left) right)))
                   ((< (order left-term) (order right-term))
                    (adjoin-term
                      right-term
                      (add-terms left (cdr right))))
                   (else
                    (adjoin-term
                      (make-term
                        (order left-term)
                        (+ (coefficient left-term)
                           (coefficient right-term)))
                      (add-terms (cdr left) (cdr right)))))))))
  (define (make-polynomial variable terms)
    (attach-tag 'polynomial (cons variable terms)))
  (define (variable polynomial-contents)
    (car polynomial-contents))
  (define (term-list polynomial-contents)
    (cdr polynomial-contents))
  (define (add-polynomial-contents left right)
    (if (eq? (variable left) (variable right))
        (make-polynomial
          (variable left)
          (add-terms (term-list left) (term-list right)))
        'different-variables))
  (define operation-table
    (list
      (cons (list 'add 'polynomial 'polynomial)
            add-polynomial-contents)))
  (define (lookup-entry key table)
    (cond ((null? table) #f)
          ((equal? key (car (car table)))
           (cdr (car table)))
          (else (lookup-entry key (cdr table)))))
  (define (apply-generic operation left right)
    (let ((method
            (lookup-entry
              (list operation (type-tag left) (type-tag right))
              operation-table)))
      (if method
          (method (contents left) (contents right))
          'no-method)))
  (define p
    (make-polynomial
      'x
      (list (make-term 2 1)
            (make-term 1 2)
            (make-term 0 1))))
  (define q
    (make-polynomial
      'x
      (list (make-term 2 1)
            (make-term 0 -1))))
  (define y
    (make-polynomial 'y (list (make-term 1 1))))
  (list (apply-generic 'add p q)
        (apply-generic 'add p y)))

Examples

Result—

Output: —
Value: —
Diagnostic: —

Execution trace0 / 0 events

Expected result

The addition program returns ((polynomial x (2 2) (1 2)) different-variables). The multiplication program returns ((polynomial x (2 1) (0 -1)) 8).

Trace focus

In addition, follow the descending-order comparison and locate the equal-order coefficient sum that drops the zero constant term. In multiplication, follow each order shift, coefficient product, recursive partial product, and add-terms merge that cancels the two order-1 terms. The variable check happens before either representation operation proceeds.

Try it yourself

Change the program and compare the result.

Multiply x² + x + 1 by x − 1, predict the sparse term list, and evaluate the result at x = 2.

Show hint

Generate one partial product for each left term, then merge equal orders. The order-1 and order-0 cancellations happen at different stages.

Complete this lesson

0 of 20 lessons complete in this chapter0%