1. Information Hiding Information hiding is a tried-and-true design principle that advocates hiding all implementation details of software components from the user in order to facilitate code maintenance. It was first formulated by David L. Parnas (in 1971-1972) as follows. One must provide the intended user with all the information needed to use the module correctly and nothing more. translation to OOP: the user should not know anything about how an interface or abstract class is implemented. For example, the user need not and should not know how IList is implemented in order to use it. The user should only program to the abstract specification. One must provide the implementor with all the information needed to complete the module and nothing more. translation to OOP: the implementor of a class or an interface should not know anything about how it will be used. For example, the implementor need not and should not know how, when, or where IList will be used. The implementor should write the implementation code based solely on the abstract specification. By adhering to the above, code written by both users and implementors will have a high degree of flexibility, extensibility, interoperability and interchangeability. The list framework that we have developed so far has failed to hide MTList and NEList, which are concrete implementations of IList, the abstract specification of the list structure. In many of the list algorithms that we have developed so far, we need to call on MTList.Singleton or the constructor of NEList to instantiate concrete IList objects. The following is another such examples. InsertInOrder.java


import listFW.*;

/**
 * Inserts an Integer into an ordered host list, assuming the host list contains
 * only Integer objects.
 */
public class InsertInOrder implements IListAlgo {

    public static final InsertInOrder Singleton = new InsertInOrder();
    private InsertInOrder() {
    }

    /**
     * This is easy, don't you think?
     * @param inp inp[0] is an Integer to be inserted in order into host.
     */
    public Object emptyCase(MTList host, Object... inp) {
        return new NEList(inp[0], host);
    }

    /**
     * Delegate (to recur)!
     * @param inp inp[0] is an Integer to be inserted in order into host.
     */
    public Object nonEmptyCase(NEList host, Object... inp) {
        int n = (Integer)inp[0];
        int f = (Integer)host.getFirst();
        return n < f ?
                new NEList(inp[0], host):
                new NEList(host.getFirst(), (IList)host.getRest().execute(this, inp[0]));
    }
}

The above algorithm to insert in order an integer into an ordered list of integers can only be used for a very specific implementation of IList, namely the one that has MTList and NEList as concrete subclasses. How can we write list algorithms that can be used for ANY implementation of the abstract specification of the list structure represented by the abstract class IList? We can achieve our goal by abstracting the behavior of MTList and NEList into interfaces with pure abstract structural behaviors. applying the Abstract Factory Design Pattern to hide the concrete implementation from the user.

2. Abstract List Behaviors The concrete empty list and non-empty list implemented as MTList and NEList are now expressed as interfaces as follow.


package listFW;

/**
 * Represents the abstract behavior of the immutable list structure.
 * A list intrinsically "knows" how to execute an algorithm on itself.
 */
interface IList {
    Object execute(IListAlgo algo, Object... inp);
}


package listFW;

/**
 * Represents the immutable empty list.
 * The empty list has no well-defined structural behavior:
 * it has no first and no rest.
 */
interface IMTList extends IList {
}


package listFW;

/**
 * Represents the immutable non-empty list.
 * An immutable non-empty list has a data object called first, and an
 * isomorphic subcomponent called rest.  Its structural behavior
 * provides access to its internal data (first) and substructure (rest).
 */
interface INEList extends IList {
    /**
     * "Gettor" method for the list's first.
     * @return this INElist's first element.
     */
    Object getFirst();

    /**
     * "Gettor" method for the list's rest.
     * @return this INElist's rest.
     */
    IList getRest();
}

3. Abstract List Factory Before we describe in general what the Abstract Factory Pattern is, let's examine what we have to do in the case of IList. Define an abstract factory interface, IListFactory, to manufacture empty and non-empty IList objects. Put IList, IMTList, INEList, IListVistor, and IListFactory in the same package. IListFactory is specified as followed. IListFactory.java


package listFW;

/**
 * Abstract factory to manufacture IMTList and INEList.
 */
interface IListFactory {
    /**
     * Creates an empty list.
     * @return an IMTList object.
     */
    IMTList makeEmptyList();

    /**
     * Creates a non-empty list containing a given first and a given rest.
     * @param first a data object.
     * @param rest != null, the rest of the non-empty list to be manufactured.
     * @return an INEList object containing first and rest
     * @exception IllegalArgumentException if rest is null.
     */
    INEList makeNEList(Object first, IList rest);
}

