Subject: [Dev] Fun with templates

From: Tanner Lovelace <[email-masked]>
Date: 12 Feb 2002 16:26:20 -0500

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
-- 
Tanner Lovelace | [email-masked] | http://wtl.wayfarer.org/
--*--*--*--*--*--*--*--*--*--*--*--*--*--*--*--*--*--*--*--*--*--*--
GPG Fingerprint = 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 
 order, will lose both and deserve neither.  --  Benjamin Franklin 

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

---

From: "M. Mueller (bhu5nji)" <[email-masked]>
Date: Tue, 12 Feb 2002 22:34:36 -0500

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.

---

From: Tanner Lovelace <[email-masked]>
Date: 12 Feb 2002 23:44:09 -0500

> understand if you actually compile it?

Perhaps. :-) You never know unless you try. ;-)

Tanner

---

From: Ed Hill <[email-masked]>
Date: 13 Feb 2002 09:10:13 -0700

> First, did you know that apparently templates are turing complete!

Ok, so you can do calculations of arbitrary complexity at compile time
with templates.  Cool.  But I've seen only a few practical examples of
anything useful accomplished with these template gymnastics.  The
applications that I'm aware of are expression templates:

  http://www.acl.lanl.gov/pete/index.html
  http://www.acl.lanl.gov/pooma/
  http://www.oonumerics.org/blitz/

and I've used them a little.

So whats my point, then?  ;-)  Well, do any of you actually use ETs or
related template methods for your projects?  If so, do you have any
examples you'd be willing to share?  I'd be interested in seeing them!

Ed

-- 
Edward H. Hill III, PhD
Post-Doctoral Researcher   |  Email:       [email-masked], [email-masked]
Division of ESE            |  URL:         http://www.eh3.com
Colorado School of Mines   |  Phone:       303-273-3483
Golden, CO  80401          |  Fax:         303-273-3311
Key fingerprint = 5BDE 4DA1 66BE 4F7B BC17  3A0C 932B 7266 1E76 F123

---

From: Brent Verner <[email-masked]>
Date: Wed, 13 Feb 2002 13:32:19 -0500

[2002-02-12 16:26] Tanner Lovelace said:
| 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:

nice.

| 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 };

caluclate a value in the fibo series.

| };
| template<> struct fibo<1> { enum { val = 1}; };
| template<> struct fibo<0> { enum { val = 0}; };

initializes the fibo generation. try with the following.
  template<> struct fibo<1> { enum { val = 2}; };
  template<> struct fibo<0> { enum { val = 1}; };

| template <int i> struct Fibo_print {
|     Fibo_print<i-1> a;

template recursion, causing the the calculation above to 
generate the fibo value in the line below.

|     enum { val = fibo<i>::val };
|     void f() { a.f(); Output<i,val> d = val; }

illegal conversion/assignment generates the error message.

| };
| template<> struct Fibo_print<1> { 
|     enum { val = fibo<1>::val };
|     void f() { Output<1,val> d = val; }
| };

stops the recursion.

| void foo() {
|     Fibo_print<17> a;
|     a.f();
| }
| // -- End program here --

-- 
"Develop your talent, man, and leave the world something. Records are 
really gifts from people. To think that an artist would love you enough
to share his music with anyone is a beautiful thing."  -- Duane Allman

---

From: Tanner Lovelace <[email-masked]>
Date: 13 Feb 2002 15:43:32 -0500

Good explanation, Brent.  I think you got everything that
was there. :-)

>examples you'd be willing to share?  I'd be interested in seeing them!

The Blitz++ library is probably one of the best examples of this
I've seen.  They basically use templates and application domain
knowledge to control things like loop unrolling, etc..  I've
even seen side by side comparisons of assembly code generated
by their C++ template program and hand coded assembly and
they're about the exact same thing.

As to whether anyone around here actually uses them, my guess
would be not that much.  ETs are a very advanced C++ concept.
Not even the C++ standards committee realized what could
be done with them until someone came in with a program
that calculated primes in the error messages.  I think
it will take a while before more people start using them.
I would expect, however, that the same guys that would
think about doing hand coded assembly might be the first
ones that would try them out, though...

Tanner

On Wed, 2002-02-13 at 13:32, Brent Verner wrote:
> _______________________________________________
> Dev mailing list
> [email-masked]
> http://www.trilug.org/mailman/listinfo/dev

---

From: "M. Mueller (bhu5nji)" <[email-masked]>
Date: Wed, 13 Feb 2002 16:29:55 -0500

> Tanner

The people I know that code assembly by hand think that C is for whimps.  
Higher order C++ concepts are way too abstract for their liking.  Obviously 
the people you know are quite different.   Are ETs what they are teaching 
undergrads these days?

Here is an article that shows some performance data of hand code vs ET vs 
lamda functions.  The results are compiler dependent.   That seems 
troublesome to me, especially in the open source world where any number of 
compilers are expected to be applied to the code.  The chart does not speak 
well of G++.  

http://www.oonumerics.org/tmpw00/striegnitz.html

It has a nice bibliography at the bottom.

Mike M.