قوالب C++ تورينج كاملة؟

Question

قيل لي أن نظام القالب في C++ مكتمل من خلال Turing في وقت الترجمة.هذا مذكور في هذا المشنور وأيضا على ويكيبيديا.

هل يمكنك تقديم مثال غير بديهي للحساب الذي يستغل هذه الخاصية؟

هل هذه الحقيقة مفيدة في الممارسة العملية؟

Answer 1

مثال

#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 ويعرف أيضًا باسم (مكتبة البرمجة التعريفية).لكن حاول تصحيح خطأ المترجم في كود القالب الخاص بك وسوف تكون في طريق طويل وصعب.

لكن مثال عملي جيد على استخدامه لشيء مفيد:

كان سكوت مايرز يعمل على توسيع لغة C++ (أستخدم المصطلح بشكل فضفاض) باستخدام تسهيلات القوالب.يمكنك أن تقرأ عن عمله هنا 'ميزات إنفاذ التعليمات البرمجية'

Answer 2

ولقد فعلت آلة تورينج في C ++ (11). الميزات التي تضيف C ++ 11 ليست كبيرة للجهاز تورينج الواقع. ويوفر فقط للقوائم حكم طول التعسفية باستخدام قوالب variadic، بدلا من استخدام metaprogramming الكلي الضارة :). وتستخدم أسماء لظروف لإخراج الرسم على المعياري. لقد إزالة هذا الرمز للحفاظ على عينة قصيرة.

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

Answer 3

و" C ++ قوالب هل تورنج كامل " يعطي تنفيذ آلة تورينج في قوالب ... وهو غير تافهة، ويثبت هذه النقطة بطريقة مباشرة جدا. وبطبيعة الحال، كما أنه ليس من المفيد جدا!

Answer 4

وبلدي 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.

وهذه النقطة هي لإثبات أن المترجم هو تقييم تماما تعريف الشيء بنفسه حتى يصل إلى إجابة.

Answer 5

لإعطاء مثال غير تافهة: http://gitorious.org/metatrace ، وC ++ وقت الترجمة راي التتبع.

لاحظ أن C ++ 0X ستضيف غير القالب، تجميع الوقت، مرفق تورينج كامل في شكل constexpr:

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

ويمكنك استخدام constexpr في التعبير في كل مكان حيث كنت في حاجة تجميع الثوابت الوقت، ولكن يمكنك أيضا استدعاء constexpr وظائف مع المعلمات غير CONST.

وشيء واحد بارد هو أن هذا سيمكن أخيرا وقت الترجمة العائمة الرياضيات نقطة، على الرغم من أن معيار ينص صراحة على أن وقت الترجمة علم الحساب نقطة عائمة لا يجب أن تطابق وقت علم الحساب النقطة العائمة:

<اقتباس فقرة>

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

     

ومن unspeci فاي إد ما إذا كانت قيمة و () سوف يكون صحيحا أو خاطئا.

Answer 6

الحديثة C ++ تصميم - برمجة الجنيسة وتصميم نمط اندريه ألكسندريسكو هو أفضل مكان للحصول على أيدي تجربة مع أنماط برمجة عامة قوية ومفيدة.

Answer 7

والمثال المضروب في الواقع لا تظهر أن القوالب وتورينج كاملة، بقدر ما يدل على أنها تدعم البدائية العودية. أسهل طريقة لإظهار أن القوالب وتورينج الكامل هو من خلال أطروحة الكنيسة، تورينج، وهذا هو طريق تنفيذ أي آلة تورينج (فوضوي وقليلا لا طائل منه) أو القواعد الثلاثة (التطبيق، وتقاسم المنافع فار) من حساب التفاضل والتكامل لامدا بلا نوع. وهذا الأخير هو أبسط من ذلك بكثير وأكثر إثارة للاهتمام.