IList, IListAlgo, and IListFactory prescribe a minimal and complete abstract specification of what we call a list software component. We claim without proof that we can do everything we ever want to do with the list structure using this specification. All algorithms (i.e. visitors) that call for the creation of concrete IList objects will need to have an abstract factory as a parameter and use it to manufacture IList objects. We usually pass the factory as an argument to the constructor of the visitor. The visitor is thus not a singleton. InsertInOrderWithFactory.java


import listFW.*;

/**
 * Inserts an Integer into an ordered host list, assuming the host list contains
 * only Integer objects.  Has no knowledge of how IList is implemented.  Must
 * make use of a list factory (IListFactory) to create IList objects instead of
 * calling the constructors of concrete subclasses directly.
 */
public class InsertInOrderWithFactory implements IListAlgo {

    private IListFactory _listFact;

    public InsertInOrderWithFactory(IListFactory lf) {
        _listFact = lf;
    }

    /**
     * Simply makes a new non-empty list with the given inp parameter as first.
     * @param host an empty IList.
     * @param inp inp[0] is an Integer to be inserted in order into host.
     */
    public Object emptyCase(IMTList host, Object... inp) {
        return _listFact.makeNEList(inp[0], host);
    }

    /**
     * Recur!
     * @param host a non-empty IList.
     * @param inp inp[0] is an Integer to be inserted in order into host.
     */
    public Object nonEmptyCase(INEList host, Object... inp) {
        int n = (Integer)inp[0];
        int f = (Integer)host.getFirst();
        return n < f ?
                _listFact.makeNEList(inp[0], host):
                _listFact.makeNEList(host.getFirst(),
                                    (IList)host.getRest().execute(this, inp[0]));
    }
}

The above algorithm only "talks" to the list structure it operates on at the highest level of abstraction specified by IList and IListFactory. It does know and does not care how IList and IListFactory are implemented. Yet it can be proved to be correct. This algorithm can be plugged into any system that subscribes to the abstract specification prescribed by IList, IListAlgo, and IListFactory. Provide a concrete implementation of the abstract factory that contains all concrete subclasses of IList as private static classes and thus hide them from all external code. CompositeListFactory.java


package listFW.factory;

import listFW.*;

/**
 * Manufactures concrete IMTList and INEList objects.  Has only one
 * instance referenced by CompositeListFactory.Singleton.
 * MTList and NEList are static nested classes and hidden from all external
 * client code.  The implementations for MTList and NEList are the same as
 * before but completely invisible to the outside of this factory.
 */
public class CompositeListFactory implements IListFactory {

    /**
     * Note the use of private static.
     */
    private static class MTList implements IMTList {
        public final static MTList Singleton = new MTList ();
        private MTList() {
        }

        final public Object execute(IListAlgo algo, Object... inp) {
            return algo.emptyCase(this, inp);
        }

        public String toString() {
            return "()";
        }
    }

    /**
     * Note the use of private static.
     */
    private static class NEList implements INEList {
        private Object _first;
        private IList _rest;

        public NEList(Object dat, IList rest) {
            _first = dat;
            _rest = rest;
        }

        final public Object getFirst() {
            return _first;
        }

        final public IList getRest() {
            return _rest;
        }

        final public Object execute(IListAlgo algo, Object... inp) {
            return algo.nonEmptyCase(this, inp);
        }


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

    /**
     * Singleton Pattern
     */
    public static final CompositeListFactory Singleton = new CompositeListFactory();
    private CompositeListFactory() {
    }

    /**
     * Creates an empty list.
     * @return an IMTList object.
     */
    public IMTList makeEmptyList() {
        return MTList.Singleton;
    }

    /**
     * Creates a non-empty list containing a given first and a given rest.
     * @param first a data object.
     * @param rest != null, the rest of the non-empty list to be manufactured.
     * @return an INEList object containing first and rest
     */
    public INEList makeNEList(Object first, IList rest) {
        return new NEList(first, rest);
    }
}

Pass such a concrete factory to all client code that need to make use of the abstract factory to manufacture concrete IList instances. Below is an example of a unit test for the InsertInOrderWithFactory algorithm. Test_InsertInOrderWithFactory.java


package listFW.visitor.test;
import listFW.*;
import listFW.factory.*;
import listFW.visitor.*;

import junit.framework.TestCase;

/**
 * A JUnit test case class.
 * Every method starting with the word "test" will be called when running
 * the test with JUnit.
 */
public class Test_InsertInOrderWithFactory extends TestCase {
  

