Szablony C ++ Turing-complete?

Powiedziano mi, że system szablonów w C ++ jest kompletny Turing w czasie kompilacji. Jest to wspomniane w tym poście, a także na Wikipedii .

Czy możesz podać nietrywialny przykład obliczenia wykorzystującego tę właściwość?

Czy ten fakt jest przydatny w praktyce?

Przykład

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

To było trochę zabawne, ale niezbyt praktyczne.

Odpowiadając na drugą część pytania:
czy ten fakt jest przydatny w praktyce?

Krótka odpowiedź: w pewnym sensie.

Długa odpowiedź: tak, ale tylko jeśli jesteś demonem szablonów.

Okazanie dobrego programowania przy użyciu metaprogramowania szablonowego, które jest naprawdę przydatne dla innych (np. Biblioteki), jest naprawdę trudne (choć wykonalne). Aby pomóc zwiększyć, ma nawet MPL aka (biblioteka programowania meta). Ale spróbuj zdebugować błąd kompilatora w kodzie szablonu, a czeka Cię długa, ciężka jazda.

Ale dobry praktyczny przykład wykorzystania go do czegoś pożytecznego:

Scott Meyers pracował nad rozszerzeniami języka C ++ (używam tego terminu luźno) przy użyciu narzędzi do tworzenia szablonów. Możesz przeczytać o jego pracy tutaj „ Egzekwowanie funkcji kodu ”

Zrobiłem maszynę Turinga w C ++ 11. Funkcje, które dodaje C ++ 11, nie są faktycznie istotne dla maszyny Turinga. Po prostu zapewnia listy reguł o dowolnej długości przy użyciu szablonów wariadycznych, zamiast używania przewrotnego metaprogramowania makr :). Nazwy warunków są używane do wyświetlania diagramu na standardowe wyjście. Usunąłem ten kod, aby próbka była krótka.

#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!");
}

„ C ++ Templates Are Turing Complete ” to implementacja maszyny Turinga w szablonach ... co jest nietrywialne i udowadnia to w bardzo bezpośredni sposób. Oczywiście nie jest to również zbyt przydatne!

Mój C ++ jest trochę zardzewiały, więc może nie być idealny, ale jest blisko.

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.

Chodzi o to, aby wykazać, że kompilator całkowicie ocenia definicję rekurencyjną, dopóki nie osiągnie odpowiedzi.

Aby dać nietrywialny przykład: http://gitorious.org/metatrace , kompilator C ++ ray tracer czasu.

Zauważ, że C ++ 0x doda nie-szablonowy, kompletny w czasie kompilacji, kompletny obiekt w postaci constexpr:

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

Możesz użyć constexpr-expression wszędzie tam, gdzie potrzebujesz stałych czasu kompilacji, ale możesz również wywołać constexpr-functions z parametrami innymi niż const.

Jedną fajną rzeczą jest to, że w końcu umożliwi to obliczenie zmiennoprzecinkowej kompilacji czasu, chociaż standard wyraźnie stwierdza, że ​​arytmetyka zmiennoprzecinkowa kompilacji czasu nie musi pasować do arytmetyki zmiennoprzecinkowej czasu działania:

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

Nie jest określone, czy wartość f () będzie prawdą czy fałszem.

Książka Modern C ++ Design - Generic Programming and Design Pattern autorstwa Andrei Alexandrescu to najlepsze miejsce na zdobycie praktycznych doświadczeń z użytecznymi i potężnymi wzorcami programowania ogólnego.

Przykład silni w rzeczywistości nie pokazuje, że szablony są kompletne w Turingu, ale pokazuje, że obsługują rekursję pierwotną. Najłatwiejszym sposobem wykazania, że ​​szablony są kompletne, jest teza Church-Turinga, czyli zaimplementowanie maszyny Turinga (niechlujnej i trochę bezcelowej) lub trzech reguł (app, abs var) nietypowego rachunku lambda. To drugie jest dużo prostsze i dużo ciekawsze.

To, co jest omawiane, jest niezwykle przydatną funkcją, gdy zrozumiesz, że szablony C ++ umożliwiają czyste programowanie funkcjonalne w czasie kompilacji, formalizm, który jest ekspresyjny, potężny i elegancki, ale także bardzo skomplikowany do napisania, jeśli masz niewielkie doświadczenie. Zwróć także uwagę, jak wiele osób uważa, że ​​samo uzyskanie kodu opartego na szablonach często wymaga dużego wysiłku: tak właśnie jest w przypadku (czystych) języków funkcjonalnych, które sprawiają, że kompilowanie jest trudniejsze, ale zaskakująco daje kod, który nie wymaga debugowania.

