Generics or as they are known in C++ haven't been the target of much study among the design patterns community. When they have, C++ templates have often been the focus, which leads people away from the concepts and into the implementation more often than not. I want to consider several well known patterns, the Singleton and Visitor and to see how generics can be used to improve them. Along the way suggestions for improving generics may be developed.
In order to develop an understanding of the purpose and use of generics in object-oriented design, first we consider an immutable list implemented in a purely OO style.
|
|
Recall the definition of a list. A list is either a head which is
data and a tail which is a list or is "null". In Scheme these
correspond to cons boxes and the null list '(). In an object oriented
style this definition is expressed through a class hierarchy. The
abstract concept of a list is represented by the
ALispList class. The binary definition of a list
is represented by the two subclasses, NonNullList and
NullList. Each of these two provide a concrete
implementation for each of the standard list operations
car (get head) and cdr (get tail). The
standard cons operation is independent of whether one is
consing onto a null or non-null list. This is expressed in the fact
that the method is concrete in the abstract super-class. Since
cons is the only way that should be used to build up a
list the constructor of the NonNullList is package so
that an instance can't be created from outside of the package i.e. only
the cons method can instantiate one. In addition to the standard
operations, toString() and accept(...)
methods are provided. The conversion to string is non strictly
necessary and could be provided through other means. It is present
for convenience and because Java objects have a toString()
which is an implied contract that all objects will provide an appropriate
conversion to a string representation. The overloading inside the
list fulfills this contract. For more info on the
toString() and accept(...) methods see
Visitor section below.
Fundamentally there is only one null list since all null lists are
equivalent. In Scheme this is expressed by the fact that there is
only one '() value. In an OO system the Singleton design pattern is
the standard way to express this. The constructor of
NullList is private so that no other class can
instantiate it. A static instance and accessor is then provided to
allow access to the single object in the system.
The method which most differentiates the OO style of list from the
procedural or functional style is accept(). This is part
of the visitor design pattern. The visitor design pattern does have
parallels to functional styles but it is not as obvious (see my OO
vs. Functional work). The visitor provides a hook to add operations
which work on a list. Though the visitor algorithms written to
operate on the list are not simply external loops or recursion, but
almost internal recursion. It can appear as if we have added a
method. This occurs through double dispatching which is available in
some other object oriented languages but must be written explicitly in
Java. Through double dispatching information is gathered. The diagram
below shows the sequence of calls which might occur near the end of a
recursive process using visitors:
|
In the diagram the client deals with some list at the abstract level
and calls accept() with the visitor. The list being
actually a concrete list calls visitNonNullList() on the
visitor passing itself as the host. The visitor does some operations
to its host then recurs by calling accept() on the rest
of the list with itself as the visitor. The rest happens to be a
NullList so it calls the visitNull() method
back on the visitor. The visitor can then do its base case operations
and the system can return back out of the recursion.
Through the process of visiting an object, discovery of the object's type and the action that needs to be done occurs. At the beginning of the process the Client is aware of the abstract action which needs to be performed (the visitor type) and of the list instance that the operation should be performed on. The client does not, however, know the type of the object the operation should be performed on. The accept method is then called on the list and the list then knows that an operation must be performed though it doesn't know exactly which one must be performed. Being the type it is, the list object knows which method must be called on the visitor. When the correct method is called on the visitor, the visitor now knows exactly what must be done. The visitor is the operation and it knows which object and the type of the object to perform the operation on. Since execution has reached its method it knows that the operation needs to be performed.
The above presents a view of the visitor as a complex discovery process through which we come to a point in the code where we implicitly know all the information we need in order to do the task required. Another view of the functioning is that we have added a method. That is, we have added to the abstract class a behavior which takes some value and returns another. In addition it is overridden to do different behaviors when called on different subclasses. The only difference then between normal methods and the added "methods" is that they are not inherent to the object and work from the "outside". They can be expressed purely in terms of the intrinsic methods.
These are two equivalent views of the role of visitors. This is why a
toString() could be written through a visitor. It isn't,
because it wouldn't then override the super class' method. One method
which would seem to be missing is a way to check whether a list is
null. This is not intrinsic because a trivial visitor can be written
to tell whether a list is null or not.
Two visitors have been written as examples of two typical algorithms
that might be written for lisp lists. The
ListLengthVisitor returns the length of the data in a
list and is independent of the data in the list. The second
ShorterThanVisitor requires that all the objects in the
list be strings. It returns the concatenation of all the strings in
the list which have a length smaller than the Integer
parameter. Both are singletons because there is only conceptually one
of each.
There are three problems with the code of
ListLengthVisitor. The fact that the parameter is unused
and really need not be passed in can't be expressed. The return type
is Integer but this is not explicit, this causes the
third problem, that a downcast which is guaranteed to always work must
still be present.
public Object visitNull(NullList host, Object unused) |
The ShorterThanVisitor suffers from similar problems.
The param and return types are not explicit which causes numerous
casts in the methods. In fact more casts would be required if the
java language did not implicitly call toString() to
concatenate objects to a string.
public Object visitNull(NullList host, Object size) |
The problems with the use of visitors is also apparent to the client who only implicitly knows the type of the param and the return from the accept method. We'll see later that Generic Java helps improve this situation.
|
The Object-Oriented lisp list as presented above works well. However
it suffers from the fact that clients of the list have no information
about the type of data stored in a list. This is often not a problem
because when your variable is named dogList its not hard
to remember that it should be filled with dogs. However it is all to
easy to pass it to some function expecting a different type of list or
one which will put different types of objects in the list. Generics
are largely aimed at correcting this.
In addition to this, the OO list suffers from the problems of missing type information around the visitor as pointed out before. Generics can also be used to address this problem.
The lisp list was modified to be generic on the data type the list
holds. This entailed modifying the ALispList to
return a list based on the same type of data from cons and cdr. To
take and return that data type from cons and car instead of
Object. Both the NonNullList and
NullList were changed to match the changes in the super
class and be generic on the data type. In addition the visitor and
accept methods were radically changed to fix the previous problems.
Although Generic Java fixes many problems with the lisp list and its
associated visitor it introduces problems with the Singleton. Before
the introduction of generic types all NullLists were
considered equivalent. The question is, is the null of a list for
holding foos equivalent to the null of the list holding bars? It is,
because in each case it behaves the same. Ff you want a list of
animals can I give you a list of dogs? If the list were mutable the
answer would be no. I might give you a list of dogs which would be
ok for you but then you may insert a cat which would break my type on
the list. However, if the object is const or immutable this is not
the case. It is safe then because you can't change the object and
mess up my typing. In the case of the null list, no matter what type
of list you expect I can give you the empty list, so it should still
be a Singleton. GJ causes problems for this because it is almost
inexpressible in GJ.
We would like to express the concept that the NullList
type is a subtype of ALispList generic on any data
type. Using a notation borrowed from the internal representation of
generics in GJ this might be written.
class NullList extends ALispList<*> |
Here the * stands for any type. So that this literally states that
NullList is a subtype all types of lists. This is
unfortunately not allowed in GJ, it is only used internally to handle
type resolution when a type is not known, say when null is passed in a
place that would be used to infer type.
In order to get close to expressing this concept in GJ one must make use of a feature provided only for backwards compatibility. GJ allows the use of a class without its generic parameters. This is called the "raw type". A raw type may be converted to any parameterized type with only a warning under the assumption that the programmer is combining legacy code with new code and knows that conversion is safe. This can be used to create a single raw type instance which is then converted and given out whenever an instance is requested. This generates one compiler warning.
public class NullList<Data> extends ALispList<Data> |
Generics fix many of the problems of the visitor presents. The accept method is generic on the parameter and return types of the visitor so that it can take and return types appropriate to the visitor. The visitor can then be generic on the parameter, return and data types. This creates an excellent system for the accept method which guarantees type safety. One issue that has not been addressed and needs more work is visitors being generic on the exceptions they throw (see A Note on Exceptions). As can been seen with the example visitors there are still a few problems with the visitors.
public abstract class ALispList<Data> |
public interface IListVisitor<Data, Return, Param> |
The two example visitors created for normal lisp lists,
ShorterThanVisitor and ListLengthVisitor
have been converted to work with the generic lisp list. The
ShorterThanVisitor has all of its problems solved
by the generics so we will consider it first.
The ShorterThanVisitor specifies an exact type for the
return and params as well as the data that should be in the list. It
doesn't suffer from the problem of the NullList singleton
because it isn't really even templated, it extends a templated class
specifying exactly the types it is templated on.
|
public class ShorterThanVisitor implements IListVisitor<String, String, Integer> { private static ShorterThanVisitor instance = new ShorterThanVisitor(); private ShorterThanVisitor() { } public static ShorterThanVisitor Singleton() { return instance; } public String visitNull(NullList<String> host, Integer size) { return ""; } public String visitNonNull(NonNullList<String> host, Integer size) { return (size.intValue()>=host.car().length()?host.car()+"\n":"") + host.cdr().accept(this,size); } } |
The ListLengthVisitor suffers from the problem that
several of its concepts can't be directly expressed in GJ. The list
length visitor always returns an integer which works well in GJ.
However it doesn't use its parameter. It would be ideal if it could
be expressed directly that the parameter is not used. By say
designating the type as void. However this is not possible, instead
Object is used and ignored. The visitor also suffers from the same
problem as the NullList, that is, the visitor doesn't
care the type of the data in the list. Another way to say this is it
is properly a subtype of all visitors who have an Integer return and
ignore their parameter, no matter what data type they expect. Since
the visitor is also a singleton then we must use the compatibility
features of GJ just as in the NullList to make it
possible to indirectly express this relationship. This makes it work, but it still
doesn't say what is actually meant.
Generics or Templates are more formally known as parametric polymorphism. This is meant to mean that the types are taken as parameters. However, it is more often taken to mean exactly what C++ does with templates. That is generate a copy of the class for each template instantiation. This look at Generics and Design Patterns shows that there use is independent of this interpretation of their implementation. Indeed their essence isn't really that of taking types as parameters, instead it is as an extended contract that a class will preserve the level of abstraction you are working at. This is parallel to the concept that when passing templated classes as const one won't damage the abstraction level one is working at.
Thus Generics are a means of extending our work with types and preserving a level of abstraction. They are only one part in an incomplete system to handle abstraction, types and polymorphism.
This research has assumed that everything takes place in an ideal world were no exceptions would be necessary. In the real world visitors often need to throw exceptions. This would necessitate the ability to be generic on the type of exception thrown. Along with that ability the logical extension is the ability to have exceptions which are generic on some type. As of this writing the first is seems partially supported but chancy. The second is not supported because it seems to require runtime support which Sun is not yet willing to provide in order to incorporate generics.