Using C++ template metaprogramming, I'll try to solve FizzBuzz by having the compiler output the solution as error messages.

FizzBuzz? The hilarious drinking game? Well, almost. It all started with a blog by Imran on how FizzBuzz was used during interviews to weed out programmers that, believe it or not, cannot program. The interview question was put like this:

“Write a program that prints the numbers from 1 to 100. But for multiples of three print “Fizz” instead of the number and for the multiples of five print “Buzz”. For numbers which are multiples of both three and five print “FizzBuzz”.”

Simple enough, but FizzBuzz proved to be scarily effective in eliminating programmers that actually cannot produce software. During the lengthy discussions that followed, a lot of creative solutions to FizzBuzz were posted. They ranged from over-engineered Java to down-to-the-metal Assembler, wicked Perl one-liners, and XSLT solutions. Of course I want to be a part of this rising FizzBuzz industry! Here’s my starting points:

1. Pure functional languages are cool,
2. recursive programs are more beautiful than their iterative counterparts, and
3. programmers like premature optimizations.

I'll try to glue it all together in C++. In fact I’m going to use a particularly evil corner of the language: templates. Metaprograms in C++ execute at compile-time and are indeed pure functional. Now, a fundamental requirement on FizzBuzz is that it prints the results. Printing in a pure functional language isn’t easy. I may be manager-material, because I’ll try to delegate this tricky problem. Who’ll get it? Well, I have a very expensive compiler in Microsoft’s Visual Studio 2005, so why not get some value for my money and have the compiler do the hard work? Here’s my first shot:

#include <iostream>

#define BOOST_MPL_CFG_NO_PREPROCESSED_HEADERS
#define BOOST_MPL_LIMIT_VECTOR_SIZE 110

#include "boost/mpl/if.hpp"
#include "boost/mpl/int.hpp"
#include "boost/mpl/vector.hpp"
#include "boost/mpl/push_back.hpp"

using namespace std;
using namespace boost::mpl;

struct Fizz{};
struct Buzz{};
struct FizzBuzz{};

template<int i>
struct RunFizzBuzz
{
   typedef vector<int_<i> > Number;

   typedef typename if_c<(i % 3 == 0) && (i % 5 == 0), FizzBuzz, 
                    typename if_c<i % 3 == 0, Fizz,
                             typename if_c<i % 5 == 0, Buzz, Number>::type>::type >::type t1;

   typedef typename push_back<typename RunFizzBuzz<i - 1>::ret, t1>::type ret;
};

template<>
struct RunFizzBuzz<0> // Terminate the recusion.
{
   typedef vector<int_<0> > ret;
};

int main()
{
   typedef RunFizzBuzz<100>::ret::compilation_error_here res;
} 

This program is impossible to outperform with respect to run-time performance; it will actually never run! And here’s the nice touch: the program will deliberately not even compile! The interesting part is that as error message, the compiler outputs the FizzBuzz solution. Look at the highlighted parts below:

\Main.cpp(36) : error C2039: 'compilation_error_here' : is not a member of
 'boost::mpl::vector101 <SNIP long argument list>'
    with
    [
         T0=boost::mpl::int_<0>,
         T1=boost::mpl::vector<boost::mpl::int_<1>>,
         T2=boost::mpl::vector<boost::mpl::int_<2>>,
         T3=Fizz,
         T4=boost::mpl::vector<boost::mpl::int_<4>>,
         T5=Buzz,
         T6=Fizz,
         T7=boost::mpl::vector<boost::mpl::int_<7>>,
         T8=boost::mpl::vector<boost::mpl::int_<8>>,
         T9=Fizz,
         T10=Buzz,
         T11=boost::mpl::vector<boost::mpl::int_<11>>,
         T12=Fizz,
         T13=boost::mpl::vector<boost::mpl::int_<13>>,
         T14=boost::mpl::vector<boost::mpl::int_<14>>,
         T15=FizzBuzz,
         <SNIP of elements 16 - 95>
         T96=Fizz,
         T97=boost::mpl::vector<boost::mpl::int_<97>>,
         T98=boost::mpl::vector<boost::mpl::int_<98>>,
         T99=Fizz,
         T100=Buzz
    ]

How it works

In C++ template metaprogramming, loops are implemented using recursive template instantiations (RunFizzBuzz<i - 1>::ret). The recursion is terminated by a template specialization (template<> struct RunFizzBuzz<0>), which is like a compile-time conditional. To simplify my work I use some powerful abstractions from the Boost Meta Programming Library (MPL): a compile-time vector for storing the types making up the FizzBuzz solution, if_c that lets me select different types, and push_back that simply returns a new vector containing the types I derived so far.
In main() I force the template instantiation, get the returned type and try to dig deeper for a nested compilation_error_here member that obviously doesn’t exist. That last step forces a diagnostic from the compiler, which helpfully dumps its detailed view of the offending type; the sequence of types building up the FizzBuzz solution.
Rather straightforward, even if I had to make a small extension; Boost MPL includes support for a maximum of 50 elements in a compile-time vector, but the library allows me to easily use larger vectors if I provide the necessary declarations myself. I put them in a boost/mpl/vector110.hpp file, turn-up the BOOST_MPL_LIMIT_VECTOR_SIZE, press compile, lean back and let Visual C++ have some serious exercise.

Exit Portability

That's it. A complete FizzBuzz solution written by Visual Studio 2005. Besides a horrific compilation time, the program has the following drawbacks:

1. It starts at 0 instead of 1. This is just to make the output more readable by having the number encoded in the template argument (T0, T1, T2, etc) map directly to its FizzBuzz representation. If you want a strict version of FizzBuzz, just change the template specialization to terminate on '1' and return a vector<int_<1> > instead.

2 . It is inherently non-portable. First, error messages in C++ aren’t standardized. Other compilers are likely to give other diagnostics and, potentially, ruin the whole game. Second, the template instantiation depth is only required to be 17 (wow – that’s a magic number!), although most modern compilers go far beyond that.

Now, the only question that remains is: would I pass the interview?

April 2007