Comp 212 Homework 3
Visitor Pattern

Part I due Monday, Feb. 11, 2002 10:00 AM - 

Part II due Monday, Feb. 18, 2002, 10:00 AM

No late submission will be accepted.

I. The Immutable List Framework

Your task is to write algorithms on AList (see source code ) 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 OOscheme.visitor, unless specified otherwise.

1. Write a visitor called ToString to compute as String representation of AList 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 ().
   • Write a test class.
2. Write a visitor called Reverse to compute and return the host in reverse order.
   • Write a test class.
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.
   • Write test class.
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.
   • Write test class.
5. Write a visitor called LastElement to find and return the last element of the host.  Do this by traversing the host only once.
   • Write test class.
6. Write a visitor called FirstNElements to compute and return an AList 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.
   • Write test class.
7. Write a visitor called  ConcatWith to concatenate the host with the input parameter and return the resulting AList .
   • Write test class.

Each of the above problems should be done independently from each other.

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.  70 points

III. Submission

The homework is to be submitted in two milestones.

1. Part I (List visitors) is due Monday, February 11, 2002 at 10:00 AM.  50% of the total homework 03 grade.
2. Part II (AST) is due Monday, February 18, 2002 at 10:00 AM.  50% of the total homework 03 grade.

Each is to be submitted via the turn-in script.  To turn in Part 1 to comp212:

1. log on to owlnet
2. type: turnin -c comp212 -p hw3-visitor mydir
   
   where mydir is the directory that encapsulates all the files you wish to turn in for part 1.
   
   

1. log on to owlnet
2. type: turnin -c comp212 -p hw3-ast mydir
   
   where mydir is the directory that encapsulates all the files you wish to turn in for part 2.

• A plain text file called README documenting what you have and/or have not done, describing specific details that you feel we need to know when grading your work.  This README file alone is worth 5 points.
• Pledge of Honor: add your pledge of honor to the README file.
• UML diagrams of all your class designs.
• All the Java source code necessary to compile and execute your test code.