1. Decoupling Algorithms from Data Structures

Recall the current formulation of the immutable list structure using the composite pattern.

Figure 1

Each time we want to compute something new, we apply the interpreter pattern add appropriate methods to IList and implement those methods in MTList 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. Any method added to the system can access the private fields of MTList and NEList and modify them at will.  In particular, the code can change _fist and _rest of NEList breaking the invariant immutable property the system is supposed to represent. The system so designed is inherently fragile, 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.  Before we present an object-oriented approach to address this issue, let's first eat!

2. 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 people out there called chefs!  These are very special kinds of chefs catering only to vegetarians and carnivores.  These chefs only know how to cook two dishes: one vegetarian dish and one meat dish.  All John and Mary have to do is to know how to ask such a chef to cook 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 chef, the two kinds of dishes the chef cooks, and how the customer orders the appropriate kind of dish from the chef?

public abstract class AEater {  
    public String getSalt() { 
        return "salt";
    }
    public String getPepper() { 
        return "pepper"; 
    }
    /**  
    * Orders n portions of appropriate food from restaurant r.  
    */  
    public abstract String order(IChef r, Integer n);    
	// NO CODE BODY!
}

public class Vegetarian extends AEater{  
    public String getBroccoli() { 
        return "broccoli"; 
    }    
    public String getCorn() { 
        return "corn"; 
    }    
    public String order(IChef c, Object n) {
        // code to be discussed later;  
    }
}

public class Carnivore extends AEater{  
    public String getMeat() { 
        return "steak"; 
    }    
    public String getChicken() { 
        return "cornish hen"; 
    }   
    public String getDog() {
        return "polish sausage"; 
    }    
    public String order(IChef c, Object n) {     
	// code to be discussed later;  
    }
}

interface IChef  {  
	String cookVeggie(Vegetarian h, Integer n);
	String cookMeat(Carnivore h, Integer n);
}

public class ChefWong implements IChef {
	public static final ChefWong Singleton
		= new ChefWong();
	private ChefWong() {}
	public String cookVeggie(Vegetarian h, Integer n) {
		return  n + " portion(s) of " +
				h.getCarrot() + ", " + 
				h.getSalt();
	}
	public String cookMeat(Carnivore h, Integer n) {
		return  n + " portion(s) of " +
				h.getMeat() + ", " +
				h.getPepper();
	}
}

public class ChefZung implements IChef {
	public static final ChefZung Singleton
		= new ChefZung();
	private ChefZung() {}
	public String cookVeggie(Vegetarian h, Integer n) {
		return  n + " portion(s) of " +
				h.getCorn() + ", " +
				h.getSalt();
	}
	public String cookMeat(Carnivore h, Integer n) {
		return  n + " portion(s) of " +
				h.getChicken() + ", " +
				h.getPepper() +
				", " + h.getSalt();
	}
}

public class Vegetarian extends AEater {
	// other methods elided
	public String order(IChef c, int n) {
		return c.cookVeggie(this, n);
	}
}

public class Carnivore extends AEater {
	// other methods elided
	public String order(IChef c, int n) {
		return c.cookMeat(this, n);
	}
}

// client code
public void party(AEater e, IChef c, int n) {
	System.out.println(e.order(c, n));}
	// blah blah blah...
	AEater John = new Carnivore();
	AEater Mary = new Vegetarian();
	party(Mary, ChefWong.Singleton, 2);
	party(John,ChefZung.Singleton, 1);
				  

3. 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!

Figure 2

NOTE: All the "state-less" visitors, that is visitors that contain no non-static fields should be singletons.  Visitors that contain non-static fields should not be singletons.

4.  Fundamental Object-Oriented Design Methodology (FOODM)

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.

Below is the UML class diagram of the resulting list design.  Click here to see the full documentation.  Click here to see the code.

Figure 3

The above design is nothing but a special case of the Visitor Pattern.  The interface IList is called the host and its method execute() is called a "hook" to the IListAlgovisitors.  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.

