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

111

Мне сказали, что система шаблонов в C ++ является полной по Тьюрингу во время компиляции. Об этом упоминается в этом посте, а также в Википедии. .

Можете ли вы привести нетривиальный пример вычисления, использующего это свойство?

Полезен ли этот факт на практике?

Федерико А. Рампони
источник

Ответы:

110

пример

#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 ++ (я использую этот термин вольно), используя средства создания шаблонов. Вы можете прочитать о его работе здесь « Применение функций кода ».

Мартин Йорк
источник
36
Черт возьми, идеи (пуф)
Мартин Йорк
5
У меня есть небольшая проблема с предоставленным примером - он не использует (полную) полноту по Тьюрингу системы шаблонов C ++. Факториал можно найти также с помощью примитивных рекурсивных функций, которые не являются полными по
Тьюрингу,
4
а и теперь у нас есть концепции lite
nurettin
1
В 2017 году мы отодвигаем концепции еще дальше. Здесь есть надежда на 2020 год.
DeiDei 01
2
@MarkKegel 12 лет спустя: D
Виктор
182

Я сделал машину Тьюринга на 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!");
}
Йоханнес Шауб - litb
источник
131
У тебя слишком много свободного времени.
Марк Кегель,
2
Это похоже на шепение, за исключением того, что все эти круглые скобки заменены словом certin.
Саймон Куанг
1
Доступен ли где-нибудь полный исходный текст для любопытного читателя? :)
OJFord
1
Просто попытка заслуживает большего уважения :-) Этот код компилируется (gcc-4.9), но не дает никаких результатов - немного больше информации, например сообщение в блоге, было бы здорово.
Альфред Браттеруд,
2
@OllieFord Я нашел его версию на странице pastebin и перепечатал ее здесь: coliru.stacked-crooked.com/a/de06f2f63f905b7e .
Йоханнес Шауб - лит
13

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

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

Джеймс Карран
источник
1
Ммм ... разве вам не нужно иметь "template <>" в строке перед struct Factorial <0>, чтобы указать специализацию шаблона?
paxos1977,
11

Приведу нетривиальный пример: 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(){
    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 () истинным или ложным.

Себастьян Мах
источник
8

Факторный пример на самом деле не показывает, что шаблоны являются полными по Тьюрингу, в большей степени он показывает, что они поддерживают примитивную рекурсию. Самый простой способ показать, что шаблоны являются полными по Тьюрингу, - это использовать тезис Черча-Тьюринга, то есть реализовать либо машину Тьюринга (беспорядочно и немного бессмысленно), либо три правила (app, abs var) нетипизированного лямбда-исчисления. Последнее намного проще и интереснее.

То, что обсуждается, является чрезвычайно полезной функцией, если вы понимаете, что шаблоны C ++ допускают чисто функциональное программирование во время компиляции, формализм, который является выразительным, мощным и элегантным, но также очень сложным для написания, если у вас мало опыта. Также обратите внимание, как многие люди считают, что получение сильно шаблонного кода часто требует больших усилий: это как раз тот случай, когда речь идет о (чистых) функциональных языках, которые усложняют компиляцию, но на удивление дают код, который не требует отладки.


источник
Эй, интересно, какие три правила вы имеете в виду, говоря «app, abs, var»? Я предполагаю, что первые два - это приложение функции и абстракция (определение лямбда (?)) Соответственно. Это так? А какой третий? Что-то связано с переменными?
Wizek
Я лично считаю, что было бы лучше, если бы язык поддерживал примитивную рекурсию в компиляторе, чем был бы Turing Complete, поскольку компилятор для языка, который поддерживает примитивную рекурсию во время компиляции, может гарантировать, что любая сборка либо завершится, либо завершится неудачно, но тот, чей процесс сборки завершен по Тьюрингу, не может, кроме как путем искусственного ограничения сборки, чтобы она не была завершена по Тьюрингу.
supercat
5

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

Том Риттер
источник
2
Это его полезная сторона. Обратной стороной является то, что я сомневаюсь, что большинство людей (и, конечно, не я) когда-либо действительно поймут даже небольшой процент того, что происходит в большинстве этих вещей. Это ужасно нечитаемый, неподдерживаемый материал.
Майкл Берр,
3
Я думаю, что это недостаток всего языка C ++. Это становится монстром ...
Федерико А. Рампони
C ++ 0x обещает значительно упростить эту задачу (и, по моему опыту, самая большая проблема - это компиляторы, которые не поддерживают его полностью, а C ++ 0x не поможет). В частности, концепции выглядят так, как будто они проясняют ситуацию, например, избавление от многих вещей SFINAE, которые трудно читать.
coppro
@MichaelBurr Комитет по C ++ не заботится о нечитаемых, неподдерживаемых вещах; они просто любят добавлять функции.
Sapphire_Brick
4

Что ж, вот реализация машины Тьюринга на этапе компиляции, в которой запущен двухсимвольный бобер с 4 состояниями.

#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/compile-time-turing-machine.html

Github с дополнительными примерами: https://github.com/fnz/CTTM

Виктор Комаров
источник
3

Вы можете проверить эту статью доктора Доббса о реализации БПФ с шаблонами, что, на мой взгляд, не так уж и тривиально. Главное - позволить компилятору выполнить лучшую оптимизацию, чем для реализаций без шаблона, поскольку алгоритм БПФ использует множество констант (например, таблицы sin).

часть I

Часть II


источник
2

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

Мэтт Прайс
источник
1

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

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

MSalters
источник
0

Машина Тьюринга Тьюринг-полной, но это не значит , что вы должны использовать одну для производства кода.

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

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

Родди
источник
4! может быть 24, но что такое MY_FAVORITE_MACRO_VALUE! ? Хорошо, я тоже не думаю, что это хорошая идея.
Джеффри Л. Уитледж,
0

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

template <int Depth, int A, typename B>
struct K17 {
    статическая константа 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;
};
шаблон <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 (недействительно) {}

Шаблоны публикации на C ++ завершены

Исаламон
источник
для любопытных ответ для x - pow (глубина 5,17);
прилетел 06
Что гораздо проще увидеть, когда вы поймете, что аргументы шаблона A и B ничего не делают, и удалите их, а затем замените все добавление на K17<Depth+1>::x * 5.
Дэвид Стоун