Tim’s Weblog

Archives

Fun with Variadic Templates: Part II

February 22, 2009 – 9:33 am

As promised in Part I, I think it’s about time we start to actually have some fun with C++0x’s variadiac templates. There’s lots of basic tutorials out there and people talking about variadics here and there, but I haven’t seen anyone really delve into yet, so here we go. First up, the most trivial but of metaprogramming we can do — emulating the C++0x sizeof... operator (which yields the number of parameters in a parameter pack):

1
2
3
4
5
6
7
8
9
10

template <typename... Args> struct count;
 
template <typename T, typename... Args> struct count<T, Args...> {
        static const int num = count<Args...>::num + 1;
};
 
template <> struct count<> { static const int num = 0; };
 
// let's use the struct
const int numArgs = count<1, 2, 3, 4, 5, 6, 7, 8, 9, 10>; // numArgs will be equal to 10 because there are 10 parameters given to the count struct

Line 1, is pretty much the root of all template metaprogramming trickery. The fundamentals of it all relies on recursive partial specialization, and line 1 just sets up a forward declaration to the count struct, which never actually gets used. There’s some complicated rules to how partial specializations are chosen by a C++ compiler, but the basic rule of thumb is that the most specialized version of the template that applies is what’s chosen. So although our instantiation at line 10 could match our blank forward declaration, it doesn’t. The meat of our tiny template metaprogram gets called instead: the recursive partial specialization at line 3.

And this partial specialization brings us to the key behind using variadic templates in the real-world. Since it’s not possible to do random access on the pack elements, the only choice is to “unroll” the packs recursively. The trick is to define the partial specialization such that the first argument is just a single parameter, and the next is a parameter pack:

template <typename FirstArg, typename... RemainingArgs> struct count<T, Args...>;

When the above struct is instantiated with a parameter pack, the first element gets pulled out of the pack into FirstArg, and the remaining parameters are placed in RemainingArgs. So, if the count struct makes an instantiation of itself with RemainingArgs... as the only instantiation parameter, again the first parameter will get pulled out and become FirstArg, and the rest will get placed in RemainingArgs. Thus, we can now easily unroll any parameter pack!

Let’s go back to the first code listing at line 4. This is where the recursion happens, and we can see exactly what we were talking about above happening. The count struct calls itself with the remaining arguments, and simply keeps track of the number of times the recursion happens by incrementing a counter along the way. When the instantiation finishes count::num will be set to the number of parameters in the parameter pack as of the initial instantiation plus 1. We add one because technically the recursion only counts the number of items in the parameter pack which, due to our partial specialization, is going to be one less than the number of parameters we pass to count (remember the first element gets picked out of the parameter pack).

The next thing we need to do, like in all forms of recursion, is to define the termination condition of the recursion. There are a number of ways to do this, but in this first example, we employ the “empty partial specialization” trick:

template <> struct count<> { static const int num = 0; };

This terminates the recursion not because num is implicitly set to zero, but because this specialization does not call itself. Therefore when the recursion has completely unrolled the parameter pack we hit this empty specialization and since there is no recursive call, nothing else happens. We only bother to define num here so that if someone explicitly instantiates a count struct with no arguments, they can still call count::num and get a value of zero rather than a compilation error.

Alright, so that was fun, now let’s look at something a little more complex, and a lot more useful:

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18

template <int N, typename... Args> struct elementType;
 
template <int N, typename T, typename... Args>
struct elementType<N, T, Args...> {
        static_assert(N < sizeof...(Args) + 1, "overflow!");
        typedef typename elementType<N - 1, Args...>::type type;
};
 
template <typename T, typename... Args>
struct elementType<0, T, Args...> {
        typedef T type;
};
 
// now let's use our elementType struct
elementType<0, int, char, std::string, double>::type var0 = 1; // var0 is an int
elementType<1, int, char, std::string, double>::type var1 = '2'; // var1 is a char
elementType<2, int, char, std::string, double>::type var2 = ";P"; // var2 is a string
elementType<3, int, char, std::string, double>::type var3 = 3.14159; // var3 is a double

The basic idea behind the elementType struct is that we give the struct an index and a variable number of types, and we can then use the struct’s type definition as a custom data type that maps back to whatever parameter the index value is associated with. The above listing at lines 15 through 18 do exactly that.

What’s so great about that, and why would such a thing be useful? While it may not seem like such an awesome thing to do at first, what we’ve done is found a way to pick elements out of a parameter pack by an index. Essentially we’ve given ourselves a way to allow random access to packs. The technique used is similar to the count struct, but not quite the same. We’re still using recursion, but this time we need to stop the recursion at the right element.

