Title: From Mechanism to Method:

Trees. Everywhere. Ones with green leaves, ones with family members, ones with files and directories, ones with classes, and many more. Trees - most often upside-down with the root at the top and leaves at the bottom - offer a common and useful mechanism for organizing program elements [Jackson]. Strict hierarchies imply nesting and exclusive containment, e.g., singleinheritance hierarchies and organizational structures blighted by antediluvian management thinking. In common use, the term hierarchy also includes DAGs (directed acyclic graphs) that, although hierarchical, are not strictly hierarchies. This is the sense in which I will use it in this article because the world we live and work in more accurately reflects the elasticity of this usage, e.g., multiple-inheritance hierarchies and family trees.

But a hierarchy, strict or otherwise, is not the only way of organizing elements in a program [Hofstadter-]:

The property that distinguishes hierarchies from heterarchies is that the former is acyclic whereas the latter contains cycles.

When we look at a well-factored program, we see that the data concepts have been abstracted according to their use more often than their representation. Primitive data elements have been grouped and reclassified as information with behavior [Cardelli-]:

In C++ we have many mechanisms for organizing our types. The two most obvious are classes - which represent an explicitly named concept made available to the compiler - and template type parameters - where the concept of type is implicit according to usage [Henney2001].

Some hierarchies represent internal structural concerns: an object hierarchy whose implementation is layered through composition and forwarding, a function hierarchy where a task is decomposed into smaller tasks that are decomposed in turn, and so on. Type hierarchies, by contrast, reflect external usage concerns.

The articulation of type and subtype concepts relates to the four forms of polymorphism [Cardelli-] - inclusion, parametric, overloading, and coercion - and the five forms of substitutability in C++ [Henney2000a] - conversion, overloading, derivation, mutability, and genericity.

There are examples of hierarchies where the structural and type concerns are co-aligned. A class hierarchy, which has a tangible structural dimension, can also be a type hierarchy, so that a pointer to a derived class instance may be used where a pointer to a base is declared. This example is the most commonly quoted form of substitutability, but it is far from being the only one.

Because the number of implicit type conversions the compiler is prepared to string together on your behalf is rather low - only one foruser-defined conversions - subtype behavior across type hierarchies based on this form of substitutability tends to be in short hops. For instance, the following definitions describe a relationship where a text object is expected a string object may be provided, and where a string object is expected a char * may be provided:

class string 
{
public:
  string(const char *);
  ...
};

class text 
{
public:
  text(const string &);
  ...
};

The following will compile happily:

text message = "This will compile";

But the following will be thrown rudely back in your face:

void print(const text &);
print("This won't compile");  // too many conversions required

When considering subtyping and genericity, an actual type must support at least the features required for the template type parameter, so the features of the named type used will inevitably be a subtype of the required features. However, subtyping with generics goes further than just this formal-actual relationship, and iterator categories provide a good example. Each category defines a type^[1], and the relationships between the categories are in terms of subtyping: anything that can be considered a random access iterator will also satisfy bidirectional iterator requirements, which in turn also satisfy forward iterator requirements, which in turn satisfy both input iterator and output iterator requirements.

When looking at type hierarchies it is worth taking some time out to understand how some of the properties of substitutability come about.

Consider a base class and a derived class that is also a proper subtype of the base (i.e., uses public inheritance from the base, overrides virtual functions at least at their level of access in the base, and ensures that any member functions that would otherwise be blocked by members declared in the derived class are made accessible through using declarations). What would you expect to find available in the derived class's interface as compared to that of the base class? You'd expect to find either the same set of members or more, but not fewer. If you found fewer, this would break substitutability because you could not use a derived where a base was expected. So although you would have a class hierarchy, it would not be a type hierarchy.

This means that the type interface, considered as a set of operations, is contravariant with subtyping: as you descend the hierarchy, narrowing the possible object types you can operate on, the set of operations varies in the opposite direction (i.e., becomes wider). You can also see this with generic types: a pointer, which is the model for random access iterators, supports the same operations as an input iterator, plus many more.