Myślę, że nazywa się to metaprogramowaniem szablonów .

Cóż, oto implementacja Turing Machine w czasie kompilacji, działająca na 4-stanowym, zajętym bobrze z 2 symbolami

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

Testowy test Ideone: https://ideone.com/MvBU3Z

Wyjaśnienie: http://victorkomarov.blogspot.ru/2016/03/compile-time-turing-machine.html

Github z dodatkowymi przykładami: https://github.com/fnz/CTTM

Możesz sprawdzić ten artykuł dr. Dobbsa na temat implementacji FFT z szablonami, które nie są moim zdaniem takie trywialne. Głównym celem jest umożliwienie kompilatorowi wykonania lepszej optymalizacji niż w przypadku implementacji innych niż szablony, ponieważ algorytm FFT wykorzystuje wiele stałych (na przykład tabele sin)

część I

część druga

Fajnie jest również wskazać, że jest to język czysto funkcjonalny, chociaż prawie niemożliwy do debugowania. Jeśli spojrzysz na post Jamesa , zobaczysz, co mam na myśli, mówiąc, że jest funkcjonalny. Ogólnie nie jest to najbardziej użyteczna funkcja C ++. Nie został do tego przeznaczony. To coś, co zostało odkryte.

Może to być przydatne, jeśli chcesz obliczyć stałe w czasie kompilacji, przynajmniej w teorii. Sprawdź metaprogramowanie szablonów .

Przykładem, który jest dość użyteczny, jest klasa współczynników. Istnieje kilka wariantów. Wyłapywanie przypadku D == 0 jest dość proste w przypadku częściowych przeciążeń. Prawdziwe obliczenie polega na obliczaniu GCD N i D oraz czasu kompilacji. Jest to niezbędne, gdy używasz tych współczynników w obliczeniach w czasie kompilacji.

Przykład: podczas obliczania centymetrów (5) * kilometrów (5) w czasie kompilacji pomnożymy współczynnik <1,100> i współczynnik <1000,1>. Aby zapobiec przepełnieniu, potrzebujesz współczynnika <10,1> zamiast współczynnika <1000,100>.

Maszyna Turinga jest Turing-complete, ale to nie znaczy, że chcesz użyć jednego kodu produkcyjnego.

Z mojego doświadczenia wynika, że ​​próba zrobienia czegoś nietrywialnego za pomocą szablonów jest niechlujna, brzydka i bezcelowa. Nie masz możliwości "debugowania" swojego "kodu", komunikaty o błędach kompilacji będą niejasne i zwykle w najbardziej nieprawdopodobnych miejscach, a te same korzyści w zakresie wydajności można osiągnąć na różne sposoby. (Podpowiedź: 4! = 24). Co gorsza, Twój kod jest niezrozumiały dla przeciętnego programisty C ++ i prawdopodobnie będzie nieprzenośny ze względu na szeroki zakres wsparcia w obecnych kompilatorach.

Szablony świetnie nadają się do generowania kodu ogólnego (klasy kontenerów, opakowania klas, mix-iny), ale nie - moim zdaniem kompletność szablonów Turinga NIE JEST PRZYDATNA w praktyce.

Kolejny przykład, jak nie programować:

szablon <int Głębokość, int A, nazwa typu B>
struct K17 {
    static const int x =
    K17 <Głębokość + 1, 0, K17 <Głębokość, A, B>> :: x
    + K17 <Głębokość + 1, 1, K17 <Głębokość, A, B>> :: x
    + K17 <Głębokość + 1, 2, K17 <Głębokość, A, B>> :: x
    + K17 <Głębokość + 1, 3, K17 <Głębokość, A, B>> :: x
    + K17 <Głębokość + 1, 4, K17 <Głębokość, A, B>> :: x;
};
szablon <int A, nazwa typu B>
struct K17 <16, A, B> {static const int x = 1; };
stała statyczna int z = K17 <0,0, int> :: x;
void main (void) {}

Publikowanie szablonów w C ++ jest w toku