Assigned: | Wednesday, September 5 |
Due: | Wednesday, September 26, 11:59pm |
This assignment gives you some experience in equational programming and has you compare that to the imperative programming that you used in assignment 1.
For this assignment, you will write the inc, sum, and product functions in an equational style instead of an imperative style. You will also write a power function.
The language that you will use is Cinnameg. There is material in the book on Cinnameg, and you can find documentation here. It is installed on xlogin.cs.ecu.edu as /usr/local/bin/cmgc [a compiler] and /usr/local/bin/cmgr [an interpreter].
Cinnameg is not a purely equational language, and it allows you to use other styles. For this assignment, stay within the equational subset for writing the arithmetic and comparison functions. Do not use loops, or anything that changes something once you have already created it. Write in a declarative, equational style.
You may use imperative aspects, such as Displayln, for testing.
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 11012 (13 decimal) would be represented by the list [1,0,1,1].
Of course, list [1,0,1,1,0] also represents 13. 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. Note that list [0] is not normalized, but [ ] is. The empty list is a normalized representation of 0.
Your assignment is to write the following functions that work on lists as representations of binary numbers. In all cases, x and y are lists of bits.
inc(x) produces x + 1 (as a normalized list);
sum(x, y) produces x + y (as a normalized list);
product(x, y) produces x * y (as a normalized list);
power(x, y) produces xy (as a normalized list). Assume that x and y are not both 0.
For example inc([1,1,0,1,0,1]) = [0,0,1,1,0,1] (43 + 1 = 44), and sum([1,1], [1,1]) = [0,1,1] (3 + 3 = 6). The result list of each function should be normalized even if the parameter lists are not. For example, inc([1,0,0,0]) = [0,1] (1 + 1 = 2).
You can handle normalization as follows. An example for inc should suffice. First, write an implementation of inc that does not worry about normalizing its result. You might call it incn, for inc-nonnormalizing. Now define inc as follows.
Define inc x = normalize(incn x).Do the same for the other functions. Function normalize is provided for you. It just removes any trailing zeroes from the list
Cinnameg allows large integers. But for this assigment, you are expected to handle the algorithms directly using lists of bits. It is not acceptable to convert from a list to an integer, do the arithmetic on the integers, and then convert back to a list. You are allowed to do arithmetic on small integers (say, any integers less than 10).
Think about the number that each list represents. Here are some correspondences between lists and numbers. In the left-hand column, x stands for a list of bits. In the right-hand column, x stands for the corresponding number.
List | Integer | |
---|---|---|
[ ] | 0 | |
0::x | 2x | |
1::x | 2x + 1 |
For example, [0,1,1] = 0::[1,1]. List [1,1] stands for 3. So [0,1,1] stands for 2(3) = 6. Similarly, [1,0,0,1] = 1::[0,0,1]. List [0,0,1] stands for 4. So [1,0,0,1] stands for 2(4) + 1 = 9.
Think about your functions first in terms of arithmetic, then convert to lists. For example, you know that 2x + (2y + 1) = 2(x+y) + 1. Converting that to list notation, and writing sum(a,b) for a + b, yields
sumn(0::x, 1:y) = 1::sumn(x,y)Write a comment with each case telling the translation of that case into arithmetic. Please take a moment to ensure that the arithmetic equation is true!
Write one package that defines and exports your definitions. Do not export the helper functions that do not normalize their results. See arithmetic.cmg for a skeleton of this module. Use the skeleton as a starting point.
Please include at least one Example for each function. I have written inc for you. You will need to provide sum, product and power.
To test your functions, use a separate module. See here for a skeleton of a testing module. Add tests.
To compile arithmetic.cmg, use command
cmgc arithmeticif you want to have a listing written, or
cmgc -l arithmeticif you do not want a listing.
The interpreter is called cmgr. You will want to compile both arithmetic.cmg and arithtest.cmg and then run arithtest. To do that use commands
cmgc arithmetic cmgc arithtest cmgr -t arithtestOption -t of cmgr tells cmgr not to perform some optimizations that would hide information from you if the program encounters an error.
Be sure to include your name in the program. When you are ready to turn in your work, use command
~abrahamsonk/3675/bin/submit 2 arithmetic.cmg arithtest.cmgon xlogin.cs.ecu.edu. Command
~abrahamsonk/3675/bin/submit 2will tell you what you have submitted.
To ask a question about your program, first submit it,
but use assignment name q1. For example, use command
~abrahamsonk/3675/bin/submit q2 arithmetic.cmg
Then send me an email with your question. Do not expect
me to read your mind. Tell me what your question(s) are.
I will look at the file that you have submitted as q2.
If you have another question later, resubmit your new file
as assignment q2 and send another email.