C++模板Turing-complete？

我被告知C++中的模板系统在编译时是图灵完备的.这篇文章以及维基百科都提到了这一点.

你能提供一个利用这个属性的计算的重要例子吗？

这个事实在实践中有用吗？

1> Johannes Sch..：

---

我用C++ 11做了一台图灵机.C++ 11添加的功能确实对图灵机而言并不重要.它只是使用可变参数模板提供任意长度的规则列表,而不是使用反向宏元编程:).条件的名称用于在stdout上输出图表.我已删除该代码以保持样本简短.

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

---

你手上有太多时间.

---

@littlenag:只有像你这样的人,世界才会无聊.

2> Martin York..：

---

例

#include 

template  struct Factorial
{
    enum { val = Factorial::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++语言(我使用松散的术语).你可以在这里阅读他的工作' 执行代码功能 '

---

Dang那里有概念(poof)

---

@nurettin:仅仅5年后.这对C++来说非常好.

---

现在我们有概念精简版

---

我提供的示例只有一个小问题 - 它没有利用C++模板系统的(完整)图灵完备性.也可以使用原始递归函数找到因子,这些函数不是图灵完备的

3> Rob Walker..：

---

" C++模板图灵完成 "在模板中提供了图灵机的实现......这是非常重要的,并且以非常直接的方式证明了这一点.当然,它也不是很有用!

---

更好的链接:[t ++ machine in c ++ 1x](http://stackoverflow.com/a/275295/14065)

4> James Curran..：

---

我的C++有点生疏,所以可能并不完美,但它很接近.

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 compile time.

关键是要证明编译器正在完全评估递归定义,直到它得到答案.

5> Sebastian Ma..：

---

举一个非平凡的例子:http://gitorious.org/metatrace,C ++编译时光线跟踪器.

请注意,C++ 0x将以下列形式添加非模板,编译时,图灵完备工具constexpr:

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

您可以constexpr在需要编译时常量的地方使用-expression,但也可以constexpr使用非const参数调用-functions.

一个很酷的事情是,这将最终启用编译时浮点数学,尽管标准明确指出编译时浮点算术不必匹配运行时浮点算术:

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()的值是真还是假是不明确的.

6> yoav.aviram..：

---

Book Modern C++ Design -由Andrei Alexandrescu 设计的通用编程和设计模式是获得有用且强大的通用编程模式经验的最佳场所.

7> 小智..：

---

因子实例实际上没有显示模板是图灵完整的,因为它表明它们支持原始递归.显示模板完成的最简单方法是通过Church-Turing论文,即通过实现图灵机(凌乱和有点无意义)或无类型lambda演算的三个规则(app,abs var).后者更简单,更有趣.

当您了解C++模板允许在编译时进行纯函数式编程时,正在讨论的是一个非常有用的功能,这是一种富有表现力,强大而优雅的形式主义,但如果您没有经验,那么编写起来也非常复杂.还要注意有多少人发现只是获得高度模板化的代码通常需要付出很大的努力:这与(纯)函数语言的情况完全相同,这使得编译更难,但令人惊讶的是产生不需要调试的代码.

8> Tom Ritter..：

---

我认为它被称为模板元编程.

---

我认为这是整个C++语言的缺点.它正在成为一个怪物......