Generic Programming
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:
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.)
<div style="padding-right: 4pt; padding-left: 4pt; padding-bottom: 1pt; margin-left: 42pt; margin-right: 0cm; padding-top: 1pt;">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).
页:
[1]