November 10, 2007
Alex Rubinsteyn

# Almost Solving Instant Insanity with C++ templates

## A brief introduction to C++ metaprogramming

Since not many people are familiar with C++'s capacity for compile-time computation, it's probably worthwhile to give a short introduction to programming with templates. If you're already a dark wizard of metaprogramming, skip along to the next section. Now, templates were added to C++ to enable generic programming (much to the delight of Alexander Stepanov). It wasn't initially obvious that they could be used for much besides containers and generic algorithms. Several years after the introduction of templates into the C++ standard, Eric Unruh discovered that they formed a Turing-complete compile-time programming language. Here's the code that revolutionized the modern programming world:

template<int N> class Factorial { public: enum { value = N * Factorial<N-1>::value }; }; class Factorial<1> { public: enum { value = 1 }; };

When this fragment is compiled the Factorial class will be instantiated for some integer value of N. Factorial<N> instantiates the type Factorial<N-1>, which in turn instantiates Factorial<N-2>, and so on. Finally, the base case of Factorial<1> is reached and the chain of template expansions halts. Though very simple, the above code teaches us most of what we need to know about C++ metaprogramming.

• There are no assignments in this metaprogram. Once a variable is defined it will retain its value forever. C++ templates are a great example of a pure functional programming language. Mutation is simply not an option.
• The above code is recursive. In fact, all metaprograms are recursive. There is no other way to loop or repeat code.
• Control flow is achieved through pattern matching. How much more like Haskell can we get?

So, even though templates generate C++ code, they themselves are a completely different model of computation. If you want to understand how templates work, you'll find lambda calculus more useful than knowledge about C++'s run-time semantics.

Note: if you are considering using template metaprogramming for a non-trivial task I would strongly advise you to use Boost.MPL. The madmen at Boost spend their time probing the arcane depths of compiler bugs so you don't have to! I give this advice hypocritically, since I've never installed Boost on my machine. However, I'm more interested in how metaprogramming works than using it for anything productive.

Here's a quick summary of how we can map the Haskell code in the Monad Reader to C++. In the following code snippet Haskell is colored maroon and C++ is in blue.

Atomic types
data R
struct R {};
Parameterized types
data Cube u f r b l d
template <U, F, R, B, L, D> struct Cube { typedef U u; typedef F f; typedef R r; typedef B b; typedef L l; typedef D d; };
Type aliases
type CubeRed = Cube R R R R R R
typedef Cube<R,R,R,R,R,R> CubeRed;
Type functions
class Transforms u f r b l d where rot :: Cube u f r b l d → Cube u r b l f d
template <typename C> struct rot { typedef Cube<typename C::u, typename C::r, typename C::b, typename C::l, typename C::f, typename C::d> result; };
Functional dependency
class And b1 b2 b | b1 b2 → b where and ::b1 → b2 → b instance And True True True where and = instance And True False False where and = instance And False True False where and = instance And False False False where and = template<typename b1, typename b2> struct And { typedef False result; }; template <> struct And<True, True> { typedef True result; };
Type lists
data Nil data x ::: xs infixr 5 :::
struct Nil {}; //C++ doesn't allow infix cons like haskell template <typename Car, typename Cdr> struct Cons { typedef Car car; typedef Cdr cdr; };
Higher order metafunctions
class Map f xs zs | f xs → zs where map :: f → xs → zs instance Map f Nil Nil where map = instance (Apply f x z, Map f xs zs) ⇒ Mapf (x ::: xs) (z ::: zs) where map = template <typename f, typename xs> struct Map { typedef Cons<f<typename xs::car>::result, Map<f, typename xs::cdr>::result> result; }; template <typename f> struct Map<f, Nil> { typedef Nil result; };

## C++ vs. Haskell: Type-Level Deathmatch

There are a few spots where's C++'s unwieldly Turing-complete type system is actually better for metaprogramming than Haskell's unwieldly Turing-complete type system. C++ has a slightly more advanced notion of type identity. Whereas Haskell requires a full enumeration of possible arguments to implement a not-equals metafunction for colors, you can do it in C++ with simple pattern matching. Compare the following verbose Haskell code:

