Generic Programming - What are you, anyway?

Generic Programming - What are you, anyway?

刘未鹏(pongba)

C++的罗浮宫(http://blog.csdn.net/pongba)

One Ring, to rule them all.

- The Lord of the Rings

The Word Around Town

Google "generic programming" and you will find a bunch of definitions of it, among which the more notable ones are:

[From http://www.generic-programming.org/, arguably the most authoritative information source of GP:]

Generic Programming is a programming paradigm for developing efficient, reusable software libraries. Pioneered by Alexander Stepanov and David Musser, Generic Programming obtained its first major success when the Standard Template Library became part of the ANSI/ISO C++ standard. Since then, the Generic Programming paradigm has been used to develop many generic libraries.

The Generic Programming process focuses on finding commonality among similar implementations of the same algorithm, then providing suitable abstractions so that a single, generic algorithm can cover many concrete implementations. This process, called lifting, is repeated until the generic algorithm has reached a suitable level of abstraction, where it provides maximal reusability while still yielding efficient, concrete implementations. The abstractions themselves are expressed as requirements on the parameters to the generic algorithm.

From this definition we can derive some interesting conclusions.

First, Generic Programming is sort of invented by Alexander Stepanov and David Musser, who, and several others including Bjarne Stroustrup and Andrew Knoenig, introduced the whole C++ Templates system and essentially “the” STL into C++. This means that Generic Programming is tightly bounded to C++ Templates and the paradigms illustrated by STL.

Second, the gist of generic programming is finding commonality, and abstracting (or, lifting), such that one implementation can fit them all. This one should be of no surprise, because abstracting is one of the most common activities when we’re programming, be it OOP or GP. The more important question is, however, does generic programming provide an essentially new abstraction mechanism? We’ll get to that later.

Third, the major advantages of generic programming are considered to be reusability and (at the same time) efficiency. This is also confirmed when we redirect to boost, the most significant and modern C++ library in the world:

Generic programming is about generalizing software components so that they can be easily reused in a wide variety of situations. In C++, class and function templates are particularly effective mechanisms for generic programming because they make the generalization possible without sacrificing efficiency.

A more important thing to notice is that of the two characteristics of C++ generic programming (not the general notion of GP), efficiency is more important than reusability. It’s not that reusability isn’t important. It’s just that the popularity of C++ generic programming comes mainly from the fact that it implements generic programming so efficiently that the abstraction penalty is reduced to nearly zero.

However, the abovementioned words don’t define exactly what generic programming is. They are all sort of limited to the generic programming notion a <personname w:st="on" productid="la C">la C</personname>++. So here’s another quote, from ACM SIGPLAN – Workshop on Generic Programming:

Generic programming is about making programs more adaptable by making them more general. Generic programs often embody non-traditional kinds of polymorphism; ordinary programs are obtained from them by suitably instantiating their parameters. In contrast with normal programs, the parameters of a generic program are often quite rich in structure; for example they may be other programs, types or type constructors, class hierarchies, or even programming paradigms.

This might be the most “generic” definition of generic programming. Just as what the word “generic” has implied, generic programming is about making programs more general such that they could become more adaptable (to a wide range of use context).

Now it’s clear that C++ templates is one of the mechanism to approach generic programming, because STL, powered by C++ templates, is clearly adaptable to a very wide range of use context. We can, for instance, make a container of our own and plug it into the STL algorithm framework without a flicker.

Another important thing this definition shows is that generic programming makes use of a new kind of polymorphism compared to traditional OO techniques. Moreover, we often call this new kind of polymorphism “parameterized polymorphism”.

So…

So what is generic programming? So far it seems pretty clear that the point of GP is to make programs more “generic”. But wait, isn’t it the same thing OO used to do (and is doing now)? Consider the code below:

template<typename InputIter, typename UnaryFun>

UnaryFun for_each(InputIter first, InputIter last, UnaryFun func)

{

for(;first != last; ++first) func(*first);

return func;

}

This is the way C++ approaches GP. Now let us take a look at how we can use OO (in Java) to archive the same thing:

interface IUnaryFun

{

void invoke(Object o);

}

interface IInputIter

{

IInputIter preIncrement();

boolean equals(IInputIter otherIter);

… // other methods

}

IUnaryFun for_each(IInputIter first, IInputIter last, IUnaryFun func)

{

for(;!first.equals(last); first.preIncrement())

func.invoke(*first);

return func;

}

This actually works. Putting aside the awkwardness of using named function call instead of operator overloading, the problem of the Java version is threefold:

1) Efficiency. The C++ version is very efficient because it trades code size for efficiency, that is, for each combination of InputIter and UnaryFun, it will generate a separate instantiation. On the other hand, in light of the Golden Law of Software Engineering, the Java version works by adding a middle-layer (i.e. the interfaces). This is where it introduces the so-called abstraction penalty. The code is probably slow in some cases because it contains another layer of method-invoking. (However, we should note that, as a result, what we get is binary reusability. If we’re going to put the code into a binary library, this is probably the only way.)

Nominal Subtyping vs. Structural Subtyping

The Java version uses what is called “nominal subtyping”(or “named conformance”). Basically it means that to say that a type conforms with a concept (represented by interfaces (Java/C#), type classes(Haskell) or concepts(C++09) ) we must explicitly stipulate it (e.g. by deriving the type from the interface)

On the other hand, “structural subtyping”(or “structural conformance”) is what we do in C++ templates. That is, a type is compatible with a concept if it has every feature the concept has (usually this means that the type should implement every method the concept stipulates).

2) Coupling/Anti-OCP. This one is somewhat interesting. Say we have a home-made container class:

class MyContainer

{

…

}

class MyContainerIterator

{

…

}

for the Java version, if we want to plug this container into the algorithm (for_each) framework, we have to derive MyContainerIterator from IInputIterator, which requires us to change the code. So what’s the big deal? So we just change the code, and everything is OK again.

But image you didn’t write MyContainer and MyContainerIterator, instead, they’re from another library, and you want to hook the container and the algorithm together (i.e. an adaptation). What can you do? You can’t change the code because it’s somebody else’s code. The only thing you can do is writing a new iterator class that adapts MyContainerIterator (i.e. the adapter pattern), but that’s obviously not the ideal way.

Another thing you should notice is that even if MyContainerIterator has exactly the same methods as IInputIter (i.e. full structural conformance), we still need to use the awkward adapter pattern:

class AdaptedMyContainerIterator implements IInputIterator

{

…

public IInputIter preIncrement(){

iter.preIncrement();

return this;

}

public boolean equals(IInputIter otherIter){

return

iter.equals(((AdaptedMyContainerIterator)otherIter).iter);

}

…

private MyContainerIterator iter;

}

Notice how the forwarding is done on a per-method basis, this is pretty cumbersome and fragile (let alone the fact that it invites much more typing).

Ideally, we should be able to simply say that MyContainerIterator is compatible with IInputIterator and leave the compiler to check if they really are compatible, which is already the case in Haskell, and will be in C++09.

Note that this problem can be alleviated by the so-called “Duck Typing”, which is a fundamental part of Ruby’s type system, and, however, isn’t without its own problem.

To quote David Vandevoorde & Nicolai M. Josuttis in “C++ Templates”:

“Polymorphism implemented via inheritance is bounded [in that] the interfaces of the types participating in the polymorphic behavior are predetermined by the design of the common base class (other terms for this concept are invasive or intrusive)”

“Polymorphism implemented via templates is unbounded [in that] the interfaces of the types participating in the polymorphic behavior are not predetermined (other terms for this concept are noninvasive or nonintrusive)”

3) Type-safety. This is an intensively-debated-upon aspect of programming language. And yet the problem of how important type-safety is is still wandering in the darkness. Every language has its own trade-off/balance between type-safety and dynamic-expressiveness. I know that this dichotomy between static-typing and dynamic-typing is far too inaccurate, but this problem is far beyond the scope of this post so I’ll just redirect you to this paper written by Erik Meijer & Peter Drayton for a starter. The reality is that type-safety is the principal motivation of adding generics into Java/C#.

The “Working” Definition

The definition below is from David Musser, one of the inventors of STL:

My working definition of generic programming is "programming with concepts," where a concept is defined as a family of abstractions that are all related by a common set of requirements. A large part of the activity of generic programming, particularly in the design of generic software components, consists of concept development -- identifying sets of requirements that are general enough to be met by a large family of abstractions but still restrictive enough that programs can be written that work efficiently with all members of the family.

This one isn’t really a definition of GP, but rather a description of what we do when we’re writing generic code. It seems that generic programming revolves around concept development, just as object-oriented programming revolves around type development.

An essentially new abstraction mechanism?

So let’s get back to the problem we dropped at the beginning of this post. The problem was: is GP an essentially new abstraction mechanism? Well, it depends on the way you look at it. If you look at it as a naturally perfect way to abstract procedural code (algorithms), as opposed to the fact that OO is the natural way to abstract entitative code (data structures), then yes, it is a new abstraction mechanism. However, if you look at it as a supplemental way of archiving efficiency, loose-coupling, and type-safety, which OO doesn’t get, in reusable algorithm development, then it is no new thing.

As a result, perhaps the right way to look at GP is not to focus on whether it’s something new, but whether it offers something different.

Further <city w:st="on"><place w:st="on">Reading</place></city>

[1] What is Generic Programming

[2] An Extended Comparative Study of Language Supports for Generic Programming