Take a look at line 6 in the above listing. This is where all the magic happens. The elementType struct calls itself using the same variadic unrolling trick that count used, except we decrement N at each step of the way, until N reaches zero, and we hit the termination condition (the partial specialization for when N is zero at lines 9 through 12). This means if we give an index of 5, we’ll get 5 recursions and the typedef that ends up getting defined is the one for the 6th parameter in the pack.

No problem right! So let’s put all this together for something actually useful — a variadic tuple class:

1
2
3
4
5
6

template <typename... Args> 
struct tuple {
        tuple(const Args&... args) {}
};
 
tuple<int, char> t1(1, '2');

The idea is we want to be able to use our tuple class like line 6 shows. This is the example from Part I, and as I previously mentioned, this isn’t so useful. Sure it lets us declare a tuple like we want, but it doesn’t actually store the tuple’s constructor arguments, nor does it give us any way to retrieve them. So how are we going to store the elements?

Like all things variadic, we’re going to use a recursive template definition! The tuple class will instantiate itself recursively, storing the arguments as it goes. Basically the tuple class will become a compile-time linked list of sorts. This means we’ll also have to use more metaprogramming to get access to the elements, but for now let’s take a look at the tuple class definition itself:

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20

template <typename... Args> struct tuple;
 
// recursion termination condition
template <> struct tuple<> {};
 
// recursive tuple template
template <typename Head, typename... TailArgs>
struct tuple<Head, TailArgs...> : private tuple<TailArgs...> {
        /**
         * \brief  Recursive constructor
        **/
        tuple(const Head& head, const TailArgs&... tailArgs) :
                tuple<TailArgs...>(tailArgs...),
                mHead(head)
        {
        }
 
private:
        Head mHead; ///< Tuple head
};

Although this might look a bit weird at first, there’s not actually that much that’s new here. We’re still just recursively defining a template class, and unrolling a parameter pack as we do it, but we’re doing it via inheritance this time. The tuple class’ base class is actually itself. We use the same trick we’ve used before to extract the first parameter from the parameter pack, but now we pass the template’s TailArgs to the base class so that the base class’ Head becomes the first element in its super class’ TailArgs.

When the instantiation of this class finishes it will be a tuple class that has an mHead member variable set to the value of the first argument in the parameter pack given to the tuple’s constructor as the head variable (which you can see being set at line 14). That tuple class will have a base class that itself has an mHead member variable which is set to be the second parameter in the initial instantiation’s parameter pack (or the first parameter given to the base class instantiation). This process repeats until all the parameters in the initial pack are exhausted and the termination condition is hit.

Okay, so that’s pretty cool, but now what? Basically we’ve got this weirdly constructed tuple class with a strange inheritance hierarchy that stores all the elements given to the constructor — we still need some method for extracting them! This is where all our previous metaprogramming fun comes into play. We’ve already built much of the framework we need to make this happen:

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37

template <typename Head, typename... TailArgs>
struct tuple<Head, TailArgs...> : private tuple<TailArgs...> {
        /**
         * \brief  Recursive constructor
        **/
        tuple(const Head& head, const TailArgs&... tailArgs) :
                tuple<TailArgs...>(tailArgs...),
                mHead(head)
        {
        }
 
        /**
         * \brief  Get a tuple argument
        **/
        template <int N>
        typename elementType<N, Head, TailArgs...>::type
        get() const {
                return getValueFromTuple<N>::template getValue<typename elementType<N, Head, TailArgs...>::type, Head, TailArgs...>(*this);
        }
 
        /**
         * \brief  Get the head value
        **/
        Head                            head() const { return mHead; }
 
        /**
         * \brief  Get the next argument in the chain
        **/
        const tuple<TailArgs...>&       next() const { return *this; }
 
private:
        Head                            mHead;                                  ///< Tuple head
};
 
// let's use our new get function!
tuple<int, char, bool, double> t1(1, '2', true, 3.14159);
char c = t1.get<1>(); // template get function where the index specified returns that parameter of the tuple class

The first function we’ve added is the tuple’s get function, which can be seen being used at line 37. So how the %@*! does that work anyway?

Our new class member template function works pretty much the same as Boost’s tuple library (although much simpler). All we’ve done is defined a template function that takes an integer as a template parameter, and we’ve used our elementType struct, which we’ve already seen from earlier in the article, to set the return type of the function to whatever type is at that index in the tuple’s parameter pack!

We are missing some pretty important code though. The get function then calls the getValue function, which we’ve yet to define:

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26

template <int N>
struct getValueFromTuple {
        template <typename ReturnType, typename Head, typename... TailArgs>
        static ReturnType getValue(tuple<Head, TailArgs...>& t) {                                                                          
                return getValueFromTuple<N - 1>::template getValue<ReturnType, TailArgs...>(t.next());
        }                                                                          
 
