Generic Programming

Part I: Fundamental Concepts

Chapter 3: Software Components

Last updated 10 April 1998

§ 3.1 -- Introduction

Generic programming is based on the idea that we can break programs down into components, and write many of the components in a general way that allows them to be mixed and matched with a variety of other components. We implement this composition by defining the set of interfaces (i.e. operators and functions) assumed by a component, and then providing those interfaces in other components. In the preceding chapter, we discussed our assumptions about the standard operators and their interfaces. However, few interesting components can be written practically using only standard operators. Rather, we must often specify interfaces at a higher level.

Using higher level interfaces provides us with a corresponding increase in the power available from our components, but it also makes it easy to define interfaces which are so specialized that it becomes difficult to use them in a variety of contexts. We can minimize this effect by clearly understanding the purposes served by components, and by designing component interfaces to cleanly satisfy one of a small set of such purposes. This perspective is the core of this chapter, which will discuss a taxonomy of software components, and describe effective techniques for developing and using them in C++.

Before we proceed with the presentation of this taxonomy, it is important to point out what we are not trying to do. The past 25 years have seen attempts to revolutionize programming by reducing all programs to a single conceptual primitive. Functional programming, for example, made everything into a function; the notions of states, addresses, and side effects were taboo. Then, with the advent of object-oriented programming (OOP), functions became taboo; everything became an object (with a state and associated methods).

Far from solving the problems of programming, these reductionist approaches have been distracting and ultimately harmful. Effective programming uses a variety of paradigms, because different parts of the problem have different requirements. For example, an array and a binary search should not be reduced to a single, fundamental notion. The two are quite different. An array is a data structure -- a component that holds data. A binary search is an algorithm -- a component that performs a computation on data stored in a data structure. As long as a data structure provides an adequate access method, you can use the binary-search algorithm on it. Only by respecting the fundamental differences between arrays and binary searches can efficiency and elegance be simultaneously achieved.

This observation leads directly to the orthogonal decomposition of component space which is at the core of generic programming. We want to understand the differences between components. Only by understanding these can we identify the meaningful similarities which are the basis of our taxonomy. This is the fundamental philosophical failure of the reductionists. By starting with the claim that everything is a function, or an object, and ignoring their differences, they discard all knowledge. A definition that fits everything provides no interesting information. The attempt to reduce everything to a single category is also methodologically wrong. It is as if mathematicians were to start with axioms, and then see if any of the resulting theorems were interesting. Instead, mathematicians start with likely theorems, attempt to prove them, and finally identify their axioms based on the requirements of of their proofs. Similarly, programming methodologies should begin with interesting algorithms, understand them well, and only then attempt to define interfaces that will make them work. (I don't actually like this analogy. It's pretty weak.)

Another important failing of the language design community has resulted from a fundamental misunderstanding of addresses and pointers. Many brilliant computer scientists have observed problems with pointers, and come to the conclusion that they should be avoided. Functional programming was motivated partially by the desire to work with values instead of addresses. Object-oriented programming attempts to minimize pointer use by providing access only to the object and not directly to its members. The Ada programming language limited pointer use to objects in the heap, forbidding their use with global (static) and stack objects.

But in fact, pointers are very good. We don't mean dangling pointers. We don't mean pointers to the stack. But the general notion of pointer is a powerful tool, universally used. In programming, as in the real world, we are usually interested in identifying specific objects rather than identifying an object with a particular value. The address of the object is how we identify it. Sometimes we can use the notion of a variable name in lieu of an explicit address, but complex data structures and algorithms to do not lend themselves to explicit naming of each component, depending on the use of anonymous pointers or indices to navigate a uniform space like a vector or a tree.

It is incorrectly believed that pointers make our thinking sequential. That is not so. Without some kind of address we cannot describe any parallel algorithm. If we attempt to describe an addition of n numbers in parallel, we need to be able to talk about the first number being added to the second number, while the third number is added to the fourth number. Some kind of indexing is required. Addresses are fundamental to our conceptualization of any algorithm, sequential or parallel.