Zooming in on the interface, what about the substitutability with respect to individual operations? As you descend the hierarchy narrowing the possible object types, you also narrow the possible behavior resulting from an operation call. This means that possible results also narrow. In C++, if a virtual function's return type is a pointer or reference, then it can be overridden with a more derived return type. Thus the return type can be covariant with subtyping: as you descend the hierarchy, the result type also descends. As an example, consider a simple factory scenario, where an interface class has a Factory Method [Gamma-et-al] that offers the creation of instances of a product hierarchy:

class product 
{
  ...
};

class factory 
{
public:
  virtual product *create() const = 0;
  ...
};

Covariance allows us to capture more accurately the constraint that a specific factory implementation returns a specific product, as opposed to any arbitrary product:

class concrete_product : public product 
{
  ...
};

class concrete_factory
        : public factory 
{
public:
  virtual concrete_product *create() const 
  {
    return new concrete_product;
  }
  ...
};

Covariant return types make sense when it is likely that a user will be accessing the feature through the derived type as opposed to the base. This is not often the case, especially for a factory that is intended to abstract concrete details, but it serves to highlight the public advertisement of the constraint. Either way, it is perfectly type-safe because any code written against the factory interface:

product *example(const factory *creator) 
{
  return creator->create();
}

is still valid if we reconsider it in terms of concrete_factory:

product *example(const concrete_factory *creator) 
{
  return creator->create();
}

And, if this is all there is to writing factories for such products, we can generalize the concrete factory code by mixing two forms of polymorphism, inheritance and templates:

template<typename concrete_product>
class concrete_factory
    : public factory 
{
public:
  virtual concrete_product *create() const 
  {
    return new concrete_product;
  }
  ...
};

Any transgression of type safety - if concrete_product is not descended from product - will be picked up at compile time.

Covariance also applies to other results, such as throw specs: an overridden virtual function must declare the same throw spec or a more restrictive one than the function it is overriding. So, a virtual function that does not have a throw spec can be overridden by one that does, a virtual function that declares an empty throw spec can only be overridden by one that also has an empty throw spec, and a virtual function that promises only to throw a base exception type can be overridden by one that promises to throw the same, a descendant, or nothing.

What about arguments? Does it make sense to have covariant arguments? There is only one circumstance in which it is safe, and C++ does not qualify for it: if a language supports out arguments that can be used only for results. C++ const reference arguments can be considered in arguments and non-const reference arguments can be considered inout arguments. Any argument that is effectively inout must be invariant to be type safe. It is feasible for in arguments to be contravariant, but this would greatly complicate C++'s already subtle overloading rules, so the rule is that all arguments remain invariant with subtyping. Some languages attempt to support some covariance with in arguments - this is the general case in Eiffel and is present only for array passing in Java and C#, where argument signatures themselves are not permitted to be covariant - but these are basically type system hacks that require significant extra support, typically involving runtime checks.

Covariance and contravariance are not just about declared types; they are more generally about behavior. The promise of behavior for an operation at supertype level must remain the same or be strengthened and become narrower with subtyping. For example, is the following a valid implementation of factory?

class null_factory
  : public factory 
{
public:
  virtual concrete_product *create() const 
  {
    return 0;
  }
  ...
};

It depends on what the expected result of factory::create was promised as. If the promised result at the base class level were simply "returns a delete-able pointer," then this permits null pointers. Code written (correctly) against such an interface would cater to this assumption:

void consume(product &);
void example(const factory *creator) 
{
  std::auto_ptr<product> ptr(creator->create());
  if(ptr.get())
    consume(*ptr);
}

And so null_factory::create could be seen to be a valid specialization of factory::create in this case because the behavior is covariant, i.e., narrower and more specific than that of the base.

However, if the promised result at the base class level were specified as "returns a non-null delete-able pointer," null_factory would break code that worked to this spec:

void consume(product &);
void example(const factory *creator) 
{
  std::auto_ptr<product> ptr(creator->create());
  consume(*ptr);
}

