c++templatestemplate-meta-programmingturing-complete

C++ templates Turing-complete?


I'm told that the template system in C++ is Turing-complete at compile time. This is mentioned in this post and also on wikipedia.

Can you provide a nontrivial example of a computation that exploits this property?

Is this fact useful in practice?


Solution

  • Example

    #include <iostream>
    
    template <int N> struct Factorial
    {
        enum { val = Factorial<N-1>::val * N };
    };
    
    template<>
    struct Factorial<0>
    {
        enum { val = 1 };
    };
    
    int main()
    {
        // Note this value is generated at compile time.
        // Also note that most compilers have a limit on the depth of the recursion available.
        std::cout << Factorial<4>::val << "\n";
    }
    

    That was a little fun but not very practical.

    To answer the second part of the question:
    Is this fact useful in practice?

    Short Answer: Sort of.

    Long Answer: Yes, but only if you are a template daemon.

    To turn out good programming using template meta-programming that is really useful for others to use (ie a library) is really really tough (though do-able). To Help boost even has MPL aka (Meta Programming Library). But try debugging a compiler error in your template code and you will be in for a long hard ride.

    But a good practical example of it being used for something useful:

    Scott Meyers has been working extensions to the C++ language (I use the term loosely) using the templating facilities. You can read about his work here 'Enforcing Code Features'