Com S 342 --- Principles of Programming Languages

               HOMEWORK 7: JAVA VISITORS AND ITERATORS,
    MULTIPLE REPRESENTATIONS, AND SYSTEMS WITH GENERIC OPERATIONS
                 (File $Date: 1999/11/29 22:12:51 $)

Due: problems 1-4, at beginning of class December 2, 1999;
     problems 5-9, at beginning of class December 9, 1999.

Note that according to the course policies, "no credit for late
homework will be given during the last week of classes (or later!)."
For this homework we will relax this a bit, but we still need to allow
the TAs time to do grading.  So the last date to hand in problems 1-4
will be December 3, and the last date to hand in problems 5-9 will be
December 10.  Please don't be late if you can help it.

In this homework you will gain practice using iterators to implement a
pipe-and-filter architecture in Java and the visitor pattern to
process data described by a grammar.   You will also learn about strategies
for handling multiple representations for abstract data and systems with
generic operations.

Warning: the problems in this homework may take a bit longer than
usual to solve.  Don't wait until the last-minute to start working on them.

The section headings below give the readings related to the problems.

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 this homework, some test cases can be found in $PUB/homework/hw7.tst.
For others, we have left the testing to you.

SICP section 2.2.2, also The Little Schemer chapter 5

1. [ScaleAtomicExpression]
   (10 points)
   There is an implementation of atomic-expressions for Java in the
   directory $PUB/lib/atomic_expression (i.e., in the package
   lib.atomic_expression).  Study this code, in particular
   ToString.java, CountLeaves.java, and IncrementBy.java, which implement
   the interface Visitor.  Then write a Java class ScaleAtomicExpression,
   which also implements the interface
         lib.atomic_expression.Visitor
   and acts like scale-tree on page 112 for atomic-expressions.
   The constructor for ScaleAtomicExpression takes a double as an argument,
   and you may assume that all the instances of type Atom hold objects
   of type Double.   To test your code, copy our test harness file
       $PUB/homework/hw7.tst/ScaleAtomicExpressionTest.java
   to your directory, compile it, and then make a script of this test.
   Be sure to hand in a print-out of your testing.

2. [MapAtomicExpression]
   (25 points)
   Abstract your answer to the previous problem, to produce a subtype
   of lib.atomic_expression.Visitor (i.e., a class that implements it),
   named MapAtomicExpression.  The constructor for
   MapAtomicExpression takes a lib.Function as an argument.  For this
   problem, you will do your own testing.  That should show how to use
   MapAtomicExpression to achieve the effect of (a) changing all
   non-string Objects in an AtomicExpression to the corresponding
   String (using the toString method), and (b) substituting all occurrences
   of the String "Scheme" by "Java" in an atomic Expression of
   Strings.  (Watch out for objects that are null in example (a).)
   Be sure to hand in a print-out of your testing with these parts clearly
   identified in the testing code.

3. [BinaryMobile]
   (50 points)
   Do exercise 2.29, parts b-c, in the text in Java using the visitor
   pattern.  That is, for the ``structures,'' define two interfaces,
   and classes that implement them.  One interface should define the
   methods of the visitors; it should be implemented by two classes,
   which solve parts b and c in the problem; that is, you should have
   one visitor class named "TotalWeight", and another named
   "Balanced".  The other interface should be implemented by the
   classes that define weights and mobiles.  You may need other
   helping classes or interfaces; feel free to write the ones you
   need.  So that you understand how to use the visitor pattern, we
   leave the rest of the details and testing to you.

SICP section 2.2.3

4. [FoldLeft]
   (20 points)
   Consider the classes Map and Filter in the library as examples of
   the use of Iterators as conventional interfaces in Java.  Write a
   class FoldLeft that implements the interface lib.Thunk.  It
   should be a reflection of the fold-left procedure discussed in
   exercise 2.38 in Java.  The constructor of FoldLeft will take three
   arguments; the first has type lib.BinaryOp, and the second is an
   Object, and the third is of type lib.Iterator.  Your code
   should *not* iterate over the iterator argument and do any
   computation unless the "value" method of FoldLeft is called.
   To test your code, copy our test harness file
       $PUB/homework/hw7.tst/FoldLeftTest.java
   to your directory, compile it, and then make a script of this test.
   Be sure to hand in a print-out of your testing.

