compile time recursive objects in c++

wuischke · 2008-03-31 17:58:01

I've skimmed this paper today and that's a really cool usage of c++! (At least once you had a look at functional programming languages)

An example, copied from the paper:

template<int N> struct F { enum { val = N * F<N-1>::val }; };
template<> struct F<0> { enum { val = 1 }; };

Do you know more less known cool features of C++? (Of course I'll read and understand the paper first. )

Cerebral · 2008-03-31 18:08:20

Heh, you've just stumbled upon "Template Metaprogramming" - it's a huge field of research, from what I understand, and there's some pretty neat things out there that use it. It's basically its own language embedded within C++ templates.

Nice Fibonacci number generator you've got there.

wuischke · 2008-03-31 23:22:34

Um...that's the factorial function n! = n * (n-1) *(n-2) [...] * 2 * 1.

After getting my feet wet with functional programming languages, I'm always confused why some things have to be done so difficulty in Cpp. See the corresponding Haskell code:
fac 0 = 1
fac n = n * fac (n-1)
Of course, in cpp it's not nearly as elegant and nice as in Haskell, but it's still better (and at least to me clearer) then the standard recursive approach in cpp (int fact(int n) { if(0 == n) { return 0; } return n * fact(n-1); }), because it won't waste stack space for every function call.
The imperative approach(int temp=1;for (int i=1;i<n;++i) { temp*=i; }) is for this particular function most probably easier, but not every function can be expressed without the use of recursion.

OK, so I'll do further research on template metaprogramming, thanks for the keyword. I have some basic knowledge of templates, but I didn't know this was possible. I'm amazed.

Cerebral · 2008-03-31 23:33:00

wuischke wrote:

Um...that's the factorial function n! = n * (n-1) *(n-2) [...] * 2 * 1.

Whooooooooooops - totally misread that. DOH. Yeah, uh, Fibonacci's done in much the same way; just change val = N * F<N-1>::val for val = F<N-1>::val + F<N-2>::val (and add a second base case for n=2.)

It certainly is some amazing stuff. Another note - with TMP (template metaprogramming), all the "grunt work" is actually done AT COMPILE TIME, meaning that when you run the generated binary, runtime is blazingly fast, at the cost of making compile-time take longer. lol

Allan · 2008-04-01 00:30:50

Template metaprogramming, especially expression templates that unroll loops at compile time, is fun. It screwed with my mind the first few weeks after I discovered it!

gradgrind · 2008-04-01 08:38:20

Well, each to his own - it might be a remarkable technical or theoretical achievement, but it's not how I want to write programs! For me (at my comparatively advanced age), an improvement in programming technology makes programs clearer, more readable. It may be cool and fast, but I'll stay with python for the moment.

Arch Linux

#1 2008-03-31 17:58:01

compile time recursive objects in c++

#2 2008-03-31 18:08:20

Re: compile time recursive objects in c++

#3 2008-03-31 23:22:34

Re: compile time recursive objects in c++

#4 2008-03-31 23:33:00

Re: compile time recursive objects in c++

#5 2008-04-01 00:30:50

Re: compile time recursive objects in c++

#6 2008-04-01 08:38:20

Re: compile time recursive objects in c++

Board footer