Computer Science 3675
Summer 2002
Programming Assignment 2

Representing nonnegative integers as lists

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.

The assignment, part 1

Write this assignment in Astarte. There are notes on using Astarte at the end of this assignment.

Write three functions: inc, add and mult. Each of these operates on a list of zeros and ones, but is thought of in terms of what it does with the numbers that the lists represent.

1. inc(x) should produce x+1. For example, inc([0,1,1]) = [1,1,1] (since 6+1 = 7) and inc([1,1]) = [0,0,1] (since 3+1 = 4).

2. add(x,y) should produce x+y. For example, add([1,1],[0,0,1]) = [1,1,1] (since 3+4 = 7) and add([1,0,1], [0,0,1,1]) = [1,0,0,0,1] (since 5+12=17)

3. mult(x,y) should produce xy (x times y). For example, mult([1,1],[0,0,1]) = [0,0,1,1] (since 3x4 = 12) and mult([1,0,1], [0,1]) = [0,1,0,1] (since 5x2 = 10).

Write the functions in an equational style in Astarte. Make your functions definitions simple and elegant. Include a comment for each function explaining what it does (but not how it works). That is, give a contract for each function.

Now write definitions of sum and product. They should be defined as follows.

  Define sum     = add.
  Define product = mult.

Check your equations to see whether they make sense. Then test your functions!. Instead of testing add and mult directly, write your tests to test sum and product. You can test them by having an execute block that computes some values and prints the results.

The assignment, part 2

Sometimes numbers are generated with zeros at the high order end. (They are at the end of the list representation of the number.) It is nice to get rid of those extraneous zeros. Write a function called removeLeadingZeros(x) which produces the list that results be removing all zeros from the beginning of list x. For example, removeLeadingZeros([0,0,1,0,1,0] = [1,0,1,0]). Then write another function called removeTrailingZeros(x) that removes all zeros from the end of list x. For example, removeTrailingZeros([0,0,1,0,1,0,0,0]) = [0,0,1,0,1]. Write removeTrailingZeros(x) by reversing x, removing leading zeros from the reversal of x, and then reversing the result. You can use standard function reverse(x) to compute the reversal of list x. For example, reverse([1,2,3]) = [3,2,1].

Now modify the definitions of sum and product (but not of add and mult) so that they remove trailing zeros from their results. The definition of sum becomes

  Define sum(?x,?y) = removeTrailingZeros(add(x,y)).

The assignment, part 3

Modify your program to make it export the inc, sum and product functions. It should have the following form. Copy everything exactly as it is except the line Your definitions go here. Put your function definitions there.

  Package arithmetic

    ===========================================
                      export
    ===========================================
  
    Expect
      inc:         [Natural] -> [Natural];
      sum,product: ([Natural],[Natural]) -> [Natural]
    %Expect
  
    ===========================================
                  implementation
    ===========================================

    Your definitions go here

  %Package

Move your tests to another package that imports the arithmetic package. Your other package will look like this, except that you replace Your tester(s) go here with your tester(s).

  Package tester
    Import "arithmetic".

    Your tester(s) go here
  %Package

Hints

Do not start worrying about Astarte syntax until you have a set of equations 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 on paper, 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). 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

      add(0::a,0::b) = 0::add(a,b)

      (0 + 2*a) + (0 + 2*b) = (0 + 2*(a+b))

Using Astarte

An implementation of Astarte is installed in the 320 lab on the Unix machines. The compiler is called astc, and the interpreter is called astr. To compile a program called myprog.ast, use command

  astc myprog

  astr myprog

I will make a version that runs under Windows available soon, as soon as a problem with the user interface is repaired.

A manual is available for the Astarte programming language. Please look at that before writing and running your program. Concentrate on the tutorials rather than the language reference manual. The most relevant pages for you are the following. Read only as much of each page that appears to be useful. When you get into more esoteric looking material, try writing your program instead of just reading on. The parts labeled by green circles are the simplest, followed by the parts labeled by blue squares . You probably won't need to read material that is labeled by a black diamond .

• Compiling and running programs
• Note to new users
• General lexical and syntactic issues
• Example package
• Elementary functional programming

You might want to consult these, but probably do not need to.

• Giving things names
• Pattern matching
• Lists
• Defining functions
• The library by category

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

Remark

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.

What to turn in

Turn in your arithmetic.ast file, using the following commands.

   alias handin "/export/stu/classes/csci3675/bin/handin csci3675"
   handin 2 arithmetic.ast