Полные по Тьюрингу шаблоны C++?

Когда вы объявляете ссылочную переменную (т. е. объект), вы действительно создаете указатель на объект. Рассмотрим следующий код, в котором вы объявляете переменную примитивного типа int:

int x;
x = 10;

В этом примере переменная x является int, и Java инициализирует ее для 0. Когда вы назначаете его 10 во второй строке, ваше значение 10 записывается в ячейку памяти, на которую указывает x.

Но когда вы пытаетесь объявить ссылочный тип, произойдет что-то другое. Возьмите следующий код:

Integer num;
num = new Integer(10);

Первая строка объявляет переменную с именем num, но она не содержит примитивного значения. Вместо этого он содержит указатель (потому что тип Integer является ссылочным типом). Поскольку вы еще не указали, что указать на Java, он устанавливает значение null, что означает «Я ничего не указываю».

Во второй строке ключевое слово new используется для создания экземпляра (или создания ) объекту типа Integer и переменной указателя num присваивается этот объект. Теперь вы можете ссылаться на объект, используя оператор разыменования . (точка).

Exception, о котором вы просили, возникает, когда вы объявляете переменную, но не создавали объект. Если вы попытаетесь разыменовать num. Перед созданием объекта вы получите NullPointerException. В самых тривиальных случаях компилятор поймает проблему и сообщит вам, что «num не может быть инициализирован», но иногда вы пишете код, который непосредственно не создает объект.

Например, вы можете имеют следующий метод:

public void doSomething(SomeObject obj) {
   //do something to obj
}

В этом случае вы не создаете объект obj, скорее предполагая, что он был создан до вызова метода doSomething. К сожалению, этот метод можно вызвать следующим образом:

doSomething(null);

В этом случае obj имеет значение null. Если метод предназначен для того, чтобы что-то сделать для переданного объекта, целесообразно бросить NullPointerException, потому что это ошибка программиста, и программисту понадобится эта информация для целей отладки.

Альтернативно, там могут быть случаи, когда цель метода заключается не только в том, чтобы работать с переданным в объекте, и поэтому нулевой параметр может быть приемлемым. В этом случае вам нужно будет проверить нулевой параметр и вести себя по-другому. Вы также должны объяснить это в документации. Например, doSomething может быть записано как:

/**
  * @param obj An optional foo for ____. May be null, in which case 
  *  the result will be ____.
  */
public void doSomething(SomeObject obj) {
    if(obj != null) {
       //do something
    } else {
       //do something else
    }
}

Наконец, Как определить исключение & amp; причина использования Трассировки стека

100
задан Community 23 May 2017 в 11:47
поделиться

14 ответов

Пример

#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++ (я использую термин свободно), использование средств шаблонной обработки. Можно читать о его работе здесь' Функции Кода Осуществления '

103
ответ дан Martin York 24 November 2019 в 04:45
поделиться

Примером, который довольно полезен, является класс отношения. Существует несколько вариантов, плавающих вокруг. При ловле D == 0 случаев довольно просты с частичными перегрузками. Реальное вычисление находится в вычислении GCD N и D и время компиляции. Это важно при использовании этих отношений в вычислениях времени компиляции.

Пример: при вычислении сантиметров (5) *kilometers (5) во время компиляции Вы будете умножать ratio< 1,100> и ratio< 1000,1>. Для предотвращения переполнения Вы хотите ratio< 10,1> вместо ratio< 1000,100>.

1
ответ дан MSalters 24 November 2019 в 04:45
поделиться

Машина Тьюринга полна по Тьюрингу, но это не означает, что необходимо хотеть использовать один для производственного кода.

Попытка сделать что-либо нетривиальное с шаблонами, по моему опыту, грязно, ужасно и бессмысленно. У Вас нет способа "отладить" Ваш "код", сообщения ошибки времени компиляции будут загадочными и обычно в самых неожиданных местах, и можно достигнуть тех же выигрышей в производительности по-разному. (Подсказка: 4! = 24). Хуже, Ваш код непостижим среднему программисту на C++ и будет вероятен быть непортативным из-за широких уровней поддержки в рамках текущих компиляторов.

Шаблоны являются большими для универсальной генерации кода (контейнерные классы, обертки класса, соединение-ins), но нет - по-моему, полнота по Тьюрингу шаблонов НЕ ПОЛЕЗНА на практике.

