## The power of C++ templates

### The power of C++ templates

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! ]

### The power of C++ templates

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

[snipped code]

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

Neat stuff. I've seen other examples in books and on the web of using the
template mechanism for generating "meta-programs", which are actually useful in
the area of automatically unrolling loops. One good example was using this
mechanism to optimize a bubble sort by breaking it into sorts of (I think)
eight adjacent elements, and implementing those sorts using straight-line code,
without actually having to write the straight-line code.

In some circumstances, however, it makes more sense to put up with some
run-time inefficiency, because the more conventional approach results in code
which is far easier for some maintenance programmer to understand down the

Also, I wouldn't go quite as far as to say that we can push as _much_
computation as we like to compile time, since the above example would have
trouble processing a number entered at run-time!

--

Ciao,
Paul

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

### The power of C++ templates

Quote:> 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
> [...]

Well, it's much more important than a pure theoretical point of view.
The fact is that it can improve numerical computations _a lot_.
There're some more examples at:
http://seurat.uwaterloo.ca/blitz/
That's known as the Blitz++ project.

Regards,
Antonio

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

### The power of C++ templates

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

A nice example!!
You will find similar techniques in publications of Todd Veldhuizen:

http://monet.uwaterloo.ca/>tveldhui/papers/Expression-Templates/exprtmpl
.html

Though, my feeling is, that C++ templates are not suitable to solve
some very simple problems, which are of more practical interest.
Actually I am quite frustrated about a simple problem, which doesn't
seems to have any solution.

See my postings

"return-type of templatized function depending on it's arguments"
1997/10/16 comp.lang.c++.moderated

"return type of function templates depending on arguments (again)"
1997/11/18 comp.lang.c++

My opinion about the power of templates is, that it is somewhat limited
due to the fact, that it is impossible (or at least extremely
inconvenient) to
define function-templates, whose return-type depends on their argument
types.
(By the way: will typeof() be part of the C++ standard?)

Harald

--
Dr. Ing. Harald Finster  ave Verkehrs- und Informationstechnik GmbH

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

### The power of C++ templates

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