5. List Visitor 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(0)
 */
public Object emptyCase(MTList 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(NEList host, Object... nu) {
	Object restLen = host.getRest().execute(this);
	return 1 + (Integer)restLen);
}

package listFW;
/**
 * Computes a String reprsentation of IList showing a left parenthesis followed
 * by elements of the IList separated by commas, ending with with a right parenthesis.
 * @stereotype visitor
 */

public class ToStringAlgo implements IListAlgo {
	public static final ToStringAlgo Singleton = new ToStringAlgo();
		private ToStringAlgo() {
		}

	/**
	 * Returns "()".
	 */
	public Object emptyCase(MTList host, Object... inp) {
		return "()";
	}

	/**
	 * Passes "(" + first to the rest of IList and asks for help to complete the computation.
	 */
	public Object nonEmptyCase(NEList host, Object...  inp) {
		return host.getRest().execute(ToStringHelper.Singleton, "(" + host.getFirst());
	}
}

/**
 * Helps ToStringAlgo compute the String representation of the rest of the list.
 */
class ToStringHelper implements IListAlgo {
	public static final ToStringHelper Singleton = new ToStringHelper();
	private ToStringHelper() {    }

/**
 * Returns the accumulated String + ")".
 * At end of list: done!
 */
public Object emptyCase(MTList host, Object... acc) {
	return  acc[0] + ")";
}

	/**
	 * Continues accumulating the String representation by appending ", " + first to acc
	 * and recurse!
	 */
	public Object nonEmptyCase(NEList host, Object... acc) {
		return host.getRest().execute(this, acc[0] + ", " + host.getFirst());
	}
}

We now can use to ToStringAlgo to implement the toString() method of an IList.

package listFW;

public class MTList implements IList {

	/**
	 * Singleton Pattern
	 */
	public final static MTList Singleton = new MTList();
		private MTList() { }
		/**
		 * Calls the empty case of the algorithm algo,
		 * passing to it itself as the host parameter
		 * and the given input inp as the input parameter.
		 * This method is marked as final to prevent all
		 * subclasses from overriding it.
		 * Finalizing a method also allows the compiler to
		 * generate more efficient calling code.
		 */
		 public final Object execute(IListAlgo algo, Object... inp) {
		 	return algo.emptyCase(this, inp);
		 }
		 public String toString() {
		 	return (String)ToStringAlgo.Singleton.emptyCase(this);
		 }
	}

package listFW;

public class NEList implements IList {
	/**
	 * The first data element.
	 */
	private Object _first; 

	/**
     * The rest or "tail" of this NEList.
     * Data Invariant: _rest != null;
     */
	private IList _rest;

    /**
     * Initializes this NEList to a given first and a given rest.
     * @param f the first element of this NEList.
     * @param r != null, the rest of this NEList.
     */
    public NEList(Object f, IList r) {
		_first = f;
		_rest = r;
    }

    /**
     * Returns the first data element of this NEList.
     * This method is marked as final to prevent all subclasses 
     * from overriding it.
     * Finalizing a method also allows the compiler to generate 
     * more efficient calling code.
     */
    public final Object getFirst() {
	    return _first;
    }

    /**
     * Returns the first data element of this NEList.
     * This method is marked as final to prevent all 
     * subclasses from overriding it.
     * Finalizing a method also allows the compiler 
     * to generate more efficient calling code.
     */
    public final IList getRest() {
 	   return _rest;
    } 

    /**
     * Calls the nonEmptyCase method of the IListAlgo parameter, 
     * passing to the method itself as the host parameter and the 
     * given input as the input parameter.
     * This method is marked as final to prevent all subclasses from
     * overriding it. Finalizing a method also allows the compiler 
     * to generate more efficient calling code.
     */
    public final Object execute(IListAlgo algo, Object... inp) {
	    return algo.nonEmptyCase(this, inp);
    }

    public String toString() {
	    return (String)ToStringAlgo.Singleton.nonEmptyCase(this);
    }
}

Download the above code here.