C ++ - Vorlagen Turing-komplett?

Mir wurde gesagt, dass das Vorlagensystem in C ++ zur Kompilierungszeit Turing-vollständig ist. Dies wird in diesem Beitrag und auch auf Wikipedia erwähnt .

Können Sie ein nicht triviales Beispiel für eine Berechnung liefern, die diese Eigenschaft ausnutzt?

Ist diese Tatsache in der Praxis nützlich?

Beispiel

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

Das hat ein bisschen Spaß gemacht, war aber nicht sehr praktisch.

Um den zweiten Teil der Frage zu beantworten:
Ist diese Tatsache in der Praxis nützlich?

Kurze Antwort: Art von.

Lange Antwort: Ja, aber nur, wenn Sie ein Vorlagendämon sind.

Es ist wirklich sehr schwierig (obwohl machbar), eine gute Programmierung mit Vorlagen-Metaprogrammierung zu erzielen, die für andere sehr nützlich ist (dh eine Bibliothek). Um zu helfen, hat sogar MPL aka (Meta Programming Library) zu steigern . Versuchen Sie jedoch, einen Compilerfehler in Ihrem Vorlagencode zu debuggen, und Sie werden eine lange, harte Fahrt erleben.

Aber ein gutes praktisches Beispiel dafür, wie es für etwas Nützliches verwendet wird:

Scott Meyers hat Erweiterungen der C ++ - Sprache (ich verwende den Begriff locker) unter Verwendung der Vorlagenfunktionen verwendet. Sie können hier ‚über seine Arbeit lesen Enforcing Code Ausführung ‘

Ich habe eine Turingmaschine in C ++ 11 gemacht. Von C ++ 11 hinzugefügte Funktionen sind für die Turing-Maschine in der Tat nicht von Bedeutung. Es werden lediglich Regellisten beliebiger Länge mit variablen Vorlagen anstelle der perversen Makro-Metaprogrammierung bereitgestellt :). Die Namen für die Bedingungen werden verwendet, um ein Diagramm auf stdout auszugeben. Ich habe diesen Code entfernt, um das Beispiel kurz zu halten.

#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 ++ - Vorlagen sind vollständig " bietet eine Implementierung einer Turing-Maschine in Vorlagen ... die nicht trivial ist und den Punkt auf sehr direkte Weise beweist. Natürlich ist es auch nicht sehr nützlich!

Mein C ++ ist ein bisschen verrostet, daher ist das vielleicht nicht perfekt, aber es ist nah.

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.

Der Punkt ist zu demonstrieren, dass der Compiler die rekursive Definition vollständig auswertet, bis er eine Antwort erreicht.

Um ein nicht triviales Beispiel zu geben: http://gitorious.org/metatrace , ein C ++ - Compile Time Ray Tracer.

Beachten Sie, dass C ++ 0x eine Nicht-Template-Funktion zur Kompilierungszeit und zur vollständigen Vervollständigung in Form von Folgendem hinzufügt constexpr:

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

Sie können constexpr-expression überall dort verwenden , wo Sie Konstanten für die Kompilierungszeit benötigen, aber Sie können auch constexpr-functions mit Nicht-const-Parametern aufrufen .

Eine coole Sache ist, dass dies endlich die Kompilierzeit-Gleitkomma-Mathematik ermöglicht, obwohl der Standard ausdrücklich festlegt, dass die Kompilierzeit-Gleitkomma-Arithmetik nicht mit der Laufzeit-Gleitkomma-Arithmetik übereinstimmen muss:

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

Es ist nicht spezifiziert, ob der Wert von f () wahr oder falsch ist.

Das Buch Modernes C ++ - Design - Generisches Programmieren und Designmuster von Andrei Alexandrescu ist der beste Ort, um praktische Erfahrungen mit nützlichen und leistungsstarken generischen Programmiermustern zu sammeln.

Das faktorielle Beispiel zeigt nicht, dass Vorlagen vollständig sind, sondern zeigt, dass sie die primitive Rekursion unterstützen. Der einfachste Weg, um zu zeigen, dass Vorlagen vollständig sind, ist die Church-Turing-These, bei der entweder eine Turing-Maschine (chaotisch und etwas sinnlos) oder die drei Regeln (app, abs var) des untypisierten Lambda-Kalküls implementiert werden. Letzteres ist viel einfacher und weitaus interessanter.

