C++ - Vorlagen Turing-vollständig?
https://stackoverflow.com/questions/189172
-
06-07-2019 - |
italiano
english
français
española
中国
日本の
العربية
Deutsch
한국어
Português
RussianFrage
Ich sagte, dass das template-system in C++ ist Turing-vollständig bei der Kompilierung.Dies wird erwähnt in dieser Beitrag und auch auf wikipedia.
Können Sie bieten eine nichttriviale Beispiel einer Berechnung, nutzt diese Eigenschaft?
Ist diese Tatsache in der Praxis?
Lösung
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 war ein kleiner Spaß, aber nicht sehr praktisch.
Zur Beantwortung der zweiten Teil der Frage:
Ist diese Tatsache in der Praxis?
Kurze Antwort:Art von.
Lange Antwort:Ja, aber nur, wenn Sie ein template-daemon.
To turn out good Programmierung über template-meta-Programmierung, die ist wirklich hilfreich für andere zu verwenden (dh eine Bibliothek) ist wirklich, wirklich hart (obwohl do-able).Zu Helfen, steigern Sie auch hat MPL aka (Meta Programming Library).Aber versuchen Sie das Debuggen zu einem compiler-Fehler im template-code und Sie werden für eine lange harte Fahrt.
Aber ein gutes praktisches Beispiel dafür, dass es für etwas nützlich ist:
Scott Meyers hat gearbeitet Erweiterungen der C++ - Sprache (ich benutze den Begriff Locker) mit der Template-Ausstattung.Sie können Lesen, über seine Arbeit hier 'Durchsetzung Code Features'
Andere Tipps
Ich habe 11 eine Turing-Maschine in C ++ durchgeführt. Features, die ++ 11 addiert C sind für die Turing-Maschine in der Tat nicht signifikant. Es bietet gerade für beliebige Länge Regellisten variadische Vorlagen verwenden, anstatt mit perversen Makro metaprogramming :). Die Namen für die Bedingungen zur Ausgabe ein Diagramm auf stdout verwendet. Ich habe diesen Code entfernt, um die Probe 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 ++ Templates sind Turing komplette " gibt eine Implementierung einer Turing-Maschine in Vorlagen ..., die nicht trivial ist und den Punkt auf eine sehr direkte Art und Weise beweist. Natürlich ist es auch nicht sehr nützlich!
Mein C ++ ist ein bisschen rostig, so kann die möglicherweise nicht perfekt, aber es ist in der Nähe.
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 zeigen, dass der Compiler vollständig die rekursive Definition prüft, bis es eine Antwort erreicht.
ein nicht-triviales Beispiel geben: http://gitorious.org/metatrace ++ ein C Zeit kompilieren Raytracer.
Beachten Sie, dass C ++ 0x eine nicht-Vorlage hinzufügen wird, Compiler-Turing-Komplettanlage in Form von constexpr:
constexpr unsigned int fac (unsigned int u) {
return (u<=1) ? (1) : (u*fac(u-1));
}
Sie können überall constexpr-Ausdruck verwenden, wo Sie Zeitkonstanten kompilieren müssen, aber Sie können auch constexpr-Funktionen mit nicht konstanten Parametern aufrufen.
Eine coole Sache ist, dass diese endlich Zeit Gleitkommamathematik kompilieren ermöglichen werden, obwohl der Standard heißt es ausdrücklich, dass die Kompilierung Gleitkomma-Arithmetik muß nicht Runtime-Floating-Point-Arithmetik entsprechen:
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 unspezi fi ziert, ob der Wert von f () wird wahr oder falsch sein.
Das Buch Moderne C ++ Entwurf - Generic Programmierung und Design-Muster von Andrei Alexandrescu ist der beste Ort, praktische Erfahrung mit nützlichen und leistungsfähigen generischen Programmierung Muster zu erhalten.
Das Fakultäts Beispiel besagt eigentlich nicht, dass Vorlagen sind Turing abgeschlossen ist, so viel wie es zeigt, dass sie Primitive Rekursion unterstützen. Der einfachste Weg, um zu zeigen, dass Vorlagen vollständig sind Turing ist von der Kirche-Turing-These, dh entweder durch eine Turing-Maschine Implementierung (chaotisch und ein wenig sinnlos) oder die drei Regeln (app, abs var) der nicht typisierten Lambda-Kalkül. Letzteres ist viel einfacher und viel interessanter.
Was diskutiert wird, ist eine äußerst nützliche Funktion, wenn Sie verstehen, dass C ++ Vorlagen rein funktionale Programmierung bei der Kompilierung erlauben, einen Formalismus, der ausdrucksvoll, kraftvoll und elegant ist, aber auch sehr kompliziert zu schreiben, wenn Sie wenig Erfahrung haben. Beachten Sie auch, wie viele Leute finden, dass nur schwer templatized Code bekommen oft einen großen Aufwand erfordern. Das ist genau der Fall mit (rein) funktionalen Sprachen, die noch schwerer machen Kompilieren aber überraschend Code ergeben, die nicht das Debuggen erfordert
Ich denke, es Vorlage Meta-Programmierung genannt wird.
Sie können Sie in diesem Artikel von Dr. Dobbs auf einer FFT-Implementierung mit Vorlagen, die ich denke nicht, dass trivial. Der wichtigste Punkt ist der Compiler zu ermöglichen, eine bessere Optimierung als für Nicht-Vorlage Implementierungen durchzuführen, wie der FFT-Algorithmus eine Menge von Konstanten (sin Tabellen zum Beispiel) verwendet
Nun, hier ist eine Kompilierung Turing-Maschine Implementierung eines 4-State-2-Symbol besetzt Biber läuft
#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 Andruck: https://ideone.com/MvBU3Z
Erläuterung: http://victorkomarov.blogspot.ru/ 2016/03 / kompilieren zeit turing-machine.html
Github mit mehr Beispiele: https://github.com/fnz/CTTM
Es macht auch Spaß, darauf zu hinweisen, dass es sich um eine rein funktionale Sprache, wenn auch zu debuggen fast unmöglich ist. Wenn Sie unter schauen James posten Sie werden sehen, was ich meine, indem sie es funktional zu sein. Im Allgemeinen ist es nicht das nützlichste Feature von C ++. Es war nicht, dies zu tun konzipiert. Es ist etwas, das entdeckt wurde.
Es kann sinnvoll sein, wenn Sie Konstanten bei der Kompilierung berechnet werden sollen, zumindest in der Theorie. Schauen Sie sich Metaprogrammierung .
Turing-Maschine ist Turing-vollständig, aber das bedeutet nicht, Sie wollen, sollten eine für Produktionscode zu verwenden.
Der Versuch, etwas nicht-trivial mit Vorlagen zu tun, ist in meiner Erfahrung unordentlich, hässlich und sinnlos. Sie haben keine Möglichkeit zu „debug“ Ihr „Code“, Compiler-Fehlermeldungen kryptisch sein wird und in der Regel in den unwahrscheinlichsten Orten, und Sie können die gleichen Leistungsvorteile auf unterschiedliche Weise erreichen. (Hinweis: 4 = 24!). Schlimmer noch, ist der Code für die durchschnittlichen C ++ Programmierer unverständlich, und wird innerhalb von aktuellen Compiler aufgrund weitreich Maß an Unterstützung wahrscheinlich nicht tragbar sein.
Vorlagen sind für generische Code-Generierung (Container-Klassen, Klassen-Wrapper, Mix-In), aber nein - meiner Meinung nach der Turing Vollständigkeit der Vorlagen ist nicht sinnvoll in der Praxis.
Ein Beispiel, das einigermaßen nützlich ist, ist ein Verhältnis Klasse. Es gibt ein paar Varianten im Umlauf. die D == 0 Fall fangen ist ziemlich einfach mit Teilüberlastungen. Die eigentliche Computing ist in der GCD von N und D zu berechnen und Zeit kompilieren. Dies ist wichtig, wenn man diese Verhältnisse in der Kompilierung-Zeitberechnungen verwenden.
Beispiel: Wenn Sie Zentimeter sind (5) berechnet * km (5), bei der Kompilierung werden Sie Verhältnis multipliziert <1100> und Verhältnis <1000,1>. Um zu verhindern, Überlauf, Sie wollen ein Verhältnis <10,1> anstelle eines Verhältnisses <1000.100>.
Nur ein weiteres Beispiel dafür, wie nicht zu programmieren:
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 unter C ++ Vorlagen vollständig sind Turing
