Modèles C ++ Turing-complete?

On me dit que le système de modèles de C ++ est Turing-complet au moment de la compilation. Ceci est mentionné dans ce post et aussi sur wikipedia .

Pouvez-vous donner un exemple non sortingvial d’un calcul qui exploite cette propriété?

Est-ce utile dans la pratique?

Exemple

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

C'était un peu amusant mais pas très pratique.

Pour répondre à la deuxième partie de la question:
Est-ce utile dans la pratique?

Réponse courte: Sorte de.

Réponse longue: Oui, mais seulement si vous êtes un démon modèle.

Faire de la bonne programmation en utilisant la méta-programmation de modèles qui est vraiment utile pour les autres utilisateurs (c.-à-d. Une bibliothèque) est vraiment très difficile (bien que faisable). Pour aider à booster, on a même MPL (Meta Programming Library). Mais essayez de déboguer une erreur de compilateur dans votre code de modèle et vous ferez un long trajet difficile.

Mais un bon exemple pratique de son utilisation pour quelque chose d'utile:

Scott Meyers a travaillé sur les extensions du langage C ++ (j'utilise le terme librement) en utilisant les fonctions de modélisation. Vous pouvez lire sur son travail ici " Application des fonctionnalités du code "

J’ai fait une machine à turing en C ++ 11. Les fonctionnalités ajoutées par C ++ 11 ne sont pas significatives pour la machine de turing. Il ne fournit que des listes de règles de longueur arbitraires utilisant des modèles variadiques, au lieu d’utiliser des métaprogrammations de macros perverses :). Les noms des conditions sont utilisés pour générer un diagramme sur stdout. J’ai supprimé ce code pour que l’échantillon rest court.

 #include  template struct Conditional { typedef A type; }; template struct Conditional { typedef B type; }; template struct ParameterPack; template struct EnableIf { }; template struct EnableIf { typedef Type type; }; template struct Identity { typedef T type; }; // define a type list template struct TypeList; template struct TypeList { typedef T type; typedef TypeList tail; }; template<> struct TypeList<> { }; template struct GetSize; template struct GetSize> { enum { value = sizeof...(Items) }; }; template struct ConcatList; template struct ConcatList, TypeList, Tail...> { typedef typename ConcatList, Tail...>::type type; }; template struct ConcatList { typedef T type; }; template struct AppendItem; template struct AppendItem> { typedef TypeList type; }; template struct PrependItem; template struct PrependItem> { typedef TypeList type; }; template struct GetItem { static_assert(N > 0, "index cannot be negative"); static_assert(GetSize::value > 0, "index too high"); typedef typename GetItem::type type; }; template struct GetItem { static_assert(GetSize::value > 0, "index too high"); typedef typename List::type type; }; template class Matcher, typename... Keys> struct FindItem { static_assert(GetSize::value > 0, "Could not match any item."); typedef typename List::type current_type; typedef typename Conditional::value, Identity, // found! FindItem> ::type::type type; }; template struct ReplaceItem { static_assert(I > 0, "index cannot be negative"); static_assert(GetSize::value > 0, "index too high"); typedef typename PrependItem::type> ::type type; }; template struct ReplaceItem, 0, NewItem> { typedef TypeList type; }; enum Direction { Left = -1, Right = 1 }; template struct Rule { typedef OldState old_state; typedef Input input; typedef NewState new_state; typedef Output output; static Direction const direction = Move; }; template struct IsSame { enum { value = false }; }; template struct IsSame { enum { value = true }; }; template struct Configuration { typedef Input input; typedef State state; enum { position = Position }; }; template struct Max { enum { value = A > B ? A : B }; }; template struct State { enum { value = n }; static char const * name; }; template char const* State::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 NAME ; \ NAME :: name = #NAME ; template struct Input { enum { value = n }; static char const * name; template struct Generate { typedef TypeList...> type; }; }; template char const* Input::name = "unnamed"; typedef Input<-1> InputBlank; #define DEF_INPUT(ID, NAME) \ typedef Input NAME ; \ NAME :: name = #NAME ; template struct Controller { typedef Config config; enum { position = config::position }; typedef typename Conditional< static_cast(GetSize::value) <= static_cast(position), AppendItem, Identity>::type::type input; typedef typename config::state state; typedef typename GetItem::type cell; template struct Matcher { typedef typename Item::old_state checking_state; typedef typename Item::input checking_input; enum { value = IsSame::value && IsSame::value }; }; typedef typename FindItem::type rule; typedef typename ReplaceItem::type new_input; typedef typename rule::new_state new_state; typedef Configuration::value> new_config; typedef Controller 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 struct Controller, Transitions, typename EnableIf::value || IsSame::value>::type> { typedef Configuration config; enum { position = config::position }; typedef typename Conditional< static_cast(GetSize::value) <= static_cast(position), AppendItem, Identity>::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 struct TuringMachine { typedef Input input; typedef Transitions transitions; typedef StartState start_state; typedef Controller, 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  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, Rule, Rule, Rule, Rule, Rule, Rule, Rule> rules; /* syntax: initial input, rules, start state */ typedef TuringMachine, rules, start> double_it; static_assert(IsSame>::value, "Hmm... This is borky!"); } 

