Com S 342 --- Principles of Programming Languages

		     HOMEWORK 4: DATA ABSTRACTION
		 (File $Date: 1999/11/14 20:41:22 $)

Due: problems 1-10, at beginning of class October 14, 1999.

In this homework you will learn about data as a means of combination
and abstraction. You will also learn about how the mechanisms in
Scheme and Java support information hiding and data abstraction;
and gain more practice with various kinds of recursion.

The section headings below give the readings related to the problems.
You may also want to look at the file $PUB/docs/type-notation.txt,
which describes the notation used for types below.

WHAT TO HAND IN

For code hand in *both* your printout of the code and a transcript of
testing.

Be sure the code has your name and section information in a comment at
the top as described in homework 0 at the top.  Although you may want
to write your code out by hand as practice for taking the tests, and
then type it in, please don't turn in handwritten code, unless the
problem specifically states otherwise.

*No* credit will be given for programming problems unless you also
hand in a transcript that includes test output.  For many problems,
we will provide test harnesses; for such problems you must run our tests.
For some problems, you will have to provide your own tests.

For this homework, the directory $PUB/homework/hw4.tst contains test
harnesses for the coding problem.

For problems that don't require code, you can write the answer by hand.
or you can hand in a printout.


SICP section 2.1

You should also read the chapter of your Java book that deals with
programming classes to make abstract data types.  For example, chapter 2 of
"The Java Programming Language" by Arnold and Gosling.

1. [line segments and points]
a. (10 points) Do exercise 2.2 in Scheme.    You can test your code using
       (test-hw4 "line-segment")
   from within scheme342. Be sure to hand in a printout of your testing.
   (See homework 1 for details of how to do this).

b. (15 points) Do exercise 2.2 in Java.  Part of this exercise is for you
   to choose appropriate names for the classes and methods,
   and the appropriate levels of privacy (public, protected, private)
   for your classes and their fields and methods.  So we'll leave the testing
   up to you. But be sure to hand in a printout of your testing.

2. [alternative representation of cons, car, and cdr]
   (10 points) Do exercise 2.4 in the book.  This can be done with pencil
   and paper; you don't need any code.  However, make your verification
   convincing by being explicit about what steps you are using.
   Don't forget to answer the question about cdr.

3. [Interval]
   (25 points) Do exercise 2.7 and 2.8 in the book in Java.
   For this you'll need to translate the code on p. 94 into Java,
   and solve exercises 2.7 and 2.8.  However, instead of using a cons cell
   as your representation, use two fields.  Call the class you create
   "Interval".  Your code should cleanly separate into one part that
   directly accesses the representation, and another that defines
   the operations "add", "mul", "div", and "sub". To test your code,
   copy our test harness file
       $PUB/homework/hw4.tst/IntervalTest.java
   to your directory, compile it, and then make a script of this test.
   Be sure to hand in a printout of your testing.

4. [data abstraction in Scheme vs. Java]
   (20 points) Describe the advantages Java has over Scheme in support of
   data abstraction.  A list is fine, but try to be complete.  Give examples
   to illustrate your points.  Are there any advantages that Scheme has over
   Java in supporting data abstraction?

5. [there is no problem 5, sorry]

SICP section 2.2.1

6. [last-pair]
   (10 points) Using Scheme, do exercise 2.17 in the text, which is
   to implement the procedure
       last-pair : (-> ((list T)) (list T)).
   You can test your code using
       (test-hw4 "last-pair")
   Is your code tail-recursive?

7. [reverse]
a. (5 points) Using Scheme, implement the procedure
       append : (-> ((list T) (list T)) (list T))
   that takes two lists, and returns a list whose elements are drawn
   from the first list, and then the second list, in that order.
   For example,
       (append (list 1 2) (list 3 4)) ==> (1 2 3 4)
       (append (list ) (list 7 9 1 3 7)) ==> (7 9 1 3 7)
       (append (list 23 55 1) (list 7 9 1 3 7)) ==> (23 55 1 7 9 1 3 7)
   You can test your code using
       (test-hw4 "append")
   
b. (20 points) Using Scheme, do exercise 2.18 in the text,
   which is to implement the procedure
       reverse : (-> ((list T)) (list T)).
   Do this first (i) using a procedure that generates a recursive process,
   and then (ii) using a procedure that generates an iterative process.
   You can test each version using
       (test-hw4 "reverse")
   but note that you have to have each version in a separate file,
   and that you must load each one before testing it.

8. [procedures with varying numbers of arguments]
a. (15 points) Do exercise 2.20 in the text in Scheme, which is to implement
   the procedure
       same-parity : (-> (number number ...) (list number)).
   You can test your code using
       (test-hw4 "same-parity")
   Hint: use a helping procedure that doesn't use dotted-tail notation.
b. (10 points) Java does not support methods with varying numbers of arguments,
   but does allow static overloading.  That is, in Java, one can have several
   procedures with the same name, but with different numbers and types of
   arguments.  (You should read more about this in a Java book.)
   Briefly compare static overloading in Java to the dotted-tail notation
   in Scheme in terms of flexibility and the ability of the language
   to check for errors made by programmers.

9. [square-list]
   (10 points) Do exercise 2.21 in Scheme, which is to implement two versions
   of the procedure
       square-list : (-> ((list number)) (list number))
   You can test your code using
       (test-hw4 "square-list")
   but note that you have to have each version in a separate file,
   and that you must load each one before testing it.

10. [bugs in square-list]
   (10 points) Do exercise 2.22 in the book.  This can be done
   with pencil and paper if you wish; you don't have to run anything.

11. (extra credit) If you have done all of the above, you can do extra
credit in SICP sections 2.1 and 2.2.1 by selecting any of the
exercises not listed above that are found in those sections, except
for 2.16.  These problems will be worth 15 points extra credit if done
in Scheme, and 10 if done in Java.  Be sure to hand in both your code
and test output.  Extra credit problems should be handed in separately
from the other problems.