Some people may find the following of (purely theoretical) interest. It

appears that the latest C++ standard defines templates in such a way

that they now form a universal computer. In principle we can now push as

much computation as we like to compile time lightening the load at run

time. Of course the example below is a little extreme but it

demonstrates the point. It's a primality tester that does all of its

work at compile time and yet makes no use of the usual C++ compile time

expression evaluator. It does so by defining integers from basic axioms

(cf. Godel, Escher, Bach by D Hofstadter). Clearly this isn't directly

useful but I found that writing it opened my eyes to some potentially

useful techniques.

//

// A C++ program to test for the primality of the number 13

//

// 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.

//

// (c) D Piponi (But copy it as much as you like if you credit me)

//

//

// 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,D::predecessor> > { };

template<class C> struct plus<C,zero>

: public C { };

//

// ...minus...

//

template<class C,class D> struct minus

: public minus<C,D::predecessor>::predecessor { };

template<class C> struct minus<C,zero>

: public C { };

//

// ...and times.

//

template<class C,class D> struct times

: public plus<C,times<C,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<C::predecessor,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,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<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,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,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<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()));

--Quote:}

Dan Piponi

[ about comp.lang.c++.moderated. First time posters: do this! ]