instance NE R R False where ne = instance NE R G True where ne = instance NE R B True where ne = instance NE R W True where ne = instance NE G R True where ne = instance NE G G False where ne = instance NE G B True where ne = instance NE G W True where ne = instance NE B R True where ne = instance NE B G True where ne = instance NE B B False where ne = instance NE B W True where ne = instance NE W R True where ne = instance NE W G True where ne = instance NE W B True where ne = instance NE W W False where ne = with a more succinct (and general) version in C++:

template <typename S, typename T> struct NE { typedef True result; }; template <typename S> struct NE<S,S> { typedef False result; };

Another advantage C++ has over Haskell is the ability to partially apply type parameters. What does that mean? Well, consider the following (rather useless) type-level function `ChooseSecond` which accepts two types, `T1` and `T2`, and yields as its value.

template <typename T1, typename T2> struct ChooseSecond { typedef T2 result; };

Now, when we're computing with types it's sometimes useful to distinguish between various kinds of types. The kind of our metafunction `ChooseSecond` is `* → * → *`, meaning it accepts two types and returns a third. If we attempt to apply just one type (as in `ChooseFirst<int>`) we'll rightfully get a compiler error. Similarly, if you attempt to apply just one type parameter to a Haskell datatype which expects two, the Haskell compiler will taser you through the keyboard. However, by adjusting our expectations of how C++ type-functions are laid out and inserting a layer of indirection, we can actually achieve partial type application. Instead of accepting type parameters directly, we delegate their use to an inner struct named `apply`. This allows us to ignore the differences between types and type functions (they now all have a kind of `*`).

struct ChooseSecond { template <typename T1, typename T2> struct apply { typedef T2 result; }; }; struct PApply { template <typename F, typename T1> struct apply { struct result { template <typename T2> struct apply { typedef typename F::apply<T1, T2>::result result; }; }; }; }; typedef PApply::apply<ChooseSecond, int>::result Fint; typedef Fint::apply<bool>::result SomeType; // SomeType = bool

I picked up the above indirection trick from Boost.MPL (which includes all sorts of crazy things like anonymous type-level functions). Don't worry if you don't understand what's happening above, the important concept is that C++ allows us to treat types more freely then we could in Haskell.

Yes, C++'s templates are tremendously powerful. Unfortunately, there's a price to be paid for accidentally implementing a programming language. When you write a compile-time program in C++, you are committing a crime against the compiler...and the compiler won't hesitate to let you know that. If there's a bug in your code, you might find yourself the unhappy recipient of several thousand error messages. This is where Haskell shines: its type system was actually intended to be powerful. When I attempt to evaluate my Instant Insanity metaprogram, Visual C++ consumes 2gb of memory before dying with a cryptic error message. Clearly, C++ compilers have a lot of catching up to do.

Another strong advantage of doing your type-level programming in Haskell is the availability of an interpreter. C++ templates exist beyond the reach of any debugger or code inspection tool. You write your metaprogram, compile, and pray. Haskell, on the other hand, allows for an incremental style of development. A Haskell interpreter will allow you to inspect the type and kind of every construct in your metaprogram. Type-level C++ programs are, as a rule, heroic hacks. Haskell, on the other hand, provides a comparatively sane development experience.

## The Code (or, Stop Reading Here)

Since I suspect at most four people will ever read this far, I can now reveal my dirty secret. I didn't really implement Instant Insanity in C++ templates. I gave in to a much darker urge and wrote a layer of C preprocessor macros to generate my template code. As a result I am now the inventor of the the world's ugliest, most brittle, and arguably most useless programming language. Feel free to use these macros however you want. Especially in large production systems. Without further ado, I give you Instant Insanity:

