Programmer's Roundabout

Tuesday, November 20, 2007

Numeric computation with Meta Programming

The earliest C++ metaprograms performed integer computations at compile time. One of the very first metaprograms was shown at a C++ committee meeting by Erwin Unruh; it was actually an illegal code fragment whose error messages contained a sequence of computed
prime numbers!

Since illegal code is hard to use effectively in a larger system, let's examine a slightly more practical application.

The following metaprogram (which lies at the heart of our little compiler test above) transliterates unsigned decimal numerals into their binary equivalents, allowing us to express binary constants in a recognizable form.


template
struct binary
{
static unsigned const value
= binary::value << 1 // prepend higher bits
| N%10; // to lowest bit
};

template <> // specialization
struct binary<0> // terminates recursion
{
static unsigned const value = 0;
};
unsigned const one = binary<1>::value;
unsigned const three = binary<11>::value;
unsigned const five = binary<101>::value;
unsigned const seven = binary<111>::value;
unsigned const nine = binary<1001>::value;


If you're wondering "Where's the program?" we ask you to consider what happens when we access the nested ::value member of binary.
The binary template is instantiated again with a smaller N, until N reaches zero and the specialization is used as a termination condition. That process should have the familiar flavor of a recursive function call—and what is a program, after all, but a function?
Essentially, the compiler is being used to interpret our little metaprogram.