[Dev] Fun with templates

[Tanner Lovelace]

--=-xeMzCdJ98C5OzK3eFki7
Content-Type: text/plain
Content-Transfer-Encoding: quoted-printable

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 =3D fibo<n-1>::val + fibo<n-2>::val };
};
template<> struct fibo<1> { enum { val =3D 1}; };
template<> struct fibo<0> { enum { val =3D 0}; };

template <int i> struct Fibo_print {
    Fibo_print<i-1> a;
    enum { val =3D fibo<i>::val };
    void f() { a.f(); Output<i,val> d =3D val; }
};
template<> struct Fibo_print<1> {=20
    enum { val =3D fibo<1>::val };
    void f() { Output<1,val> d =3D 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 =3D ((p%i) && is_prime< (i>2 ? p : 0), i-1>::prim) };
};
template<> struct is_prime<0,1> { enum { prim =3D 1}; };
template<> struct is_prime<0,0> { enum { prim =3D 1}; };

template <int i> struct Prime_print {
    Prime_print<i-1> a;
    enum { prim =3D is_prime<i,i-1>::prim };
    void f() { a.f(); D<i,prim> d =3D prim; }
};
template<> struct Prime_print<2> {=20
    enum { prim =3D 1};
    void f() { D<2,prim> d =3D 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
--=20
Tanner Lovelace | lovelace@wayfarer.org | http://wtl.wayfarer.org/
--*--*--*--*--*--*--*--*--*--*--*--*--*--*--*--*--*--*--*--*--*--*--
GPG Fingerprint =3D A66C 8660 924F 5F8C 71DA  BDD0 CE09 4F8E DE76 39D4
GPG Key can be found at http://wtl.wayfarer.org/lovelace.gpg.asc
--*--*--*--*--*--*--*--*--*--*--*--*--*--*--*--*--*--*--*--*--*--*--
 Those who are willing to sacrifice essential liberties for a little=20
 order, will lose both and deserve neither.  --  Benjamin Franklin=20

 History teaches that grave threats to liberty often come in times
 of urgency, when constitutional rights seem too extravagant to=20
 endure.  --  Justice Thurgood Marshall, 1989=20

--=-xeMzCdJ98C5OzK3eFki7
Content-Type: application/pgp-signature; name=signature.asc
Content-Description: This is a digitally signed message part

-----BEGIN PGP SIGNATURE-----
Version: GnuPG v1.0.6 (GNU/Linux)
Comment: For info see http://www.gnupg.org

iD8DBQA8aYh8zglPjt52OdQRAuDmAJ44bsq9qncKECDaJ4drhevgYfE6+gCggCcE
sCwBvheCRH9J+QaUFUiqIpQ=
=hQP9
-----END PGP SIGNATURE-----

--=-xeMzCdJ98C5OzK3eFki7--