Nicolás Brailovsky

C++0X brings some very cool changes, and I wanted to start a series of posts regarding some of these changes, with a small explanation of each new feature (that I currently understand, at least), an example of its usage and why I think it’s a cool thing. Notice these two may be mutually exclusive, some of these may just be cool but I wouldn’t recommend using them on a day to day basis. An example of a very cool feature which I wouldn’t normally use in a project is the one I want to write about today: variadic templates.

What’s not to love about variadic templates? Its name implies (correctly) that it uses templates, and it also has a “variadic” thingy, which you can use to look smart since no one really knows what it means.

Templates themselves can quickly get complicated if used by unexperienced padawans in the art of martial C++, yet their hypnotic beauty draws every programmer to use them just like flies are drawn to fire. When used correctly they can produce very elegant code; if not for the template programmer, at least for the end user. Yet in all their power, templates in C++ have been lacking a fundamental aspect: a variable number of arguments.

There are ways to work around this limitation, like using a list of types paired with a template-paramlist-object. Sounds familiar? (I know it doesn’t, don’t worry). You could also generate N constructors, one overload for each parameter count. The drawback, exponential compile time (say, TR1). These are all hacks, which are in place only because there wasn’t a safe way of passing a list of types associated with a list of arguments. This is over now with variadic templates in C++0X.

So, what kind of problem would variadic templates solve? Let’s name a few:
* A typesafe varargs function (a function with a variable number of arguments)
* Easily create a template object which acts as a tuple
* An easier implementation of a  reduce (inject) function

This entry is getting quite long so we’ll start seeing these examples on the next post.

So, virtual dispatching is just too much overhead for you? I bet you do need every femtosecond from your CPU. Even if you don’t, who doesn’t like weird C++ constructs? Take CRTP, for example, a Curiously recurring template pattern:

Using this weird looking (ain’t them all?) template device you can have static dispatching with most of the flexibility of dynamic dispatching. As a bonus, you’ll drive all your cow-orkers insane!

Bonus non useful information: In C++ 0X you could use variadic templates and have a proxy object with static dispatching. How cool is that?

This is the end. My only reader, the end. After 15 chapters of template metaprogramming you should have learned why staying away from them is a good idea, but if you have been following this series then you should know now when and why they could be useful.

These posts were a compendium of mostly isolated data I found during my travels through the depths of metaprogramming tricks, there are books and people much more capable than me if you want to learn more about this subject (Modern C++ Design by Andrei Alexandrescu comes to mind).

The whole idea of having a cache and a virtual template method was nice, but after seeing the result I decided it was best to have a factory method and an IDL. It may not be so l33t, but whoever has to maintain the code after me will be grateful.

This is the last post on this topic because I feel I have written most, if not everything, I can transmit through this medium but also for an important reason, most likely I won’t be working with C++ code so much from now on [1] so there won’t be as many chances for me to see the dark, insane, side of this beautiful (in its own way) programming language in a programming language. I know most of you must have barely skimmed through these articles, but I still hope you enjoyed them.

[1] That’s right, I’m leaving C++ for the dark side of development, I’ll be working with Java from now on. Keep in mind this article may have been written a long time before it’s published.

[2] Wow, it was a long time since I used the meta-post category

If you remember previous entry, we got our evil device to the point of getting a specific instance using only a type hint. Now we need to put all the code together. I won’t add much to the code, you should be able to parse it yourself.

The only thing missing now is a map, to convert a primitive type to an index type, but that’s trivial and so it will be left as an exercise for the reader (?). We just implemented the most evil code in the whole world. Next time, the conclusions.

Last time we had a virtual template dispatch problem… we got to the point of knowing which was the index of the cache we were searching for, now we need to actually retrieve an instance of that cache. That’s a problem. Why? To begin with, there are no instances, only types!

The next logical step would be to create a Map device, to map a list of types to a list of instances… let’s see how can we do that, in pseudocode

Looks easy. How can we map that to c++?

