CSC 8310 Linguistics of Programming Languages
Dr. David Matuszek
Fall 1997, Villanova University

Polynomial Manipulation

A polynomial in one unknown may be represented as a list of (coefficient, exponent) pairs. For example, the polynomial x4 - 7x + 3 may be represented as ((1 4) (-7 1) (3 0)).

We will say that a polynomial is normalized if

  1. the terms are ordered from largest exponent to smallest,
  2. no two terms have the same exponents, and
  3. zero terms are omitted.
In terms of a list of pairs, this means
  1. the pairs are in order by decreasing cadrs,
  2. no two pairs have the same cadr, and
  3. no pair has a car of zero.

Write and test the following Lisp functions. All functions (except NORMALIZE and EVALUATE) should take normalized polynomials as input and return a normalized polynomial as their result.
( ADD_POLY poly1 poly2)
Add the two normalized polynomials and return the normalized result.

( SUBTRACT_POLY poly1 poly2)
Subtract the second polynomial from the first and return the normalized result.

( MULTIPLY_POLY poly1 poly2)
Multiply the two normalized polynomials and return the normalized result.

Normalize the possibly unnormalized polynomial and return the result.

( EVALUATE poly integer)
Evaluate the polynomial at the given point and return the (integer) result.
Turn in a listing of your functions, along with a listing showing your tests of these functions.

It is good form to write additional "helper" functions as needed. For example, ADD_POLY will probably be much simpler to write if you first write a function ( ADD_TERM pair poly ). As a second example, a good way to write NORMALIZE might be