Comp 212 Homework 3
Visitor Pattern

Due Sunday, Sept. 23, 2001 11:59 PM - No late submission will be accepted.

I. The Immutable List Framework

Your task is to write algorithms on IList (see code and UML diagrams) as visitors as specified in the following problems.  You are free to add any private and protected methods to your visitor classes to support your public operations.  You are also free to write helper visitors to support your main visitors.  You are not allowed to check for the type of any object , such as using instanceof or add a method to check for the type, to perform any task.   The visitors should be in the package schemeFW.visitor, unless specified otherwise.

1. Write a visitor called ToString to compute as String representation of IList with matching parentheses as in Scheme.  For example, ToString for the list containing 1, 2 ,3, should return (1 2 3), and ToString for the empty list should return ().
2. Write a visitor called Reverse to compute and return the host in reverse order.
3. Write a visitor called MakeClone to compute and return a copy of the host.  The copy should not contain any non-empty substructure of the original.
4. Write a visitor called GetNth to compute and return the n-th elements of the host.  Here 0 <= n, and the case n equals 0 corresponds to the first element of the list.  Decide how to pass n to GetNth yourself.
5. Write a visitor called LastElement to find and return the last element of the host.  Do this without using the length of the host.
6. Write a visitor called FirstNElements to compute and return an IList that contains the first n elements of the host.  Here 0 <= n, and the case n equals 0 corresponds to the empty list.  Decide how to pass n to FirstNElements yourself.
7. Write a visitor called  ConcatWith to concatenate the host with the input parameter and return the resulting IList .

Each of the above problems should be done independently from each other.  For each of the above problems, be sure to add test cases which cover all reasonable cases.  As with all programs in this course, lack of good coding style (good style includes reasonable variable names, a header before each non-overridden function, reasonable indentation) will result in a substantial loss of points.  The code should be documented in javadoc style. 

II. Abstract Syntax Tree

A common problem in computing is to read in an arithmetic expression such as 3 * (4 + 5) and evaluate it.  This can be done by first parsing it and create a corresponding "abstract syntax tree" (AST):

    *
  /    \
3      +
      /     \
    4        5

Once the AST is built, one can then traverse and evaluate it.  We are not concern with the problem of parsing at this point in time.  What we want to do in this exercise is to build an object model for the AST and then write visitors to interpret it.  We shall restrict ourselves to arithmetic expressions containing integers, strings (representing variables), and binary operations such as  addition and multiplication.  To evaluate such an expression, we need to have an environment that matches each variable in the expression with an integer value.  An environment can be viewed as a set of id/value pairs.  The complete UML diagrams with full javadoc documentation of an AST, its visitors and environments are given here.  Your assignment is to read the documentation of each the diagrams, figure out what it means and implement it.

III. Submission

The homework is due Sunday Sept. 23, 2001 11:59 PM.  It is to be submitted electronically.  No late submission will be accepted.  The complete homework set should contain the following:

• An ASCII (or html) README file to indicate what you have and/or have not done, and to point out specific details that you feel we need to know when grading your work. 
• StructureBuilder's UML diagrams of all your class designs.
• All the Java source code necessary to compile and execute your test code.