Computer Science 3675
Summer 2000
Programming Assignment 2
Due: May 25, 5:00.
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 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 and elegant.
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.
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
You will find some a helper function useful. Write a function
inc(x) that adds one to x. That is, if x is a list that represents
number n, then inc(x) is a list that represents number n+1.
Think about the cases to handle.
- What is inc([])?
- What is inc(0::x)?
- What is inc(1::x)?
Check your answers.
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.
You might want to consult these.
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.