Due: Friday, Oct 3, 11:59:00
An integer can be represented in binary as a list of zeros and ones. The most convenient way to do so is to put the least significant bit first. For example, the binary number 1101 (13 decimal) would be represented by the list [1,0,1,1]. Of course, list [1,0,1,1,0] also represents the same number. Leading zeros in the standard representation (as in 01101) are ignored, and they become trailing zeros in the list representation. The empty list is a representation of 0.
Your assignment is to write functions inc, sum, and product, where: inc(x) produces a list representing a number that is one larger than the number that x represents; sum(x,y) produces the sum of numbers x and y, represented as lists; and product(x,y) computes the product of x and y.
For example, inc([1,1,1]) = [0,0,0,1] (since 7 + 1 = 8), sum([1,0,1], [0,0,1,1]) = [1,0,0,0,1] (since 5+12=17), and product([1,0,1], [0,1]) = [0,1,0,1] (since (5)(2) = 10). Your function should be capable of handling inputs with extra zero bits, but it must not produce answers with extra zeros. So sum([1,0,0],[1,0,0]) = [0,1] since 1+1 = 2.
Write the functions in an equational style in Astarte. Check your equations to see whether they make sense. Then test your functions!. But do not just try random experimentation. Think about the equations.
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.
Do not start worrying about Astarte syntax until you have a set of equations (on paper) 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, code them up. See below on how to do that.
Think of a list as representing a number. Let N(L) be the number that list L represents. For example, N([0,0,1]) = 4. Then N(h::t) = h + 2*N(t). So, for example, N(0::t) = 2*N(t), and N(1::t) = 1 + 2*N(t). When inspecting equations, see if they make any sense when the lists are thought of as numbers. If you write A = B, then you should expect that N(A) = N(B). For example, one equation that you might write is
sum(0::a,0::b) = 0::sum(a,b)
Check this out, keeping in mind that sum(x,y) is supposed to be x+y.
So N(sum(x,y)) = N(x) + N(y).
Suppose that A is N(a) and B is N(b).
In terms of the numbers that the lists represent, the equation says that
(0 + 2*A) + (0 + 2*B) = (0 + 2*(A+B))
which is easily seen to be true for every A and B.
Check all of your equations this way.
Astarte is installed on the Unix machines in the lab. You will also be supplied shortly with a Windows version. Give your program file a name that ends on .ast. To compile a program called arithmetic.ast, use
astc arithmeticThis produces a compiled version called arithmetic.aso. To run the program, use
astr arithmetic
A manual is available for the Astarte programming language.
The following sections of the manual are most relevant to you. Read only as much of each that appears to be useful. When you get into more esoteric looking material, try writing your program instead of just reading on.
You might want to consult these.
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 of the sum function.
Execute
Let six = [0,1,1].
Let seven = [1,1,1].
Let eight = [0,0,0,1].
Writeln[$six, " + ", $six, " = ", $(sum(six,six))].
Writeln[$six, " + ", $seven, " = ", $(sum(six,seven))].
Writeln[$six, " + ", $eight, " = ", $(sum(six,eight))].
Writeln[$seven, " + ", $eight, " = ", $(sum(seven,eight))].
%Execute
You may use the built-in arithmetic operators (+,-,...) provided they are only used on small numbers (say, less than 10). It is not acceptable to convert your binary list to a large integer and then to rely on the built-in operations to do the arithmetic. Do the algorithms yourself.
Turn in the source code of your program using the handin program. Put it all in one file. If your file is called arithmetic.ast, you will hand it in as follows.
handin3675 2 arithmetic.astusing the alias from assignment 1. Be sure that handin says that it was successful. If do not get a report of success, presume that it was not successful.
Include your tests. After testing one function, do not delete the tests. Keep all of the tests in the program.
Be sure to include your name in the program.