C++ templates Turing-complete?

Question

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?

Clemens

"C++ Templates Are Turing Complete" gives an implementation of a Turing machine in templates ... which is non-trivial and proves the point in a very direct way. Of course, it also isn't very useful! – Drynurse

You can check this article from Dr. Dobbs on a FFT implementation with templates which I think not that trivial. The main point is to allow the compiler to perform a better optimization than for non template implementations as the FFT algorithm uses a lot of constants ( sin tables for instance ) part I part II – Jaynejaynell

Answer 1

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'

Macleod

C++ in the next iteration of the standard (aka C++0x) is going to introduce "concepts". Part of the point of concepts is that they will make debugging templates much easier. – Galliwasp

Dang there went concepts (poof) – Macleod

I only have a small issue with the provided example - it does not exploit the (full) Turing-completeness of C++'s template system. Factorial can be found also using Primitive recursive functions, which are not turing-complete – Pigg

@Dalibor - I think there's a case for accidental Turing completeness, where none of the problems you intend to solve require a Turing complete language, but the easiest way to solve all of them is still a Turing-complete language. The alternative would probably be lots of different specialist non-Turing-complete mechanisms. Even then, the Turing-complete language can solve many more problems you haven't anticipated, often (but also often not) reasonably easily. – Muggy

aand now we have concepts lite – Gaptoothed

Over in 2017, we're pushing concepts even further back. Here's hope for 2020. – Brahma

@MarkKegel 12 years later :D – Garage

Answer 2

I've done a turing machine in C++11. Features that C++11 adds are not significant for the turing machine indeed. It just provides for arbitrary length rule lists using variadic templates, instead of using perverse macro metaprogramming :). The names for the conditions are used to output a diagram on stdout. i've removed that code to keep the sample short.

#include <iostream>

template<bool C, typename A, typename B>
struct Conditional {
    typedef A type;
};

template<typename A, typename B>
struct Conditional<false, A, B> {
    typedef B type;
};

template<typename...>
struct ParameterPack;

template<bool C, typename = void>
struct EnableIf { };

template<typename Type>
struct EnableIf<true, Type> {
    typedef Type type;
};

template<typename T>
struct Identity {
    typedef T type;
};

// define a type list 
template<typename...>
struct TypeList;

template<typename T, typename... TT>
struct TypeList<T, TT...>  {
    typedef T type;
    typedef TypeList<TT...> tail;
};

template<>
struct TypeList<> {

};

template<typename List>
struct GetSize;

template<typename... Items>
struct GetSize<TypeList<Items...>> {
    enum { value = sizeof...(Items) };
};

template<typename... T>
struct ConcatList;

template<typename... First, typename... Second, typename... Tail>
struct ConcatList<TypeList<First...>, TypeList<Second...>, Tail...> {
    typedef typename ConcatList<TypeList<First..., Second...>, 
                                Tail...>::type type;
};

template<typename T>
struct ConcatList<T> {
    typedef T type;
};

template<typename NewItem, typename List>
struct AppendItem;

template<typename NewItem, typename...Items>
struct AppendItem<NewItem, TypeList<Items...>> {
    typedef TypeList<Items..., NewItem> type;
};

template<typename NewItem, typename List>
struct PrependItem;

template<typename NewItem, typename...Items>
struct PrependItem<NewItem, TypeList<Items...>> {
    typedef TypeList<NewItem, Items...> type;
};

template<typename List, int N, typename = void>
struct GetItem {
    static_assert(N > 0, "index cannot be negative");
    static_assert(GetSize<List>::value > 0, "index too high");
    typedef typename GetItem<typename List::tail, N-1>::type type;
};

template<typename List>
struct GetItem<List, 0> {
    static_assert(GetSize<List>::value > 0, "index too high");
    typedef typename List::type type;
};

template<typename List, template<typename, typename...> class Matcher, typename... Keys>
struct FindItem {
    static_assert(GetSize<List>::value > 0, "Could not match any item.");
    typedef typename List::type current_type;
    typedef typename Conditional<Matcher<current_type, Keys...>::value, 
                                 Identity<current_type>, // found!
                                 FindItem<typename List::tail, Matcher, Keys...>>
        ::type::type type;
};