        template <typename ReturnType, typename Head, typename... TailArgs>
        static const ReturnType getValue(const tuple<Head, TailArgs...>& t) {                                                                          
                return getValueFromTuple<N - 1>::template getValue<ReturnType, TailArgs...>(t.next());
        }                                                                          
};                                                                           
 
// termination condition for when getValueFromTuple is instantiated with zero
template <>
struct getValueFromTuple<0> {
        template <typename ReturnType, typename... Args>
        static ReturnType getValue(tuple<Args...>& t) {                                                                         
                return t.head();
        }                                                                         
 
        template <typename ReturnType, typename... Args>
        static const ReturnType getValue(const tuple<Args...>& t) {                                                                         
                return t.head();
        }                                                                         
};

This might look a bit complicated, but there’s absolutely nothing here we haven’t seen before. We define a template struct called getValueFromTuple that takes an integer as a template parameter. This is done so that we can partially specialize the struct so we have a termination condition for the function we actually need (getValue). C++ function templates are a bit more limited than class templates in how we can partially specialize them — specific specializations by constants are not allowed, so we use this struct wrapping trick to give us what we need.

The getValue function is also nothing new. It does the exact same recursive unrolling that the elementType struct uses to extract a specific parameter by index. The function recursively instantiates itself until N reaches zero and the termination condition is called. The trick here is that getValue calls the tuple class’ next() function during each instantiation, which passes the tuple’s base class to the next instantiation of the function. All we’re doing here is walking the “list” of parameters passed to the tuple’s constructor, we just happen to be doing it by walking the class hierarchy.

Let’s take a quick look at the tuple’s next() function to see how this works:

const tuple<TailArgs...>&       next() const { return *this; }

This is how we trick the compiler into returning its base class — which has an mHead that contains the next parameter in the pack. The return type is the same type that the base class has, so when we return ourselves through the this pointer the compiler does the right thing and casts down to the base class.

So there we go: a fully functioning variadic tuple class that stores its constructor parameters and gives us a way to get at them by their index! We can now do this:

tuple<int, char, string, double> t1(1, '2', "variadics rule", 3.14159);
 
int    var0 = t1.get<0>(); // var0 is now 1
char   var1 = t1.get<1>(); // var1 is '2'
string var2 = t1.get<2>(); // var2 is now "variadics rule"
double var3 = t1.get<3>(); // var3 is now 3.14159

Sweet! Of course there are many improvements that could be made such as allowing access to elements by reference (for efficiently storing and retrieving large structures), adding iterators, copy constructors, operator overrides, etc, but I’ll leave that stuff as reader exercises :).

For the next installment the plan is to go even deeper down the the metaprogramming hole, and see what kind of compile-time fun we can have. Template metaprogramming is a really useful skill to have; the more you can do at compile time, the fewer instructions need to get executed at runtime, plus, as we’ve just seen in this article, metaprogramming trickery can make other code more readable and, in turn, easier to maintain. Not only that but playing around with template metaprogramming is a great way to get to know your compiler, and the C++ language!

By Tim.|Posted in Blog, Programming|

Fun with Variadic Templates: Part I

February 18, 2009 – 7:15 pm

If you’re a C++ user, you’ve probably heard that the up and coming language revision, C++0x, is adding support for variadic templates. And if you’re anything like me, perhaps your first question was “Cool, so what good are they?” And I would say “Excellent question!” to such an inquiry, because C++ has been doing variadic style templates and functions for a while now. Even C could do variadic functions with its ellipsis operator and vararg API. Combine that with function overloading and default function arguments and you’ve got yourself a pretty powerful variadic function system.

The same goes for C++’s templates. Have you ever wondered how Boost’s Tuple library works? Well, Boost does a lot of cool complex things, like defining variadic templates using preprocessor and template metaprogramming, but in the end it’s actually pretty simple:

struct NullArg {};
template<typename Type1 = NullArg, typename Type2 = NullArg, typename Type3 = NullArg> 
class tuple {
        tuple(T0 t0) {}
        tuple(T0 t0, T1 t1) {}
        tuple(T0 t0, T1 t1, T2 t2) {}
};
 
tuple<int, char> t(1, '2');

Of course this tuple class doesn’t store or let you retrieve arguments, only allows for up to three parameters (adding more arguments, while monotonous without some preprocessor fun, is easy), and there’s some definite metaprogramming magics that go into tuple’s get<X>() template function, but it’s all still possible.

Getting back to the point: alright so we can, in effect, do variadic templates already, even without fancy C++0x. So why are they good? Well, all we’re really able to do is emulate variadic templates. The compiler always sees those “variadic” structs as having the maximum number of parameters, which means extremely long mangled names (increased binary size), slower compilation time, stupidly complex compiler diagnostic output, and did I mention slower compilation time? Not to mention that it’s an ugly and hacky way to achieve something that could be much more elegant. It’s fine for libraries to define handy structs with variadic emulation, but do you really want your production code nastied up like that? Likely not.