[defining integers according to Peano's axioms - elided]

Interresting and fun.

But remember that on some compilers the instanciation
limit is 32 (annex 0 only recommands 17).

Quote:> //
> // 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"; }

- to show that you are a real C++ programmer, don't use stdio
- string litterals are of type const char* in C++
- use a boolean type, not integers for true and false;
you'll get more (compile-time, ie meta-)type checking
- you can also make the result is part of an error
message; saldy this is implementation dependant

Have you tried it with a C++ compiler (EDG ?) ?

--

info about C++/a propos du C++: http://www.pratique.fr/~bonnardv/

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

### The power of C++ templates

>// You'll need a good C++ compiler.

I tried to compile this under Watcom C/C++ 11.0 and it errors.  Is the
Watcom compiler not up to date enough for this example?

Marty

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

### The power of C++ templates

C++ Gems (ed: Lippman) has some examples of this.
Barton and Nackmann (sp?) have some *excellent* examples of this.  Scott
Meyers gave me some references, but I don'; have them handy.  Any good
online references?

~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~
Why is a raven like a writing desk?
Because there is a "B" in both.
-- Lewis Carroll

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

### The power of C++ templates

>> // A C++ program to test for the primality of the number 13
>[defining integers according to Peano's axioms - elided]
[...]
>But remember that on some compilers the instanciation
>limit is 32 (annex 0 only recommands 17).
[...]
>Have you tried it with a C++ compiler (EDG ?) ?

The program works with at least two different UNIX compilers *I* have
access to. The compilers are SGI MIPSpro 7.2 and Digital C++ 6.0 *Field
Test* (aka public beta).

The SGI MIPSpro compiler is indeed EDG based, I don't know anything
about how the Digital C++ compiler is implemented, except that I they
aren't on EDG's public customer list (which is supposed to be a
*partial* list of the customers who wishes to be identified).

Interrestingly, both compilers seems to have the same template
instantiation limits, and almost identical error output when it's
exceeded... The Digital C++ compiler smells EDG based...

Both handles numbers up to 28, and fails on 29. The error output does
differ a little, but only fairly minor typographical differences (530
vs 515 lines due to slightly more whitespaces in SGI's output, and
slightly different wording)

--
Torbjvrn Lindgren

If Santa ever DID deliver presents on Christmas Eve, he's dead now.

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

### The power of C++ templates

Quote:> Interrestingly, both compilers seems to have the same template
> instantiation limits, and almost identical error output when it's
> exceeded... The Digital C++ compiler smells EDG based...
> Both handles numbers up to 28, and fails on 29.

A number of (sceptical?) people have e-mailed me asking me how I managed
to compile my 'axiomatic' primality tester (now at
http://www.tanelorn.demon.co.uk/peano.htm ). I actually used KAI C++ but
any compiler that implements partial template specialisation should do.
You can get a 28 day demo license for many platforms from
http://www.kai.com. (I'm not affiliated with them in any way etc. etc.
etc.)

Incidentally KAI C++ also fails first on 29. This is not necessarily
because it shares code with any other compiler but because all of these
compilers appear to be following the ANSI standard to the letter and
giving up at any attempt at more than 32 levels of instantiation (in
ge<>). I find this surprising given that with the move from C to C++ and
its elegant container classes there is no longer need for hard coded array
sizes.

Coming soon...compile time natural language parsing using partial template
specialisation to allow programs written in English...
(Only kidding! But maybe it'll spark an idea in someone's head...)

Dan Piponi
http://www.tanelorn.demon.co.uk

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

### The power of C++ templates

>> Interrestingly, both compilers seems to have the same template
>> instantiation limits, and almost identical error output when it's
>> exceeded... The Digital C++ compiler smells EDG based...

>> Both handles numbers up to 28, and fails on 29.

>A number of (sceptical?) people have e-mailed me asking me how I managed
>to compile my 'axiomatic' primality tester (now at
>http://www.tanelorn.demon.co.uk/peano.htm ). I actually used KAI C++ but
>any compiler that implements partial template specialisation should do.
>You can get a 28 day demo license for many platforms from
>http://www.kai.com. (I'm not affiliated with them in any way etc. etc.
>etc.)

>Incidentally KAI C++ also fails first on 29. This is not necessarily
>because it shares code with any other compiler but because all of these
>compilers appear to be following the ANSI standard to the letter and
>giving up at any attempt at more than 32 levels of instantiation (in
>ge<>). I find this surprising given that with the move from C to C++ and
>its elegant container classes there is no longer need for hard coded array
>sizes.

The reason for the limit is mainly to permit the compiler to diagnose
program errors in a reasonable way.  For example, many compilers just
loop until they run out of swap space when you compile something like

template <class T> inline void f(T t) { f(&t); }
int main()
{
f(1);
}

or

template <class T> struct A {
A<T*> a;  // should have been A<T>*
};
A<int> ai;

So far, most of the cases where deeply recursive instantiations occur
have been a result of program errors.  The limit that is imposed by
the EDG front end is just an error test.  The actual value is a
configuration parameter, and could easily be made a command line
option.

I'd be interested in knowing whether people have run into this limit on
real-life programs.  If so, we'll certainly make a change to better
accommodate that kind of use.

John Spicer
Edison Design Group
--
John Spicer
Edison Design Group

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

### The power of C++ templates

> any compiler that implements partial template specialisation should

do

You can extract the same metaprogramming power from nested templates.

Jean-Louis Leroy
http://ourworld.compuserve.com/homepages/jl_leroy

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

### The power of C++ templates

KAI C++ has a command line option to increase this limit. Use the
command line option, --max_pending_instantiations <new_limit> to
increase the limit. We use the EDG front-end so we do share some code
with other compilers.

> Incidentally KAI C++ also fails first on 29. This is not necessarily
> because it shares code with any other compiler but because all of these
> compilers appear to be following the ANSI standard to the letter and
> giving up at any attempt at more than 32 levels of instantiation (in
> ge<>). I find this surprising given that with the move from C to C++ and
> its elegant container classes there is no longer need for hard coded array
> sizes.

--
#include <std/disclaimer.h>                 Kuck and Associates

http://www.kai.com/C_plus_plus/_index.html  Champaign, IL   61820
KAI C++ - Cross Platform C++ Compiler       (217) 356-2288 ext 36

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