  public void test_ordered_insert() {
    IListFactory fac = CompositeListFactory.Singleton;
    IListAlgo algo = new InsertInOrderWithFactory(fac);
    
    IList list0 = fac.makeEmptyList();   
    assertEquals("Empty list", "()", list0.toString());
    
    IList list1 = (IList) list0.execute(algo, 55);
    assertEquals("55->()", "(55)", list1.toString());

    IList list2 = (IList) list1.execute(algo, 30);
    assertEquals("30->(55)", "(30, 55)", list2.toString());
    
    IList list3 = (IList) list2.execute(algo, 100);
    assertEquals("100 -> (30, 55)", "(30, 55, 100)", list3.toString());
    
    IList list4 = (IList) list3.execute(algo, 45);
    assertEquals("45->(30, 55, 100)", "(30, 45, 55, 100)", list4.toString());
    
    IList list5 = (IList) list4.execute(algo, 60);
    assertEquals("60 -> (30, 45, 55, 100)", "(30, 45, 55, 60, 100)", list5.toString()); 
  }  
}

The above design process is an example of what is called the Abstract Factory Design Pattern. The intent of this pattern is to provide an abstract specification for manufacturing a family of related objects (for examples, the empty and non-empty IList) without specifying their actual concrete classes thus hiding all details of implementation from the user. Our example of the list structure framework successfully delineates specification from implementation and faithfully adheres to the principle of information hiding. IList, IMTList, INEList, IListAlgo, and IListFactory provide a minimal and complete abstract specification. InsertInOrderWithFactory is a concrete implementation of IListAlgo that performs a concrete operation on the host list. Yet this algorithm need only communicate with the list structure and the list factory via their public interface. It will work with any implementation of IList and IListFactory. CompositeListFactory is a concrete implementation of IListFactory. It uses the composite pattern and the visitor pattern to implement IList. It only communicates with IListAlgo at and knows nothing about any of its concrete implementation. The private static attributes provide the proper mechanism to hide all implementation details from all code external to the class. Click here to access the complete javadoc documentation and UML class diagram of the list component described in the above. Click here to download the complete source code and documentation of the list component described in the above.

4. Frameworks 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. The above list framework dictates the design of all algorithms operating on the list structure: All algorithms must be some concrete implementation of IListAlgo. Algorithms that require the construction of empty and/or non-empty lists, must do so via some abstract list factory, IListFactory. In order to apply an algorithm to a list, one must ask a list to "execute" that algorithm, giving it the required input parameter. 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. We do not know anything about how the above list framework is implemented, yet we have been able to write quite a few algorithms and test them for correctness. In order to obtain concrete lists and test an algorithm, we call on a concrete IListFactory, called CompositeListFactory, to manufacture empty and non-empty lists. We do not know how this factory creates those list objects, but we trust that it does the right thing and produces the appropriate list objects for us to use. And so far, it seems like it's doing its job, giving us all the lists we need.

5. Bootstrapping Along Let's take a look back at what we've done with a list so far: Created an invariant list interface with two variant concrete subclasses (Composite pattern) where any algorithms on the list where implemented as methods of the interface and subclasses (Interpreter pattern) Extracted the variant algorithms as visitors leaving behind an invariant "execute" method. Accessor methods for first and rest installed. The entire list structure now becomes invariant. Abstracted the creation of a list into an invariant factory interface with variant concrete subclass factories. Separated the list framework into an invariant hierarchy of interfaces and a variant implementation which was hidden inside of a variant factory class. Is there something systematic going on here? Notice that at every stage in our development of our current list framework, we have applied the same abstraction principles to the then current system to advance it to the next stage. Specifically, we have identified and separated the variant and invariant pieces of the system and defined abstract representations whenever needed. This really tells us about some general characteristics of software development: Software development is an iterative process. You never get the right answer the first time and you have to slowly "evolve" your code closer and closer to what you want. Every time you change your code you learn something more and/or new about your system and/or problem. This is because every new formulation of your solution represents a new way, a new view as it were, on the problem and this new view highlights aspects you hadn't considered before. The revision process is driven along by a repetitive application of the abstract decomposition techniques such as separating the variant and invariant. Are we done with our list refinements? Will we ever be "done"? What do the above characteristics say about the way we should approach software development? Also, now that we have managed to abstract structure, behavior and construction, is there anything left to abstract? Or is there one more piece to our abstraction puzzle (at least)?