So, in come’s C++0x’s variadic templates. They’re easy, fun, and the whole family can use them! The syntax looks like this:

template<typename... Args> 
class tuple {};
 
tuple<char, int, bool> t;

Not so useful yet, but as you can see the ellipsis operator is given new purpose, and in this case it’s meant to denote a template parameter pack. It can also be used to denote a parameter pack expansion, like this:

template<typename... Args> 
class tuple {
        tuple(Args...) {};
};
 
tuple<char, int, bool> t('1', 2, false);

Here we’ve created a variadic tuple template and expanded the Args parameter pack in the constructor, thus letting us pass a variable number of arguments to the tuple’s constructor.

You can use the pack expansion pretty much anywhere it makes sense: base classes, constructor initializers, you name it, but in my opinion the real power of variadics comes once you start using them in conjunction with template functions and we begin to utilize C++’s powers of argument deduction. Take a look at this:

template<typename... Args>
struct tuple {
        tuple(Args...) {};
};
 
template<typename... Args>
tuple<Args...> make_tuple(Args... args) {
        return tuple<Args...>(args...);
}
 
int main() {
        auto t1 = make_tuple(1, 2, 3, 4, 5);
        return 0;
}

Nice and clean! There’s no need to specify all the template arguments to make_tuple because the compiler deduces them from the function arguments! Also note the use of the C++0x auto keyword there. Auto variables are still statically typed, they just get their type set to whatever initializes them.

So there’s the ultra-basics. Up next I’m going to start exploring what you can really do with variadic templates — like how you can extract an arbitrary element from a pack, pack searching, and other fun compile time trickery. You’d think Bjarne might have wanted to allow random access to variadic parameter lists, but that just wouldn’t be any fun. Why do things with random access when you can do it all with recursion!

Ready for more? Head to Part II!

By Tim.|Posted in Blog, Programming|

Links from the Tubes

February 10, 2009 – 8:11 am

Random tube weirdness:

By Tim.|Posted in Blog|

Clean Bill of Health

February 5, 2009 – 8:49 pm

So it’s official: I don’t have anything nasty… that they tested me for. I’ve just been sick a lot, and I only fainted that one time. ;).

They x-ray’ed me twice, did three malaria screens on different samples of my blood, ultrasounded my liver, spleen, and for some reason the underside of my freakin’ spine. Seriously, when pregnant women get ultrasounds of their babies done, does it feel like the doctor is trying to forge the ultrasound wand into the sub-atomic particles inside the molecules on the back of your skin?

Anyway… so yeah, after all that, a bunch more blood tests (at least 10 vials worth), 3 urine samples, plus the fainting episode, and a trip to the hospital in an ambulance, they were able to give me the diagnosis that I am perfectly healthy!

I’m actually pretty stoked about it. Plus who knew that your liver and spleen were so cute. Well at least mine are. My internal organs are so much cuter than everyone else’s, and it’s not just because they’re mine! They were way cuter than any of those blotchy fetus ultrasound photos I’ve seen.

So my liver and spleen didn’t have hands or arms or legs, or a head. Nor did they look remotely different from each other in any way. They were smooth, and oblong, and completely uniform in colour. That’s what I’m talking about.

Alright I have no idea what I’m talking about.

The whole experience was a bit mad, but I’m thankful it’s over, and I suppose in a way I’m glad it all happened the way it did. Next time I feel weak from 4 nights of fevers though, I’m staying in bed!

By Tim.|Posted in Blog, News|

All is well!

February 2, 2009 – 7:50 pm

They released me from the hospital after nearly killing me with a “chicken” “sandwich” on “whole wheat” “bread”. They told me nothing was wrong with me and my first Malaria screen came back negative (yayy!). I also don’t have tuberculosis (YAYY!). Tomorrow there’s another round of tests though so we’ll see.

As for the fainting… maybe I just think about things too much or something but it was not a fun experience. I felt powerless, like, I knew it was going to happen and there was nothing I could do about it. Maybe that’s not true but at the time that’s how it felt.

Plus, waking up on the floor, seeing your wife’s terrified face… never fun.

Thanks to everyone who wished me a speedy recovery!

I’ll update again tomorrow after I’ve had my spleen ultrasounded!

By Tim.|Posted in Blog, News|

Hospitalized!

February 2, 2009 – 11:41 am

Posting from my phone. Jess and I have been feeling on and off crappy since getting back from the DR in Dec. Finally decided to go to the Doctor this morn. They sent me to a lab for bloodwork and I fainted while standing in line. Rode in ambulance. Currently laying in hospital bed waiting for bloodwork to come back. Will update again as soon as I know more.

By Tim.|Posted in Blog, News|