template<typename List, int I, typename NewItem>
struct ReplaceItem {
    static_assert(I > 0, "index cannot be negative");
    static_assert(GetSize<List>::value > 0, "index too high");
    typedef typename PrependItem<typename List::type, 
                             typename ReplaceItem<typename List::tail, I-1,
                                                  NewItem>::type>
        ::type type;
};

template<typename NewItem, typename Type, typename... T>
struct ReplaceItem<TypeList<Type, T...>, 0, NewItem> {
    typedef TypeList<NewItem, T...> type;
};

enum Direction {
    Left = -1,
    Right = 1
};

template<typename OldState, typename Input, typename NewState, 
         typename Output, Direction Move>
struct Rule {
    typedef OldState old_state;
    typedef Input input;
    typedef NewState new_state;
    typedef Output output;
    static Direction const direction = Move;
};

template<typename A, typename B>
struct IsSame {
    enum { value = false }; 
};

template<typename A>
struct IsSame<A, A> {
    enum { value = true };
};

template<typename Input, typename State, int Position>
struct Configuration {
    typedef Input input;
    typedef State state;
    enum { position = Position };
};

template<int A, int B>
struct Max {
    enum { value = A > B ? A : B };
};

template<int n>
struct State {
    enum { value = n };
    static char const * name;
};

template<int n>
char const* State<n>::name = "unnamed";

struct QAccept {
    enum { value = -1 };
    static char const* name;
};

struct QReject {
    enum { value = -2 };
    static char const* name; 
};

#define DEF_STATE(ID, NAME) \
    typedef State<ID> NAME ; \
    NAME :: name = #NAME ;

template<int n>
struct Input {
    enum { value = n };
    static char const * name;

    template<int... I>
    struct Generate {
        typedef TypeList<Input<I>...> type;
    };
};

template<int n>
char const* Input<n>::name = "unnamed";

typedef Input<-1> InputBlank;

#define DEF_INPUT(ID, NAME) \
    typedef Input<ID> NAME ; \
    NAME :: name = #NAME ;

template<typename Config, typename Transitions, typename = void> 
struct Controller {
    typedef Config config;
    enum { position = config::position };

    typedef typename Conditional<
        static_cast<int>(GetSize<typename config::input>::value) 
            <= static_cast<int>(position),
        AppendItem<InputBlank, typename config::input>,
        Identity<typename config::input>>::type::type input;
    typedef typename config::state state;

    typedef typename GetItem<input, position>::type cell;

    template<typename Item, typename State, typename Cell>
    struct Matcher {
        typedef typename Item::old_state checking_state;
        typedef typename Item::input checking_input;
        enum { value = IsSame<State, checking_state>::value && 
                       IsSame<Cell,  checking_input>::value
        };
    };
    typedef typename FindItem<Transitions, Matcher, state, cell>::type rule;

    typedef typename ReplaceItem<input, position, typename rule::output>::type new_input;
    typedef typename rule::new_state new_state;
    typedef Configuration<new_input, 
                          new_state, 
                          Max<position + rule::direction, 0>::value> new_config;

    typedef Controller<new_config, Transitions> next_step;
    typedef typename next_step::end_config end_config;
    typedef typename next_step::end_input end_input;
    typedef typename next_step::end_state end_state;
    enum { end_position = next_step::position };
};

template<typename Input, typename State, int Position, typename Transitions>
struct Controller<Configuration<Input, State, Position>, Transitions, 
                  typename EnableIf<IsSame<State, QAccept>::value || 
                                    IsSame<State, QReject>::value>::type> {
    typedef Configuration<Input, State, Position> config;
    enum { position = config::position };
    typedef typename Conditional<
        static_cast<int>(GetSize<typename config::input>::value) 
            <= static_cast<int>(position),
        AppendItem<InputBlank, typename config::input>,
        Identity<typename config::input>>::type::type input;
    typedef typename config::state state;

    typedef config end_config;
    typedef input end_input;
    typedef state end_state;
    enum { end_position = position };
};

template<typename Input, typename Transitions, typename StartState>
struct TuringMachine {
    typedef Input input;
    typedef Transitions transitions;
    typedef StartState start_state;

