You are here: Home V2 Software Software More ... Developer Notes Legacy Notes Keller on Genericity

Keller on Genericity

Further musings on genericity. Keller 2006

Does this solve the type redeclaration avalanche?

Further musings on genericity

The short answer for Java is only partially, but it might be good enough. (C++ is different: with its free-for-all casting you can solve the problem if you know what you are doing, or blast yourself completely out of orbit if you don't). The article that helped me get this straight is by Meyer (again): "Genericity versus Inheritance", Object-Oriented Programming, Systems, Languages and Applications, Proceedings p 391 (1986). The text of this article is freely available from http://se.ethz.ch/~meyer/publications/acm/geninh.pdf so I'm not going to discuss it extensively. The point is that Meyer compares implementing [ADA-like] genericity using inheritance with implementing inheritance using genericity. In doing this, he makes a distinction between constrained and unconstrained genericity.

Our LinkedList/BiLinkedList3 Java example provides an example of constrained genericity: these classes make use of other classes of linkable elements. The constraint is that in order to maintain the genericity of LinkedList and BiLinkedList3, Linkable and BiLinkable3 have to provide a set of features that LinkedList and BiLinkedList3 require (namely the setNext method). In this case, we have done this by creating an inheritance hierarchy between the linkable element classes that mirrors that between the linked list classes. There is no absolute requirement to do this: BiLinkable3 could be defined so that it provides a setNext method without inheriting from from Linkable. We would then be in trouble, and would have to accept extensive code duplication between LinkedList and BiLinkedList3 just to sort out types. Note that encapsulating the construction of the linkable element relies on the fact that a reference to a BiLinkable3 can be cast to a Linkable, which is allowed because the supertype relationship holds between these two types (in the subtyping notation of the Java Language Specification, Linkable :> BiLinkable3). If this wasn't true, we would either have to duplicate code, or weaken the static type safety of the application by defining newElement to return a reference to Object.

In a pure programming  environment it wouldn't necessarily be so bad: Eiffel allows multiple inheritance so that the BiLinkable3.setNext() method can always be acquired through an inheritance hierarchy, and Java provides interfaces and inner classes for the same reason. In the memops framework which does not have these features, things would get awkward if BiLinkable3 could not inherit from Linkable.

The limiting type of genericity is unconstrained genericity, when there is no requirement for a type that is used by a class to provide any particular features at all. Meyer's example of this is in the article above is a STACK type: objects of any type can be stackable. (You could even have a stack of stacks!) How do you then ensure that all the elements on a stack are the same type? What is the return type for the method that returns the top element of the stack? This is the problem that the introduction of generics in Java 5.0 addresses - in earlier versions the STACK class(es) would have to either:

  • declare the stackable element as type Object and lose much of the benefit of polymorphism (or do some hairy programming with the reflection interface), or:
  • define a STACK_XXX class for every type XXX that you want to have a stack for. There are then two sub-possibilities that unconstrained genericity allows:
    1. The types XXX are members of a common inheritance hierarchy, even though they don't provide any features to the STACK_XXX classes. The approach in the linked-list examples here should then still be applicable, although there is  still a problem with return types: methods that return an element of the stack can only have a return type of the highest common superclass of the XXX types (violating this in Java 1.4 and below will produce a compile-time error). This means that when retrieving an object from a STACK using an overridden method like STACK_XXX.pop(), you can only access methods of some superclass of XXX, unless you cast the returned object back to the original type XXX. This eliminates the possibility of static type checking for clients of the STACK_XXX class.
    2. The types XXX are not members of a common inheritance hierarchy. Extensive code duplication to sort out type declarations (i.e. the redeclaration avalanche) is then inevitable to avoid violating the Java casting and type conversion rules. Using interfaces is not going to help here: an interface definition STACKABLE would be empty and so provide us with nothing.
So my provisional conclusion is that genericity (constrained and unconstrained) implemented with inheritance could be handled up to a point in the new memops framework without needing to implement Java's generics and without triggering the redeclaration avalanche - this is what following Meyers rules on conformance for method arguments gives us. There would still be a problem with method return types and support for Java 1.4 and below: some conditional casting may be required in Java code, or the rules on method overriding hardened so that the return type is not allowed to change.


Constrained genericity that is not implemented with inheritance is by itself a non-obvious thing to do. Where it is required is where two types A and B that are already subclasses of other classes but not related to each other by inheritance need to provide some common set of methods to two other classes X and Y. X and Y are related by inheritance. This cannot be handled in the current memops framework, and the redeclaration avalanche could result from this. Java provides interfaces to get around this problem, and it may be that if any cases are hit where this is a problem, memops and the Java code generator would need to support interfaces too.

Unconstrained genericity that is not implemented with inheritance is equivalent to the new generics feature in Java 5.0. Once again this is not supported by the current memops framework.

Concrete suggestions now: it is probably too much to do to implement everything to avoid the redeclaration avalanche at this stage (and it would raise issues about supporting Java 1.4 and below anyway).

  • Allow method overriding with conforming parameter types (and return types? to be discussed): this would already go half-way towards avoiding the problem, and be a huge improvement on what is currently there.
  • Support for interfaces would probably not be a huge job (says he, not really knowing :-)), but it is not clear that we need to support code generation from them at this stage. Suggestions:
    • Consider/discuss supporting interfaces at this stage, but only to the extent that the ObjectDomain->Memops transformation checks that an interface's methods are implemented in realising classes, and that the return and parameter types conform across the realisation relationship. In this connection, we note that "an interface X is realised by a class A, and has a method m that is implemented in class A" is closely related to "a class X has a subclass A, and has a method m that is overridden in class A". In other words, the "realises" relationship is much like the "inherits from" relationship, and "implements" is much like "overrides". The salient difference is that a class can only inherit from one other class, but can implement any number of interfaces. This might seem to be sliding into multiple inheritance territory, but unlike with classes there is no conceptual problem here as long as the conformance rules are applied:
      1. If a class A realises two interfaces X and Y, and X and Y both define a method m, nothing special needs to be done. The parameters and return type of A.m() are checked separately for conformance with those of X.m() and Y.m(). The model only passes if both checks pass. This is trivially extended to the case where A inherits from a class B, as well as realising X and Y, and A also overrides a method B.m() [although this does beg the question whether it should be B rather than A that realises X and Y].
      2. Interfaces can inherit from each other. Once again, nothing special needs to be done: methods can be redefined in decscendant interfaces only if the conformance rules are satisfied.
    • Don't consider multiple inheritance for interfaces at this stage, even though they don't present the same problems as multiple inheritance for classes. It is not clear that they would be useful to any actual CCPN-associated projects.
    • Don't consider the generation of interfaces by the Java code generator in the next version of the memops framework, but keep an eye out for any cases where it would be useful to have this. A concrete example would also help to decide if there are any considerations relevant to the Python code generator. To make this feature really useful, associations with interfaces would need to be supported, and this is another complicating factor.
  • Don't consider supporting Java 5.0-type generics (i.e. unconstrained genericity without inheritance). This is a complex subject, and is for the longer-term future, unless someone comes up with a show-stopping case that cannot be handled in any other way.