Assigned: | Tuesday, September 12 |
Due: | Tuesday, September 19, 11:59pm |
For this assignment, you will write the inc, sum and product functions in a functional style instead of an imperative style. You should find them fairly short and simple.
The language that you will use is Cinnameg. Chapters 15 and 16 give some examples written in Cinnameg, and Appendix A tells some more. There is also an overview and a manual available.
Cinnameg is not a purely functional language, and it allows you to use other styles. For this assignment, stay within the functional subset for writing the arithmetic functions. Do not use Relet. Do not use loops, or anything that changes something once you have already created it.
See the end of this page for more on how to write and run your program.
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 representation of 0.
Your assignment is to write functions inc, sum, and product that work on lists as representations of binary numbers.
inc(x) produces x + 1 (as a normalized list);
sum(x,y) produces x + y (as a normalized list);
product(x,y) produces the product x * y (as a normalized list)
For example inc([1,1,0,1,0,1]) = [0,0,1,1,0,1], and sum([1,1], [1,1]) = [0,1,1]. 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].
You can handle normalizion 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 inc_a, for example. Now define inc as follows.
Define inc ?x = normalize(inc_a x).Do the same for the other functions. Function normalize is provided for you.
Write one package that defines and exports your definitions. Do not export the helper functions that do not normalize their results. See here for a skeleton of this module. Copy and paste this into a file called arithmetic.cmg.
Please include at least one example with each function. I have written inc for you. You will need to provide sum and product.
To test your functions, use a separate module. See here for a skeleton of a testing module. Add a few tests in addition to the examples in the implementation module.
You can use either a Windows or Unix implementation of Cinnameg.
To comple your packages in Unix, use the following commands (assuming your packages are called arithmetic.cmg and arithtest.cmg.)
cmgc arithmetic cmgc arithestThis produces compiled versions called arithmetic.cmo and arittest.cmo. To run the tester, use command
cmgr arithtest
Note. The compiler and interpreter are /usr/local/bin/cmgc and /usr/local/bin/cmgr. You need to be sure that /usr/local/bin is in your path.
Note. If you do not want to get a listing, use option -l (dash lower-case-ell). For example, use command
cmgc -l arithmetic
A Windows version is available here. That page contains instructions on how to install it. Read the instructions. See here for instructions on how to use the Windows implementation, once it is installed.
When you are ready to turn in your work, use command
~karl/3675/bin/submit 2 arithmetic.cmg arithtest.cmgon a Unix machine.
Be sure to include your name in the program.