And so null_factory would not be substitutable for factory, and therefore not a subtype.

You can also see the covariant promise in action with iterator types: For an input or output iterator, there is no guarantee that a == b implies ++a = ++b, but for a forward iterator - and subtypes - the behavioral promise is strengthened and this guarantee exists. Conversely, requirements placed on callers of functions follow contravariance.

If you are familiar with design by contract [Meyer], you may recognize this as the strengthening of postconditions and weakening of preconditions with inheritance. This variance in design by contract is simply a different expression of the substitutability principle and can be derived from it directly.

Although you want to avoid cycles in your compile-time dependency graph or between threads synchronizing on common resources, there are occasions when heterarchies provide a more appropriate structuring scheme than hierarchies. A function heterarchy is expressed through recursion - either simple recursion when a function calls itself or mutual recursion where another called function calls the original caller. A bidirectional relationship between objects can be considered an object heterarchy. At any point in the execution, which object is considered to be the top-level one depends on the action and context. This is often the case with inversions of control flow such as event notification callbacks.

In a hierarchy there is a unique concept of up and down - imagine yourself anywhere in a hierarchical structure; there is a strong sense of what is above you and what is below, and a strong separation. In a heterarchy there is no such gravity - imagine yourself in a heterarchy, looking "up" or "down" you can see yourself.

Function recursion and cyclic object relationships are examples of structural heterarchies, but what of type heterarchies? The simplest example of type substitutability with a cycle is between int and double: one can be substituted where the other is expected. Granted, double to int is lossy, undesirable, and accompanied by a warning on most compilers, but it does indeed form a type heterarchy. Similarly, if a string class supports both a conversion to and from const char * (the former being ill advised, but nonetheless common), it too forms a cyclic substitutability relationship.

However, these two examples are cautionary rather than exemplary, and neither of them involves everyone's favorite class relationship, inheritance.

Imagine that you have customized the new and delete operators for a class:

class workpiece 
{
public:
  static void *operator new(std::size_t);
  static void operator delete(void *, std::size_t);
  ...
private:
  ...
  static allocation heap;
};

Assume that allocation is a class that actually provides the appropriate allocation intelligence - optimization for speed, instrumentation for debugging, etc. - and can allocate objects of a size fixed on its initialization and deallocate objects that it allocated:

class allocation 
{
public:
  allocation(std::size_t, const std::type_info &);
  void *allocate();
  void deallocate(void *);
  ...
};

Its correct use would be:

allocation workpiece::heap(
  sizeof(workpiece), typeid(workpiece));

void *workpiece::operator new(
                std::size_t size) 
{
  return size == sizeof(workpiece) ?
                heap.allocate() :
                ::operator new(size);
}

void workpiece::operator delete(
                void *ptr, std::size_t size) 
{
  if(size == sizeof(workpiece))
    heap.deallocate(ptr);
  else
    ::operator delete(ptr);
}

The size checks are important because new and delete are, by default, inherited and consequently may be used on a class whose size does not equal that of the base. The code above ensures that heap is used only for the intended size and all other allocations and deallocations are rerouted to the global operators.

If you intend to use allocation for the same purpose in any other classes, it would be nice to somehow factor out the code above as a mix-in class so that each class that wanted these services would simply inherit from the mix-in. Something like the following:

class allocated {
public:
  static void *operator new(std::size_t);
  static void operator delete(
                 void *, std::size_t);
  ...
private:
  ...
  static allocation heap;
};

class workpiece : public allocated {
  ...
};

Except not. All classes derived from allocated will share the same static heap:

class command : public allocated {
  ...
};

A command may not have the same size as a workpiece and will certainly not have the same type, so not only is heap shared but it also becomes impossible to initialize or use correctly, as the places marked ??? in the following code indicate:

allocation allocated::heap(
  sizeof(???), typeid(???));

void *allocated::operator new(
                 std::size_t size) 
{
  return size == sizeof(???) ?
                 heap.allocate() :
                 ::operator new(size);
}

