Computer Science 3675
Fall 2002
Programming Assignment 2

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].

3. diff1(p,q) produces the difference of polynomials p and q. For example, diff1([3,5], [0,7,-3]) = [3,-2,3].

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].

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].

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. 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? Write one or more Execute blocks to test your functions. Do they seem to work?

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 a definition of normalize and a definition of 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 installed in the 320 lab on the Unix machines. The compiler is called astc, and the interpreter is called astr. To compile a program called myprog.ast, use command

  astc myprog

  astr myprog

If you have a Unix computer of your own, you can install Astarte on it. See getting Astarte.

Using Astarte in Windows

A version of the Astarte implementation is available that runs under Windows is available. The user interface has some bugs. If you create a file, it will sometimes refuse to compile it. If you close the user interface and reopen it on the same file, it works. I will try to fix this soon. See getting Astarte.

I will make a version that runs under Windows available soon, as soon as a problem with the user interface is repaired.

Reading the manual

A manual is available for the Astarte programming language. Please look at that before writing and running your program. Concentrate on the tutorials rather than the language reference manual. The most relevant pages for you are the following. Read only as much of each page that appears to be useful. When you get into more esoteric looking material, try writing your program instead of just reading on. The parts labeled by green circles are the simplest, followed by the parts labeled by blue squares . You probably won't need to read material that is labeled by a black diamond .

• Compiling and running programs
• Note to new users (please read this)
• General lexical and syntactic issues (please read this)
• Example package
• Elementary functional programming

You might want to consult these, but probably probably do not need to.

• Giving things names
• Pattern matching
• Lists
• Defining functions
• The library by category

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.

   handin3675 2 polynomial.ast