/* colors */ SYMBOL(R); SYMBOL(G); SYMBOL(B); SYMBOL(W); /* cube structure */ RECORD6(Cube, u, f, r, b, l, d); LET(Cube1, CREATE6(Cube, B, G, W, G, B, R)); LET(Cube2, CREATE6(Cube, W, G, B, W, R, R)); LET(Cube3, CREATE6(Cube, G, W, R, B, R, R)); LET(Cube4, CREATE6(Cube, B, R, G, G, W, W)); LET(Cubes, LIST4(Cube1, Cube2, Cube3, Cube4)); /************************** Cube Transformations ****************************/ DEFUN1(Rotation, C) RETURN(CREATE6(Cube, GET(C,u), GET(C,r), GET(C,b), GET(C,l), GET(C,f), GET(C,d))); END DEFUN1(Twist, C) RETURN(CREATE6(Cube,GET(C,f), GET(C,r), GET(C,u),GET(C,l),GET(C,d),GET(C,b))); END DEFUN1(Flip, C) RETURN(CREATE6(Cube,GET(C,d),GET(C,l),GET(C,b),GET(C,r),GET(C,f),GET(C,u))); END
//--Compute all 24 ways to orient a cube. // haskell: orientations c = // [c'''|c'<-[c, rot c, rot (rot c), rot(rot (rotc))], // c''<-[c', twist c', twist (twist c')], // c'''<-[c'', flip c'']]
DEFUN1(Rotations, C) LET(rot, APPLY1(Rotation, C)); LET(rot2, APPLY1(Rotation, rot)); LET(rot3, APPLY1(Rotation, rot2)); RETURN(LIST4(C, rot, rot2, rot3)); END DEFUN1(Twists, C) LET(twist, APPLY1(Twist, C)); LET(twist2, APPLY1(Twist, twist)); RETURN(LIST3(C, twist, twist2)); END DEFUN1(Flips, C) LET(flip, APPLY1(Flip, C)); RETURN(LIST2(C, flip)); END DEFUN1(Orientations, C) LET(rots, APPLY1(Rotations, C)); LET(twists, APPLY2(MapAppend, Twists, rots)); RETURN(APPLY2(MapAppend, Flips, twists)); END
//--Two cubes are compatible if they have different colours on every visible face. // haskell: compatible c c' = and [x/=x'|(x,x') <- zip(visible c)(visible c')]
DEFUN2(Compatible, C1, C2) LET(samefaces, LIST4( APPLY2(NotEq, GET(C1, f), GET(C2, f)), APPLY2(NotEq, GET(C1, b), GET(C2, b)), APPLY2(NotEq, GET(C1, r), GET(C2, r)), APPLY2(NotEq, GET(C1, l), GET(C2, l)))); RETURN(APPLY1(All, samefaces)); END
//--Determine whether a cube can be added to pile of cubes, without //--invalidating the solution. // haskell: allowed c cs = and[compatible c c'|c' <- cs]
MATCH(Allowed) DEFAULT2(cube, pile) RETURN(IF(APPLY2(Compatible, cube, HD(pile)), APPLY2(Allowed, cube, TL(pile)), False)); ENDCASE CASE1(cube, PATTERN2(cube, Nil)) RETURN(True); ENDCASE ENDMATCH MATCH(MatchingOrientations) DEFAULT2(orientations, solution) LET(rest, APPLY2(MatchingOrientations, TL(orientations), solution)); LET(cube, HD(orientations)); RETURN(IF(APPLY2(Allowed, cube, solution), CONS(CONS(cube, solution), rest), rest)); ENDCASE CASE1(solution, PATTERN2(Nil, solution)) RETURN(Nil); ENDCASE ENDMATCH MATCH(AllowedCombinations) DEFAULT2(orientations, solutions) LET(rest, APPLY2(AllowedCombinations, orientations, TL(solutions))); LET(matching, APPLY2(MatchingOrientations, orientations, HD(solutions))); RETURN(APPLY2(Append, matching, rest)); ENDCASE CASE1(orientations, PATTERN2(orientations, Nil)) RETURN(Nil); ENDCASE ENDMATCH MATCH(Solutions) DEFAULT1(cubes) LET(cube, HD(cubes)); LET(orientations, APPLY1(Orientations, cube)); LET(sols, APPLY1(Solutions, TL(cubes))); RETURN(APPLY2(AllowedCombinations, orientations, sols)); ENDCASE CASE0(PATTERN1(Nil)) RETURN(LIST1(Nil)); ENDCASE ENDMATCH MAIN LET(cubes, LIST4(Cube1, Cube2, Cube3, Cube4)); LET(solutions, APPLY1(Solutions, cubes)); PRINT(solutions); END_MAIN

## The Expanded Mess of C++

For completeness, I'm also posting the expanded version this program (care of cl.exe /P). All structs and symbols have automatically generated string representations in the form of a static `to_s` function. The string representations are necessary to get the results of the compile-time computation. This demonstrates how pervasively functional template metaprogramming is. Since output is a side effect, the results of a computation must be inspected from outside the metaprogram.

