[Dev] Fun with templates

[M. Mueller (bhu5nji)]

Ow!  It hurts my head.  I can see the math in the enum.  Is it easier to 
understand if you actually compile it?

Mike M.

On Tuesday 12 February 2002 04:26 pm, you wrote:
> All these questions about the STL had me thinking about a class
> I took a few years ago about advanced templates and the STL.
> I thought I might share a few things with the list, if anyone
> is interested.
>
> First, did you know that apparently templates are turing complete!
> I.e. you can actually calculate things using templates.  If you
> don't believe me, save the following program as fibonacci.cpp
> and run this command:
>
> g++ -c fibonacci.cpp 2>&1 | grep Output
>
> // -- Cut here ---
> template <int n, int f> struct Output {};    // creates output
>
> template <int n> struct fibo {
>     enum { val = fibo<n-1>::val + fibo<n-2>::val };
> };
> template<> struct fibo<1> { enum { val = 1}; };
> template<> struct fibo<0> { enum { val = 0}; };
>
> template <int i> struct Fibo_print {
>     Fibo_print<i-1> a;
>     enum { val = fibo<i>::val };
>     void f() { a.f(); Output<i,val> d = val; }
> };
> template<> struct Fibo_print<1> {
>     enum { val = fibo<1>::val };
>     void f() { Output<1,val> d = val; }
> };
>
> void foo() {
>     Fibo_print<17> a;
>     a.f();
> }
> // -- End program here --
>
> What you should see is the following output:
>
> non-scalar type `Output<1, 1>' requested
> non-scalar type `Output<17, 1597>' requested
> non-scalar type `Output<16, 987>' requested
> non-scalar type `Output<15, 610>' requested
> non-scalar type `Output<14, 377>' requested
> non-scalar type `Output<13, 233>' requested
> non-scalar type `Output<12, 144>' requested
> non-scalar type `Output<11, 89>' requested
> non-scalar type `Output<10, 55>' requested
> non-scalar type `Output<9, 34>' requested
> non-scalar type `Output<8, 21>' requested
> non-scalar type `Output<7, 13>' requested
> non-scalar type `Output<6, 8>' requested
> non-scalar type `Output<5, 5>' requested
> non-scalar type `Output<4, 3>' requested
> non-scalar type `Output<3, 2>' requested
> non-scalar type `Output<2, 1>' requested
>
> Ignore the first line, and look at the second number
> inside the <> of the rest.  What do we have?
> It's a fibonacci sequence.  Where did it come from?
> The error messages!?!  How did it come from the
> error messages?  The templates calculated it.
>
> I'm kind of interested if anyone can tell us why.
> If no one can, I'll post why later, but I'd like
> to hear people's guesses first.
>
> You might also want to try the following program:
>
> // -- cut here --
> template <int i, int prim> struct D {};
> template <int i> struct D<i,0> { D(int);};
>
> template <int p, int i> struct is_prime {
>     enum { prim = ((p%i) && is_prime< (i>2 ? p : 0), i-1>::prim) };
> };
> template<> struct is_prime<0,1> { enum { prim = 1}; };
> template<> struct is_prime<0,0> { enum { prim = 1}; };
>
> template <int i> struct Prime_print {
>     Prime_print<i-1> a;
>     enum { prim = is_prime<i,i-1>::prim };
>     void f() { a.f(); D<i,prim> d = prim; }
> };
> template<> struct Prime_print<2> {
>     enum { prim = 1};
>     void f() { D<2,prim> d = prim; }
> };
>
> void foo() {
>     Prime_print<17> a;
>     a.f();
> }
> // -- end program --
>
> Try saving this one as prime.cpp and compiling it with
> the following command:
>
> g++ -c prime.cpp 2>&1 | grep requested
>
> Tanner