Skip to content

C++ Template Metaprogramming

2010-04-21

My close personal friend and colleague Encsé posted a fun little programming exercise and invited us to send him solutions in our favorite Turing-complete tool, especially if it happens to be mod_rewrite or C++ templates. Unfortunately, I don’t think there is a single sane person on the planet who would consider C++ their favorite anything, and I like Encsé better than to let him needlessly associate with any additional crazy people. Obviously, this meant that I had to delve into the murky depths of template madness myself.

Here is a copy of the problem, in case Encsé decides to delete his post once he finds out it has been tainted with C++ — which would be an entirely sensible (and, indeed, healthy) reaction:

Find a number consisting of 9 digits in which each of the digits from 1 to 9 appears only once. This number must also satisfy these divisibility requirements:

  1. The number should be divisible by 9.
  2. If the rightmost digit is removed, the remaining number should be divisible by 8.
  3. If the rightmost digit of the new number is removed, the remaining number should be divisible by 7.
  4. And so on, until there’s only one digit (which will necessarily be divisible by 1).

OK, so I implemented a solution using C++ template metaprogramming. It was actually easier than I thought, and the experience was surprisingly interesting. Which is not to say I’d like to do it again. I imagine I would feel this exact same way after performing an autopsy.

My approach encodes digits as template parameters using variadic templates, which are a recent addition to the language.  They make template metaprogramming more convenient the same way as a drop of mayonnaise would make a shit sandwich easier to swallow.

To make things easier to fit into the template syntax, the digits are encoded “backwards”, with the least significant digit to the left. The interesting part is the search template, which implements a simple exhaustive search (based on lexically incrementing the digit list). It trims the search space whenever a particular (partial) list of digits doesn’t satisfy the constraints above. The solution is not particularly efficient, and since template tail recursion isn’t optimized away, you’ll probably need to increase the maximum depth of template expansion in your compiler. (A limit of 2000 nested templates should be sufficient.) I needed this many levels due to the clumsy recursive chaining that I do in the topmost definition of the search_i template, which is expanded whenever the search tree is trimmed.

// Author: karoly@lorentey.hu, 2010-04-20.
//
// To compile this, you'll need a recent C++ compiler supporting C++0x
// variadic templates.
//
// Sample command line for GCC 4.4:
//
// g++ -Wall -ftemplate-depth-2000 -std=c++0x -o 9digits 9digits.cc

#include <iostream>

// value<DIGITS>::v is the value of DIGITS in decimal.
// The list starts with the least significant digit.
template<int... digits>
struct value;

template<>
struct value<>
{
  static const int v = 0;
};

template<int first, int... rest>
struct value<first, rest...>
{
  static int const v = 10 * value<rest...>::v + first;
};

// contains<ELEM, SET>::v is true if ELEM is in SET.
template<int elem, int... set>
struct contains;

template<int elem>
struct contains<elem>
{
  static const bool v = false;
};

template<int elem, int first, int... rest>
struct contains<elem, first, rest...>
{
  static const bool v = elem == first || contains<elem, rest...>::v;
};

// divisor_test<DIGITS>::v is true if the number of digits
// in DIGITS is a divisor of their decimal value.
template<int... digits>
struct divisor_test;

template<>
struct divisor_test<>
{
  static const bool v = true;
};

template<int first, int... rest>
struct divisor_test<first, rest...>
{
  static const int num = value<first, rest...>::v;

  static const int div = sizeof...(rest) + 1;

  static const int mod = num % div;

  static const bool v = mod == 0;
};

// test_candidate<FIRST, REST>::v is true if cons(FIRST, REST) satisfies
// all constraints, assuming that REST already does.
template<int first, int... rest>
struct test_candidate
{
  static const bool v = (divisor_test<first, rest...>::v
                         && !contains<first, rest...>::v);
};

// search<LENGTH, DIGITS>::v is the first number that is greater or
// equal to the decimal value of DIGITS, satisifies all constraints
// and is of the given LENGTH.  (-1 if there is no such number.)
template<int length, int... digits>
struct search;

template<int length, bool good, bool final, int digit, int... rest>
struct search_i
{
  static const int v = search<length, digit + 1, rest...>::v;
};

template<int length, int digit, int... rest>
struct search_i<length, true, true, digit, rest...>
{
  static const int v = value<digit, rest...>::v;
};

template<int length, int digit, int... rest>
struct search_i<length, true, false, digit, rest...>
{
  static const int v = search<length, 1, digit, rest...>::v;
};

template<int length, int digit, int... rest>
struct search<length, digit, rest...>
{
  static const bool good = test_candidate<digit, rest...>::v;
  static const bool final = good && 1 + sizeof...(rest) == length;
  static const int v = search_i<length, good, final, digit, rest...>::v;
};

template<int length>
struct search<length, 10>
{
  static const int v = -1;
};

template<int length, int next, int... rest>
struct search<length, 10, next, rest...>
{
  static const int v = search<length, next + 1, rest...>::v;
};

template<int length>
struct search<length>
{
  static const int v = search<length, 1>::v;
};

// This program eats cute kittens for breakfast.
int
main ()
{
  std::cout << search<9>::v << '\n';

  return 0;
}

You can download the source and try it yourself if you want. Your doctor would probably suggest that you don’t.

