Computer Science 3675
Fall 2000
Programming Assignment 2

Due: Wednesday, September 20

The assignment

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.

Your assignment is to write three functions, sum, difference and product, that compute the sum, difference and product of two binary numbers, each represented as a list. For example, sum([1,0,1], [0,0,1,1]) = [1,0,0,0,1] (since 5+12=17), difference([0,0,1,1], [1,0,1]) = [1,1,1] (since 12 - 5 = 7) and product([1,0,1], [0,1]) = [0,1,0,1] (since (5)(2) = 10). Your answers might have additional 0 bits on the end -- don't worry about that. The difference function requires its first number to be no smaller than its second, so that no negative numbers result.

Write the functions in an equational style in Astarte. Check your equations to see whether they make sense. Then test your functions!.

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

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, code them up.

Hint 1. Understanding lists as numbers

Think of a list as representing a number. Let N(L) be the number that list L represents. 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

      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. The equation says

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

which is easily seen to be true.

Hint 2: inc and dec

You will find some two helper functions useful. Write a function inc(x) that adds one to x and dec(x) that subtracts 1 from x. That is, if x is a list that represents number n, then inc(x) is a list that represents number n+1 and dec(x) is the list that represents the number n-1. (Function dec requires that its input be a positive number.) Think about the cases to handle. For example,

What is inc([])?
What is inc(0::x)?
What is inc(1::x)?

Note that you are not required to handle dec([]). Check your equations.

Using Astarte

A manual is available for the Astarte programming language. Please look at that before writing and running your program. The most relevant pages for you are the following. Read only as much of each that appears to be useful. When you get into more esoteric looking material, try writing your program instead of just reading on.

Compiling and running programs

Note to new users

General lexical and syntactic issues

Example package

Functional programming

You might want to consult these.

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 the source code of your program using the handin program. Put it all in one file. If your file is called arithmetic.ast, you will hand it in as follows.

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

Do not include your tests. Be sure to include your name in the program.

Computer Science 3675 Fall 2000 Programming Assignment 2