# 0. To Cook or Not To Cook

Mary is a vegetarian.  She only cooks and eats vegetarian food.  John is carnivorous.  He cooks and eats meat!  If Mary wants to eat broccoli and cheese, she can learn how to cook  broccoli and cheese.  If she wants corn of the cob, she can learn how to cook corn on the cob.  The same goes for John.  If he wants to eat greasy hamburger, he can learn how to cook greasy hamburger.  If he wants to eat fatty hotdog, he can learn how to cook fatty hotdog.  Every time John and Mary want to eat something new, they can learn how to cook it.  This requires that John and Mary to each have a very big head in order to learn all the recipes.

But wait, there are things out there called restaurants!  These are very special kinds of restaurants catering only to vegetarians and carnivores.  These restaurants only have two dishes on their menus: one vegetarian dish and one meat dish.  All John and Mary have to do is to know how to call such a restaurant to order their favorite dish.  Mary will only order the vegetarian dish, while John will only order the meat dish!

How do we model the vegetarian, the carnivore, the restaurant, the two kinds of food the restaurant serves, and how the customer orders the appropriate kind of dish from the restaurant?

## The Food

To simplify the problem, let's treat food as String.  (In a more sophisticated setting, we may want to model  food as some interface with veggie and meat as sub-interface.)

## The Food Consumers