    typedef Controller<Configuration<Input, StartState, 0>, Transitions> controller;
    typedef typename controller::end_config end_config;
    typedef typename controller::end_input end_input;
    typedef typename controller::end_state end_state;
    enum { end_position = controller::end_position };
};

#include <ostream>

template<>
char const* Input<-1>::name = "_";

char const* QAccept::name = "qaccept";
char const* QReject::name = "qreject";

int main() {
    DEF_INPUT(1, x);
    DEF_INPUT(2, x_mark);
    DEF_INPUT(3, split);

    DEF_STATE(0, start);
    DEF_STATE(1, find_blank);
    DEF_STATE(2, go_back);

    /* syntax:  State, Input, NewState, Output, Move */
    typedef TypeList< 
        Rule<start, x, find_blank, x_mark, Right>,
        Rule<find_blank, x, find_blank, x, Right>,
        Rule<find_blank, split, find_blank, split, Right>,
        Rule<find_blank, InputBlank, go_back, x, Left>,
        Rule<go_back, x, go_back, x, Left>,
        Rule<go_back, split, go_back, split, Left>,
        Rule<go_back, x_mark, start, x, Right>,
        Rule<start, split, QAccept, split, Left>> rules;

    /* syntax: initial input, rules, start state */
    typedef TuringMachine<TypeList<x, x, x, x, split>, rules, start> double_it;
    static_assert(IsSame<double_it::end_input, 
                         TypeList<x, x, x, x, split, x, x, x, x>>::value, 
                "Hmm... This is borky!");
}

Oestrin

You have way too much time on your hands. – Galliwasp

It looks like lisp except with a certin word replacing all those parentheses. – Danseur

Is the full source publicly available somewhere, for the curious reader? :) – Berretta

Just the attempt deserves way more credit :-) This code compiles (gcc-4.9) but gives no output - a little more information, like a blog post, would be great. – Penult

@OllieFord I found a version of it on a pastebin page and repasted it here: coliru.stacked-crooked.com/a/de06f2f63f905b7e . – Oestrin

Although this is amazing (+1), what will happen when the boss wants to add what he calls just a little addition? My problem with excessive and nested templates is that debugging them will be my only problem... given the time it takes for a simpleton like myself. – Scourings

Answer 3

My C++ is a bit rusty, so the may not be perfect, but it's close.

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

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

const int num = Factorial<10>::val;    // num set to 10! at compile time.

The point is to demonstrate that the compiler is completely evaluating the recursive definition until it reaches an answer.

Glendoraglendower

Answer 4

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.

Kemp

Answer 5

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.

Lunation

Hey, what three rules you refer to, I wonder, by "app, abs, var"? I presume the first two are function application and abstraction (lambda definition(?)) respectively. Is that so? And what is the third one? Something having to do with variables? – Teishateixeira

I personally think that it would be generally better to a language support Primitive Recursion in the compiler than have it be Turing Complete, since a compiler for a language that supports compile-time Primitive Recursion could guarantee that any build will either complete or fail, but one whose build process is Turing Complete cannot, except by artificially constraining the build so it isn't Turing Complete. – Robby

Answer 6

Well, here's a compile time Turing Machine implementation running a 4-state 2-symbol busy beaver

#include <iostream>

#pragma mark - Tape

constexpr int Blank = -1;

template<int... xs>
class Tape {
public:
    using type = Tape<xs...>;
    constexpr static int length = sizeof...(xs);
};

#pragma mark - Print

template<class T>
void print(T);

template<>
void print(Tape<>) {
    std::cout << std::endl;
}

template<int x, int... xs>
void print(Tape<x, xs...>) {
    if (x == Blank) {
        std::cout << "_ ";
    } else {
        std::cout << x << " ";
    }
    print(Tape<xs...>());
}

#pragma mark - Concatenate

template<class, class>
class Concatenate;

template<int... xs, int... ys>
class Concatenate<Tape<xs...>, Tape<ys...>> {
public:
    using type = Tape<xs..., ys...>;
};

#pragma mark - Invert

template<class>
class Invert;

template<>
class Invert<Tape<>> {
public:
    using type = Tape<>;
};

