Due: July 8, 11:59pm.
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.
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.
neg(p) negates all members of the list. It takes the negative of a polynomial. For example, neg([3,-8,2]) = (-3,8,-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.
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.
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.
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.
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.
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 %PackagePut 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 %PackageBe sure that there are not any Execute parts in polynomial.ast. Check that everything works, by running the tester.
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.
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.
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 myprogTo run that program, use command
astr myprogIf you prefer, just use astr. It will compile the program for you if it needs compiling, but then you will not get a listing.
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
Turn in your polynomial.ast file, using the following command.
~karl/3675/bin/submit 2 polynomial.ast(This assumes that you have created the alias shown in assignment 1.) Do not include your tests. Be sure to include your name in the program. Take credit for your work.