Vegetarians and carnivores are basically the same animals and differ only in the way they order food from the restaurant.  We model them as two concrete subclasses of an abstract class called AEater with an abstract method called order, as shown in the table below.

 public abstract class AEater {   protected String _address;   protected AEAter(String address) { _address = address; }   public String getAddess() { return _address; }   /**   * Orders n portions of appropriate food from restaurant r.   */   public abstract String order(IRestaurant r, Integer n);    // NO CODE BODY! } public class Vegetarian extends A Eater{   public Vegetarian(String address) {      super(address);    }   public String order(IRestaurant r, Object n) {      // code to be discussed later;   } } public class Carnivore extends AEater{   public Carnivore(String address) {      super(address);    }   public String order(IRestaurant r, Object n) {      // code to be discussed later;   } }

### Abstract Class vs. Interface

When a class is declared as abstract, it cannot be instantiated, and in order for it to be of any use, one must define concrete subclasses for it  Its purpose is to define zero or more attributes (aka fields) for certain type of objects, zero or more default behaviors (i.e. methods with some code) for these objects, zero or more abstract behaviors (i.e. methods with no code body, declared as abstract) for these objects.  If an abstract class has fields, usually they are protected, meaning they can be accessed by subclasses of the abstract class.  Moreover, the existence of fields usually required a constructor to properly initialize these fields at construction time.  Such constructors are usually declared as protected to make them only accessible by the subclasses.  A constructor of a subclass must call the appropriate constructor of the abstract super class via the key word super, passing to it the appropriate parameters.  An abstract class usually has some concrete code in it.  A concrete subclass of an abstract super class inherits all the code of the super class but must override all abstract behaviors of the super class.  Any class with an abstract behavior must be declared as abstract.

The syntax for making class B a subclass of class A is: class B extends A {...}.

An interface is like an abstract class with the special constraint that all methods must be pure abstract and have no code bodies.  By definition, an interface and its methods are always public and abstract.  Thus one need not declare them using the public and abstract attributes.  An interface is used to specify a type without any concrete implementation.  When a class implements an interface, it must provide concrete code for each of the methods in this interface.  In Java, a class can extends only one other class, but can implement as many interfaces as it sees fit.  This provides a form of multiple-inheritance that has proven to be quite flexible and useful in many advanced OO designs.

The following links provide additional discussions on objects, object relationships, inheritance and polymorphism:

## The Restaurant

The restaurant is represented as an interface IRestaurant with two methods, one to cook a vegetarian dish and one to cook a meat dish, as shown in the table below.

 interface IRestaurant {    String cookVeggie(Vegetarian h, Integer n);    String cookMeat(Carnivore h, Integer n); } public class ChezAlan implements IRestaurant {   // Singleton Pattern:   public static final ChezAlan Singleton = new ChezAlan();   private ChezAlan() {}     public String cookVeggie(Vegetarian h, Integer n) {        return  n + " Brocoli and Cheese " +                "delivered to " + h.getAddress();   }   public String cookMeat(Carnivore h, Integer n) {     return  n + " Greasy Hamburger " +             "delivered to " + h.getAddress();   } } public class ChezZung implements IRestaurant {   // Singleton Pattern:   public static final ChezZung Singleton = new ChezZung();   private ChezZung() {}   public String cookVeggie(Vegetarian h, Integer n) {     return  n + " Corn on the Cob " +             "delivered to " + h.getAddress();   }   public String cookMeat(Carnivore h, Integer n) {     return  n + " Fatty Hotdog " +             "delivered to " + h.getAddress();   } }

### The Singleton Pattern

In the above, ChezAlan and ChezZung implement what is called the singleton (design) pattern.  The singleton pattern is a way to ensure that a class can only have one unique instance.  In Java, the coding pattern is very simple.

class ClassName {
public static final ClassName Singleton = new ClassName();
private ClassName() { };
// other fields and methods...
}

The constructor ClassName() is private; as a result, no client code outside of ClassName can instantiate a ClassName object.  The only way to obtain an instance of ClassName is via the reference ClassName.SingletonClassName.Singleton is instantiated only once and cannot be reassigned to another object because it is declared as final.  For example, ClassName.Singleton = null will be flagged as an error by the compiler.

Later we will apply the singleton pattern to EmptyList to express the fact that there is only one empty list in our model for the immutable list structure.

## Ordering Food From Restaurant

To order food from an IRestaurant, a Vegetarian object simply calls cookVeggie, passing itself as one of the parameters, while a Carnivore object would call cookMeat, passing itself as one of the parameters as well.  The Vegetarian  and Carnivore objects only deal with the IRestaurant object at the highest level of abstraction and do not care what the concrete IRestaurant is.  The polymorphism machinery guarantees that the correct method in the concrete  IRestaurant will be called and the appropriate kind of food will be returned to the AEater caller  The table below shows the code for Vegetarian  and Carnivore, and sample client code using these classes.

 public class Vegetarian extends A Eater{   public Vegetarian(String address) {      super(address);    }   public String order(IRestaurant r, Object n) {      return r.cookVeggie(this, n);   } } public class Carnivore extends AEater{   public Carnivore(String address) {      super(address);    }   public String order(IRestaurant r, Object n) {      return r.cookMeat(this, n);   } } // client code public  void party(AEater e, IRestaurant r, int n) {   System.out.println(e.order(r, n)); } // blah blah blah... AEater John = new Carnivore("Duncan hall"); AEater Mary = new Vegetarian("Paris, Texas"); party(Mary, ChezAlan.Singleton, 2); party(John,ChezZung.Singleton, 1);

The above design is an example of what is called the visitor pattern.  The abstract class AEater and its concrete subclasses are called the hosts.  The restaurant interface IRestaurant and all of  its concrete implementations are called visitors.  Before we present the visitor pattern, we discuss a simple pattern called the union pattern.

### The Union Pattern

Suppose I am faced with the problem of computing the areas of geometrical shapes such as rectangles and circles.  I need to build objects that are capable of computing these areas.  The variants for this problems are the infinitely many shapes: rectangles, circles, etc.  What I do is define concrete classes such as Rectangle and Circle, and make them subclasses of an interface, called IShape, which has the abstract capability of computing its area.  This is an example of the simplest yet most fundamental OO design pattern called the Union Pattern

The Union Pattern is the result of partitioning the sets of objects in the problem domain into disjoint subsets and consists of

• an abstract class (AClass)  or interface representing the superset of all the objects of interest,
• several concrete subclasses (Variant1, Variant2) representing disjoint subsets of the above superset; the union of these subsets equals the superset.

A client of the Union Pattern uses instances of the concrete subclasses (Variant1, Variant2), but should only see them as AClass objects.   The client class code should only concern itself with the public methods of AClass and should not need to check for the class type of the concrete instances it is working with.  Conditional statements to distinguish the various cases are gone resulting in reduced code complexity, making the code easier to maintain.

NOTE: the term Union Pattern is not part of the standard pattern language in the design pattern community.  Such a pattern is taken for granted in all OO design.  Here we give it a name to facilitate the discussion of its use in all future designs.

# I. The Visitor Pattern

The visitor pattern is a pattern for communication and collaboration between two union patterns: a "host" union and a "visitor" union.  An abstract visitor is usually defined as an interface in Java.  It has a separate method for each of the concrete variant of the host union.  The abstract host has a method (called the "hook") to "accept" a visitor and leaves it up to each of its concrete variants to call the appropriate visitor method.  This "decoupling" of the host's structural behaviors from the extrinsic algorithms on the host permits the addition of infinitely many external algorithms without changing any of the host union code.  This extensibility only works if the taxonomy of the host union is stable and does not change.  If we have to modify the host union, then we will have to modify ALL visitors as well!

NOTE: All the "state-less" visitors should be singletons.

# II. Decoupling Algorithms from Data Structures

Recall the current formulation of the immutable list structure.

Each time we want to compute something new, we have to add appropriate methods to IList and implement those methods in EmptyList and NEList.  This process of extending the capability of the list structure is error-prone at best and cannot be carried out if one does not own the source code for this structure.  The system so designed is inherently cumbersome, rigid, and limited.  We end up with a forever changing IList that includes a multitude of unrelated methods.

These design flaws come of the lack of delineation between the intrinsic and primitive behavior of the structure itself and the more complex behavior needed for a specific application. The failure to decouple primitive and non-primitive operations also causes reusability and extensibility problems. The weakness in bundling a data structure with a predefined set of operations is that it presents a static non-extensible interface to the client that cannot handle unforeseen future requirements.  Reusability and extensibility are more than just aesthetic issues; in the real world, they are driven by powerful practical and economic considerations.  Computer science students should be conditioned to design code with the knowledge that it will be modified many times.  In particular is the need for the ability to add features after the software has been delivered.  Therefore one must seek to decouple the data structures from the algorithms (or operations) that manipulate it.  An object-oriented approach to address this issue proceeds as follows.

# III. Fundamental Object-Oriented Design Methodology (FOODM)

1. Identify and separate the variant and the invariant behaviors.

2. Encapsulate the invariant behaviors into a system of classes.

3. Add "hooks" to this class to define communication protocols with other classes.

4. Encapsulate the variant behaviors into a union of classes that comply with the above protocols.

The result is a flexible system of co-operating objects that is not only reusable and extensible, but also easy to understand and maintain.

Let us illustrate the above process by applying it to the design of the immutable list structure and its algorithms.

1. Here, the invariant is the intrinsic and primitive behavior of the list structure, IList, and the variants are the multitude of extrinsic and non-primitive algorithms that manipulate it, IListAlgo.

2. The recursive list structure is implemented using the composite design pattern and encapsulated with a minimal and complete set of primitive structural operations:  getFirst() and getRest()

3. The hook method Object execute(IListAlgo ago,  Object inp) defines the protocols for operating on the list structure. The hook works as if a IList announces to the outside world the following protocol:

“If you want me to execute your algorithm, encapsulate it into an object of type IListAlgo, hand it to me together with its inp object as parameters for my execute().  I will send your algorithm object the appropriate message for it to perform its task, and return you the result.

• emptyCase(...) should be the part of the algorithm that deals with the case where I am empty.

• nonEmptyCase(...) should be the part of the algorithm that deals with the case where I am not empty.”

4. IListAlgo and all of its concrete implementations forms a union of algorithms classes that can be sent to the list structure for execution.

The above design is nothing but a special case of the Visitor Pattern.  Class IList is called the host and its method execute() is called a "hook" to the IListAlgo visitors.  Via polymorphism, IList knows exactly what method to call on the specific IListAlgo visitor.  This design turns the list structure into a (miniature) framework where control is inverted: one hands an algorithm to the structure to be executed instead of handing a structure to an algorithm to perform a computation.  Since an IListAlgo only interacts with the list on which it operates via the list’s public interface, the list structure is capable of carrying out any conforming algorithm, past, present, or future.  This is how reusability and extensibility is achieved.

The following is a direct quote from the Design Patterns book by Gamma, Helm, Johnson, and Vlissides (the Gang of Four - GoF).

"Frameworks thus emphasizes design reuse over code resuse...Reuse on this level leads to an inversion of control between the application and the software on which it's based. When you use a toolkit (or a conventional subroutine library software for that matter), you write the main body of the application and call the code you want to reuse. When you use a framework, you reuse the main body and write the code it calls...."

The linear recursive structure (IList) coupled with the visitors as shown in the above is one of the simplest, non-trivial, and practical examples of frameworks.  It has the characteristic of "inversion of control" described in the quote. It illustrates the so-called Hollywood Programming Principle: Don't call me, I will call you. Imagine the IList union sitting in a library. When we write an algorithm on an IList  in conformance with its visitor interface, we are writing code for the IList to call and not the other way around. By adhering to the IList framework's protocol, all algorithms on the IList can be developed much more quickly. And because they all have similar structures, they are much easier to "maintain". The IList  framework puts polymorphism to use in a very effective (and elegant!) way to reduce flow control and code complexity.

# IV. Visitor Code Examples

 /**  * Computes the length of the IList host.  */ public class GetLength implements IListAlgo {    /**    * Singleton Pattern.    */    public static final GetLength Singleton = new GetLength();    private GetLength() {   } /**    * Returns Integer(0).    * @param nu not used    * @return Integer    */    public Object emptyCase(IEmptyList host, Object... nu) {      return 0;   } /**     * Return the length of the host's rest plus 1.     * @param nu not used.     * @return Integer > 0.     */     public Object nonEmptyCase(INEList host, Object... nu) {      Integer restLen = (Integer)host.getRest().execute(this);       return 1 + restLen;  // auto-unboxing of restLen and auto-boxing of 1 + restLen    } /**  * Assumes the IList host contains Integer, computes the minimum of the all  * the Integer objects in the host.  */ public class GetMin implements IListAlgo {     /**      * Singleton Pattern.      */     public static final GetMin Singleton = new GetMin();     private GetMin() {     } /**     * Throws an IllegalArgumentException.     * @param nu not used     * @return does not return.     * @exception IllegalArgumentException    */     public Object emptyCase(IEmptyList host, Object... nu) {       throw new IllegalArgumentException("no data!");     } /**    * Passes the host's data to the host's rest     *  and asks for help.    * @param nu not used    * @return Integer    */    public Object nonEmptyCase(INEList host, Object... nu) {      return host.getRest().execute(GetMinHelp.Singleton, host.getFirst());   } public class GetMinHelp implements IListAlgo {     public static final GetMinHelp Singleton = new GetMinHelp();     private GetMinHelp() {     } /**   * Returns inp[0].   * @param inp Integer inp[0] is the minimum of the preceding list.   * @return Integer   */    public Object emptyCase(IEmptyList host, Object... inp) {      return inp[0];   } /**    * Recurs by passing the minimum between the host's first    * and inp, the accumulated current minimum.    * @param inp Integer inp[0] is the minimum of the preceding list.    * @return Integer    */    public Object nonEmptyCase(INEList host, Object... inp) {      int f = (Integer)host.getFirst(); // auto-unboxing      int i = (Integer)inp[0];          // auto-unboxing      return host.getRest().execute(this, Math.min(f, i));  // auto-boxing of Math.min(f, i)   }

dxnguyen at rice edu, Last Revised 01/31/2005