C++ templates: Creating a compile-time higher-order meta-programming language

For the Halloween lecture in my advanced compilers class, I decided to scare students with C++ template meta-programming. To prove that C++ templates are Turing-complete, we constructed a higher-order functional programming language out of them. The language supports higher-order functions, literal values (raw types), natural numbers (as types), booleans and conditionals. We made an SICP-like eval/apply interpeter for this language out of templates. This embedded language shows that any computable function can computed at compile-time in C++.

How: Template specialization

The Turing-completeness of templates in C++ is an accident arising from the collision of two features: templates and template specialization. These two features allow C++ templates to act like an untyped term-rewriting language. A template declares a data type parameterized by some constants and by some types; for example:

template <typename A>
struct ListNode
{
  A data ;
  ListNode<A>* next ;
} ; 

A template specialization allows the programmer to override the definition of a template for some combination of template parameters. For example, we could override the definition of ListNode when parameterized with the type unsigned int:

template <>
struct ListNode<unsigned int>
{
  /* Don't let them use unsigned ints. */
  int data ;
  ListNode<int>* next ;
} ;

The standard example of why you would want to specialize is so that you could have Vector<bool> implemented as a true bit-vector, instead of wasting one word per element.

Factorial example

The canonical example of compile-time computation is factorial in templates:

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

Without the template specialization, a reference to Factorial<4>::value would re-write itself forever, eventually causing the template equivalent of a stack overflow. Note the use of enumerations to force compile-time evaluation of the member constant value. With this template in place, code could refer to Factorial<4>::value and get 24 computed at compile-time.

Encoding and pattern-matching data structures

In C++ template meta-programming, types are used to encode structured data, and specializations are used to destructure that data with pattern-matching. For example, we could encode the natural numbers using a Zero type, and a Succ<Number> template type:

struct Zero 
{
  enum { value = 0 } ;
} ;

template <typename N>
struct Succ 
{
  enum { value = N::value + 1 } ;
} ;

We could then make a template that matches the value 1 encoded as Succ<Zero>:

template <typename N>
struct MatchOne
{
  enum { value = 0 } ;
} ;


template <>
struct MatchOne<Succ<Zero> >
{
  enum { value = 1 } ;
} ;

so that the following code works:

cout << MatchOne<Zero >::value << endl; 
// Prints: 0

cout << MatchOne<Succ<Zero> >::value << endl; 
// Prints: 1

cout << MatchOne<Succ<Succ<Zero> > >::value << endl; 
// Prints: 0

Proving Turing-completeness

To prove Turing-completeness, we have to show that C++ templates can be implemented by a Turing machine (gcc take care of this), and that C++ templates can implement a Turing machine. It's well known that the λ-calculus (which actually predates the Turing machine) is Turing-complete, so just have to show that C++ templates can implement the λ-calculus. In fact, in an effort to make this a little more than a toy exercise, the evaluator can handle conditionals, booleans and literal values too. One could actually do some programming with this language.

The commented code below explains how this is done. Remarkably, we don't have to utilize very much of the C++ language to pull this off. We don't need templates that generate templates, embedded templates or even templates that accept templates. We just use templates, template specialization, struct, typename and typedef for the necessary parts. And, it's barely 200 lines of code with comments included.