struct TypeEnum { enum Value { Cons, Symbol, Record1, Record2, Record3, Record4, Record5, Record6, Record7, Record8, Function, Function1, Function2, Function3, Function4, Function5, Function6, Function7, Function8, Int }; }; struct True { static const TypeEnum::Value metatype = TypeEnum::Symbol; static std::string to_s() { return "True"; } }; struct False { static const TypeEnum::Value metatype = TypeEnum::Symbol; static std::string to_s() { return "False"; } }; struct If { static const TypeEnum::Value metatype = TypeEnum::Function; template <typename Truth, typename Tval, typename Fval> struct apply { typedef Fval result; }; template <typename Tval, typename Fval> struct apply <True, Tval, Fval> { typedef Tval result; }; }; struct Nil { static const TypeEnum::Value metatype = TypeEnum::Symbol; static string to_s() { return "[]"; } }; template <typename argcar, typename argcdr> struct ConsCell { static const TypeEnum::Value metatype = TypeEnum::Cons; typedef argcar car; typedef argcdr cdr; typedef ConsCell<car, cdr> result; static std::string to_s() { return "[ " + car::to_s() + " " + ConsPrinter<cdr>::to_s() + "]"; }; template <typename elt> struct ConsPrinter { static string to_s() { return Aux<elt::metatype>::to_s(); } template<TypeEnum::Value type> struct Aux { static string to_s() { return elt::to_s(); } }; template <> struct Aux<TypeEnum::Cons> { static string to_s() { return elt::car::to_s() + " " + ConsPrinter<elt::cdr>::to_s(); } }; }; template <> struct ConsPrinter<Nil> { static string to_s() { return ""; } }; }; struct Cons { static const TypeEnum::Value metatype = TypeEnum::Function2; template <typename car, typename cdr> struct apply { typedef ConsCell<car,cdr> result; }; }; struct NotEq { static const TypeEnum::Value metatype = TypeEnum::Function; template <typename S, typename T> struct apply { typedef True result; }; template <typename S> struct apply <S, S> { typedef False result; }; }; struct Append { static const TypeEnum::Value metatype = TypeEnum::Function; template <typename List1, typename List2> struct apply { typedef ConsCell<typename List1::car, typename Append::apply<typename List1::cdr,List2>::result> result; }; template <typename List2> struct apply <Nil, List2> { typedef List2 result; }; }; struct MapAppend { static const TypeEnum::Value metatype = TypeEnum::Function; template <typename fn, typename list> struct apply { typedef typename fn::apply<typename list::car>::result ResultList; typedef typename MapAppend::apply<fn, typename list::cdr>::result RestOfList; typedef typename Append::apply<ResultList, RestOfList>::result result; }; template <typename fn> struct apply <fn, Nil> { typedef Nil result; }; }; struct R { static const TypeEnum::Value metatype = TypeEnum::Symbol; static std::string to_s() { return "R"; } }; struct G { static const TypeEnum::Value metatype = TypeEnum::Symbol; static std::string to_s() { return "G"; } }; struct B { static const TypeEnum::Value metatype = TypeEnum::Symbol; static std::string to_s() { return "B"; } }; struct W { static const TypeEnum::Value metatype = TypeEnum::Symbol; static std::string to_s() { return "W"; } }; template <typename arg_u, typename arg_f, typename arg_r, typename arg_b, typename arg_l, typename arg_d> struct Cube { static const TypeEnum::Value metatype = TypeEnum::Record6; typedef arg_u u; typedef arg_f f; typedef arg_r r; typedef arg_b b; typedef arg_l l; typedef arg_d d; typedef Cube<u, f, r, b, l, d> result; static std::string to_s() { return std::string("{") + "u:" +u::to_s() + ", " + "f:" + f::to_s() + ", " + "r:" + r::to_s() + ", " + "b:" +b::to_s() + ", " + "l:" + l::to_s() + ", " + "d:" + d::to_s() + "}"; } }; typedef Cube<B,G,W,G,B,R> Cube1; typedef Cube<W,G,B,W,R,R> Cube2; typedef Cube<G,W,R,B,R,R> Cube3; typedef Cube<B,R,G,G,W,W> Cube4; struct Rotation { static const TypeEnum::Value metatype = TypeEnum::Function1; template <typename C> struct apply { typedef Cube<typename C::u,typename C::r, typename C::b,typename C::l,typename C::f, typename C::d> result; }; }; struct Twist { static const TypeEnum::Value metatype = TypeEnum::Function1; template <typename C> struct apply { typedef Cube<typename C::f,typename C::r,typename C::u, typename C::l,typename C::d,typename C::b> result; }; }; struct Flip { static const TypeEnum::Value metatype = TypeEnum::Function1; template <typename C> struct apply { typedef Cube<typename C::d,typename C::l,typename C::b,typename C::r, typename C::f,typename C::u> result; }; }; struct Rotations { static const TypeEnum::Value metatype = TypeEnum::Function1; template <typename C> struct apply { typedef typename Rotation::apply<C>::result rot; typedef typename Rotation::apply<rot>::result rot2; typedef typename Rotation::apply<rot2>::result rot3; typedef ConsCell<C, ConsCell<rot, ConsCell<rot2, ConsCell<rot3, Nil> > > > result; }; }; struct Twists { static const TypeEnum::Value metatype = TypeEnum::Function1; template <typename C> struct apply { typedef typename Twist::apply<C>::result twist; typedef typename Twist::apply<twist>::result twist2; typedef ConsCell<C, ConsCell<twist, ConsCell<twist2, Nil> > > result; }; }; struct Flips { static const TypeEnum::Value metatype = TypeEnum::Function1; template <typename C> struct apply { typedef typename Flip::apply<C>::result flip; typedef ConsCell<C, ConsCell<flip, Nil> > result; }; }; struct Orientations { static const TypeEnum::Value metatype = TypeEnum::Function1; template <typename C> struct apply { typedef typename Rotations::apply<C>::result rots; typedef typename MapAppend::apply<Twists,rots>::result twists; typedef typename MapAppend::apply<Flips,twists>::result result; }; }; struct Compatible { static const TypeEnum::Value metatype = TypeEnum::Function2; template <typename C1, typename C2> struct apply { typedef ConsCell<typename NotEq::apply<typename C1::f,typename C2::f>::result, ConsCell<typename NotEq::apply<typename C1::b,typename C2::b>::result, ConsCell<typename NotEq::apply<typename C1::r,typename C2::r>::result, ConsCell<typename NotEq::apply<typename C1::l,typename C2::l>::result, Nil> > > > samefaces; typedef typename All::apply<samefaces>::result result; }; }; struct Allowed { static const TypeEnum::Value metatype = TypeEnum::Function; template <typename cube, typename pile> struct apply { typedef typename If::apply<typename Compatible::apply<cube, typename pile::car>::result,typename Allowed::apply<cube, typename pile::cdr>::result,False>::result result; }; template <typename cube> struct apply <cube, Nil> { typedef True result; }; }; struct MatchingOrientations { static const TypeEnum::Value metatype = TypeEnum::Function; template <typename orientations, typename solution> struct apply { typedef typename MatchingOrientations::apply<typename orientations::cdr, solution>::result rest; typedef typename orientations::car cube; typedef typename If::apply<typename Allowed::apply<cube,solution>::result, ConsCell<ConsCell<cube,solution>,rest>,rest>::result result; }; template <typename solution> struct apply <Nil, solution> { typedef Nil result; }; }; struct AllowedCombinations { static const TypeEnum::Value metatype = TypeEnum::Function; template <typename orientations, typename solutions> struct apply { typedef typename AllowedCombinations::apply<orientations, typename solutions::cdr>::result rest; typedef typename MatchingOrientations::apply<orientations, typename solutions::car>::result matching; typedef typename Append::apply<matching,rest>::result result; }; template <typename orientations> struct apply <orientations, Nil> { typedef Nil result; }; }; struct Solutions { static const TypeEnum::Value metatype = TypeEnum::Function; template <typename cubes> struct apply { typedef typename cubes::car cube; typedef typename Orientations::apply<cube>::result orientations; typedef typename Solutions::apply<typename cubes::cdr>::result sols; typedef typename AllowedCombinations::apply<orientations,sols>::result result; }; template <> struct apply <Nil> { typedef ConsCell<Nil, Nil> result; }; }; template <typename T> struct Main { static void exec() { typedef ConsCell<Cube1, ConsCell<Cube2, ConsCell<Cube3, ConsCell<Cube4, Nil> > > > cubes; typedef typename Solutions::apply<cubes>::result solutions; std::cout << solutions::to_s() << std::endl;} }; int main(int argc, char* argv[]) { Main<int>::exec(); return 0; }