C++ templates Turing-complete?

To give a non-trivial example: https://github.com/phresnel/metatrace , a C++ compile time ray tracer.

Note that C++0x will add a non-template, compile-time, turing-complete facility in form of constexpr:

constexpr unsigned int fac (unsigned int u) {
        return (u<=1) ? (1) : (u*fac(u-1));
}

You can use constexpr-expression everywhere where you need compile time constants, but you can also call constexpr-functions with non-const parameters.

One cool thing is that this will finally enable compile time floating point math, though the standard explicitly states that compile time floating point arithmetics do not have to match runtime floating point arithmetics:

bool f(){
    char array[1+int(1+0.2-0.1-0.1)]; //Must be evaluated during translation
    int  size=1+int(1+0.2-0.1-0.1); //May be evaluated at runtime
    return sizeof(array)==size;
}

It is unspecified whether the value of f() will be true or false.

The factorial example actually does not show that templates are Turing complete, as much as it shows that they support Primitive Recursion. The easiest way to show that templates are turing complete is by the Church-Turing thesis, that is by implementing either a Turing machine (messy and a bit pointless) or the three rules (app, abs var) of the untyped lambda calculus. The latter is much simpler and far more interesting.

What is being discussed is an extremely useful feature when you understand that C++ templates allow pure functional programming at compile time, a formalism that is expressive, powerful and elegant but also very complicated to write if you have little experience. Also notice how many people find that just getting heavily templatized code can often require a big effort: this is exactly the case with (pure) functional languages, which make compiling harder but surprisingly yield code that does not require debugging.

It may be useful if you want to compute constants at compile time, at least in theory. Check out template metaprogramming.