Deconstructing Compile Time FizzBuzz in C++ Without Boost
Several years ago Adam Peterson published an article on how to implement FizzBuzz at cmpile time in C++. The code was clever, but had a dependency on Boost and didn't go into great detail on how it worked, so I thought I'd write it again from scratch and try to explain my workings. In this article I'm only going to show examples that would work for very small FizzBuzz sequences because, well, this is a learning exercise not a typing exercise!
At the end of this article you'll find the source that I used to run the examples below - up to 16 items in the sequence. Much of what follows is a variation on the code in chapter 5 of C++ Template Metaprogramming, in particular the use of mpl::vector and the 'tiny' sequence.
First, get an error message
To make this work, we first have persuade the compiler to print an error message to the console when we build the program, something like this:
This is a simplified version of the mpl::vector example from C++ Template Metaprogramming. In particular note the typedef for ‘self’ and the typedefs for template parameters; we’ll be using these in our helper templates. When we compile this with VS2010, we get this:
This is promising; it displays the types that we put in, and in the right order. That’s fine, but the compiler works with types and we need to display numeric values, so we need a helper to convert intergers to types. [Loki](http://loki-lib.sourceforge.net/ “Loki library”) calls this `Int2Type` and [Boost.MPL](http://www.boost.org/doc/libs/1_54_0/libs/mpl/doc/index.html “Boost.MPL”) has `mpl::int_` that does the same thing, but it’s really easy to implement:
12345
template<intN>structint_{staticconstintvalue=N;};
For each distinct value ‘N’, this template creates a distinct type, so `int_<0>` is a different type from `int_<1>` etc.
Now we can put this into our ‘error’ template:
That's fine, but now we need to generate the sequence.
To get a new sequence, we have to append a new type (e.g. int_<1>) to an existing sequence (int_<0>). Loki uses typelists that we could just append to but here we're modelling our sequence on mpl::vector so we need to do more work.
We can only do that if we know how big our current sequence is, so we first need to specialize our template for every possible size of sequence (this is why we're only working with small sequences!). This is a very much simplified version of the code in C++ Template Metaprogramming, in particular I've not implemented 'apply' metafunctions to make it clearer what's going on. Note that here the size is derived from the int_<> helper template that we defined earlier so that we can get the 'value' later:
For an existing length, the 'size' template will select the 'best' specialisation of the size_impl template and add the new type as the last parameter. So now we can append a new type to another:
The same idea applies here; we use the push_back template to select the most appropriate push_back_impl template for the existing size. Note that we're not checking that the sequence is already full; this shouldn't be a problem with our limited use case for this example.
Now we can use the recursive parts of Adam's RunFizzBuzz to generate our sequence:
In this case the compiler will use the primary template and will recursively subtract 1 from the number and then instantiate itself until the number gets to zero, when it will use the specialisation for '0' to terminate the sequence.
That looks a lot like what we want, but so far we havn't output Fizz or Buzz; we'll fix that now…
Selecting Fizz
We need to select a different type (Fizz) if the number is divisible by 3. This calculation is a compile time constant for each template instantiation, so we can use it as a parameter to a template; if_c is a fairly simple type selection template that works by specializing for one value of the condition (in this case 'false'):