Computer Science 3675
Summer 2004
Programming Assignment 2

Due: July 8, 11:59pm.

Representing polynomials as lists

You can represent a polynomial by a list of its coefficients. It is simplest to put the low order coefficient at the beginning of the list. For example, list [9,2,5] stands for polynomial 9 + 2x + 5x². An empty list stands for the polynomial all of whose coefficients are 0.

Say that a list standing for a polynomial is in normal form if it does not end on a 0. That is, you do not want to store unnecessary 0 coefficients.

The assignment, part 1

Write this assignment in Astarte. There are notes on using Astarte at the end of this assignment.

Write five functions on polynomials, where a polynomial is represented by a list of its coefficients.

1. neg(p) negates all members of the list. It takes the negative of a polynomial. For example, neg([3,-8,2]) = (-3,8,-2).

2. sum1(p,q) produces the sum of polynomials p and q. For example, sum1([3,5], [0,7,-3]) = [3,12,-3]. The result is not necessarily in normal form.

3. diff1(p,q) produces the difference of polynomials p and q. For example, diff1([3,5], [0,7,-3]) = [3,-2,3]. The result is not necessarily in normal form.

4. scalarProduct1(c,p) produces the result of multiplying all coefficients of polynomial p by number c. For example, scalarProduct1(5,[2,3,4]) = [10,15,20]. The result is not necessarily in normal form.

5. product1(p,q) produces the product of polynomials p and q. (That is, multiply them.) For example, product1([2,6,-9], [3,7]) = [6,32,15,-63]. The result is not necessarily in normal form.

Write these functions in an equational style. There should be no imperative aspects to what you write here. Make your functions definitions simple and elegant. Include a comment for each function explaining what it does (but not how it works). That is, give a contract for each function. The product1 function returns the product of the polynomials, for example. When you talk about parameters, use their names.

For this part, do not worry about whether the result is in normal form. That is, there can be trailing 0's in the answers.

Read your equations. Do you believe them? Why? Write one or more Execute blocks to test your functions. Do they seem to work? You can convert a list to a string using the $ operator.

The assignment, part 2

Now introduce functions that are similar to the ones that you wrote above, but that ensure their results are in normal form. A function called normalize is provided for you. Define sum, diff, scalarProduct and product. Here is the definition of sum.

  Define sum(?x,?y) = normalize(sum1(x,y)).

The assignment, part 3

Modify your program to make it export the sum, diff, product and showPoly functions. (Function showPoly is provided for you. See below.) Your package should have the following form. Copy everything exactly as it is except the line Your definitions go here. Put your function definitions there.

Package polynomial

===========================================
                   export
===========================================
 
Expect 
  sum     : ([Real],[Real]) -> [Real]

          %" sum(p,q) produces the sum p+q of polynomials
          %" p and q, in normal form.
          ;

  diff    : ([Real],[Real]) -> [Real]

          %" diff(p,q) produces the difference p-q of
          %" polynomials p and q, in normal form.
          ;

  product : ([Real],[Real]) -> [Real]

          %" product(p,q) produces the product p*q of
          %" polynomials p and q, in normal form.
          ;

  showPoly: [Real] -> String

          %" showPoly(p) produces a string that describes
          %" polynomial p.  For example, showPoly([2,-5,3]) =
          %" "3x^2 - 5x + 2".

%Expect
   
===========================================
              implementation
===========================================

    Your definitions go here

%Package

Move your tests to another package that imports the polynomial package. Your other package will look like this, except that you replace Your tester(s) go here with your tester(s).

Package tester
  Import "polynomial".

  Your tester(s) go here
%Package

A starting point

See the starting package for a starting point. This package provides definitions of normalize and showPoly (and some helper functions that showPoly uses). You can just modify this, and turn in your package with the given definitions in it.

Hints

Do not start worrying about Astarte syntax until you have a set of equations that you believe are correct and complete, in the sense that every case is covered by at least one equation. When you think you have solid equational definitions on paper, code them up.

Using Astarte in Unix

An implementation of Astarte is available on the Unix machines in the lab. You will need to be sure that /usr/local/bin is in your PATH to use it.

The compiler is called astc, and the interpreter is called astr. To compile a program called myprog.ast, use command

  astc myprog

  astr myprog

Reading the manual

A manual is available for the Astarte programming language. The manual is under construction, and not all parts are done. I expect more to be done as the term progresses.

Read only the parts that appear to be useful.

To test your functions, the simplest approach is just to compute a few values and see what they are. For example, here is a very rudimentary (and not very complete) test.

Execute
  Let a = [2,6,-9].
  Let b = [3,7].
  Writeln["a = ", showPoly a].
  Writeln["b = ", showPoly b].
  Writeln["a + b = ", showPoly(sum(a,b))].
  Writeln["a - b = ", showPoly(diff(a,b))].
  Writeln["a * b = ", showPoly(product(a,b))].
%Execute

What to turn in

Turn in your polynomial.ast file, using the following command.

   ~karl/3675/bin/submit 2 polynomial.ast