Computer Science 3675
Summer 1999
Programming Assignment 2

Due: May 27

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 would be represented by the list [1,0,1,1]. Of course, list [1,0,1,1,0] also represents the same number. The empty list is a representation of 0.

Your assignment is to write two functions, sum and product, that compute the sum 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), and product([1,0,1], [0,1]) = [0,1,0,1] (since (5)(2) = 10).

Write the functions in an equational style in Astarte. Test your functions on at least the same numbers as in programming assignment 1.

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

Keep track of your time, in just the same way as for programming assignment 1.

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.

inc

You will find some helper functions useful. Write a function inc(x) that adds one to x. Think about the cases to handle.

  1. What is inc([])?
  2. What is inc(0::x)?
  3. What is inc(1::x)?
Keep in mind that, if list x represents number n, then list 0::x represents 2n, and list 1::x represents 2n+1.

sumWithCarry

Write a function sumWithCarry(x,y,c), where x and y are lists and c is either 0 or 1. It should produce the list that represents the sum x+y+c. Think about the cases.

  1. What is sumWithCarry([], y, c)?
  2. What is sumWithCarry(x, [], c)?
  3. What is sumWithCarry(a::x, b::y, c)?
The answer to question 3 will be a list that has a head and a tail. What is the head of the result? What is the tail of the result? That is, when you add x+y+c in binary, what is the rightmost bit, and how to you get the remaining bits? You may use the built-in addition operator + to add small numbers.

You might find yet another helper function useful.

sum, product

Write function sum. It should be trivial, since you have sumWithCarry.

Write function product. Think about the cases that you need, and then solve each case separately, and write an equation for each case. Be sure that you think the equations are true.

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.
  • Giving things names
  • Pattern matching
  • Lists
  • Defining functions

    • What to turn in

    Email me the source code of your program. Put it all in one file, including the test code, for simplicity. Send your program as an attachment, not in the body of the message. As a subject, use
    3675 Assn 2 your name
    Be sure to include your name in the program.

    The body of the email message should report your account of time spent, in hours. For example, 

               Learning language: 2.5 hr
           Development:       1 hr
           Debugging/testing: 1 hr
    Of course, the times shown here are only examples, and might not be representative of the times that you use.