” Les modèles C ++ sont Turing Complete ” donne une implémentation d’une machine Turing dans les templates … ce qui n’est pas sortingvial et prouve le sharepoint manière très directe. Bien sûr, ce n’est pas très utile!

Mon C ++ est un peu rouillé, donc peut-être pas parfait, mais c’est proche.

 template  struct Factorial { enum { val = Factorial::val * N }; }; template <> struct Factorial<0> { enum { val = 1 }; } const int num = Factorial<10>::val; // num set to 10! at comstack time. 

Il s’agit de démontrer que le compilateur évalue complètement la définition récursive jusqu’à ce qu’elle obtienne une réponse.

Pour donner un exemple non sortingvial: http://gitorious.org/metatrace , un traceur de temps de compilation C ++.

Notez que C ++ 0x appenda une fonction non-template, à la compilation, au format turing-complete sous la forme de constexpr :

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

Vous pouvez utiliser constexpr partout où vous avez besoin de constantes de compilation, mais vous pouvez également appeler les constexpr constexpr avec des parameters non const.

Une chose intéressante est que cela permettra finalement de comstackr le calcul en virgule flottante, bien que la norme stipule explicitement que les arithmétiques en virgule flottante ne doivent pas nécessairement correspondre à l'arithmétique à virgule flottante à l'exécution:

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

Il n'est pas précisé si la valeur de f () sera vraie ou fausse.

Le Design Book C ++ moderne – Programmation générique et design par Andrei Alexandrescu est le meilleur endroit pour acquérir une expérience pratique avec des schémas de programmation génériques utiles et puissants.

L’exemple factoriel ne montre pas que Turing est complet dans la mesure où il montre qu’il prend en charge la récursivité primitive. Le moyen le plus simple de montrer que les templates sont complets est d’utiliser la thèse de Church-Turing, c’est-à-dire implémenter soit une machine Turing (désordonnée et un peu inutile) soit les trois règles (app, abs var) du lambda calcul Ce dernier est beaucoup plus simple et beaucoup plus intéressant.

Ce qui est discuté est une fonctionnalité extrêmement utile lorsque vous comprenez que les modèles C ++ permettent une functional programming pure au moment de la compilation, un formalisme expressif, puissant et élégant, mais aussi très compliqué à écrire si vous avez peu d’expérience. Notez également combien de personnes trouvent que le simple fait d’obtenir du code lourd peut souvent nécessiter un gros effort: c’est exactement le cas avec les langages fonctionnels (purs), ce qui rend la compilation plus difficile mais étonnamment le code qui ne nécessite pas de débogage.

Je pense que cela s’appelle la méta-programmation de modèles .

Vous pouvez vérifier cet article de Dr. Dobbs sur une implémentation FFT avec des modèles que je ne trouve pas sortingvial. L’essentiel est de permettre au compilateur de réaliser une meilleure optimisation que pour les implémentations non-modèles car l’algorithme FFT utilise beaucoup de constantes (tables de sin par exemple)

partie I

Partie II

Il est également amusant de faire remarquer qu’il s’agit d’un langage purement fonctionnel, mais quasiment impossible à déboguer. Si vous regardez James post, vous verrez ce que je veux dire par sa fonctionnalité. En général, ce n’est pas la fonctionnalité la plus utile de C ++. Il n’a pas été conçu pour cela. C’est quelque chose qui a été découvert.

Cela peut être utile si vous voulez calculer des constantes au moment de la compilation, du moins en théorie. Découvrez la métaprogrammation de modèles .