All those next.next.next.instance look ugly. Let’s use some more meta-magic to get the Nth instance (why not a [] operator? several reasons, you can’t mix non-const ints with templates nicely, there would be problems to define the return type… all those options are workable but it’s easier if we do this in another device.

Remember that one from the toolbox? Now we know how to get a specific index position, yet getting the instance is a different problem (the Nth device returns a type, not an instance). We should do something different, the problem is knowing the return type. What’s the return type for the Nth instance of the Instances list?

Not so easy, right? This is the translated C++:

And the code from fetching the instance itself is even more difficult, so I’ll leave that for next time.

Remember our virtual template method problem, from the other time? (I know, I said the answer was scheduled for a week after that post, but then I just forgot about it). May be we could avoid the virtual part by keeping a list of all our caches… how would we know which one should we dispatch the message to? Easy, using templates.

Instead of a list let’s keep two, for twice the fun. One for the rows cache, another for the PKs. We can use PK to know which ROW Cache should we choose. Let’s try to write a pseudo code for it:

Doesn’t look too hard. Building on our previous toolbox, let’s use Eq, Position and the definition of a list:

Great, now we can find an element on a list of types. The real virtual dispatch for the next entry

Wow, number eleven already. We’re getting more chapters here than Final Fantasy games. I didn’t even imagine there was so much to write about such an esoteric language features like templates. I do wonder if anyone will actually read it, but that’s a completly different problem.

Enough meta-meta talk: what can we do with all the things we have learned? We can calculate pi and e, we already showed that as an example on one of the first chapters. This chapter I’m going to write about what motivated me to explore the bizarre underworld of template metaprogramming. Some time ago I had to work with a Berkeley DB researching the feasibility of developing a magic cache for (real) DB table. Leaving aside the discussion of whether this is a good idea (the project did have a good reason to be researched) I hit a major roadblock when trying to provide a façde for every table; something like this: See the problem? To do something like that we’d need a virtual template method, and you can’t have that. After seeing that I thought to myself “Hey, I’ll use templates!”. Then I had two problems, but the damage was done, I couldn’t go back. What kind of contorted device could we implement to make such a devious requirement work? I’ll leave you to think it, the answers I came up with next week.

So far we’ve learned the basic constructs of template metaprogramming (loops, branching, return values) and some basic list operations (getting the length of a list, appending and preppending elements, checking if an element is included in a list). Let’s put it all together by creating an operation to return the position of an element. It’ll be very useful later on too.

If we go back to the Includes operation we can get some help to define the Position operation: the position of an element in a list is one plus the position of the element we’re searching for in the tail, or zero if the head equals said element. The operation is not defined if the element is not in the list.

Translating to pseudo-code:

The translation to C++ is not so trivial this time. Try it, I’ll wait… ready? OK, let’s start

Looks easy… but doesn’t work. First problem, we can’t compare two types, remember? We need to use Eq<X, Y> again. Second problem, although we said the operation is undefined if the element is not included on the list, it would be nice if we could force the compiler to fail if (or when) that happens. Let’s rewrite the operation using a façade again, but adding an Assert:

Oh, we haven’t defined assert yet! There’s another problem, too: even if it won’t compile, the compiler will try to expand _Position< …, NIL > indefinately, causing an error after too many nested template calls. Not nice. We need to add a case to make the compiler stop:

All that code for such a simple operation, man. Also, see what we did with Assert<>? It seems making a compile fail is actually quite easy. That’s what I have most experience with.

We’ve been through quite a lot, and our toolboox should be quite big already. Next time we’ll start steering towards some sort of aplicability, trying to use some of all these stuff to implement a real, useful and working program… assuming that’s even posible.

By now we should have learned how to perform loops, branching and returns using templates. Let’s add a couple of useful operations to our library: append and prepend.

Prepending an element to a list is very easy: the result is a list (oh surprise) consisting of a head (the element we want to add) and a tail (the old list). In the pseudocode I’ve been using so far:

And in C++ (trivial, this time):

Appending is a little bit more difficult, as we need to first find the end of the list. Think for a second how would you define it… back? Ok, I’d define it this way: appending an element to the list yields a list, consisting of the same head and the result of appending said element to the tail. The null case, as usual, is appending an element to a NIL list; in this case the result is a list with the element itself. So:

Looks complicated what it follows the same structure as the rest of the basic-ops:

Easy. Now, what happens if we want to add a default value for Lst, so we can use Append to create lists? Easy too, but we need a façade this time; just rename Append to _Append, then

I promised to add one more operation to our toolbox, returning the position of an element, but this post is getting quite long and I’m afraid it may be too much for the average attention span of a programmer… we’ll leave it for next time.

Remember last time? We learned how to get the lenght of a list. This time I’ll introduce some more of these basic ops. Let’s begin with “Nth”: getting the Nth element of a list; which, remember, in this case is a type, not a concrete element. This means the Nth element will be something like int, char, const char*, not 1, 2 or 3. We introduced a trick to get around this limitation before using a template <int>, go there to refresh your memory if needed.

So, what would the coloquial definition of “Nth” be? I’d put it like “The operation Nth for a list equals the head of the list for N = 0 and Nth (minus one) of tha tail otherwise”. A little bit more formally:

Translating this to C++ should be a breeze to you now. Try it, I’ll wait. Read? OK, this is MY answer:

Though the structure is very similar to the previous “basic operation”, getting the length of a list, the concept is quite different. This time we’re defining a return type recursivly. Anyway, it was too easy indeed, let’s try a more complex operation now.

How can we check if an element exists on a list? Seems easy enough, an element is included in a list if the head equals the element itself or if the element is included in the tail. In the pseudo language I just invented:

Looks easy, right? Well, there’s a bug there, can you spot it? Yeah, we’re missing the false condition. We should add a third spetialization:

Again, let’s translate the pseudocode to C++. Try it, I’ll wait. Read? OK, this is MY answer:

Looks nice, doesn’t it? Too bad it won’t work, you can’t compare two types. What would (int == char) mean in C++? We need a helper there, some kind of trick to compare to types. We can use partial template spetialization again:

With this little struct now we can write our include operation this way:

Very esoteric looking, the right mix of Haskel, C++ and booze to ensure job security for life. Next time we’ll find a way to search for the position of an element, a somewhat more complicated task.