void allocated::operator delete(
                void *ptr,std::size_t size) 
{
  if(size == sizeof(???))
    heap.deallocate(ptr);
  else
    ::operator delete(ptr);
}

Even attempting to factor out the constant sizeof expression will not solve the problem. It serves only to highlight it more sharply.

Essentially the problem is that the mix-in cannot be made fully independent of any derived class: there is a lingering dependency on the name and size of the derived class. This creates a cycle that can be broken by treating the downward dependency as a parameter of variation, and therefore something to template [Coplien1999]:

template<typename derived>
class allocated 
{
public:
  static void *operator new(std::size_t);
  static void operator delete(
  void *, std::size_t);
  ...
private:
  ...
  static allocation heap;
};

Given this, the implementation code can now get at the name and size of the type:

template<typename derived>
allocation allocated<derived>::heap(
  sizeof(derived), typeid(derived));

template<typename derived>
void *allocated<derived>::operator new(
                          std::size_t size) 
{
  return size == sizeof(derived) ?
               heap.allocate() :
               ::operator new(size);
}

template<typename derived>
void allocated<derived>::operator delete(
                 void *ptr, std::size_t size) 
{
  if(size == sizeof(derived))
    heap.deallocate(ptr);
  else
    ::operator delete(ptr);
}

The last piece falls into place with the mixing-in itself:

class workpiece : public allocated<workpiece>
{
  ...
};

class command : public allocated<command> {
  ...
};

Now the derived class inherits from a class that knows about it, but without any hardwired coupling that prevents its use as a general solution. Each parameterization of allocated results in a distinct type with its own code and data, which is exactly what was required.

This is the increasingly well-known Self-Parameterized Base Class or Curiously Recurring Template pattern - the latter being an evocative description of its recognition [Coplien1995] and the former being a more appropriate contemporary name based on its structure.

The allocated class template demonstrates an example of heterarchical structure involving class relationships. However, it is not a type heterarchy because no useful properties of type, except for typeid and sizeof, are used: it steadfastly avoids dealing with objects.

Consider a simple shape hierarchy, with the usual suspects ellipse and rectangle. It makes sense to be able to copy such objects polymorphically by cloning them:

class shape 
{
public:
  virtual shape *clone() const = 0;
  ...
};

class ellipse : public shape 
{
public:
  explicit ellipse(const ellipse &);
  virtual shape *clone() const {
    return new ellipse(*this);
  }
  ...
};

class rectangle : public shape 
{
public:
  explicit rectangle(const rectangle &);
  virtual shape *clone() const {
    return new rectangle(*this);
  }
  ...
};

There are a couple of observations to make on this:

It would be nice to factor out the common source structure, except that it is the structure as opposed to the verbatim code that needs factoring out. Again, there is a cyclic type dependency, and this time more entrenched because of object creation and copy construction. And again, a Self-Parameterized Base Class offers a way to break the cycle [Henney1999]:

class shape 
{
public:
  virtual shape *clone() const = 0;
  ...
};

template<typename derived, typename base>
class cloner : public virtual base 
{
public:
  virtual base *clone() const 
  {
    return new derived(
      static_cast<const derived &>(*this));
  }
  ...
};

class ellipse : public cloner<ellipse, shape> 
{
  ...
};

class rectangle : public cloner<rectangle, shape> 
{
  ...
};

There are a few observations to make on this solution:

A template technique that is becoming increasingly common has been taken and explored within the conceptual framework of substitutability. From its early sightings [Barton-] and subsequent exploration [Coplien1995] to the present day [Henney2000b, Kreft-], the Self-Parameterized Base Class pattern has found increased applicability in expressing cyclic type relationship problems once they have been recognized as such.

There are many techniques that combine two main forms of generalization - templates and inheritance - and a number of them have been used in this article. However, a Self-Parameterized Base Class has the distinction that it unifies the forms under the heading of substitutability but not of hierarchy.