Due: Friday, September 21, 11:59pm
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 are ignored. The empty list is a representation of 0.
Your assignment is to write five functions: inc, dec, sum, diff and product. Inc and dec increment and decrement a binary number, respectively. For dec, presume that the number is positive. Sum, diff and product compute the sum, difference and product of two binary numbers, respectively. For diff, presume that the result will not be negative. You do not need to handle cases where the difference would be negative.
For example, sum([1,0,1], [0,0,1,1]) = [1,0,0,0,1] (since 5+12=17), diff([0,0,1,1], [1,0,1]) = [1,1,1] (since 12 - 5 = 7) and product([1,0,1], [0,1]) = [0,1,0,1] (since (5)(2) = 10). Your answers might have additional 0 bits on the end -- don't worry about that.
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 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. Give your program file a name that ends on .ast. To compile a program called arithmetic.ast, use
astc arithmeticThen, to run the program, use
astr arithmetic
A manual is available for the Astarte programming language. If you like, you can get the entire manual, so that you can have it locally on your machine. Please do not install the entire manual on the lab machines. You can also get other things:
Download the full Astarte 0.10.2 distribution for Unix. Only do this if you want to load Astarte onto a Unix or Linux computer. Do not install Astarte in the lab. It is already installed.
README file for Astarte 0.10.2 distribution for Unix. This tells how to install Astarte on a Unix or Linux machine.
Download entire hypertext documentation only for Astarte 0.10.2. This allows you to have the documentation on your local machine.
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.astBe 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.