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
- the terms are ordered from largest exponent to smallest,
- no two terms have the same exponents, and
- zero terms are omitted.
In terms of a list of pairs, this means
- the pairs are in order by decreasing cadrs,
- no two pairs have the same cadr, and
- 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 poly)
- 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
(DEFUN NORMALIZE (POLY)
(DELETE_ZERO_TERMS (COMBINE_ADJ_TERMS (SORT POLY))) )
Hints:
- Start with the easiest ones: ADD_TERM, then ADD_POLY, then SUBTRACT_POLY.
- If you do NORMALIZE as suggested above, notice that the order in which you call the helper functions is important.
- SORT is not difficult if you write a helper function (INSERT_TERM pair poly) to insert a pair into a normalized polynomial.
- MULTIPLY_POLY is probably the hardest; you really need a good helper function or two.
- Use meaningful names for your functions and/or include descriptive comments, particularly for helper functions not explicitly required by this assignment.