Template metaprogramming II: Openning the box

We saw last time how to print a factorial using only template metaprogramming, but didn't explain anything about it. I promised to fix that in this article. Starting by the very beginning:

template <int N> struct Factorial {
	static const int result = N * Factorial<N-1>::result;
};

template <> struct Factorial<0> {
	static const int result = 1;
};

int main() {
	std::cout << Factorial<5>::result << "n";
	return 0;
}

Why static const?

Templates get evaluated on compile time, remember? That means all that code actually executes when compiling the source, not when executing the resulting binary (assuming it actually compiles, of course). Having as a constraint the fact that all your code must resolve on compile time means only const vars make sense. Also, as you're working with classes (templates are applied to classes, not objects) only static objects make sense.

That explains the static const thing, what about the Factorial<0>? Well it's obviously an edge case. It describes a specific case of a Factorial. It's a specialization! Why do we need it? Take a look again at the definition of struct Factorial: it's a recursive definition. How do we break from the recursive loop? With a base case, obviously.

If this is starting to remind you of anything then you are crazier than you think, and you already know some Haskel. Indeed, template metaprogramming has some resemblance to Haskel programming: no const "variables", no for-loop (only recursion), base cases (pattern matching), and cryptic error messages which makes you want to jump of a cliff.

A useful trick I learned when working with Haskel (many many years ago) is to declare the problem, instead of thinking it. For our problem the factorial of a number is defined as said number times the factorial of that same number minus one, being the factorial of 0 always 1.

Translating:

// the factorial of a number is defined as said number times
// the factorial of that same number minus one

template <int N> struct Factorial {
	static const int result = N * Factorial<N-1>::result;
};

// being the factorial of 0 always 1.
template <> struct Factorial<0> {
	static const int result = 1;
};

That's good for a first approach... next time something more complex (and less theory, promise).

---

Thanks to Stéphane Michaut for reporting broken code in this page.