ما يجري مناقشته هو ميزة مفيدة للغاية عندما كنت أفهم أن القوالب C ++ تسمح البرمجة الوظيفية البحتة في وقت الترجمة، والشكلية التي هي معبرة وقوية وأنيقة ولكن أيضا معقدة للغاية لكتابة إذا كان لديك خبرة قليلة. ولاحظ أيضا كيف كثير من الناس تجد أن مجرد الحصول على كود templatized بشكل كبير في كثير من الأحيان يمكن أن تتطلب جهدا كبيرا: هذا هو الحال مع (نقية) اللغات الوظيفية، الأمر الذي يجعل من الصعب تجميع ولكن من المدهش تسفر التعليمات البرمجية التي لا تتطلب التصحيح بالضبط

Answer 8

وأعتقد أنه دعا قالب الفوقية البرمجة .

Answer 9

ويمكنك التحقق من هذه المادة من الدكتور دوبس على تنفيذ الاتحاد الفرنسي للتنس مع القوالب التي لا أعتقد أن تافهة. والنقطة الرئيسية هي للسماح للمترجم لأداء الأمثل أفضل من لتطبيقات غير القالب كما خوارزمية الاتحاد الفرنسي للتنس يستخدم الكثير من الثوابت (الجداول الخطيئة على سبيل المثال)

جزء

I

الجزء الثاني

Answer 10

حسنا، وهنا وقت الترجمة تورينج تنفيذ آلة تشغيل 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;
}

وIdeone برهان المدى: https://ideone.com/MvBU3Z

شرح: http://victorkomarov.blogspot.ru/ 2016/03 / تجميع لمرة و-تورينج-machine.html

وجيثب مع مزيد من الأمثلة: https://github.com/fnz/CTTM

Answer 11

وكما انها متعة أن نشير إلى أنه من لغة وظيفية بحتة وإن كان من المستحيل تقريبا التصحيح. إذا نظرتم جيمس إضافة سترى ما أعنيه كونها وظيفية. بشكل عام انها ليست ميزة مفيدة للغاية من C ++. لم يصمم للقيام بذلك. انه شيء الذي تم اكتشافه.

Answer 12

وقد يكون من المفيد إذا كنت ترغب في حساب الثوابت في وقت الترجمة، على الأقل من الناحية النظرية. تحقق من قالب metaprogramming .

Answer 13

أ آلة تورينج هو Turing-Complete، ولكن هذا لا يعني أنك يجب أن ترغب في استخدام واحد لرمز الإنتاج.

إن محاولة القيام بأي شيء غير تافه باستخدام القوالب هي في تجربتي فوضوية وقبيحة ولا معنى لها.ليس لديك طريقة "لتصحيح" "الكود" الخاص بك، وستكون رسائل الخطأ في وقت الترجمة مشفرة وعادةً ما تكون في الأماكن غير المتوقعة، ويمكنك تحقيق نفس فوائد الأداء بطرق مختلفة.(تَلمِيح:4!= 24).والأسوأ من ذلك، أن التعليمات البرمجية الخاصة بك غير مفهومة لمبرمج C++ العادي، ومن المحتمل أن تكون غير قابلة للنقل بسبب مستويات الدعم الواسعة النطاق داخل المترجمين الحاليين.

تعتبر القوالب رائعة لإنشاء الأكواد العامة (فئات الحاويات، وأغلفة الفئات، والمكونات الإضافية)، ولكن لا - في رأيي، يعد "اكتمال تورينج" للقوالب هو غير مفيدة في التمرين.

Answer 14

ومثال وهو مفيد بشكل معقول هي فئة النسبة. هناك عدد قليل من المتغيرات وتطوف. اصطياد حالة D == 0 بسيط إلى حد ما مع الزائدة جزئية. الحوسبة الحقيقية هي في حساب GCD من N و D و ترجمة الوقت. وهذا أمر ضروري عندما كنت تستخدم هذه النسب في حسابات وقت الترجمة.

وعلى سبيل المثال: عندما كنت حساب سم (5) * كيلومترات (5)، في وقت الترجمة عليك أن تكون مضاعفة نسبة <1100> ونسبة <1000،1>. لمنع تجاوز، كنت ترغب في نسبة <10،1> بدلا من نسبة <1000.100>.

Answer 15

مجرد مثال آخر لكيفية عدم البرمجة:

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++ تكتمل