Plantillas C ++ Turing-complete?
https://stackoverflow.com/questions/189172
-
06-07-2019 - |
italiano
english
français
española
中国
日本の
العربية
Deutsch
한국어
Português
RussianPregunta
Me han dicho que el sistema de plantillas en C ++ es Turing completo en tiempo de compilación. Esto se menciona en esta publicación y también en wikipedia .
¿Puede proporcionar un ejemplo no trivial de un cálculo que explote esta propiedad?
¿Es útil este hecho en la práctica?
Solución
Ejemplo
#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";
}
Eso fue un poco divertido pero no muy práctico.
Para responder a la segunda parte de la pregunta:
¿Es útil este hecho en la práctica?
Respuesta corta: Más o menos.
Respuesta larga: Sí, pero solo si eres un demonio de plantilla.
Para lograr una buena programación usando metaprogramación de plantillas que es realmente útil para que otros usen (es decir, una biblioteca) es realmente muy difícil (aunque factible). Para ayudar a impulsar incluso tiene MPL aka (Meta Biblioteca de programación). Pero intente depurar un error del compilador en su código de plantilla y se encontrará con un largo y duro viaje.
Pero un buen ejemplo práctico de que se usa para algo útil:
Scott Meyers ha estado trabajando extensiones para el lenguaje C ++ (uso el término libremente) usando las instalaciones de plantillas. Puede leer sobre su trabajo aquí ' Aplicación de funciones de código '
Otros consejos
He hecho una máquina de Turing en C ++ 11. Las características que agrega C ++ 11 no son significativas para la máquina de trabajo. Solo proporciona listas de reglas de longitud arbitrarias usando plantillas variadas, en lugar de usar macroprogramación de macro perversa :). Los nombres de las condiciones se utilizan para generar un diagrama en stdout. he eliminado ese código para mantener la muestra corta.
#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!");
}
" Las plantillas de C ++ se están completando " ofrece una implementación de una máquina de Turing en plantillas ... que no es trivial y demuestra el punto de una manera muy directa. ¡Por supuesto, tampoco es muy útil!
Mi C ++ está un poco oxidado, por lo que puede que no sea perfecto, pero está cerca.
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.
El punto es demostrar que el compilador está evaluando completamente la definición recursiva hasta que alcanza una respuesta.
Para dar un ejemplo no trivial: http://gitorious.org/metatrace , un tiempo de compilación de C ++ rastreador.
Tenga en cuenta que C ++ 0x agregará un recurso que no es plantilla, tiempo de compilación, turing-complete en forma de constexpr:
constexpr unsigned int fac (unsigned int u) {
return (u<=1) ? (1) : (u*fac(u-1));
}
Puede usar <=> - expresión en todas partes donde necesite compilar constantes de tiempo, pero también puede llamar a <=> - funciones con parámetros no constantes.
Una cosa interesante es que esto finalmente permitirá la matemática de punto flotante de tiempo de compilación, aunque el estándar establece explícitamente que la aritmética de punto flotante de tiempo de compilación no tiene que coincidir con la aritmética de punto flotante de tiempo de ejecución:
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; }Es unspeci & # 64257; ed si el valor de f () será verdadero o falso.
El libro Diseño moderno de C ++: programación genérica y patrón de diseño por Andrei Alexandrescu es el mejor lugar para obtener experiencia práctica con patrones de programación genéricos útiles y potentes.
El ejemplo factorial en realidad no muestra que las plantillas estén completas en Turing, sino que muestra que admiten la recursividad primitiva. La forma más fácil de mostrar que las plantillas se están completando es mediante la tesis de Church-Turing, es decir, implementando una máquina de Turing (desordenada y un poco inútil) o las tres reglas (aplicación, abs var) del cálculo lambda sin tipo. Este último es mucho más simple y mucho más interesante.
Lo que se está discutiendo es una característica extremadamente útil cuando comprende que las plantillas C ++ permiten una programación funcional pura en tiempo de compilación, un formalismo expresivo, potente y elegante, pero también muy complicado de escribir si tiene poca experiencia. Observe también cuántas personas encuentran que el simple hecho de obtener un código con muchas plantillas puede requerir un gran esfuerzo: este es exactamente el caso con los lenguajes funcionales (puros), lo que hace que la compilación sea más difícil pero sorprendentemente produce código que no requiere depuración.
Creo que se llama metaprogramación de plantillas .
Puede consultar este artículo del Dr. Dobbs sobre una implementación de FFT con plantillas que creo que no son tan triviales. El punto principal es permitir que el compilador realice una mejor optimización que para implementaciones sin plantilla, ya que el algoritmo FFT usa muchas constantes (tablas sin, por ejemplo)
Bueno, aquí hay una implementación de Turing Machine en tiempo de compilación que ejecuta un castor ocupado de 4 símbolos y 2 símbolos
#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;
}
Prueba de prueba de Ideone: https://ideone.com/MvBU3Z
Explicación: http://victorkomarov.blogspot.ru/ 2016/03 / compile-time-turing-machine.html
Github con más ejemplos: https://github.com/fnz/CTTM
También es divertido señalar que es un lenguaje puramente funcional, aunque casi imposible de depurar. Si miras la publicación James , verás lo que quiero decir con que sea funcional. En general, no es la característica más útil de C ++. No fue diseñado para hacer esto. Es algo que se descubrió.
Puede ser útil si desea calcular constantes en tiempo de compilación, al menos en teoría. Consulte metaprogramación de plantillas .
Una La máquina de Turing está completa de Turing, pero eso no significa que deba desear usar uno para el código de producción.
Intentar hacer algo no trivial con plantillas es, en mi experiencia, desordenado, feo y sin sentido. No tiene forma de & Quot; depurar & Quot; su " code " ;, los mensajes de error en tiempo de compilación serán crípticos y generalmente en los lugares más improbables, y puede lograr los mismos beneficios de rendimiento de diferentes maneras. (Sugerencia: 4! = 24). Peor aún, su código es incomprensible para el programador promedio de C ++ y es probable que no sea portátil debido a los amplios niveles de soporte dentro de los compiladores actuales.
Las plantillas son excelentes para la generación de código genérico (clases de contenedor, envoltorios de clase, mezclas), pero no, en mi opinión, la integridad de Turing de las plantillas es NO ÚTIL en la práctica.
Un ejemplo que es razonablemente útil es una clase de razón. Hay algunas variantes flotando. Capturar el caso D == 0 es bastante simple con sobrecargas parciales. La computación real está en calcular el MCD de N y D y el tiempo de compilación. Esto es esencial cuando usa estas proporciones en los cálculos en tiempo de compilación.
Ejemplo: cuando calcula centímetros (5) * kilómetros (5), en el momento de la compilación multiplicará la relación < 1,100 > y relación < 1000,1 > ;. Para evitar el desbordamiento, desea una relación & Lt; 10,1 & Gt; en lugar de una relación < 1000,100 > ;.
Solo otro ejemplo de cómo no programar:
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) { }
Publique en Las plantillas de C ++ se están completando