Was diskutiert wird, ist eine äußerst nützliche Funktion, wenn Sie verstehen, dass C ++ - Vorlagen eine reine funktionale Programmierung zur Kompilierungszeit ermöglichen. Dieser Formalismus ist ausdrucksstark, leistungsstark und elegant, aber auch sehr kompliziert zu schreiben, wenn Sie wenig Erfahrung haben. Beachten Sie auch, wie viele Leute feststellen, dass das Erhalten von Code mit starken Vorlagen oft einen großen Aufwand erfordert: Dies ist genau der Fall bei (reinen) Funktionssprachen, die das Kompilieren erschweren, aber überraschenderweise Code liefern, der kein Debuggen erfordert.

Ich denke, es heißt Template-Meta-Programmierung .

Nun, hier ist eine Turing Machine-Implementierung zur Kompilierungszeit, auf der ein 4-Status-Biber mit 2 Symbolen ausgeführt wird

#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

Erläuterung: http://victorkomarov.blogspot.ru/2016/03/compile-time-turing-machine.html

Github mit weiteren Beispielen: https://github.com/fnz/CTTM

Sie können diesen Artikel von Dr. Dobbs über eine FFT-Implementierung mit Vorlagen lesen, die ich nicht so trivial finde. Der Hauptpunkt besteht darin, dem Compiler eine bessere Optimierung als bei Nicht-Template-Implementierungen zu ermöglichen, da der FFT-Algorithmus viele Konstanten verwendet (z. B. Sin-Tabellen).

Teil I.

Teil II

Es macht auch Spaß darauf hinzuweisen, dass es sich um eine rein funktionale Sprache handelt, die jedoch kaum zu debuggen ist. Wenn Sie sich James Post ansehen, werden Sie sehen, was ich damit meine, dass er funktionsfähig ist. Im Allgemeinen ist es nicht die nützlichste Funktion von C ++. Es war nicht dafür ausgelegt. Es ist etwas, das entdeckt wurde.

Dies kann nützlich sein, wenn Sie zumindest theoretisch Konstanten zur Kompilierungszeit berechnen möchten. Schauen Sie sich die Metaprogrammierung von Vorlagen an .

Ein Beispiel, das einigermaßen nützlich ist, ist eine Verhältnisklasse. Es gibt einige Varianten. Das Erfassen des D == 0-Falls ist bei teilweisen Überlastungen ziemlich einfach. Die eigentliche Berechnung besteht in der Berechnung der GCD von N und D und der Kompilierungszeit. Dies ist wichtig, wenn Sie diese Verhältnisse für Berechnungen zur Kompilierungszeit verwenden.

Beispiel: Wenn Sie Zentimeter (5) * Kilometer (5) berechnen, multiplizieren Sie zur Kompilierungszeit das Verhältnis <1.100> und das Verhältnis <1000,1>. Um einen Überlauf zu vermeiden, möchten Sie ein Verhältnis <10,1> anstelle eines Verhältnisses <1000,100>.

Eine Turing-Maschine ist Turing-vollständig, aber das bedeutet nicht, dass Sie eine für den Produktionscode verwenden möchten.

Der Versuch, mit Vorlagen etwas nicht Triviales zu tun, ist meiner Erfahrung nach chaotisch, hässlich und sinnlos. Sie haben keine Möglichkeit, Ihren "Code" zu "debuggen". Fehlermeldungen zur Kompilierungszeit sind kryptisch und befinden sich normalerweise an den unwahrscheinlichsten Stellen. Sie können dieselben Leistungsvorteile auf unterschiedliche Weise erzielen. (Hinweis: 4! = 24). Schlimmer noch, Ihr Code ist für den durchschnittlichen C ++ - Programmierer unverständlich und wird wahrscheinlich nicht portierbar sein, da die aktuellen Compiler ein breites Maß an Unterstützung bieten.

Vorlagen eignen sich hervorragend für die generische Codegenerierung (Containerklassen, Klassenumbrüche, Mix-Ins), aber nein - meiner Meinung nach ist die Vollständigkeit von Vorlagen in der Praxis NICHT NÜTZLICH .

Nur ein weiteres Beispiel dafür, wie man nicht programmiert:

Vorlage <int Tiefe, int A, Typname B>
Struktur K17 {
    statische const int x =
    K17 <Tiefe + 1, 0, K17 <Tiefe, A, B >> :: x
    + K17 <Tiefe + 1, 1, K17 <Tiefe, A, B >> :: x
    + K17 <Tiefe + 1, 2, K17 <Tiefe, A, B >> :: x
    + K17 <Tiefe + 1, 3, K17 <Tiefe, A, B >> :: x
    + K17 <Tiefe + 1, 4, K17 <Tiefe, A, B >> :: x;
};
Vorlage <int A, Typname B>
Struktur K17 <16, A, B> {statische Konstante int x = 1; };
statische Konstante int z = K17 <0,0, int> :: x;
void main (void) {}

Post at C ++ - Vorlagen sind vollständig