Sunday, October 9, 2016

"Replacing" C++ Virtual Function with Template (and More)

There are several ways you can replace C++ virtual function with template. These are some related examples to accomplish the task:
Curiously recurring template pattern

However, I found that the philosophy of using virtual function itself is quite "flawed" when one already use template in his/her C++ code. Why? Because, the Standard Template Library (STL) or Boost, or other C++ template library for that matter has a very different approach to programming than Object Oriented (OO) philosophy. Most if not all of them are meant to provide generic programming in C++ (as opposed to OO)--Generic as in ADA ( and in general I might be stating a hard line here, but nonetheless, that was what STL was written for. See for yourself what Alexander Stepanov (the most prominent STL author) wrote:

What I stated in the previous paragraph meant that, in order to use template in a substantial C++ code base, we need a paradigm shift. Instead of looking at the solution as related objects, I think we need to look at the solution as "interfaces to generic algorithms". I think that you should gain more understanding of what I meant once you've read Stepanov remark in his notes. This is an important excerpt from his notes:
It is essential to know what can be done effectively before you can start your design. Every programmer has been taught about the importance of top-down design. While it is possible that the original software engineering considerations behind it were sound, it came to signify something quite nonsensical: the idea that one can design abstract interfaces without a deep understanding of how the implementations are supposed to work. It is impossible to design an interface to a data structure without knowing both the details of its implementation and details of its use. The first task of good programmers is to know many specific algorithms and data structures. Only then they can attempt to design a coherent system. Start with useful pieces of code. After all, abstractions are just a tool for organizing concrete code.
If I were using top-down design to design an airplane, I would quickly decompose it into three significant parts: the lifting device, the landing device and the horizontal motion device. Then I would assign three different teams to work on these devices. I doubt that the device would ever fly. Fortunately, neither Orville nor Wilbur Wright attended college and, therefore, never took a course on software engineering. The point I am trying to make is that in order to be a good software designer you need to have a large set of different techniques at your fingertips. You need to know many different low-level things and understand how they interact.
The most important software system ever developed was UNIX. It used the universal abstraction of a sequence of bytes as the way to dramatically reduce the systems’ complexity. But it did not start with an abstraction. It started in 1969 with Ken Thompson sketching a data structure that allowed relatively fast random access and the incremental growth of files. It was the ability to have growing files implemented in terms of fixed size blocks on disk that lead to the abolition of record types, access methods, and other complex artifacts that made previous operating systems so inflexible. (It is worth noting that the first UNIX file system was not even byte addressable – it dealt with words – but it was the right data structure and eventually it evolved.) Thompson and his collaborators started their system work on Multics – a grand all-encompassing system that was designed in a proper top-down fashion. Multics introduced many interesting abstractions, but it was a still-born system nevertheless. Unlike UNIX, it did not start with a data structure!
One of the reasons we need to know about implementations is that we need to specify the complexity requirements of operations in the abstract interface. It is not enough to say that a stack provides you with push and pop. The stack needs to guarantee that the operations are taking a reasonable amount of time – it will be important for us to figure out what “reasonable” means. (It is quite clear, however, that a stack for which the cost of push grows linearly with the size of the stack is not really a stack – and I have seen at least one commercial implementation of a stack class that had such a behavior – it reallocated the entire stack at every push.) One cannot be a professional programmer without being aware of the costs of different operations. While it is not necessary, indeed, to always worry about every cycle, one needs to know when to worry and when not to worry. In a sense, it is this constant interplay of considerations of abstractness and efficiency that makes programming such a fascinating activity. 
I need to emphasize the last paragraph of Stepanov note because I have just encountered a not so "miserable" failure very closely related to what Stepanov said in that paragraph. I need to cleanup some left-over code which supposed to provide abstraction for some sort of file system operation in two very different OSes. Unfortunately, the previous code failed "quite" miserably to provide good abstraction on the task, precisely because it wasn't designed from the ground-up on both OSes as Stepanov suggested. It was only designed from the ground-up to work well in one of them. Therefore, the design lean more to one of them. Fortunately, not all hope is lost because I think the task could still be salvaged through several iteration to fix the abstraction. I said "quite" miserably because the state of the matter could still be salvaged/fixed somehow. It's not a total disaster.

Let's put the theory aside and take a look at one of the alternative to replace C++ virtual function with its C++ template analog. The code below illustrate one of the approach you can use to replace virtual function with template-based solution.
#include <iostream>

using namespace std;

template <class T> class Compute
    T multiply(T x, T y);
    T add(T x, T y);

template <class T> T Compute<T>::multiply(T x,T y)
    cout << "Inside function: " << __func__ << "()" << endl;

    return x*y;

template <> double Compute<double>::multiply(double x,double y)
    cout << "Inside function: " << __func__ << "() -- double version" << endl;

    return x*y;

template <class T> T Compute<T>::add(T x, T y)
    cout << "Inside function: " << __func__ << "()" << endl;

    return x+y;

int main()
    Compute <int> test;
    Compute <double> testFp;

    cout << "12 x 3 = " << test.multiply(12, 3) << endl;
    cout << "1.25 x 3 = " << testFp.multiply(1.25, 3) << endl;

The output of the code above is as follows:
Inside function: multiply()
12 x 3 = 36
Inside function: multiply() -- double version
1.25 x 3 = 3.75

The code above demonstrate the use of "function overloading" with C++ template, as explained by Herb Sutter over at The "specialized"/"overloaded" version of the multiply() method is called to handle double data type. This "overloaded" implementation is slightly different compared to other generic types handled by the template, it shows a different string in the output of the program.
Anyway, you could replace double with your own custom data type as long as the data type implements the required operator, i.e. + and * in the example above. You could use and extend the technique shown in the example above to handle many cases that previously requires virtual function in C++. The basic philosophy is: instead of inheriting from parent class(es) and implementing virtual function(s), use a class "instance" that behaves as required based on the template instantiation parameter(s)--or simply said: template parameter(s).

On another note, it's rather disappointing that present C++ standard doesn't yet impose adequate template instantiation error checking. One of the most promising avenue to address this issue is the so-called C++ concepts that could be helpful, but not yet ratified in C++ standard.

Last but not least, I hope this post is a good food for thought for C++ programmers out there.

Post a Comment

No comments: