C++ Templates and Turing Completeness

Sometimes C++ programmers can be quite snobby. They can look down on C programmers and when C programmers eventually do learn C++ they make quips like "I bet you just treat C++ like C with fancy structs". But the fact is that for most people C++ is just C with fancy structs. The point is that up until templates were introduced to C++ it was almost trivial to convert any C++ program to C. If that is the case then why actually bother coding in C++.

But then templates came along. Many C++ programmers rejected them as complicated or confusing. Even today, if you browse the books on C++ in your local bookstore, you'll find dozens of chapters on fancy structs and maybe a short section in the miscellaneous chapter at the end on templates. But this is a pretty egregious sin. With the addition of templates the compiler itself becomes Turing complete. While the C preprocessor can be proved not to be Turing complete the C++ compiler can actually perform important work at compile time lightening the load at runtime. This is an immense difference and today, in 2003, programmers are still trying to work out the implications.

Using templates you can now implement a multiplicity of constructs that are impossible in C without major preprocessing of the code. You can make generic code that's independent of the underlying datatype. You can make code fragments that are elegantly linked together into complete algorithms at compile time. You can make closures, like in functional languages. You can almost write your own compiler that builds efficient code the way you want.

If you're not using templates you're just a C programmer using fancy structs.

Anyway, in 1997 I posted the following code to USENET that demonstrates what you can do at compile time.


//
// A C++ program to test for the primality of the number 13
//
// I waive all copyright to this code.  Dan Piponi.
// http://www.sigfpe.com
// peano@sigfpe.com
//
// It has the curious property that it does no arithmetic
// but uses only the template mechanism and class derivation
// to achieve its result. It starts at the most basic axioms
// of arithmetic starting with the definition of zero and
// its successors...
//
// You'll need a good C++ compiler. 
// egcs-2.91.66 works if you stretch the template
// recursion depth a bit by using:
//
// g++ -ftemplate-depth-128 -o peano peano.C
//

//
// First a little trick to find the base class of our
// classes because the template mechanism requires
// exact matches.
//
// Two values are considered equivalent if they have
// the same baseclass. For example 1+1 isn't
// identical to 2 but 1+1 *is* derived from 2.
//
template<class V> struct Value { typedef V value; };

//
// Define zero
//
struct zero
	   : public Value<zero> { };

//
// Define the successor of an integer
//
template<class C> struct S
	   : public Value<S<C> > { typedef C predecessor; };

//
// Now we have the integers. So introduce some convenience
// types.
//
typedef S<zero> one;
typedef S<one> two;
typedef S<two> three;
typedef S<three> four;
typedef S<four> five;
typedef S<five> six;
typedef S<six> seven;
typedef S<seven> eight;
typedef S<eight> nine;
typedef S<nine> ten;

//
// Define plus,...
//
template<class C,class D> struct plus
	   : public S<plus<C,typename D::predecessor> > { };

template<class C> struct plus<C,zero>
	   : public C { };

//
// ...minus...
//
template<class C,class D> struct minus
	   : public minus<C,typename D::predecessor>::predecessor { };

template<class C> struct minus<C,zero>
	   : public C { };

//
// ...and times.
//
template<class C,class D> struct times
	   : public plus<C,typename times<C,typename D::predecessor>::value> { };

template<class C> struct times<C,zero>
	   : public zero { };

//
// Define the usual ordering on the integers.
//
template<class C,class D> struct ge
	   : public ge<typename C::predecessor,typename D::predecessor> { };

template<class C> struct ge<C,zero>
	   : public one { };

template<class C> struct ge<zero,C>
	   : public zero { };

template<> struct ge<zero,zero>
	   : public one { };

//
// Divisibility testing
//
template<class C,class D,class E = S<S<zero> > > struct Divisible { };

template<class C,class D> struct Divisible<C,D,S<S<zero> > >
	   : public Divisible<C,D,typename ge<C,D>::value> { };

//
// The case C<D:
// In this case D divides C iff C is zero.
//
template<class C,class D> struct Divisible<C,D,zero>
	   : public zero { };

template<class C> struct Divisible<zero,C,zero>
	   : public one { };

//
// The case C>=D:
// D divides C iff D divides C-D.
//
template<class C,class D> struct Divisible<C,D,S<zero> >
	   : public Divisible<typename minus<C,D>::value,D> { };

//
// Primality testing
//
template<class C,class D = two,class S = zero,class E = zero,class F = zero> struct Prime { };

//
// We use recursion to set up a loop from 2 to one less
// than the integer we are testing. Essentially this is a state machine
// using template parameters to record the current state.
//

// Are we at the end of the recursion?
//
template<class C,class D> struct Prime<C,D,zero,zero,zero>
	   : public Prime<C,D,one,zero,typename ge<D,C>::value> { };

//
// Test potential factor D, trying successor on failure.
//
template<class C,class D> struct Prime<C,D,one,zero,zero>
	   : public Prime<C,S<D>,zero,typename Divisible<C,D>::value,zero> { };

//
// Found a factor.
//
template<class C,class D> struct Prime<C,D,zero,one,zero>
	   : public zero { };

//
// Reached the end of the loop without finding divisor.
//
template<class C,class D> struct Prime<C,D,one,zero,one>
	   : public one { };

//
// Convenience method for humans allowing input of
// numbers in decimal format.
//
template<class C,class D> struct Decimal
	   : public plus<typename times<ten,C>::value,D> { };

//
// Unfortunately the I/O interface spoils the purity of it all.
//
#include <stdio.h>

template<class C> char *output(C);

template<> char *output(zero) { return "No"; }

template<> char *output(one) { return "Yes"; }


main() {
   //
   // Is 13 prime?
   //
   puts(output(Prime<Decimal<one,three>::value>::value()));
}

Contact

Feel free to email me (Dan Piponi) at stirfry (at) sigfpe.com.
Back to Robotics.