template<int x, int... xs>
class Invert<Tape<x, xs...>> {
public:
    using type = typename Concatenate<
        typename Invert<Tape<xs...>>::type,
        Tape<x>
    >::type;
};

#pragma mark - Read

template<int, class>
class Read;

template<int n, int x, int... xs>
class Read<n, Tape<x, xs...>> {
public:
    using type = typename std::conditional<
        (n == 0),
        std::integral_constant<int, x>,
        Read<n - 1, Tape<xs...>>
    >::type::type;
};

#pragma mark - N first and N last

template<int, class>
class NLast;

template<int n, int x, int... xs>
class NLast<n, Tape<x, xs...>> {
public:
    using type = typename std::conditional<
        (n == sizeof...(xs)),
        Tape<xs...>,
        NLast<n, Tape<xs...>>
    >::type::type;
};

template<int, class>
class NFirst;

template<int n, int... xs>
class NFirst<n, Tape<xs...>> {
public:
    using type = typename Invert<
        typename NLast<
            n, typename Invert<Tape<xs...>>::type
        >::type
    >::type;
};

#pragma mark - Write

template<int, int, class>
class Write;

template<int pos, int x, int... xs>
class Write<pos, x, Tape<xs...>> {
public:
    using type = typename Concatenate<
        typename Concatenate<
            typename NFirst<pos, Tape<xs...>>::type,
            Tape<x>
        >::type,
        typename NLast<(sizeof...(xs) - pos - 1), Tape<xs...>>::type
    >::type;
};

#pragma mark - Move

template<int, class>
class Hold;

template<int pos, int... xs>
class Hold<pos, Tape<xs...>> {
public:
    constexpr static int position = pos;
    using tape = Tape<xs...>;
};

template<int, class>
class Left;

template<int pos, int... xs>
class Left<pos, Tape<xs...>> {
public:
    constexpr static int position = typename std::conditional<
        (pos > 0),
        std::integral_constant<int, pos - 1>,
        std::integral_constant<int, 0>
    >::type();

    using tape = typename std::conditional<
        (pos > 0),
        Tape<xs...>,
        Tape<Blank, xs...>
    >::type;
};

template<int, class>
class Right;

template<int pos, int... xs>
class Right<pos, Tape<xs...>> {
public:
    constexpr static int position = pos + 1;

    using tape = typename std::conditional<
        (pos < sizeof...(xs) - 1),
        Tape<xs...>,
        Tape<xs..., Blank>
    >::type;
};

#pragma mark - States

template <int>
class Stop {
public:
    constexpr static int write = -1;
    template<int pos, class tape> using move = Hold<pos, tape>;
    template<int x> using next = Stop<x>;
};

#define ADD_STATE(_state_)      \
template<int>                   \
class _state_ { };

#define ADD_RULE(_state_, _read_, _write_, _move_, _next_)          \
template<>                                                          \
class _state_<_read_> {                                             \
public:                                                             \
    constexpr static int write = _write_;                           \
    template<int pos, class tape> using move = _move_<pos, tape>;   \
    template<int x> using next = _next_<x>;                         \
};

#pragma mark - Machine

template<template<int> class, int, class>
class Machine;

template<template<int> class State, int pos, int... xs>
class Machine<State, pos, Tape<xs...>> {
    constexpr static int symbol = typename Read<pos, Tape<xs...>>::type();
    using state = State<symbol>;

    template<int x>
    using nextState = typename State<symbol>::template next<x>;

    using modifiedTape = typename Write<pos, state::write, Tape<xs...>>::type;
    using move = typename state::template move<pos, modifiedTape>;

    constexpr static int nextPos = move::position;
    using nextTape = typename move::tape;

public:
    using step = Machine<nextState, nextPos, nextTape>;
};

#pragma mark - Run

template<class>
class Run;

template<template<int> class State, int pos, int... xs>
class Run<Machine<State, pos, Tape<xs...>>> {
    using step = typename Machine<State, pos, Tape<xs...>>::step;

public:
    using type = typename std::conditional<
        std::is_same<State<0>, Stop<0>>::value,
        Tape<xs...>,
        Run<step>
    >::type::type;
};