Rather than attempt to avoid pointers, we will abstract their useful properties, developing them carefully in Part III. By abstracting them, we can actually provide a more disciplined usage, which helps to avoid some of the problems which led to the misguided attempts to eliminate pointers.

§ 3.2 -- Taxonomy of Software Components

Taxonomy of Types and Data Structures

Taxonomy of Algorithms

§ 3.3 -- Function Objects

Writing and using general-purpose algorithms depends on our ability to take the operations defined on an arbitrary type and map them to the specific operations required by a generic algorithm. For example, consider a sort algorithm. Its most fundamental requirement is an operation which compares two elements of the data structure being sorted, and orders them. Although the default "<" operator is often appropriate for this purpose, it is by no means the only interesting ordering operator. Thus, we need a way to provide a specific function with the name expected by the generic algorithm.

Even in C, we can pass a pointer to a function as a parameter to another function, but this is not as general as we would like. It is useful to be able to specify not only the code to be used for a function, but also some state. For example, if we are passing a function which adds two numbers modulo some base, we need to associate the base value with the function. We call this construct a function object, because it is an object which incorporates a function's code along with the state data which it requires. The alternatives, i.e. putting the state in global variables referenced by the function, or writing a distinct version of the function for each state of interest, are clearly less desirable.

In C++, our preferred technique for defining and using function objects is derived from the treatment of template functions. When C++ sees a function call which matches a template, it automatically instantiates the template with the required template parameters. However, it must be able to derive those parameters' types from the types of the function call parameters. Consider the following code fragment: 


template < class T, class Compare >
void sort ( T* first, T* last )
{
  Compare comp;
  ...
}
The intent of this code fragment is that an instantiation of the template specifies, as template parameters, the type T of the values to be sorted, and the type Compare of a function object which can be used for comparisons. This type Compare can then be used inside sort to declare the function object comp that is actually used for comparisons. This approach has the apparent advantage that the call to sort need not pass a parameter for the Compare function object type.

However, if the application calls this template function for sort, the compiler cannot deduce the desired Compare type from the parameter list, which specifies only the first and last positions to be sorted. Instead, then, we use a declaration like the following, passing the function object as an explicit parameter: 


template < class T, class Compare >
void sort ( T* first, T* last, Compare comp )
{
  ...
}
Although this version requires an additional parameter to the sort function, this is less of a concern than it seems. If the Compare class contains no data members, serving only to identify the comp function it encapsulates, an effective compiler can ignore the parameter in the instantiation of the sort function. (This is also why we generally pass function objects by value instead of by reference -- the object itself is generally small enough that avoiding a copy is not worth the cost of dereferencing a pointer.) More importantly, as we shall soon see, the comp function object may contain data members which cannot be derived from its type, in which case the first version of sort above would be unable to make use of it. For both of these reasons, generic function should generally include formal function object parameters for any function on which it as generic dependencies, unless the function type can be unambiguously derived from the other parameters.

With this context in mind, let us consider the appropriate interface for the Compare function object itself. We could require that the Compare class have a comparison function as a member function with a particular name. But C++ gives us a means to avoid adding another name to the specification -- we can define an application operator, which allows us to simply treat the function object's name as the function name: 


// Define a comparison function using <
template < class T >
struct less
{
  ...
  bool operator() ( const T& x, const T& y ) const
  {
    return x < y;
  }
};

// Instantiate and use a function less:
int i[100];
...
sort ( i, i+100, less<int>() );
This simple function object exhibits some interesting points. First, notice how we pass the function object in our call to sort. The syntax, less<int>(), specifies an instantiation of the less class for type T as int with the string "less<int>", and the parentheses following it indicate the invocation of a default constructor to create a concrete object of that type as the actual parameter.

