Generic Programming: A personal motivation

published at 25.09.2013 20:37 by Guntram Berti
Save to Instapaper Pocket

Moments of enlightenment are rare. When musing about my talk on this year's Meeting C++ conference, I vividly remembered having one of those moments in early 1996 when I came across the HP technical report written by Alexander Stepanov and Meng Lee describing the design of the STL. At the time, I worked on my PhD in scientific computing, and I was deeply annoyed by the fact that each implementation I created was doomed to work only in the very context it was created for, namely on top of the application specific data structures — a tiny fraction of its theoretic potential. When reading that report, the bulb went on and I immediately realized that this was the way to go.

In the years that followed, I worked on transferring the ideas of the STL to scientific computing, in particular to geometric algorithms and meshes. It was painstaking. Only when egcs 1.0 was released in December 1997, serious work with templates got possible with gcc. Compiling could take hours (or, literally, eternally). Memory would overflow. ICEs. Tons of compiler error messages, no: error novels. I remember one of them overflowing my disk during a nightly build. We still enjoy all this today occasionally, but on a different level. Despite these practical difficulties, which at times bordered downright user-hostility, I never doubted on having chosen the right path. It helped that as a PhD student, I could afford to spend a lot of time at the bleeding edge until it worked.

What is it that makes me so confident about the virtues of the generic approach? As a mathematician, the fundamental loss of generality that typically occurs when translating mathematical concepts into a program has always struck me as almost sinful. It's like having to creep on the dusty ground, when you feel you should fly freely in the sky. What attracts me to generic programming (GP) is its promise to preserve the generality of the mathematical algorithm in the implementation: It is a radical shift from an implementation style that “sticks to the ground” by making arbitrary assumptions about irrelevant details to an approach “flying high” by trying hard to remove all unnecessary assumptions. With GP, I was indeed able to actually create implementations that were as universal as the algorithms themselves. ... Digressing to thinking about what an algorithm actually is — but this is another intriguing topic.

I believe that generality of implementation is far from being merely an aspect of beauty or elegance. Many algorithms are used (and implemented ... and tested ... and debugged ... and optimized) over and over again.
What a waste. Having a single, well-tested (or even provably correct) implementation is a boost in productivity and code quality.

But how can we achieve such an implementation fitting all circumstances? How does one start developing generic code in C++ (or another language)? For me, the answer lies less in the technical mastering of language features like templates with their (perceived) dark corners, but rather in thinking about the problem with a kind of impartial, widened mindset freed from the concrete context. We can ask ourselves: “What is the essence of what this implementation is doing?”, and then start to strip away all irrelevant, context-specific details.

This approach leads to making an implementation generic in a bottom-up, incremental fashion. Let's say you have an algorithm, like “computing the area A of a triangle given by 3 points a,b,c”, which is given by the mathematical formula

A(a,b,c) = 0.5 det(b-a, c-a)

Now, “computing the area of a triangle” is already a pretty general description of the problem. But a typical implementation is not nearly as general:

struct point2d {
  double x,y;
 ...
};
...
double triangle_area(point const& a, point const& b, point const& c)
{
  point ba, ca;
  ba.x = b.x -a.x;
  ...
  return 0.5*(ba.x*ca.y-ba.y*ca.x);
}

In the bottom-up approach, we now want to gradually lift this implementation to make it more generic. So let's pause and try to imagine where and how we or somebody else would like to use this algorithm. Maybe we want to change the underlying data type to float? Or our colleague uses her own point type:

typedef float point[2];

What kind of point types can we support? What is a point, after all: What is the mathematical concept behind it, and how does it translate into requirements on types? For instance, do we need to require subtraction on points types?

When we start to step by step generalize our implementation, by allowing more and more types for points, we'll soon realize that we need some way of mapping types to other types (e.g. the point type to the result type of the area function) and accessor functions (e.g. for accessing the coordinates). To implement them, we'll have to know and choose the appropriate language constructs and idioms, like template specializations, function overload control or traits, but this is now a fairly “standard” toolbox.

However, we can then go deeper into the matter: Is computing the area of a quadrangle still the “same” algorithm? Or even general polygons? What about the 3D case? nD, anyone? Where do we draw the line? Surely we can reuse some of the work for the more general cases, but what's a systematic way to do this?

These are the important questions that arise when we want to program generically. And they are quite independent of the implementation language. Only when we have answered these questions, it is time to get worried about templates (if we choose C++).

In this short blog article, I cannot unfold the example in detail (maybe in a follow-up post, or you browse through the Boost geometry intro for s similar discussion). However, if you are interested in how to make your implementations more generic, you can learn more about it in my detailed tutorial on generic programming where I get down to the technical details like template specialization and overload resolution, using a different example (sum and reduction). During Meeting C++ 2013, you'll have a chance to attend my talk Generic Programming for the rest of us, where I'll give an introduction to the process, and hopefully also have time to look into the promises that generic programming holds for writing parallel code.

Join the Meeting C++ patreon community!
This and other posts on Meeting C++ are enabled by my supporters on patreon!