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

For the Halloween lecture in myadvanced compilers class, Iscare students with C++ template meta-programming.

To prove that C++ templates are Turing-complete, we constructed ahigher-order functional programming language out of them.

The language supports higher-order functions, literal values (rawtypes), natural numbers (as types), booleans and conditionals.

Specifically, we made anSICP-likeeval/apply interpeter out of templates.

This embedded language shows that any computable function can be computedat compile-time in C++.

How: Template specialization

The Turing-completeness of templates in C++ is an accident arisingfrom the collision of two features: templates and template specialization.

These two features allow C++ templates to act like an untypedterm-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 thedefinition of a template for some combination of template parameters.

For example, we could override the definition ofListNodewhen parameterized with the typeunsigned 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 thatyou could haveVector<bool> implemented as a truebit-vector, instead of wasting one word per element.

Factorial example

The canonical example of compile-time computation is factorial intemplates:

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 toFactorial<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 constantvalue.

With this template in place, code could refer toFactorial<4>::value and get24 computed atcompile-time.

Encoding and pattern-matching data structures

In C++ template meta-programming, types are used to encodestructured data, and specializations are used to destructure that datawith pattern-matching.

For example, we could encode the natural numbers using aZero type, and aSucc<Number> templatetype:

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 asSucc<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: 0cout << MatchOne<Succ<Zero> >::value << endl; // Prints: 1cout << MatchOne<Succ<Succ<Zero> > >::value << endl; // Prints: 0

Proving Turing-completeness

To prove Turing-completeness, we have to show that C++ templatescan be implemented by a Turing machine (gcc takes care of this), andthat C++ templates can implement a Turing machine.

It's well known that the λ-calculus (which actually predates theTuring 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 valuestoo.

One could actually do some programming with this language.

The commented code below explains how this is done.

We don't have to utilize much of the C++ language topull this off.

We don't need templates that generate templates, embedded templates oreven templates that accept templates.

We use templates, template specialization,struct,typename andtypedef.

And, it'sbarely 200 lines of code with comments included.

An abstract syntax in templates

We'll use integers for variables names (although we can easily provide aliases for them).

We need to use instantiated template types to represent program terms:

// Anonymous functions:templatestruct Lambda {} ;// Function call/Application:templatestruct App {} ; // References:templatestruct Ref {} ;// Conditionals:templatestruct If {} ;// Literals:templatestruct Lit {} ;

Environments as templates

Environments, which map names to values,are type-level linked lists:

// EmptyEnv is the empty environment:struct EmptyEnv ;// Bindings<Name,Value,Env> is a type than encodes the environment Env// extended with a binding for Name => Value:template <int Name, typename Value, typename Env>struct Binding {} ;

The template metafunctionEnvLookup accepts a name and an environmentto yield a value:

// EnvLookup<Name,Env> :: result looks up the value of Name in Env:template <int Name, typename Env>struct EnvLookup {} ;template <int Name>struct EnvLookup <Name,EmptyEnv> {} ; // Name not found.template <int Name, typename Value, typename Env>struct EnvLookup <Name, Binding<Name,Value,Env> > {  Value typedef result ;} ;template <int Name, int Name2, typename Value2, typename Env>struct EnvLookup <Name, Binding<Name2,Value2,Env> >{  typename EnvLookup<Name,Env> :: result typedef result ;} ;

EnvLookup illustrates an important convention: to define a type-level meta-function, wetypedef itsreturn value to the fieldresult.

Accessing the fieldresult forces the expansionand yields the return value.

Type-level values

Of course, run-time "values" in a template meta-program are actually types:

// Closures:templatestruct Closure {} ;// Booleans:struct True {} ;struct False {} ;

Eval and apply as meta-functions

Finally, we define eval and apply as type-level meta-functions:

// Eval<Exp,Env> :: result is the value of expression Exp in// environment Env.template <typename Exp, typename Env>struct Eval {} ;// Apply<Proc,Value> :: result is the value of applying Proc to Value.template <typename Proc, typename Value>struct Apply {} ;// Literals evaluate to themselves:template <typename T, typename Env>struct Eval <Lit<T>, Env>{  T typedef result ;} ;// Variable references are looked up in the current environment:template <int Name, typename Env>struct Eval <Ref<Name>, Env>{  typename EnvLookup<Name, Env> :: result typedef result ;} ;// Lambda terms evaluate into closures:template <int Name, typename Body, typename Env>struct Eval <Lambda<Name,Body>, Env>{  Closure<Lambda<Name, Body>, Env> typedef result ;} ;// Applications apply the value of the function expression to the// value of the argument expression:template <typename Fun, typename Arg, typename Env>struct Eval<App<Fun, Arg> , Env> {  typename Apply<typename Eval<Fun,Env> :: result ,                 typename Eval<Arg,Env> :: result > :: result            typedef result ;} ;// Branch true:template <typename Then, typename Else, typename Env>struct Eval<If<True,Then,Else>,Env> {  typename Eval<Then,Env> :: result typedef result ;} ;// Branch false:template <typename Then, typename Else, typename Env>struct Eval<If<False,Then,Else>,Env> {  typename Eval<Else,Env> :: result typedef result ;} ;// Evaluate the condition:template <typename Cond, typename Then, typename Else, typename Env>struct Eval<If<Cond,Then,Else>,Env> {  typename Eval<If<typename Eval<Cond,Env> :: result,                    Then,                   Else>,                Env> :: result            typedef result ;} ;// Transition to the body of the lambda term inside the closure:template <int Name, typename Body, typename Env, typename Value>struct Apply<Closure<Lambda<Name,Body>, Env>, Value> {  typename Eval<Body, Binding<Name,Value,Env> > :: result            typedef result ;} ;

All together

Now, we can construct and execute simple template meta-programs:

  // Testing ((lambda (x) x) 2):  enum { X } ;    int x = Eval<App<Lambda<X,Ref<X> >,Lit<Succ<Succ<Zero>     > > >,EmptyEnv> :: result :: value ;  assert(x == 2) ;  // Testing (if #f 0 1):  int y = Eval<If<Lit<False>,Lit<Zero>,Lit<Succ<Zero>     > >,EmptyEnv> :: result :: value ;    assert(y == 1) ;

Code

The code is available.

Resources and related pages

• C++ Templates: The Complete Guide is the definitive guide to C++ templates and template meta-programming:
  
  It's written by two C++ standards committee members. The afternotes in each chapter which mention the proceedings of the standards committee are fascinating. In case you're wondering, the Turing-completeness of templates was first an accident, and then a feature.
• There'sanother implementation of a lambda-calculus-based language for C++ templates out there.
• Structure and Interpretation of Computer Programs, the classic MIT textbook, covers eval/apply interpreters in Chapter 4:
  

Exercise

If you would like to practice some of the principles on display in thisarticle, I'm providing a challenge problem: implementing addition as a templatemeta-program.

Thestub code is available.

You need to create (two) specializations of theAdd struct tomake it work.