ET: Genericity and Arrays

Some of the classes that we will need, particularly in libraries, are container classes, describing data structures made of a number of objects of the same or similar types. Examples of containers include arrays, stacks and lists. The class DEPOSIT_LIST posited in earlier examples describes containers.

It is not hard, with the mechanisms seen so far, to write the class DEPOSIT_LIST, which would include such features as count (query returning the number of deposit objects in the list) and put (command to insert a new deposit object).

Most of the operations, however, would be the same for lists of objects other than deposits. To avoid undue replication of efforts and promote reuse, we need a way to describe generic container classes, which we can use to describe containers containing elements of many different types.

Making a class generic

The notation class C [G] ... The rest as for any other class declaration ...

introduces a generic class. A name such as G appearing in brackets after the class name is known as a formal generic parameter; it represents an arbitrary type.

Within the class text, feature declarations can freely use G even though it is not known what type G stands for. Class LIST of EiffelBase, for example, includes features first: G -- Value of first list item extend (val: G) -- Add a new item of value val at end of list ...

The operations available on an entity such as first and val, whose type is a formal generic parameter, are the operations available on all types: use as source y of an assignment x := y, use as target x of such an assignment (although not for val, which as a formal routine argument is not writable), use in equality comparisons x = y or x /= y, and application of universal features from ANY such as twin, is_equal and copy.

To use a generic class such as list, a client will provide a type name as actual generic parameter. So instead of relying on a special purpose class DEPOSIT_LIST, the class ACCOUNT could include the declaration all_deposits: LIST [DEPOSIT]

using LIST as a generic class and DEPOSIT as the actual generic parameter. Then all features declared in LIST as working on values of type G will work, when called on the target all_deposits, on values of type DEPOSIT. With the target all_accounts: LIST [ACCOUNT]

these features would work on values of type ACCOUNT.

Info: A note of terminology: to avoid confusion, Eiffel always uses the word argument for routine arguments, reserving parameter for the generic parameters of classes.

Genericity reconciles extendibility and reusability with the static type checking demanded by reliability. A typical error, such as confusing an account and a deposit, will be detected immediately at compile time, since the call all_accounts. extend ( dep ) is invalid for dep declared of type DEPOSIT. What is valid is something like all_accounts. extend ( acc ) for acc of type ACCOUNT. In other approaches, the same effect might require costly run-time checks (as in Java, C# or Smalltalk), with the risk of run-time errors.

Info: This form of genericity is known as unconstrained because the formal generic parameter, G in the example, represents an arbitrary type. You may also want to use types that are guaranteed to have certain operations available. This is known as constrained genericity and will be studied with inheritance.

Arrays

An example of generic class from the Kernel Library is ARRAY [G], which describes direct-access arrays. Features include:

  • put to replace an element's value, as in my_array.put (val, 25) which replaces by val the value of the array entry at index 25.
  • item to access an entry, as in my_array.item (25) yielding the entry at index 25. A synonym is infix "@", so that you may also write more tersely, for the same result, my_array @ 25 .
  • lower, upper and count: queries yielding the bounds and the number of entries.
  • The creation procedure make, as in create my_array.make (1, 50) which creates an array with the given index bounds. It is also possible to resize an array through resize, retaining the old elements. In general, the Eiffel method abhors built-in limits, favoring instead structures that resize themselves when needed, either from explicit client request or automatically.

The comment made about INTEGER and other basic classes applies to ARRAY too: Eiffel compilers know about this class, and will be able to process expressions of the form my_array.put (val, 25) and my_array @ 25 in essentially the same way as a C or Fortran array access -- my_array [25] in C. But it is consistent and practical to let developers treat ARRAY as a class and arrays as objects; many library classes in EiffelBase, for example, inherit from ARRAY. Once again the idea is to get the best of both worlds: the convenience and uniformity of the object-oriented way of thinking; and the efficiency of traditional approaches.

A similar technique applies to another Kernel Library class, that one not generic: STRING, describing character strings with a rich set of string manipulation features.

Generic derivation

The introduction of genericity brings up a small difference between classes and types. A generic class C is not directly a type since you cannot declare an entity as being of type C: you must use some actual generic parameter T -- itself a type. C [T] is indeed a type, but class C by itself is only a type template.

The process of obtaining a type C [T] from a general class C is known as a generic derivation; C [T] is a generically derived type. Type T itself is, recursively, either a non-generic class or again a generically derived type D [U] for some D and U, as in LIST [ARRAY [INTEGER]].)

It remains true, however, that every type is based on a class. The base class of a generically derived type C [T] is C.