SICP sections 2.4 and 2.5

5. [symbolic derivatives with data dirrected dispatch]
   (15 points)
   Using Scheme, do exercise 2.73, parts a-c, in the book.
   For parts b and c, write your code into a package, using an outline
   like the following:

      (load-quietly-from-lib "operation-type-table.scm")
      (define (install-deriv-package)
        ;; internal procedures
        ...
        ;; interface to the rest of the system
        ...
      )
     (install-deriv-package)

   You can get the code quoted in the problem from $PUB/sicp/ch2.scm.
   The code for the original representation of algebraic expresions
   is found in $PUB/lib/algebraic-expression.scm; however, note that
   the procedures addend, augend, multiplier, and multiplicand can't be
   used directly in what you are to do for this problem; part of part a
   of this problem is to understand why.
   You can test your code for part b using the following.
       (test-hw7 "deriv")
   Do your testing for part c on your own.

6. [get-record, get-salary, find-empolyee-record]
   (70 points)
   Using Scheme, do exercise 2.74, parts a-d, in the text.
   You might want to read page 160 in the text for more background.
   Besides answering the questions about sturcutring in English,
   You will need to code the three procedures get-record,
   get-salary, and find-employee-record, and test them
   using at least 2 "divisions" of the company.  For example, you might use
   for data something like the following for testing.

    (define division-a-file
      '((harry ((salary 12) (hire-year 1994) (title admin)))
        (jane ((salary 14) (hire-year 1993) (title ceo)))))

    (define division-b-file
      '((fred . ((name . fred) (salary . 13)
                 (hire-year . 1997) (title . programmer)))
        (mabel . ((name . mabel) (salary . 15)
                  (hire-year . 1999) (title . programmer)))))

   However, you may need to add type tags to these "data files"
   (but figuring out exactly how to do that is part of the problem).
   Feel free to use the code for type tags and operation-type tables
   by writing the following in your code.
     (load-from-lib "tagged-data.scm")
     (load-from-lib "operation-type-table.scm")
   More hints: you may find it helpful to store curried procedure
   in the operation-type table, so that the arguments with type tags
   can be used to index into the operation-type table, and so that what
   is found in the table is a procedure that can be partially-applied
   to the arguments that had type tags.  An invocation of such a curried
   procedure would look something like
         ((apply-generic 'get-record personnel-file) name)
   Don't use the error procedure in Scheme when you can't find the requested
   data in a set or record; instead, as in Scheme's assoc procedure, return #f
   if the key can't be found.  This will allow you to search several files
   in part c.

   Figuring out how to organize the data across divisions is the heart
   of this problem, so we won't be able to tell you exactly what code to
   write or how to test it.  Testing will thus be left to you.

7. [make-from-mag-ang]
   (10 points)
   Using Scheme, do exercise 2.75 in the text.
   You can test your code using the following.
	(test-hw7 "make-from-mag-ang")

8. [Changes due to evolution]
   (20 points)
   Do exercise 2.76 in the text.  You can do this with pencil and paper.
   Assume that when adding operations, that they do not need direct access to
   the representation of the data, but that you want different behavior for
   each type of data.  Please organize your answer clearly.

9. [Scheme vs. Java]
   (40 points)
   Compare and contrast the support provided by Scheme and Java
   for dealing with (a) multiple representations of data,
   (b) data-directed programming, (c) message passing, and
   (d) systems with generic operations.  Be specific and cite relevant
   examples.

(extra credit)
To avoid a crush of work for the TAs, we won't be taking
any extra credit homework related to this homework.