The HyperCube Metaphor for Generic Programming in C++

Stepanov (author of C++'s stl) is a proponent of what he calls generic programming. This post considers a metaphor that might make more intuitive what he is advocating. This metaphor offers a visual image that makes clear the benefits of programming this way, a 4-D hypercube.

Consider a project with several data types that all need a similar set of functions. In a procedural language, the set of functions would have to be written over and over again for every data type. Think of a 2-D grid with two orthogonal axes. On one axis are the data types, on the other the functions. The programmer had to fill the area defined by the axes. Since the work scales quadratically with the length of the axes, large projects quickly become unwieldy. Both the development and maintenance costs of this approach are high and obvious.

Object oriented languages attempt to solve this problem through polymorphism. The intent is to write one axis, the functions, just for the base class, with the other axis populated with the derived types. Now the programmer only has to program the 'axes', not the area they conceptually cover. His work now scales only linearly with the size of the project, instead of quadratically. This actually works quite well for many problems, but unfortunately, by no means all. Part of why templates were developed is because they cover a wider range of such problems.

Now the idea of generic programming is to extend this basic strategy. The C++ stl did so in two new directions, containers and algorithms. Conceptually, each defines a new axis. Now there are four axis, defining a 4-D hypercube. My guess is that the intent of Design Patterns is to define an abstraction that can be treated as an 'axis' and code only to the axis. Client code therefore gains the benefit of the body of the hypercube, but without imposing polynomial complexity upon the programmer.

As an example, consider a project with 10 base classes, an average of 10 derived classes per base class, 10 different containers, and 10 algorithms. Programming the entire body of the hypercube in a procedural language would require 10,000 entities. Programmed with generic programming, it would require only 40.

In the history of software, there have been two great advances. The transition from machine code to assembler increased programmer productivity by a factor of 10, an order of magnitude. So did the transition from assembler to procedural languages. Since then, there has been no comparable advance, with the exception of special cases such as databases. Object oriented languages were supposed to be the next great advance, but despite their advantages, they only increased programmer productivity by a factor of two. The rise of new tools, IDE's, etc. have had at least as large an impact. Generic programming may have the potential to offer an order of magnitude improvement in programmer productivity.

Now for the gotcha. Stepanov states that C++ is the language that allowed him to get closest to generic programming. The stl is his expression of what he means by generic programming. In exploring this virgin territory he has made impressive progress and shown the rest of us the way. However, the design of the algorithms in the stl all assume that the contents of the containers are 'values'. When they are pointers, many of the algorithms don't do what the programmer most likely intends. The sort algorithm for instance will sort the pointers, when what is intended is to sort the objects. Ideally, the objects get compared, and the pointers get swapped. Indeed, the sort algorithm is overloaded with an optional compare routine which permits this, but having to write the sort algorithm another time violates the hypercube metaphor.

One company has come out with a ptr_vector container to address this issue, but this means the vector container was coded again, so this approach also violates the hypercube metaphor. The reason this hole is important is that polymorphism in C++ requires the use of pointers. Without them, an entire axis of the hypercube is lost. To have my 4-D hypercube, I want to include polymorphism, but I can't have a container of pointers and keep the algorithms of the stl. One way or another, my hypercube becomes just a cube. What is needed is to recognize that the abstract concepts of value and pointer define another axis, one which might be extended indefinitely to include any number of degrees of dereferencing. (This might sound academic, but the original Mac made heavy use of handles, pointers to pointers, to optimize memory management allowing automatic compaction to reduce memory fragmentation.)

So what I seek is a way to template the algorithms for either values or pointers. It is not entirely clear to me how to achieve this, but the company that figures it out, may find they have a business opportunity offering a replacement stl.

Making the C Macro 'offsetof' Work with C++

The macro offsetof is a little-known bit of C tucked away in stddef.h. It computes the byte offset of a member from the start of the structure. It is defined in gcc 3.3 as...

#define offsetof(__s_name, __m_name) ((__size_t)((__s_name*)0)->__m_name))

It's clever, efficient, and portable. It is particularly useful in embedded systems, and often legacy systems as well. There is just one problem with using it in C++ , it will be incompatible with any class with a user defined constructor, for then ((class*)0)->member becomes illegal. Interestingly, the construct ((class*)1->member is not (go figure), so the solution is to redefine offsetof after any include of stddef.h as...

#define offsetof(c,m) ((size_t)((c*)1->m)-1)

If the compiler complains about a redefinition, just undef it first.

C++: Class Constants vs. Defines

In C, one might do this...

struct Sam {

  unsigned char  flags;

  #define SAM_FIN  0x01

   #define SAM_SYN   0x02

   #define SAM_RST   0x04

   ...

};

struct Sam sam;

sam.flags = SAM_FIN && SAM_RST;

The intent of code like this is to imply that flags can take on only those defined values. However, the scope of the #defines is not limited to the structure, so name mangling must be used with it's attendant possibility of a collision. Worse, a client program might redefine one of these, with nary a peep from the compiler, resulting in undefined behavior.

In C++, the intent can be achieved much more gracefully like this...

class Sam {

public:

   unsigned char   flags;

   static const char   FIN = 0x01;

   static const char   SYN = 0x02;

   static const char   RST = 0x04;

   ...

};

Sam sam;

sam.flags = Sam::FIN && Sam::RST;

Because integer type static consts can be initialized in the body of the class, no external definition is required. Since the names are scoped to the class, there is no need for name mangling, and since they are constants, the client program cannot change them. All of the gains, none of the hassle.

Very cool.