Project I

Due: Monday, 25 February, beginning of class. Change! Due Thursday, 28 Feb, at 11:59PM.

One of the advantages of a list-processing language like Scheme is its convenience for manipulating symbols in addition to doing the usual numerical calculations. Remember that functional languages in general, and Lisp in particular, were designed originally to manipulate symbols. This project requires you to develop a symbolic algebra of polynomials. By a symbolic algebra we mean a program that represents the items under discussion as certain combinations of symbols and then performs operations on these items as symbols rather than as numerical values.

Specifications

The handout describes polynomial arithmetic and provides algorithms for many of the operators. The functions that your solution must provide include the following. You can add other functions as you wish. These functions are also described in the handout. All these functions should be defined at the top level.

Note that you must also define a constant called the-zero-poly that has exactly one term of degree 0 and leading coefficient 0.

Function	Parameters	Action	Assertion
zero-poly?	a polynomial p	returns true if p has zero degree and zero leading coefficient.	Parameter must be a well-formed polynomial
degree	a polynomial p	returns the degree of the leading term. This will be the largest degree in the polynomial.	Parameter must be a well-formed polynomial
rest-of-poly	a polynomial p	returns the polynomial p with its leading term deleted.	Parameter must be a well-formed polynomial
poly-cons	a degree d (of the new term) a leading coefficient a (of the new term) and a polynomial p	returns the polynomial p2 formed by adding ax d to the front of p	The degree d must be larger than the largest degree of p
make-term	a degree d (of the new term) a leading coefficient a (of the new term)	Creates and returns a new term axd	d and a must be numbers.
leading-term	A polynomial p	Returns the first term of p	p must be a well formed polynomial
negative-poly	A polynomial p	Returns the negation of the polynomial p	p must be a well formed polynomial
poly-value	A polynomial p and a number n	Returns the value of the polynomial when n is substituted for x in each term.	p must be a well formed polynomial
p+	Two polynomials p1 and p2	Returns the polynomial p3 where p3 = p1 + p2	Both p1 and p2 must be well formed polynomials
p-	Two polynomials p1 and p2	Returns the polynomial p3 where p3 = p1 - p2	Both p1 and p2 must be well formed polynomials
p*	Two polynomials p1 and p2	Returns the polynomial p3 where p3 = p1 * p2	Both p1 and p2 must be well formed polynomials

Data Structure

Your solution must represent polynomials by a list of pairs of numbers. In each pair, the first element is the degree of a term, and the second element is the coefficient of that term. The pairs corresponding to terms with zero coefficients are not included, except for the-zero-poly, which is represented by ((0 0)). The pairs are ordered so that the degrees decrease. Thus the polynomial:

has the repesentation ((n a_n) (n - 1 a_n-1) ... (1 a₁) (0 a₀)), for those terms with a_i <> 0.

Constraints, Testing and Deliverables

• Polynomials used to test your functions will be defined globally in the interpreter. You may not use any global variables other than the-zero-poly
• You may not use any imperative features in any of your functions. This means that the only control method you can use is recursion and that you can only define variables via let or letrec expressions.
• You must use a locally defined function in at least one of p+, p*, and/or p-.
• A file containing test function calls will be made avaialble soon.
• A file containing all of your definitions should be placed in the Faculty/barrj/CS321/turn-in/project1 folder on Nova. Your code must be well commented and meet the standards provided in COMP 171 and COMP 220.

Last updated on 25 Feb 2008 by John Barr