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.

Succinct Initialization of Arrays of Objects in C++

Whenever a system is changed, particularly with the intent to add substantial new functionality, previous methods of doing things do not always survive the transition. While often the new system provides better ways of doing things, it cannot be mastered all at once, and during the transition period it is terribly annoying to no longer be able to use a mature technique even though eventually there will no longer be a need to. This is the case with the transition from C to C++.

This post considers a specific example, the challenge of initializing arrays of objects in C++.

In C one could do this...

struct sD2 {
   int x;
   int y;
};

sD2 sd2[][3] = { {0,0}, {0,1}, {0,2} },
                 {1,0}, {1,1}, {1,2} },
               };

It was concise, clear, and easy to expand. Note the unused last comma, so cutting & pasting a new row is flawless.

Initializing arrays of objects is more awkward because a constructor must be called explicitly. The closest I’ve found in C++ is the following...

class withLongName {
public:
   int x;
   int y;
   withLongName () {} // Default ctor so withLongName a[5]; compiles.
   withLongName (int x_, int y_) : x(x_), y(y_) {} // 2-arg ctor.
};

#define withLongName C
withLongName wlnc[][3] = { { C(0,0), C(0,1), C(0,2) },
                           { C(1,0), C(1,1), C(1,2) },
                         };
#undef C

Without the defines, the table easily expands past the window width and adds typographic clutter to the initialization...

withLongName lnc[][3] = { { withLongName(0,0), withLongName(0,1), withLongName(0,2) },
                          { withLongName(1,0), withLongName(1,1), withLongName(1,2) },
                        };

One could use ‘D’ for data, or ‘I’ for initialization, or others, but I think I like ‘C’ for constructor. I don’t care for the extra preprocessor lines, but if one specs a struct to initialize, then respecs it as the body of the class, and loads the object from the struct, one has both duplicated info, separation of variables from their initialization values, and even more extra lines.

Robert Tadlock tested this strategy and found that it avoided the typical inefficiencies of calling both the default constructor and another one, or of creating temporary objects subsequently destroyed in the initialization process.

Quantum Attack on Dinning Philosophers

The Dinning Philosophers is a prototypical problem in multi-tasking software. Five philosophers sit around a table with one utensil (fork, chop stick) between them. To eat, a philosopher must have two utensils. A philosopher is either eating or thinking. This maps to a program which is either using the resources or not.

The problem is one of deadlock. If each philosopher grabs the fork to the left, and the waits for the fork on their right to become available, no resources are utilized, and everyone starves. The challenge is to detect the deadlock and then resolve it in a fair and efficient way.

The epiphany is to ask if abstract quantum systems (AQS) such as Quantum Tic-Tac-Toe can suggest new attacks on this problem. In such quantum systems, the state is an entangled superposition until a cyclic entanglement occurs, which then collapses to classical values. The tie in with self-reference is the point of the epiphany.