Modèles C ++ Turing-complet?
https://stackoverflow.com/questions/189172
-
06-07-2019 - |
italiano
english
français
española
中国
日本の
العربية
Deutsch
한국어
Português
RussianQuestion
On me dit que le système de templates en C ++ est Turing-complete au moment de la compilation. Ceci est mentionné dans ce message et également sur wikipedia .
Pouvez-vous fournir un exemple non trivial de calcul exploitant cette propriété?
Ce fait est-il utile dans la pratique?
La solution
Exemple
#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";
}
C'était amusant mais pas très pratique.
Pour répondre à la deuxième partie de la question:
Ce fait est-il utile dans la pratique?
Réponse courte: type de.
Réponse longue: Oui, mais uniquement si vous êtes un démon de modèle.
Produire une bonne programmation en utilisant une méta-programmation de gabarit qui est vraiment utile pour les autres (une bibliothèque) est vraiment très difficile (bien que réalisable). Pour aider à stimuler même a MPL aka (Meta Bibliothèque de programmation). Mais essayez de déboguer une erreur du compilateur dans votre code de modèle et vous vous retrouverez dans une situation difficile.
Mais un bon exemple pratique de son utilisation pour quelque chose d'utile:
Scott Meyers a travaillé sur des extensions du langage C ++ (j’utilise le terme vaguement) à l’aide des installations de modèles. Vous pouvez en savoir plus sur son travail à la section Application des fonctionnalités du code '
Autres conseils
J'ai créé une machine à écrire en C ++ 11. Les fonctionnalités ajoutées par C ++ 11 ne sont pas significatives pour la machine de turing. Il fournit simplement des listes de règles de longueur arbitraire utilisant des modèles variés, au lieu d’utiliser une métaprogrammation macro pervers :). Les noms des conditions sont utilisés pour générer un diagramme sur stdout. J'ai supprimé ce code pour que l'échantillon soit court.
#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!");
}
" Les modèles C ++ sont mis à jour Complètement " donne une implémentation d'une machine de Turing dans des templates ... qui est non triviale et prouve le point de manière très directe. Bien sûr, cela n’est pas très utile non plus!
Mon C ++ est un peu rouillé, alors le résultat n'est peut-être pas parfait, mais il est proche.
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.
Il s’agit de démontrer que le compilateur évalue complètement la définition récursive jusqu’à ce qu’il atteigne une réponse.
Pour donner un exemple non trivial: http://gitorious.org/metatrace , une compilation C ++ traceur de rayons.
Notez que C ++ 0x ajoutera une fonction de turing-complete non gabarit, à la compilation, sous la forme de constexpr:
constexpr unsigned int fac (unsigned int u) {
return (u<=1) ? (1) : (u*fac(u-1));
}
Vous pouvez utiliser <=> - expression partout où vous avez besoin de constantes de temps de compilation, mais vous pouvez également appeler des fonctions <=> - avec des paramètres non const.
Une bonne chose, c’est que cela va enfin permettre de calculer les calculs en virgule flottante à la compilation, bien que la norme stipule explicitement que les arithmétiques à virgule flottante ne doivent pas nécessairement correspondre aux arithmétiques à virgule flottante d’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 spécifié & # 64257; ed de déterminer si la valeur de f () sera vraie ou fausse.
Le livre Conception en C ++ moderne - Programmation générique et modèle de conception par Andrei Alexandrescu est le meilleur endroit pour acquérir une expérience pratique avec des modèles de programmation génériques utiles et puissants.
L'exemple factoriel n'indique pas réellement que les modèles sont complets, mais montre qu'ils prennent en charge la récursion primitive. Le moyen le plus simple de démontrer que les modèles sont complets est de s’appuyer sur la thèse de Church-Turing, c’est-à-dire en implémentant soit une machine de Turing (en désordre et un peu inutile), soit les trois règles (app, abs var) du calcul lambda sans type. 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 programmation purement fonctionnelle lors 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 un code fortement structuré peut souvent nécessiter un gros effort: c'est exactement le cas avec les langages fonctionnels (purs), qui rendent la compilation plus difficile mais qui produit un code surprenant qui ne nécessite pas de débogage.
Je pense que cela s'appelle la méta-programmation de modèles .
Vous pouvez consulter cet article de M. Dobbs sur une implémentation FFT avec des modèles qui, à mon avis, n’est pas si anodin. L’essentiel est de permettre au compilateur d’optimiser davantage que pour les implémentations sans modèle car l’algorithme FFT utilise beaucoup de constantes (tables sin par exemple)
Eh bien, voici une implémentation de Turing Machine au moment de la compilation exécutant un castor occupé à 4 symboles et à 4 états
#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;
}
Test Ideone: https://ideone.com/MvBU3Z
Explication: http://victorkomarov.blogspot.ru/ 2016/03 / compile-turing-machine.html
Github avec plus d'exemples: https://github.com/fnz/CTTM
Il est également amusant de souligner qu’il s’agit d’un langage purement fonctionnel bien que presque impossible à déboguer. Si vous consultez le James message, vous verrez ce que je veux dire par son utilisation fonctionnelle. En général, ce n'est pas la fonctionnalité la plus utile du C ++. Ce n'était pas conçu pour faire ça. C'est quelque chose qui a été découvert.
Cela peut être utile si vous souhaitez calculer des constantes au moment de la compilation, du moins en théorie. Consultez la métaprogrammation du modèle .
Une machine de Turing est Turing-complete, mais cela ne veut pas dire que vous devriez vouloir en utiliser un pour le code de production.
Essayer de faire quelque chose de non trivial avec des modèles est, dans mon expérience, désordonné, moche et inutile. Vous n’avez aucun moyen de & "Déboguer &"; vos " code " ;, les messages d'erreur de compilation seront cryptés et se trouveront généralement aux endroits les plus improbables, et vous pourrez obtenir les mêmes avantages en termes de performances 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 du large éventail de niveaux de support pris en charge par les compilateurs actuels.
Lesmodèles sont parfaits pour la génération de code générique (classes de conteneur, encapsuleurs de classes, mixages), mais non - dans la pratique, l’exhaustivité des modèles de Turing est NON UTILE .
Un exemple raisonnablement utile est une classe de ratio. Il y a quelques variantes qui circulent. Attraper le cas D == 0 est assez simple avec des surcharges partielles. Le calcul réel consiste à calculer les différences de temps de calcul entre N et D et le temps de compilation. Ceci est essentiel lorsque vous utilisez ces ratios dans les calculs au moment de la compilation.
Exemple: lorsque vous calculez des centimètres (5) * kilomètres (5), au moment de la compilation, vous multipliez le rapport < 1 100 > et rapport < 1000,1 > ;. Pour éviter les débordements, vous souhaitez un rapport & Lt; 10,1 & Gt; au lieu d'un rapport < 1000,100 >.
Juste un autre exemple de comment ne pas programmer:
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) { }
Publier à l'adresse Les modèles C ++ sont complets