ADD_STATE(A);
ADD_STATE(B);
ADD_STATE(C);
ADD_STATE(D);

ADD_RULE(A, Blank, 1, Right, B);
ADD_RULE(A, 1, 1, Left, B);

ADD_RULE(B, Blank, 1, Left, A);
ADD_RULE(B, 1, Blank, Left, C);

ADD_RULE(C, Blank, 1, Right, Stop);
ADD_RULE(C, 1, 1, Left, D);

ADD_RULE(D, Blank, 1, Right, D);
ADD_RULE(D, 1, Blank, Right, A);

using tape = Tape<Blank>;
using machine = Machine<A, 0, tape>;
using result = Run<machine>::type;

int main() {
    print(result());
    return 0;
}

Ideone proof run: https://ideone.com/MvBU3Z

Explanation: http://victorkomarov.blogspot.ru/2016/03/compile-time-turing-machine.html

Github with more examples: https://github.com/fnz/CTTM

Durer

Answer 7

I think it's called template meta-programming.

Shakeup

This is the useful side of it. The downside is that I doubt most people (and certainly not me) will ever actually understand even a small percentage of what's going on in most of that stuff. It's horribly unreadable, unmaintainable stuff. – Kuebbing

That's the drawback of the whole C++ language, I think. It's becoming a monster... – Clemens

C++0x is promising to make a lot of it easier (and in my experience, the biggest issue is the compilers that don't support it fully, which C++0x won't help). Concepts in particular look like they'll clear things up, like getting rid of a lot of the SFINAE stuff, which is hard to read. – Sophistry

@MichaelBurr The C++ committee doesn't care about unreadable, unmaintainable stuff; they just love to add features. – Bestiary

Answer 8

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

Hexahedron

Answer 9

It's also fun to point out that it is a purely functional language albeit nearly impossible to debug. If you look at James post you will see what I mean by it being functional. In general it's not the most useful feature of C++. It wasn't designed to do this. It's something that was discovered.

Biedermeier

Answer 10

An example which is reasonably useful is a ratio class. There are a few variants floating around. Catching the D==0 case is fairly simple with partial overloads. The real computing is in calculating the GCD of N and D and compile time. This is essential when you're using these ratios in compile-time calculations.

Example: When you're calculating centimeters(5)*kilometers(5), at compile time you'll be multiplying ratio<1,100> and ratio<1000,1>. To prevent overflow, you want a ratio<10,1> instead of a ratio<1000,100>.

Alisonalissa

Answer 11

A Turing machine is Turing-complete, but that doesn't mean you should want to use one for production code.

Trying to do anything non-trivial with templates is in my experience messy, ugly and pointless. You have no way to "debug" your "code", compile-time error messages will be cryptic and usually in the most unlikely places, and you can achieve the same performance benefits in different ways. (Hint: 4! = 24). Worse, your code is incomprehensible to the average C++ programmer, and will be likely be non-portable due to wide ranging levels of support within current compilers.

Templates are great for generic code generation (container classes, class wrappers, mix-ins), but no - in my opinion the Turing Completeness of templates is NOT USEFUL in practice.

Acoustician

4! may be 24, but what’s MY_FAVORITE_MACRO_VALUE! ? OK, I don't actually think this is a good idea, either. – Flavourful

Answer 12

Just another example of how not to program :

template<int Depth, int A, typename B>
struct K17 {
    static const int x =
    K17 <Depth+1, 0, K17<Depth,A,B> >::x
    + K17 <Depth+1, 1, K17<Depth,A,B> >::x
    + K17 <Depth+1, 2, K17<Depth,A,B> >::x
    + K17 <Depth+1, 3, K17<Depth,A,B> >::x
    + K17 <Depth+1, 4, K17<Depth,A,B> >::x;
};
template <int A, typename B>
struct K17 <16,A,B> { static const int x = 1; };
static const int z = K17 <0,0,int>::x;
void main(void) { }

Post at C++ templates are turing complete

Pipsissewa

for the curious, the answer for x is pow(5,17-depth); – Neritic

Which is much simpler to see when you realize that template arguments A and B do nothing and delete them, and then replace all of the addition with K17<Depth+1>::x * 5. – Madson