Шаблоны C ++ по Тьюрингу-завершены?
-
06-07-2019 - |
Решение
Пример
#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";
}
Это было немного забавно, но не очень практично.
Чтобы ответить на вторую часть вопроса:
Полезен ли этот факт на практике?
Краткий Ответ:Вроде того.
Длинный Ответ:Да, но только если вы являетесь демоном шаблонов.
Создать хорошее программирование с использованием шаблонного метапрограммирования, которое действительно полезно для использования другими (то есть библиотекой), действительно очень сложно (хотя и выполнимо).Чтобы помочь boost даже имеет MPL aka (Библиотека метапрограммирования).Но попробуйте отладить ошибку компилятора в коде вашего шаблона, и вам предстоит долгий и трудный путь.
Но хороший практический пример того, как это используется для чего-то полезного:
Скотт Мейерс работал над расширениями для языка C ++ (я использую этот термин в широком смысле), используя средства создания шаблонов.Вы можете прочитать о его работе здесь 'Применение функций кода'
Другие советы
Я сделал машину Тьюринга в 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!");
}
Мой 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.
Суть в том, чтобы продемонстрировать, что компилятор полностью оценивает рекурсивное определение, пока не достигнет ответа.
Чтобы дать нетривиальный пример: http://gitorious.org/metatrace , время компиляции C ++ трассировщик лучей.
Обратите внимание, что C ++ 0x добавит нематериальное средство времени компиляции во время компиляции в виде constexpr
:
constexpr unsigned int fac (unsigned int u) {
return (u<=1) ? (1) : (u*fac(u-1));
}
Вы можете использовать <=> - выражение везде, где вам нужны постоянные времени компиляции, но вы также можете вызывать <=> - функции с неконстантными параметрами.
Одна интересная вещь - это, наконец, включение математики с плавающей запятой во время компиляции, хотя стандарт прямо заявляет, что арифметика с плавающей запятой во времени компиляции не должна соответствовать арифметике с плавающей запятой во время выполнения:
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; }
Не указано & # 64257; ed, будет ли значение f () истинным или ложным.
Книга Современный дизайн C ++ - шаблон общего программирования и проектирования Андрея Александреску это лучшее место, где можно получить практический опыт использования полезных и мощных шаблонов программирования.
Факторный пример фактически не показывает, что шаблоны Тьюринга завершены, а показывает, что они поддерживают Примитивную рекурсию. Самый простой способ показать, что шаблоны являются полными по Тьюрингу, это тезис Черча-Тьюринга, то есть реализовать машину Тьюринга (грязную и немного бессмысленную) или три правила (app, abs var) нетипизированного лямбда-исчисления. Последнее намного проще и гораздо интереснее. Р>
То, что обсуждается, является чрезвычайно полезной функцией, когда вы понимаете, что шаблоны C ++ допускают чисто функциональное программирование во время компиляции, формализм, который является выразительным, мощным и элегантным, но также очень сложным для написания, если у вас мало опыта. Также обратите внимание, как много людей находят, что получение сильно шаблонизированного кода часто может потребовать больших усилий: это в точности относится к (чистым) функциональным языкам, которые усложняют компиляцию, но неожиданно дают код, который не требует отладки.
Мне кажется, это называется шаблонное метапрограммирование . Р>
Вы можете проверить эту статью доктора Доббса о реализации FFT с шаблонами, которые, я думаю, не так уж и просты. Суть в том, чтобы позволить компилятору выполнять лучшую оптимизацию, чем для не шаблонных реализаций, поскольку алгоритм FFT использует много констант (например, таблицы sin)
Хорошо, вот реализация 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 / время компиляции-Туринг-machine.html
Github с другими примерами: https://github.com/fnz/CTTM
Также забавно отметить, что это чисто функциональный язык, хотя его практически невозможно отладить. Если вы посмотрите сообщение Джеймса , вы поймете, что я имею в виду под его функциональностью. В общем, это не самая полезная особенность C ++. Он не был предназначен для этого. Это то, что было обнаружено.
Это может быть полезно, если вы хотите вычислить константы во время компиляции, по крайней мере, в теории. Ознакомьтесь с метапрограммированием шаблонов .
Машина Тьюринга завершена по Тьюрингу, но это не значит, что вам нужно использовать один для производственного кода.
Попытка сделать что-нибудь нетривиальное с шаблонами в моем опыте грязно, безобразно и бессмысленно. Вы не можете & Quot; отладить & Quot; ваш " code " ;, сообщения об ошибках во время компиляции будут зашифрованы и, как правило, в самых неожиданных местах, и вы можете добиться одинакового выигрыша в производительности разными способами. (Подсказка: 4! = 24). Хуже того, ваш код непонятен среднему программисту на C ++ и, вероятно, будет непереносимым из-за широкого диапазона уровней поддержки в современных компиляторах. Р>
Шаблоны отлично подходят для генерации общего кода (контейнерные классы, обертки классов, дополнения), но нет - на мой взгляд, полнота шаблонов Тьюринга на практике НЕ ПОЛЕЗНА . Р>
Примером, который является достаточно полезным, является класс отношений. Есть несколько вариантов, плавающих вокруг. Поймать случай D == 0 довольно просто с частичными перегрузками. Реальные вычисления заключаются в вычислении GCD N и D и времени компиляции. Это важно, когда вы используете эти соотношения в вычислениях во время компиляции.
Пример. Когда вы вычисляете сантиметры (5) * километров (5), во время компиляции вы умножаете коэффициент < 1100 > и соотношение < 1000,1 > ;. Чтобы предотвратить переполнение, вы хотите соотношение & Lt; 10,1 & Gt; вместо отношения < 1000,100 >.
Еще один пример того, как не программировать.
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 ++ завершены а> р>