Due: Wed. Oct 6, 11:59pm
A nonnegative 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. Say that a list is normalized if it does not end on 0. So [1,0,1,1] is normalized, but [1,0,1,1,0] is not.
The empty list is a representation of 0.
You can represent a signed integer (positive or negative) by attaching a sign to a list of bits. For signs, we will use characters '+' and '-'. For example, the ordered pair ('+', [1,0,1,1]) represents 13, and pair ('-', [1,0,1,1]) represents -13.
Your assignment is to write functions sum, diff and product that work on signed integers, where
sum(x,y) produces x + y;
diff(x,y) preduces x - y;
product(x,y) computes the product of x * y.
compare(x,y) produces 1 if x > y, 0 if x = y and -1 if x < y.
All four of these operations should use the representation (c,L) where c is either '+' or '-' and L is a list of zeros and ones. Each must be able to deal with parameters that are not normalized. However, each of sum, diff and product must produce normalized results.
You will write a package that exports these definitions, to be used in another package. Write another package to test your definitions.
Write the function definitions 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.
Include at least one example with each function definition. See the starting point file to see how to write an example.
Get the following two files to start with. Two of the functions have been written already.
You will find it convenient to write three groups of functions.
The first group should work with unsigned integers represented just as lists. They do not need to worry about signs. For example, write a function to add two unsigned integers, and another to subtract x-y where x <= y. These functions should not worry about whether their results are normalized. They can also presume that their parameters are normalized, if it is helpful.
The second group should also work with unsigned integers, but should be sure to work on unnormalized parameters, and should produce normalized results.
The third group should be the four exported functions.
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.
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).
For short notation, write N(a) as A and
N(b) as 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. A Windows version is also available, and a Unix/Linux version is available as source code. 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 command
astc arithmeticThis produces a compiled version called arithmetic.aso. To run the program, use command
astr arithmetic
Note. The compiler and interpreter are /usr/local/bin/astc and /usr/local/bin/astr. You need to be sure that /usr/local/bin is in your path.
A manual is available for the Astarte programming language.
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 arithmetic.ast and arithtest.ast program using the submit program. Use command
~karl/3675/bin/submit 2 arithmetic.ast arithtest.ast
Be sure to include your name in the program.