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 takes 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.
We don't have to utilize 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 use templates, template specialization, struct,
typename and typedef.
And, it's barely 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: template struct App {} ; // References: template struct Ref {} ; // Conditionals: template struct If {} ; // Literals: template struct 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 metafunction EnvLookup accepts a name and an environment
to 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, we typedef its
return value to the field result.
Accessing the field result forces the expansion
and 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
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's another 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 this article, I'm providing a challenge problem: implementing addition as a template meta-program.
The stub code is available.
You need to create (two) specializations of the Add struct to
make it work.