1
ответ дан Roddy 24 November 2019 в 04:45
поделиться

Может быть полезно, если Вы хотите вычислить константы во время компиляции, по крайней мере, в теории. Выезд шаблонное метапрограммирование .

2
ответ дан 24 November 2019 в 04:45
поделиться

Это - также забава указать, что это - чисто функциональный язык, хотя почти невозможный для отладки. Если Вы посмотрите сообщение James, то Вы будете видеть то, что я подразумеваю под ним являющийся функциональным. В целом это не самая полезная функция C++. Это не было разработано, чтобы сделать это. Это - что-то, что было обнаружено.

2
ответ дан Community 24 November 2019 в 04:45
поделиться

Можно проверить эту статью от доктора Dobbs на реализации FFT с шаблонами, которые я думаю не что тривиальный. Основной момент должен позволить компилятору работать, лучшая оптимизация, чем для не обрабатывают реализации по шаблону, поскольку Алгоритм бпф использует много констант (таблицы греха, например)

первая часть

вторая часть

3
ответ дан 24 November 2019 в 04:45
поделиться

Книга современный Дизайн C++ - Универсальный Шаблон программирования и Шаблон разработки Andrei Alexandrescu является лучшим местом для доставления опыт с полезными и мощными универсальными шаблонами программирования.

8
ответ дан yoav.aviram 24 November 2019 в 04:45
поделиться

Мой 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.

точка должна продемонстрировать, что компилятор полностью оценивает рекурсивное определение, пока это не достигает ответа.

13
ответ дан Luc Touraille 24 November 2019 в 04:45
поделиться

" Шаблоны C++ полны по Тьюрингу ", дает реализацию Машины Тьюринга в шаблонах..., которая нетривиальна и подтверждает точку зрения очень прямым способом. Конечно, это также не очень полезно!

27
ответ дан Michael Mrozek 24 November 2019 в 04:45
поделиться

Я сделал машину Тьюринга в C++ 11. Опции, которые добавляет C++ 11, не являются значительными для машины Тьюринга действительно. Это просто предусматривает списки правила произвольной длины с помощью variadic шаблоны, вместо того, чтобы использовать извращенное макро-метапрограммирование:). Названия условий используются для вывода схемы на 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!");
}
172
ответ дан Johannes Schaub - litb 24 November 2019 в 04:45
поделиться

Я думаю, что это звонило шаблонное метапрограммирование .

5
ответ дан Tom Ritter 24 November 2019 в 04:45
поделиться

The factorial example actually does not show that templates are Turing complete, as much as it shows that they support Primitive Recursion. The easiest way to show that templates are turing complete is by the Church-Turing thesis, that is by implementing either a Turing machine (messy and a bit pointless) or the three rules (app, abs var) of the untyped lambda calculus. The latter is much simpler and far more interesting.

What is being discussed is an extremely useful feature when you understand that C++ templates allow pure functional programming at compile time, a formalism that is expressive, powerful and elegant but also very complicated to write if you have little experience. Also notice how many people find that just getting heavily templatized code can often require a big effort: this is exactly the case with (pure) functional languages, which make compiling harder but surprisingly yield code that does not require debugging.

8
ответ дан 24 November 2019 в 04:45
поделиться

Еще один пример того, как не программировать:

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 ++ завершены по Тьюрингу

0
ответ дан 24 November 2019 в 04:45
поделиться

В качестве нетривиального примера: 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 -функции с неконстантными параметрами.

Одна интересная вещь заключается в том, что это, наконец, позволит использовать математику с плавающей запятой во время компиляции, хотя в стандарте явно указано, что арифметика времени компиляции с плавающей запятой не должна соответствовать арифметике с плавающей запятой во время выполнения:

 bool f () {{{1 }} массив символов [1 + int (1 + 0,2-0,1-0,1)]; // Должен быть вычислен во время перевода 
int size = 1 + int (1 + 0.2-0.1-0.1); // Может быть оценено во время выполнения 
return sizeof (array) == size; 
} 
 

Не указано, будет ли значение f () истинным или ложным .

10
ответ дан 24 November 2019 в 04:45
поделиться
Другие вопросы по тегам:

Похожие вопросы: