C + + 模板图灵完成？

“ C + + 模板正在图灵完成”在模板中给出了一个图灵机的实现... ... 这是非常重要的，并以一种非常直接的方式证明了这一点。当然，它也不是很有用！

如果您想在编译时计算常量，至少在理论上是这样，那么它可能很有用。

我想它叫 模板元编程模板元编程。

我的 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.

关键是要证明编译器正在完全评估递归定义，直到得到一个答案。

指出它是一种纯函数式语言也很有趣，尽管几乎不可能进行调试。如果你看看 詹姆斯后，你就会明白我所说的功能性是什么意思。一般来说，它不是 C + + 最有用的特性。它不是被设计成这样的。这是被发现的东西。

例子

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

有点意思，但不是很实际。

回答问题的第二部分:
这个事实在实践中有用吗？

简短的回答: 算是吧。

详细的回答: 是的，但只有在您是模板守护进程的情况下。

使用模板元编程(模板元编程对其他人非常有用，例如库)来编写优秀的程序非常困难(尽管是可行的)。帮助提高甚至有 MPL又名(元编程库)。但是，如果尝试在模板代码中调试编译器错误，那么您将陷入长期的困境。

但是一个很好的实际例子是它被用于一些有用的东西:

Scott Meyers 一直在使用模板工具对 C + + 语言进行扩展。你可以在这里阅读他的作品‘ 执行代码特性’

Andrei Alexandrescu 的 abc 0书籍是获得有用且强大的通用编程模式经验的最佳地方。

您可以查看 Dobbs 博士关于使用模板的 FFT 实现的文章，我认为这些模板并不是那么简单。 主要的一点是允许编译器执行比非模板实现更好的优化，因为 FFT 算法使用了很多常量(例如 sin 表)

第一部分

第二部分

图灵机是图灵完成的，但这并不意味着您应该将其用于生产代码。

在我的经验中，尝试用模板做任何不平凡的事情都是混乱、丑陋和毫无意义的。您没有办法“调试”您的“代码”，编译时错误消息将是神秘的，通常在最不可能的地方，并且您可以通过不同的方式获得相同的性能好处。(提示: 4！= 24).更糟糕的是，您的代码对于普通的 C + + 程序员来说是不可理解的，并且由于当前编译器中的广泛支持级别，它很可能是不可移植的。

模板对于泛型代码生成(容器类、类包装器、混合)来说是很棒的，但是在我看来，模板的图灵完备性在实践中是 没用的。

一个相当有用的例子是比率类。有一些变种到处都是。使用部分重载捕获 D = = 0情况相当简单。真正的计算是计算 N 和 D 的 GCD 和编译时间。在编译时计算中使用这些比率时，这一点至关重要。

例如: 当你计算厘米(5) * 公里(5)时，在编译时，你将乘以比率 < 1,100 > 和比率 < 1000,1 > 。为了防止溢出，您需要一个比率 < 10,1 > 而不是一个比率 < 1000,100 > 。

我用 C + + 11做过一个图灵机。C + + 11添加的特性对于图灵机来说并不重要。它只是使用可变模板提供任意长度的规则列表，而不是使用反常的宏元编程:)。这些条件的名称用于在标准输出上输出一个关系图。我已经删除了代码，以保持样本短。

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

阶乘示例实际上并没有显示模板是图灵完成的，只是表明它们支持原始递归。最简单的方法是通过邱奇－图灵论题来展示模板正在变成完整的，也就是通过实现一个图灵机(混乱且有点无意义)或者三个规则(app，abs var)的 λ演算。后者要简单得多，也有趣得多。

当您了解 C + + 模板允许在编译时进行纯函数式编程时，正在讨论的是一个非常有用的特性，这是一种表达性强、功能强大且优雅的形式，但如果您没有什么经验，编写起来也非常复杂。还要注意有多少人发现，仅仅获得大量模板化的代码通常就需要付出很大的努力: (纯)函数式语言就是这种情况，这使得编译更加困难，但令人惊讶的是产生的代码不需要调试。

这只是另一个不编程的例子:

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) { }

在 C + + 模板完成站岗

给出一个非常重要的例子: https://github.com/phresnel/metatrace，一个 C + + 编译时光线跟踪器。

注意，C + + 0x 将以 constexpr的形式添加一个非模板、编译时、图灵完成工具:

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

可以在需要编译时常量的任何地方使用 constexpr-expression，但也可以使用非常量参数调用 constexpr-函数。

一个很酷的事情是，这将最终启用编译时浮点数算法，尽管标准明确规定，编译时浮点数算法不必与运行时浮点数算法匹配:

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 ()的值是 true 还是 false。

这里有一个编译时图灵机实现运行一个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;
}

理想证明运行: https://ideone.com/MvBU3Z

说明: http://victorkomarov.blogspot.ru/2016/03/compile-time-turing-machine.html

Github 和更多例子: https://github.com/fnz/CTTM