Generic Software Design
I'm taking a course this semester called Generic Software Design. One fascinating piece of reading for the course is Notes on Programming (PDF) by Alex Stepanov, father of the STL. It's great reading that seems deceptively simple, just designing a class that represents a vector of integers. But even this simple design exercise exposes some very interesting concepts.
This course got me thinking about function overloading. That is, in C, if you wanted to do foo to an int and to a double, you'd have to write two functions, void foo(int) and void food(double), for example, whereas in C++ you can define void foo(double) and the compiler will pick the best function. This seems like a trivial thing, but it is a very deep idea. Whereas in traditional object-oriented programming you can inherit a class and specialize it, overloading allows you to generalize concepts (without going through the trouble of creating a superclass and making various things inherit it). This is particularly nice because it generalizing is more powerful than specializing, just ask any mathematician.
In math, you learn about absolute value back in pre-calculus, if not before. You use the notation |x|. Then you get to vectors and the teacher says, “We'll define |v| to be the length of the vector v.” This seems like a trivial extension at the time, but suppose you do the same thing in code. If you have a class for geometric vectors (not to be confused with std::vector) and you add the function double abs(const Vector& v);, you have extended your Vector class to be “a thing with a magnitude”. If you had code that worked before on things with magnitude, that code will now work with Vectors. As a trivial example,
template
double sum_of_lengths(const T& a, const T& b) {
return abs(a) + abs(b);
}
Overloading abs(·) is nice for reasons of clarity; let's consider a use that's nice performance-wise: swap(·,·). The STL provides std::swap(T&, T&) to swap the values of two variables. With GCC, its default implementation can be found in /usr/include/c++/*/bits/stl_algobase.h and just uses a temporary. Many of the STL algorithms make use of this - std::reverse(·,·), for example. As you probably know, the STL provides a swap function for all of its data structures, meaning that you can reverse(·,·) an array of N std::lists in just O(N) time and with essentially no additional memory usage.
While the default implementation makes almost any class “swappable” the STL invites you to implement your own specialized swap(·,·) function to improve performance. That is, you have the option to make your class satisfy the concept of “fast swappable”.
For a final example of overloading in action, I've been working on code for research which uses meshes and atoms. The code had been full of things like:
double atom_pos[3];
getPos(atom_ref, pos);
double vertex_pos[3];
V_coord(vert, vertex_pos);
It's not pretty. But conceptually, it's simple, it's just ugly code because the interfaces are different for these different types. So generalize: define the concept “is at a point in space” to be something for which we can call position(·). So I implemented position(·) for these two types without making changes to the classes themselves and the above becomes
Vector atom_pos = position(atom_ref);
Vector vertex_pos = position(vert);
By using function overloading in this way, code becomes simpler, complexity is reduced, and overarching concepts are reflected clearly in the code.
I have more to say, but I'll save it for later.
This course got me thinking about function overloading. That is, in C, if you wanted to do foo to an int and to a double, you'd have to write two functions, void foo(int) and void food(double), for example, whereas in C++ you can define void foo(double) and the compiler will pick the best function. This seems like a trivial thing, but it is a very deep idea. Whereas in traditional object-oriented programming you can inherit a class and specialize it, overloading allows you to generalize concepts (without going through the trouble of creating a superclass and making various things inherit it). This is particularly nice because it generalizing is more powerful than specializing, just ask any mathematician.
In math, you learn about absolute value back in pre-calculus, if not before. You use the notation |x|. Then you get to vectors and the teacher says, “We'll define |v| to be the length of the vector v.” This seems like a trivial extension at the time, but suppose you do the same thing in code. If you have a class for geometric vectors (not to be confused with std::vector) and you add the function double abs(const Vector& v);, you have extended your Vector class to be “a thing with a magnitude”. If you had code that worked before on things with magnitude, that code will now work with Vectors. As a trivial example,
template
double sum_of_lengths(const T& a, const T& b) {
return abs(a) + abs(b);
}
Overloading abs(·) is nice for reasons of clarity; let's consider a use that's nice performance-wise: swap(·,·). The STL provides std::swap(T&, T&) to swap the values of two variables. With GCC, its default implementation can be found in /usr/include/c++/*/bits/stl_algobase.h and just uses a temporary. Many of the STL algorithms make use of this - std::reverse(·,·), for example. As you probably know, the STL provides a swap function for all of its data structures, meaning that you can reverse(·,·) an array of N std::lists in just O(N) time and with essentially no additional memory usage.
While the default implementation makes almost any class “swappable” the STL invites you to implement your own specialized swap(·,·) function to improve performance. That is, you have the option to make your class satisfy the concept of “fast swappable”.
For a final example of overloading in action, I've been working on code for research which uses meshes and atoms. The code had been full of things like:
double atom_pos[3];
getPos(atom_ref, pos);
double vertex_pos[3];
V_coord(vert, vertex_pos);
It's not pretty. But conceptually, it's simple, it's just ugly code because the interfaces are different for these different types. So generalize: define the concept “is at a point in space” to be something for which we can call position(·). So I implemented position(·) for these two types without making changes to the classes themselves and the above becomes
Vector atom_pos = position(atom_ref);
Vector vertex_pos = position(vert);
By using function overloading in this way, code becomes simpler, complexity is reduced, and overarching concepts are reflected clearly in the code.
I have more to say, but I'll save it for later.