Eh bien, voici une implémentation de la machine de Turing en temps de compilation exécutant un castor occupé à 4 états à 2 symboles

 #include  #pragma mark - Tape constexpr int Blank = -1; template class Tape { public: using type = Tape; constexpr static int length = sizeof...(xs); }; #pragma mark - Print template void print(T); template<> void print(Tape<>) { std::cout << std::endl; } template void print(Tape) { if (x == Blank) { std::cout << "_ "; } else { std::cout << x << " "; } print(Tape()); } #pragma mark - Concatenate template class Concatenate; template class Concatenate, Tape> { public: using type = Tape; }; #pragma mark - Invert template class Invert; template<> class Invert> { public: using type = Tape<>; }; template class Invert> { public: using type = typename Concatenate< typename Invert>::type, Tape >::type; }; #pragma mark - Read template class Read; template class Read> { public: using type = typename std::conditional< (n == 0), std::integral_constant, Read> >::type::type; }; #pragma mark - N first and N last template class NLast; template class NLast> { public: using type = typename std::conditional< (n == sizeof...(xs)), Tape, NLast> >::type::type; }; template class NFirst; template class NFirst> { public: using type = typename Invert< typename NLast< n, typename Invert>::type >::type >::type; }; #pragma mark - Write template class Write; template class Write> { public: using type = typename Concatenate< typename Concatenate< typename NFirst>::type, Tape >::type, typename NLast<(sizeof...(xs) - pos - 1), Tape>::type >::type; }; #pragma mark - Move template class Hold; template class Hold> { public: constexpr static int position = pos; using tape = Tape; }; template class Left; template class Left> { public: constexpr static int position = typename std::conditional< (pos > 0), std::integral_constant, std::integral_constant >::type(); using tape = typename std::conditional< (pos > 0), Tape, Tape >::type; }; template class Right; template class Right> { public: constexpr static int position = pos + 1; using tape = typename std::conditional< (pos < sizeof...(xs) - 1), Tape, Tape >::type; }; #pragma mark - States template  class Stop { public: constexpr static int write = -1; template using move = Hold; template using next = Stop; }; #define ADD_STATE(_state_) \ template \ class _state_ { }; #define ADD_RULE(_state_, _read_, _write_, _move_, _next_) \ template<> \ class _state_<_read_> { \ public: \ constexpr static int write = _write_; \ template using move = _move_; \ template using next = _next_; \ }; #pragma mark - Machine template class, int, class> class Machine; template class State, int pos, int... xs> class Machine> { constexpr static int symbol = typename Read>::type(); using state = State; template using nextState = typename State::template next; using modifiedTape = typename Write>::type; using move = typename state::template move; constexpr static int nextPos = move::position; using nextTape = typename move::tape; public: using step = Machine; }; #pragma mark - Run template class Run; template class State, int pos, int... xs> class Run>> { using step = typename Machine>::step; public: using type = typename std::conditional< std::is_same, Stop<0>>::value, Tape, Run >::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; using machine = Machine; using result = Run::type; int main() { print(result()); return 0; } 

Démonstration d’Ideone: https://ideone.com/MvBU3Z

Explication: http://victorkomarov.blogspot.ru/2016/03/comstack-time-turing-machine.html

Github avec plus d’exemples: https://github.com/fnz/CTTM

Une machine Turing est complète à Turing, mais cela ne signifie pas que vous devez en utiliser une pour le code de production.

Essayer de faire quelque chose de non-sortingvial avec des modèles est dans mon expérience désordonnée, laide et inutile. Vous n’avez aucun moyen de “déboguer” votre “code”, les messages d’erreur à la compilation seront cryptiques et généralement dans les endroits les plus improbables, et vous pourrez obtenir les mêmes avantages de performance de différentes manières. (Indice: 4! = 24). Pire encore, votre code est incompréhensible pour le programmeur C ++ moyen et sera probablement non portable en raison des nombreux niveaux de prise en charge dans les compilateurs actuels.

Les templates sont parfaits pour la génération de code générique (classes de conteneur, wrappers de classes, mix-ins), mais non – à mon avis, le caractère complet des templates de Turing n’est PAS utile dans la pratique.

Un exemple qui est raisonnablement utile est une classe de ratio. Il existe quelques variantes qui circulent. Catching D == 0 cas est assez simple avec des surcharges partielles. Le calcul réel consiste à calculer le GCD de N et D et le temps de compilation. Ceci est essentiel lorsque vous utilisez ces ratios dans les calculs de compilation.

Exemple: Lorsque vous calculez des centimètres (5) * kilomètres (5), au moment de la compilation, vous multipliez le rapport <1,100> et le ratio <1000,1>. Pour éviter le débordement, vous voulez un ratio <10,1> au lieu d’un ratio <1000,100>.

Juste un autre exemple de comment ne pas programmer:

 template 
 struct K17 {
     statique const int x =
     K17 > :: x
     + K17 > :: x
     + K17 > :: x
     + K17 > :: x
     + K17 > :: x;
 };
 template 
 struct K17 <16, A, B> {statique const int x = 1;  };
 statique const int z = K17 <0,0, int> :: x;
 annulation de la main (annulation) {}

Les modèles postés sur C ++ sont complets