С++ шаблоны Turing-complete?
Мне говорят, что система шаблонов на С++ является Turing-complete во время компиляции. Это упоминается в этом сообщении, а также на wikipedia.
Можете ли вы представить нетривиальный пример вычисления, использующего это свойство?
Этот факт полезен на практике?
Ответы
Ответ 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 aka (Библиотека метапрограмм). Но попробуйте отлаживать ошибку компилятора в вашем шаблоне кода, и вы окажетесь на долгое время.
Но хороший практический пример его использования для чего-то полезного:
Скотт Мейерс работает над расширением языка С++ (я использую этот термин свободно) с использованием шаблонов. Вы можете прочитать о его работе здесь. Выполнение функций кода
Ответ 2
Я сделал машину turing в С++ 11. Возможности, которые добавляет С++ 11, не являются существенными для машины turing. Он просто предоставляет списки произвольных длин, используя вариационные шаблоны, вместо использования макропопрограммирования макросов макросов:). Имена условий используются для вывода диаграммы на 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!");
}
Ответ 3
" С++ Templates Turing Complete" дает реализацию машины Тьюринга в шаблонах..., которая нетривиальна и доказывает указывают очень прямо. Конечно, это тоже не очень полезно!
Ответ 4
Мой С++ немного ржавый, поэтому он может быть не идеальным, но он близок.
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.
Цель состоит в том, чтобы продемонстрировать, что компилятор полностью оценивает рекурсивное определение, пока не достигнет ответа.
Ответ 5
Книга Современный дизайн С++ - Общий шаблон программирования и дизайна от Andrei Alexandrescu - лучшее место, чтобы получить опыт работы с полезными и мощными родовыми программные шаблоны.
Ответ 6
Чтобы дать нетривиальный пример: http://gitorious.org/metatrace, трассировщик времени компиляции С++.
Обратите внимание, что С++ 0x добавит объект без шаблона, компиляции, времени turing-complete в форме 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() истинным или ложным.
Ответ 7
Факторный пример на самом деле не показывает, что шаблоны являются завершающими, поскольку он показывает, что они поддерживают примитивную рекурсию. Самый простой способ показать, что шаблоны завершены, - это тезис Церкви-Тьюринга, то есть путем внедрения либо машины Тьюринга (беспорядочной, и немного бессмысленной), либо трех правил (app, abs var) нетипизированного лямбда-исчисления. Последнее намного проще и интереснее.
То, что обсуждается, является чрезвычайно полезной функцией, когда вы понимаете, что шаблоны С++ позволяют чисто функциональное программирование во время компиляции, формализм, который является выразительным, мощным и элегантным, но также очень сложным для написания, если у вас мало опыта. Также обратите внимание на то, как много людей находят, что просто получить сильно затененный код часто может потребовать больших усилий: это точно так же (с чистыми) функциональными языками, которые делают сборку сложнее, но удивительно дают код, который не требует отладки.
Ответ 8
Я думаю, что он называется мета-программирование шаблонов.
Ответ 9
Вы можете проверить эту статью у доктора Доббса по реализации FFT с шаблонами, которые, я думаю, не так уж и тривиальны.
Главное состоит в том, чтобы позволить компилятору выполнять лучшую оптимизацию, чем для реализации без шаблонов, поскольку алгоритм FFT использует множество констант (например, таблицы sin)
часть I
часть II
Ответ 10
Это может быть полезно, если вы хотите вычислить константы во время компиляции, по крайней мере теоретически. Отметьте метапрограммирование шаблонов.
Ответ 11
Также интересно отметить, что это чисто функциональный язык, хотя почти невозможно отладить. Если вы посмотрите на Джеймс, вы увидите, что я имею в виду, что это функциональность. В общем, это не самая полезная функция С++. Он не был предназначен для этого. Это то, что было обнаружено.
Ответ 12
Ну, вот компиляция времени Turing Machine, выполняющая 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
Ответ 13
A Машина Тьюринга завершена, но это не значит, что вы должны использовать ее для производственного кода.
Попытка сделать что-то, что нетривиально с шаблонами, по моему опыту беспорядочно, уродливо и бессмысленно. У вас нет возможности "отлаживать" ваш "код", сообщения об ошибках во время компиляции будут загадочными и обычно в самых маловероятных местах, и вы можете добиться одинаковых преимуществ по производительности по-разному. (Подсказка: 4!= 24). Хуже того, ваш код непонятен среднему программисту на С++ и, вероятно, будет не переносимым из-за широкого диапазона поддержки в текущих компиляторах.
Шаблоны отлично подходят для генерации общего кода (классы контейнеров, оболочек классов, микширования), но нет - на мой взгляд, полнота шаблонов Тьюринга НЕ ПОЛЕЗНАЯ на практике.
Ответ 14
Примером, который достаточно полезен, является класс отношения. Есть несколько вариантов, плавающих вокруг. Захват случая D == 0 довольно прост с частичными перегрузками. Реальные вычисления состоят в вычислении GCD из N и D и времени компиляции. Это важно, когда вы используете эти коэффициенты при расчетах времени компиляции.
Пример. Когда вы вычисляете сантиметры (5) * километров (5), во время компиляции вы будете умножать коэффициент < 1100 > и коэффициент < 1000,1 > . Чтобы предотвратить переполнение, вам нужно отношение < 10,1 > вместо отношения < 1000,100 > .
Ответ 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) { }
Опубликовать в Шаблоны С++ завершены
