Comp310: Generic Lists

COMP 310	Generic List Frameworks

A more basic discussion can be found at the Resources page on Java Generics

For this discussion, we will examine how generics can be used to reformulate our immutable list framework to produce a much more type-safe system.

The code available for download (genILists.zips) contains the algorithms mentioned below and test code plus the list implementation of a mutable list framework (LRS).

Here's the code:

The definition of visitors in the generic IList framework is of particular interest: It shows the use of paremeterized methods, upper and lower bounds and multiple type parameters very well.

Here is the definition of the IList interface:

package listFW;
 
/**
 * Defines an immutable list that holds elements of type E.
 * Serves as a host for an algorithm on a list to visit its internal structure.
 * Has a "hook" method to call on the appropriate method of the visitor, making
 * the immutable list structure a framework.
 * @author Dung X. Nguyen
 * @author Stephen B. Wong
 * @since Copyright 2004 - DXN, SBW All rights reserved
 * @stereotype host
 * @param <E> The type of data held by the list (the elements of the list)
 */
public interface IList<E> {
    /**
     * A visitor pattern "hook" method that executes an IListAlgo.
     * @param algo the visitor, the algorithm to be executed.  
     * Any visitor that works on a super type of E is accepted.
     * @param <R> The type of the return value
     * @param <P> The type of the vararg input parameter values.
     * @param inp a generic input parameter to be used by the algorithm algo.
     * @return Object output from executing the algorithm algo.
     */
    public abstract  <R,P>  R execute(IListAlgo<? super E, R, P> algo, P ... inp);
}

First, note the <E> in the interface declaration: It tells you that we are defining a list containing instances of E, whatever that may be. For example, an IList<Integer> contains Integer objects.

In the definition of the execute() method, however, we see <R,P>, and that defines two more type parameters R and P that are only valid for this one method. This is an example of a parameterized method inside a parameterized class. R is the type of the return value of the execute() method, and P is the type of the inp varargs.

Furthermore, the definition of execute() spells out exactly what kind of visitor it needs:

The visitor needs to operate on lists containing elements of type E, or supertypes of it. Supertypes are allowed too, because a visitor that is designed to handle any object of type Number can certainly also handle objects or type Integer. We therefore make use of lower bounds.
The visitor must return objects of type R.
The visitor must accept varargs of type P as parameters.

The actual types of R and P will be deduced at the call site for execute(); they are not nailed down in this definition. The compiler, however, will make sure that all occurrences of R, P and E at a call site are consistent, so you cannot execute a visitor for lists of numbers on a list of strings, or pass string varargs to a visitor requiring numbers.

Take a look at the definition of the IListAlgo interface:

package listFW;
 
/**
 * A visitor to (algorithm on) an IList<T> where T is a subclass of E
 * Also parameterized by it return type R and parameter type T.
 * @param <E> The type of data held by the host list (the elements of the list)
 * @param <R> The type of the return value
 * @param <P> The type of the vararg input parameter values.
 */
public interface IListAlgo<E,R,P> {
 
    /**
     * Case that is executed when the host is an empty list
     */ 
    public abstract R emptyCase(IMTList<? extends E> host,  P ... inp);
 
    /**
     * Case that is executed when the host is a non-empty list
     */
    public abstract R nonEmptyCase(INEList<? extends E> host,  P ... inp);
}

The visitor has three type parameters, E, R and P, and they specify the types of the list elements the visitor can process, the return value, and the varargs, respectively. If you look at the definition of the two visitor methods, you can see that they accept IMTList and INEList instances whose type parameter is E or a subclass thereof. This is an example of an upper bound.

The upper bound on E tells us that a given algorithm (visitor) can operate on any list who holds elements that are subtypes of of the type for which the algorithm was designed. That is, an algorith that can process Fruit can also process Apples or Oranges.

Examples of algorithms on the generic IList framework in the supplied code.

Sum a list of Integers
Sum a list of Numbers returning a double value
Reverse a list
Find an element in a list of Comparables

A Matter of Viewpoint

Notice that in a generic visitor pattern, that the hosts express their visitors in terms of lower bounded wildcard generics (a "contravariant" relationship) while the visitors express their hosts in terms of upper bounded wildcard generics (a "covariant" relationship). (Here's a nice article on covariance and contravariance in relation to bounded generics.)

These opposite relationships are not a hack to get the visitor system to work but rather a fundamental aspect of how the two pieces of the system relate to eachother. A Visitor Design Pattern system like a list framework is an example of a "Component-Framework System" or "Component-Framework Architecture". In these systems, there is an overarching "framework" whose job is to provide invariant, intrinsic services for the system. Here, the framework is the list, i.e. the hosts. "Components", on the other hand, "plug into" the framework and provide the remaining variant services for the system. Here, the components are the visitors. The combination of the components and the framework thus form the complete system.

Component-framework system are very common in modern applications, especially user applications. Essentially any "plug-in" architecture is a component-framework system, e.g. Eclipse, any web browser and most media and office productivity applications. Component-framework systems are also very common in modular back-end systems that need high degrees of configurability, such as in accounting and other management systems.

The upper bounded wildcard (covariant) vs. lower bounded wildcard (contravariant) generic relationship is intrinsic to component-framework systems. From the viewpoint of a framework, looking at its components, a framework can only work with components that can handle more types than the framework was designed for -- an upper-bound/contravariant situation.

But the components are seeing the overall system from the opposite viewpoint. When a component looks at the framework, a component can only work in a framework that is designed for fewer types than that component can handle--a lower-bound/covariant situation.

In the end, this all means that one can expect to use both covariant and contravariant relationships whenever one is trying to express a component-framework system.

This page was adapted and augmented from discussion material created by Mathias Ricken (code created by S. Wong and D. X. Nguyen)

COMP 310

Generic List Frameworks

A Matter of Viewpoint