Almost Solving Instant Insanity with C++ templates

In the latest edition of the Monad Reader, Conrad Parker wrote a solution to Instant Insanity using only Haskell's type system. While reading, I was immediately struck by how closely Haskell's parameterized types correspond to C++ templates. To see how far I could push this connection, I endeavoured to translate Conrad's code into a C++ metaprogram. I should admit up front that my translated code doesn't quite perform its intended task. The solution in the Monad Reader involves an exhaustive search of compatible cube orientations, which pushes Visual C++ past its dainty limits. However, the code does appear to be correct (it works for 1-3 cubes), and the process of writing it taught me a great deal about type-level programming (both in C++ and Haskell).

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:

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.

Converting Haskell into C++

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

C++ 's advantages

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++:

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.

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 *).

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.

Haskell's advantages

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:

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.