Parameterized Definitions

In our extended Java specification, interface and class definitions can be parameterized, allowing them to define a group of related types that have similar behavior but which differ in the types of objects they manipulate. All parameters are types; the definition indicates the number of parameters, and provides formal names for them. For example, the interface

    interface SortedList [T] ...  

    interface Map [Key, Value] ...  

In general, a parameterized definition places certain requirements on its parameters. For example, a "SortedList" must be able to sort its elements; this means that the actual element type must provide an ordering on its elements. Similarly a "Map" must be able to compare keys to see if they are equal. The parameterized definition states such requirements explicitly by giving _where clauses_, which state the signatures of methods and constructors that objects of the actual parameter type must support. We discuss why we selected where clauses rather than other parameter constraint mechanisms in Section 2.8.

Figure 1 shows these two interfaces with their where clauses.

    interface SortedList [T]
          where T { boolean lt (T t); } ... { }
    interface Map [Key, Value]
          where Key { boolean equals (Key k); } ... { }

In the definition of "SortedList", the where clause indicates that a legal actual parameter must have a method named "lt" (less than) that takes a "T" argument and returns a "boolean". The second definition states that a legal actual parameter for "Key" must have a method named "equals" that takes a "Key" as an argument and returns a "boolean". Note that "Map" does not impose any constraints on the "Value" type, and therefore any type can be used for that parameter.

The body of a parameterized definition uses the type parameters to stand for the actual types that will be provided when the definitions are used. For example, Figure 2 gives the sorted list interface. Note the use of the parameter "T" to stand for the element type in the headers of the methods. Thus the "insert" method takes in an argument of type "T", and the "first" method returns a result of type "T".

interface SortedList[T] where T {boolean lt (T t);} {
// overview:  A "SortedList" is a mutable, ordered sequence.
//   Ordering is determined by the "lt" method of the element type.

    void insert (T x);
    // modifies:  this
    // effects:  adds x to this

    T first ( ) throws empty;
    // effects:  if this is empty, throws empty,
    //   else returns the smallest element of this

    void rest ( ) throws empty;
    // modifies:  this
    // effects:  if this is empty, throws empty,
    //   else removes the smallest element of this

    boolean empty ( );
    // effects:  if this is empty, returns true,
    //   else returns false.
}