Computer Science 3675
Summer 2003
Programming Assignment 2

Due: Wed July 9

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 + 5x2. 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, it multiplies 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 your functions 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)).
Try these and see if they seem to work.

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
Put this into a file called polynomial.ast.

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
Be sure that there are not any Execute parts in polynomial.ast. Check that everything works, by running the tester. The tester will automatically link to polynomial.ast.

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
To run that program, use command 
  astr myprog
If you prefer, just use astr, and not use astc. The interpreter will compile the program for you if it needs compiling, but then you will not get a listing. Option -m causes astr to compile without asking questions. For example, 
  astr -m myprog
runs myprog, but compiles it first, if it needs to be compiled.

Using Astarte in Windows

A Windows implementation of Astarte is available. It still has some peculiarities that I need to work out, but it appears to work well enough to be usable. To install it:

  1. Create a folder, such as C:\Astarte, such that the full path name of the folder does not contain any blanks. (This is one of the peculiarities that needs to be fixed.)
  2. Save this file into that folder.
  3. Unzip the file.
  4. To run the system, run astide.exe. The run menu has items that will compiler or run a program. Currently, you can only have one program open at once, and can only compile the open program.
The interpreter window does not resize correctly - another thing to fix.

Reading the manual

A manual for Astarte is available. 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 .

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

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

Instructions for turning in programs will be given as soon as I have them.