Next, consider the declaration of the formal parameters to operator() as const T&. While we could pass them by value, this could be much more expensive for large types T, or for types T with expensive copy constructors. This is particularly true in cases where the "<" operator for T ends up referencing a small part of the object. On the other hand, if the type T is a simple type without copy constructors, the compiler is free to actually pass it by copying the value if that is less expensive. With an ideal compiler, therefore, we get the best of both worlds.

To deal with less than ideal compilers, in important cases, it may still be desirable to provide specializations of the function object for common simple cases. For example, we might specialize for int as follows: 


// Specialize template struct less for int:
template <>
struct less<int>
{
  ...
  bool operator() ( int x, int y ) const
  {
    return x < y;
  }
};
In this template specialization in scope, an instantiation of less<int>() in our call to sort will produce the specialization, passing the parameters by value, instead of instantiating the more general template and possibly passing them by reference.

The examples we have considered so far associate no state with the function object -- the function code requires none. This is not always the case, however. In fact, much of the power of function objects comes from the ability to include state with the function, without passing additional parameters and thereby changing the interface.

As a demonstration, let us consider a different sorting problem. Some algorithms in graphics, for instance convex hulls, start by sorting a list of points in the order of the angle of a line connecting a particular point with each of them in turn. This sorting problem involves a comparison operator with state in the form of the distinguished point. If points are represented as pairs of floats, we might start with the following definition: 


// Define a point:
struct point
{
  float x_coord;
  float y_coord;

  // Construct a point (x,y):
  point (void) : x_coord(0.0), y_coord(0.0) {}
  point (float x, float y) : x_coord(x), y_coord(y) {}
};
Obviously, this is a very simple definition. We represent a point simply as its x and y coordinates in the plane, and provide a default constructor as well as a constructor which creates a point from its coordinates. The default copy constructor and assignment operator, which will simply copy the coordinate members, are satisfactory for our purposes. In order to provide a full regular type, as we specified in the previous chapter, we should provide global operator== and operator< functions as well, but we will not need them for this simple example, so we omit them here. Observe that this definition is really an instance of the STL pair template. The struct definition above could be replaced simply by: 

typedef pair<float,float> point;
Doing so is simpler, and would automatically provide the missing functions. We provide the above definition just to be explicit.

Now consider how to sort a set of these points in order of their angles from a central point. First, we define a function which returns the angle between the line connecting them and the x-axis: 


// Angle in radians between points p1 and p2:
inline float angle (const point& p1, const point& p2)
{
  return atan2 (p2.y_coord-p1.y_coord, p2.x_coord-p1.x_coord);
}
Finally, we are ready to define our comparison operator, and use it to sort a vector of points: 

// Define a less-than function based on the angle:
template <>
struct less<point>
{
  point origin;

  // Construct a less function object:
  less<point> (const point& p) : origin(p) {}

  // Compare two points based on their angle:
  bool operator() (const point& p1, const point& p2) const
  {
    return angle (origin, p1) < angle (origin, p2);
  }
};

...
// Sort a list of points relative to origin (x,y):
float x, y;
point origin (x, y);
less<point> comp (origin);
point p[100];
...
sort ( p, p+100, comp );
...

Next, present an example of a function object with state. One possibility is a less than function defined on points in a plane, comparing the distance of two points from a fixed third point; This fits well into the sort framework we have already introduced. A second possibility is a function which tests whether its parameter value is less than some fixed value. This could be used with the find function. It provides the basis for a discussion of the binder function object adapters, and could lead into, or fit into, the next section.

§ 3.4 -- Function Object Adapters

§ 3.5 -- Binding and Composition

§ 3.6 -- Component Traits

§ 3.7 -- Categories and Category Dispatching

§ 3.8 -- Primitive Recursive Functions

Implementation Queue

The following are points to be integrated somewhere:

Send comments about this page to Jim Dehnert or Alex Stepanov.