If you step back a few meters and squint your eyes a bit, the general approach may look a bit similar to that of a functional language like Haskell or Clean, except NOT AT ALL, WHAT THE HELL HAVE YOU BEEN SMOKING, STOP COMPARING THIS SENSELESS PERVERSION OF A LANGUAGE TO SOMETHING NAMED AFTER HASKELL CURRY, YOU DERANGED LUNATIC!!!

For shits and giggles I did some compilation benchmarks on my MacBook Pro (2.66 GHz Core 2 Duo, 4 GB). I don’t know how much time GCC version 4.3 needs to compile this… thing, because it still hasn’t finished, but amazingly, GCC 4.4 only required 6.9 seconds and about 115 MB RAM. This actually isn’t too bad at all, especially if you consider some of the alternatives.

Those intertwined template specializations mean that for every list of digits that this algorithm evaluates, it creates a new specialization for the value template, the contains template, the divisor_test template, et cetera, et cetera. To find the value of that single constant expression in the main function, the compiler ends up with thousands upon thousands of these little cross-referencing one-off types. Fortunately, each of them consists of one or more static const members, and none of these structs are ever instantiated, so all traces of them can be completely eliminated from the compiled object file.

All the interesting stuff happens inside the compiler, and the end result is an executable file that is equivalent to the slightly less cuckoo (but unfortunately still C++) program below. GCC 4.4 compiles this trivial program in 0.25 seconds, which is (only!) about thirty times faster than the abomination listed above. GCC is getting pretty good these days, isn’t it?

#include <iostream>

int
main ()
{
  // SPOILERS!
  std::cout << 381654729 << '\n';
  return 0;
}

(Incidentally, a C version that uses printf instead of these mysterious shift operators compiles in under 0.04 secs. I like C. C likes me. You always know where you are with C.)

I could prove that these programs produce the same results by posting the compiler’s assembly outputs, but publishing C++ disassembly is against the Universal Declaration of Human Rights. Compile them and see for yourself, if you dare.

Is this a clever trick? Yeah, it’s undoubtedly pretty clever.

Is this approach useful in real life? Well, there are some considerably less insane use cases. Boost has some well-written examples.

Is it a good idea to use these kinds of language hacks in any project that you or your company depend on? Absolutely not. For example, Boost also includes a rich variety of lovingly hand-crafted C preprocessor hacks. Using C++ template metaprogramming for anything serious is at least as good an idea as using any of those. For best (i.e., worst) effect, try combining the power of templates and the C preprocessor!

Let this post serve as a warning for us all. Please do not use C++ at home. Or at work. Especially not at work.

As far as members of the C language family go, I’m staying with C, Objective C, Java and C#, thank you very much. I hear D is also pretty nice.

Update: GCC 4.3 finished in 15 minutes and 54 seconds, consuming 1.5 GB of address space. Hurray for progress!

Update 2: Cactus has created a Haskell version of this algorithm. Its beauty contrasts nicely with the morbid ugliness of the C++ version.

From → deranged

10 Comments
  1. +10 for wicked awesome.

    -1 for poor imitation of Jeremy Clarkson :)

    • Yay, 9 points for Gryffindor!

      Is that the guy from Top Gears? No wonder I cannot imitate him well, we have completely different hair.

  2. Here’s my reconstruction of the algorithm in Haskell:

    http://gergo.erdi.hu/cs/ninedigits/lorentey-c%2B%2B-tmp/lorentey-c%2B%2B-tmp.hs

    It is much more readable than that C++ TMP mess. But still, the mapping between the C++ TMP code and the Haskell code is straightforward enough that I’m tempted to write a two-way compiler…

    • Thanks! That Haskell code is the most awesome thing I have seen this week.

  3. Status report:

    I’ve written everything to parse & typecheck a simple, Haskell-like functional language (I’m calling it Kiff for Keep It Fun & Functional). It has a Hindley-Milner type system with algebraic data types and two builtin primitive types Int and Bool (and also the usual syntax sugar for lists), recursive let, and higher-order functions.

    I’ve also created the internal representation of C++ TMP’s, and I have everything to represent algebraic data types in C++TMP.

    So I think the chances are pretty good that I’ll have a simple Kiff -> C++TMP compiler in a couple of days. It should be, at the very least, be able to take the above source file and compile it to a functional equivalent of your hand-crafted TMP.

    • That’s too slick for words! I fully support the idea of eliminating the need for hand-crafted TMP, and Hindley-Milner type systems are my favorite type systems of all.

  4. It’s not complete or finished or anything remotely like that, but I’ve made my Git repo public, so interested readers can check it out:

    http://gergo.erdi.hu/projects/metafun/

  5. Well, C++ metaprogramming can indeed sometimes be a pain. But it can also be used for pretty useful things, one example being Boost.MPL and its usage.

    I’ve also had a stab at this, at http://cplusplus.co.il/2010/01/27/compile-time-primality-test/

    I liked the post, thanks :)

Trackbacks & Pingbacks

  1. 9 Digit Problem in Haskell « Lingua Computa
  2. Twitter Weekly Updates for 2011-05-02 « Zenshō (前哨)

Comments are closed.

Follow

Get every new post delivered to your Inbox.

%d bloggers like this: