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.
No comments:
Post a Comment