Recipe for implementing an immutable ADT that is specified by an
algebraic specification.

Let T be the name of the ADT.

Assumptions:

    Each operation of the ADT takes at least one argument of
    type T.

    Each operation is specified by one or more equations.  If
    an operation is specified by more than one equation, then
    the left hand sides of the equations differ according to
    which basic constructor was used to create an argument of
    type T.

    The equations have certain other technical properties that
    allow them to be used as rewriting rules.

    We are to implement the ADT in Java.

    The operations of the ADT are to be implemented as static
    methods of a class named T.

Recipe:

    Determine which operations of the ADT are basic
    constructors, and which are other operations.

    Define an abstract class named T.

    For each basic constructor c of the ADT, define a concrete
    subclass of T whose instance variables correspond to the
    arguments that are passed to c.  For each such subclass,
    define a Java constructor that takes the same arguments as
    c and stores them into the instance variables.

    [So far we have defined the representation of T.  Now we
    have to define the operations.]

    For each operation f of the ADT that is not a basic
    constructor, define an abstract method f that takes one
    less argument than f.  The missing argument should be of
    type T.  If f has more than one argument of type T, then
    the missing argument should be the argument that
    discriminates between the various equations for f.

    For each operation of the ADT, define a static method
    within the abstract class.

        If the operation is a basic constructor c, then this
        static method should create and return a new instance
        of the subclass that corresponds to c.

        If the operation is not a basic constructor, then this
        static method should delegate to the corresponding
        dynamic method, passing it all but one of its arguments.
        (The missing argument will be available to the dynamic
        method via the special variable named "this".)  Suppose,
        for example, that the static method T.f is called with
        arguments x1, x2, x3, and x4, where x1 is the only
        argument of type T.  Then the body of T.f should be

            return x1.f (x2, x3, x4);

    For each operation f of the ADT that is not a basic
    constructor, and for each concrete subclass C of T, define
    f as a dynamic method within C that takes the arguments
    that were declared for the abstract method f and returns
    the value specified by the algebraic specification for
    the case in which Java's special variable this will be an
    instance of C.  If the algebraic specification does not
    specify this case, then the code for f should throw a
    RuntimeException such as an IllegalArgumentException.

****************************************************************

Variations on this recipe.

There is a conflict, or tradeoff, between

    encapsulation
    modularity
    representation independence
    information hiding

and

    extensibility.

For maximum encapsulation, the subclasses of T should be private
static inner classes of T.  For maximum extensibility, these
subclasses should be public classes.  For a compromise between
encapsulation and extensibility, use default (package) or
protected (package + subclass) access.

If the subclasses of T are not private static inner classes of
T, then encapsulation can be increased by declaring each of the
dynamic methods as final.  For maximum extensibility, dynamic
methods should not be final.

If an operation f is specified by a set of equations that do not
depend on which basic constructors were used to create values of
type T, then f can be implemented entirely within the class T
without delegating to a dynamic method.  The main advantage of
this is that the code becomes smaller and simpler; the main
disadvantage is that certain changes in the specification of f
might involve adding a corresponding dynamic method to all
subclasses of T, instead of to restricting the changes to those
subclasses of T that were directly affected by the change in the
specification.

If one of the basic constructors of T takes no arguments, then
that basic constructor can return null instead of creating a
new object.  If this is done, then all of the operations except
for the basic constructors will have to check for null before
delegating to the dynamic method.  The potential advantages of
this are performance (as when the basic constructor that has
been implemented by returning null is the most common operation
of the ADT) and potentially smaller or simpler code (as when
this change eliminates all of the subclasses; see below).  The
main disadvantage is that the code will be harder to modify if
the specification is changed to add some arguments to that
basic constructor, or to add some mutable state to values that
are created by that basic constructor.

If there is only one basic constructor of T, or if there are
only two basic constructors and one of them is implemented by
returning null instead of creating a new object, then T can be
a concrete class whose instance variables correspond to the
arguments that are passed to the only basic constructor that
is not implemented by returning null.  If this is done, then
there will be no need for subclasses, and the dynamic methods
can be folded into the static methods.  The main advantage
of this is smaller and simpler code (and potentially better
performance).  The main disadvantage is that the code will be
harder to modify if the ADT's specification is changed to add
another basic constructor.

The operations of the ADT can be implemented as dynamic methods
instead of static methods.  The advantages of using static
methods are:

    One of the basic constructors that takes no arguments can
    return null instead of creating a new object.

    The ADT's encapsulation cannot be subverted by creating a
    subclass that overrides static methods.  (This can be done,
    and may be useful, but it has no effect on the encapsulation
    of the original ADT.)  Note, however, that a similar effect
    can be achieved using dynamic methods by declaring them
    final.

The main advantage of using dynamic methods is extensibility:
Dynamic methods can be overridden by a subclass.

****************************************************************