C ++模板图灵完成？
我被告知C ++中的模板系统在编译时是Turing-complete的。 这在这篇文章中也提到了维基百科 。
你能提供一个利用这个属性的计算的一个不平凡的例子吗？
这在事实上是有用的吗？
例
#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"; } 这是一个有趣的，但不是很实际。
回答问题的第二部分：
这在事实上是有用的吗？
简答：sorting。
长答案：是的，但只有当你是一个模板守护进程。
为了使用模板元编程（对于其他人来说真的很有用）（例如库）来编写好的编程是非常困难的（虽然可行）。 即使有MPL又名（元编程库），以帮助提升。 但是，尝试在你的模板代码中debugging一个编译器错误，你会很长一段时间。
但是一个很好的实际例子，它被用于一些有用的东西：
Scott Meyers一直在使用模板工具来扩展C ++语言（我使用术语松散）。 你可以在这里阅读他的工作“ 执行代码function ”
我用C ++ 11做了一个图灵机。 C ++ 11增加的function对于图灵机来说并不重要。 它只是使用可变参数模板提供了任意长度的规则列表，而不是使用不正确的macros元编程:)。 条件的名称用于在stdout上输出图表。 我已经删除了该代码，以保持简短的样本。
#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 ++模板是图灵完整的 ”提供了模板中的图灵机的实现…这是不平凡的，并以非常直接的方式certificate了这一点。 当然，这也不是很有用！
我的C ++有点生疏，所以可能不完美，但它很接近。
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.
重点是certificate编译器完全评估recursion定义，直到达到答案。
书籍现代C ++devise – Andrei Alexandrescu的generics编程和devise模式是获得有用和强大的通用编程模式的经验的最佳场所。
给一个非平凡的例子： http : //gitorious.org/metatrace ，一个C ++编译时光线追踪器。
请注意，C ++ 0x将以constexprforms添加一个非模板，编译时，图灵完成工具：
constexpr unsigned int fac (unsigned int u) { return (u<=1) ? (1) : (u*fac(u-1)); }
你可以在需要编译时间常量的地方使用constexpr -expression，但是你也可以用非const参数调用constexpr函数。
一个很酷的事情是，这将最终使编译时浮点math，虽然标准明确指出，编译时浮点算术不需要匹配运行时浮点算术：
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; }未明确f（）的值是真还是假。
该因子示例实际上并不显示模板是图灵完整的，尽pipe它表明它们支持基本recursion。 显示模板完整的最简单的方法是通过Church-Turing论文，即通过实现无typeslambda微积分的图灵机（混乱和有点无意义）或三个规则（app，abs var）。 后者更简单，更有趣。
当你理解C ++模板允许在编译时进行纯粹的函数式编程时，正在讨论的是一个非常有用的特性，这是一种forms化，强大和优雅的forms，如果你没有什么经验，它也是非常复杂的。 另外请注意有多less人发现只是模板化的代码经常需要很大的努力：（纯）函数式语言就是这种情况，这使得编译更困难，但出乎意料地产生了不需要debugging的代码。
我认为这就是所谓的模板元编程 。
你可以从Dr. Dobbs那里查看这篇关于FFT实现的文章，我认为这不是那么简单。 重点是允许编译器执行比非模板实现更好的优化，因为FFTalgorithm使用了很多常量（例如sin表）
第一部分
第二部分
指出这是一个纯粹的function语言，尽pipe几乎不可能debugging也很有趣。 如果你看詹姆斯的post，你会看到我的意思是function。 一般来说，这不是C ++最有用的function。 这不是为了做到这一点。 这是被发现的东西。
如果你想在编译时计算常量，至less在理论上是有用的。 检查模板元编程 。
那么，这是一个编译时间图灵机运行一个4状态2符号繁忙的海狸
#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; }
Ideonecertificate运行： https ：//ideone.com/MvBU3Z
说明： http : //victorkomarov.blogspot.ru/2016/03/compile-time-turing-machine.html
Github更多的例子： https ： //github.com/fnz/CTTM
一个图灵机是图灵完成的，但这并不意味着你应该使用一个生产代码。
试图用模板做任何不重要的事情，在我的经验中是凌乱的，丑陋的和毫无意义的。 你没有办法“debugging”你的“代码”，编译时错误信息将是神秘的，通常在最不可能的地方，你可以通过不同的方式获得相同的性能优势。 （提示：4！= 24）。 更糟糕的是，你的代码对普通的C ++程序员来说是无法理解的，而且由于目前的编译器支持范围广泛，所以可能是不可移植的。
模板对于generics代码生成（容器类，类包装，混合）非常有用 ，但是在我看来，模板的图灵完整性在实践中并不实用。
一个合理有用的例子是一个比率类。 有几个变种浮动。 捕捉D == 0的情况相当简单，部分超载。 真正的计算是在计算N和D的GCD和编译时间。 在编译时计算中使用这些比率时，这是非常重要的。
示例：当计算厘米（5）*公里（5）时，在编译时您将乘以比率<1,100>和比率<1000,1>。 为了防止溢出，你需要比率<10,1>而不是比率<1000,100>。
另一个如何不编程的例子：
template <int Depth，int A，typename B>
结构K17 {
static const int x =
K17 <深度+1,0，K17 <深度，A，B>> :: x
+ K17 <深度+ 1，1，K17 <深度，A，B>> :: x
+ K17 <深度+1,2，K17 <深度，A，B>> :: x
+ K17 <深度+ 1，3，K17 <深度，A，B>> :: x
+ K17 <深度+1,4，K17 <深度，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）{}
在C ++模板上发布完成
