Computer Science 3675
Section 001
Fall 2008
Programming Assignment 2

Overview of assignment

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. As before, please keep track of the amount of time that you spend writing this.

Language

The language that you will use is Cinnameg (version 4.1). Unfortunately, I am behind getting the documentation and implementation ready for you. There is material in the book on Cinnameg. See Chapter 19 and Appendix A. Documentation for version 4.1, and a better implementation, will be made available soon.

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.

Representing nonnegative integers

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 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.

The assignment

Your assignment is to write functions inc, sum, and product that work on lists as representations of binary numbers.

1. inc(x) produces x + 1 (as a normalized list);

2. sum(x,y) produces x + y (as a normalized list);

3. 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 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 incNN, for inc-non-normalizing. Now define inc as follows.

   Define inc x = normalize(incNN x).

Requirement

Cinnameg allows large integers. But for this assigment, you are expected to handle the algorithms for adding and multiplying 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.

More on writing and running the program

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.

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. The lab machines (both Linux and Windows) currently have an implementation of Cinnameg version 4.1.0, which is a little buggy. You will probably not encounter bugs for this assignment. But if you run the interpreter and it asks you whether you want it to compile the file, say no (n), and run the compiler instead, since that is one of the bugs.

To compile arithmetic.cmg using the command line version, use command

  cmgc arithmetic

  cmgc -l arithmetic

  cmgc -l arithmetic
  cmgc -l arithtest
  cmgr arithtest

In the windows lab, run C:\Program Files\Cinnameg\4-1\cmgide.exe to run a very simple development tool. You can write or open the program. Compile using menu item Run/Compile, and run using one of the Run/Run items. You will need to compile both modules. Be sure to run arithtest.cmg. If you run arithmetic.cmg, the examples in it will run, but that is all.

Submitting your work

Be sure to include your name in the program. Also, near the top of the program, write the amount of time spent on program 1 and the amount spent on program 2. When you are ready to turn in your work, use command

   ~abrahamsonk/3675/bin/submit 2 arithmetic.cmg arithtest.cmg