Comp 212 Homework 2
Boolean Expressions

Due 99.Sept.24 10:00a.m. (in class)

Preparation

Before tackling these problems, you should carefully do all of the exercises in Lab Tutorial 2 and read Ch. 3 of JPL.

Problems

1. We want to design a system of classes to represent and evaluate boolean expressions.   We model the abstract notion of boolean expressions by an abstract class called ABooleanExpression and define its concrete variants (sublasses) as follows.
   • a Constant(c) where c is either true or false, is an ABooleanExpression,
   • And(b1,b2) where b1, b2 are ABooleanExpressions,  is an ABooleanExpression,
   • Or(b1,b2) where b1, b2 are ABooleanExpressions,  is an ABooleanExpression,
   • Not(b1) where b1 is an ABooleanExpressions,  is an ABooleanExpression,
   • Implies(b1,b2) where b1, b2 are ABooleanExpressions,   is an ABooleanExpression.

   Implement the preceding data definition. Save each class in a separate file according to the Java convention.  Each concrete subclass should include appropriate constructors and overriding definitions of the toString() method so that:

   • Constant(true) prints as "true" and Constant(false) prints as "false"
   • And(b1,b2) prints as "(& B1 B2)" where B1, B2 are the toString() forms for b1, b2
   • Or(b1,b2) prints as "(| B1 B2)"
   • Not(b1) prints as "(! B1)"
   • Implies(b1,b2) prints as "(> B1 B2)"

   In addition, each class should include the method Constant eval() that evaluates its instance using the common rules of logic and returns the result.  For example, the instance represented by And  (false, Or (true, false)) evaluates to Constant (false).  Write a class called TestEval with a main method to test your implementation thoroughly. Draw the class diagram for your design.

2. Modify the definition your preceding class design as follows.
   • Add the variant
     • Variable(s) where s is a string is an ABooleanExpression

     to the definition of the ABooleanExpression type.

   • Represent this variant by a new subclass called Variable containing an appropriate constructor and overriding definition of the toString method to return the string held in Variable.
   • Define a new class called Environment to represent an Environment where an Environment is defined by:
     • Empty is an Environment,
     • Cons(name,value,tail) where name is string, value is a boolean, and tail is an Environment, is an Environment.

     The new class should include an appropriate constructor, an overriding definition of toString(), and a method boolean lookup(String name) that finds the first Cons object in this with a name field matching the name parameter and returns the value of the matching Cons object.

   • Add a new method Constant eval(Environment env) to the ABooleanExpression class that evaluates this given the variable bindings in env. If this mentions a variable name that is not bound in env, then eval should throw a an UnboundVariableException where the class UnboundVariableException extends RuntimeException.  There are now two eval methods with distinct parameter lists.  The method eval is said to be "overloaded" in OOP parlance.  What should the behavior of Variable be for the method Constant eval() that it inherits from ABooleanExpression?
   • Write a class called TestEvalEnv with a main method to test your implementation thoroughly. Draw the class diagram for your design.
     
     
3. The following is another design to represent boolean expressions using a combination of the strategy pattern and the composite pattern.
   • A BoolExpRef has a (abstract) ABoolExp.
   • BoolTrue is an ABoolExp,
   • BoolFalse is an ABoolExp,
   • AndExp (b1, b2) where b1 and b2 are BoolExpRefs, is an ABoolExp,
   • OrExp (b1, b2) where b1 and b2 are BoolExpRefs, is an ABoolExp,
   • NotExp (b) where b is a BoolExpRefs, is an ABoolExp,
   • ImpliesExp (b1, b2) where b1 and b2 are BoolExpRefs, is an ABoolExp,
   • VarExp (s) where s is a String, is an ABoolExp.

   The correspondence between this design and the design in questions 1 and 2 should be obvious.  Draw the class diagram and implement the equivalent of question 1 for this design.  The method Constant eval() in question 1 should be replaced by the method Boolean eval(). ABoolExpcan be thought of as an abstract strategy for a BoolExpRefto evaluate itself.  Apply the strategy pattern to this implementation.  Write a class called TestRefEval with a main method to test your implementation thoroughly.

4. Implement the equivalent of question 2 for this design.  Class Variable in question 2 should be replaced by class VarExp.  The method Constant eval(Environment env) in question 2 should be replaced by the method Boolean eval(Environment env). Reuse the Environment class in question 2.   Again, as in question 3, apply the strategy pattern.  Write a class called TestRefEvalEnv with a main method to test your implementation thoroughly.
   
   
5. Which design do you prefer?  Write no more than a page to compare the 2 designs and to explain your preference.

Submission

Submit a separate hard copy solution for each of the above questions.  You do not have to print everything.  You only need to print the new codes that are relevant to the question.  You can make calls to the old code without printing them.  We will assume that previously written codes are correct.  Stay tuned for instructions on electronic submission.