C++ templates Turing-complete?

Question

Me dijeron que el sistema de plantillas en C++ es Turing-completo en tiempo de compilación. Esto se menciona en this post y también en wikipedia.

¿Puede proporcionar un ejemplo no trivial de un cálculo que explota esta propiedad?

¿Es útil este hecho en la práctica?

Answer 1

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 era un poco divertido, pero no es muy práctico.

responder a la segunda parte de la pregunta:
Es este hecho útil en la práctica?

Respuesta corta: Tipo de.

Respuesta larga: Sí, pero solo si usted es un daemon de plantilla.

Para realizar una buena programación utilizando meta-programación de plantillas que es realmente útil para que otros la usen (es decir, una biblioteca) es realmente muy difícil (aunque posible). Para ayudar a impulsar incluso tiene MPL aka (Meta Programming Library). Pero intente depurar un error del compilador en su código de plantilla y se encontrará con un duro viaje largo.

embargo, un buen ejemplo práctico de que se utilice para algo útil:

Scott Meyers ha estado trabajando extensiones al lenguaje C++ (utilizo el término vagamente) utilizando las instalaciones de plantillas. Puede leer sobre su trabajo aquí 'Enforcing Code Features'

Answer 2

"C++ Templates Are Turing Complete" 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!

Answer 3

Puede ser útil si desea calcular las constantes en tiempo de compilación, al menos en teoría. Consulte template metaprogramming.

Answer 4

Creo que se llama template meta-programming.

Answer 5

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 objetivo es demostrar que el compilador está evaluando por completo la definición recursiva hasta que alcanza una respuesta.

Answer 6

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 su funcionamiento. En general, no es la característica más útil de C++. No fue diseñado para hacer esto. Es algo que fue descubierto.

Answer 7

El libro Modern C++ Design - Generic Programming and Design Pattern de Andrei Alexandrescu es el mejor lugar para obtener experiencia práctica con patrones de programación genéricos útiles y potentes.

Answer 8

Puede consultar este artículo del Dr. Dobbs sobre una implementación de FFT con plantillas que no creo que sean triviales. El punto principal es permitir que el compilador para realizar una mejor optimización de las implementaciones no de plantilla como el algoritmo FFT utiliza una gran cantidad de constantes (tablas pecado por ejemplo)

part I

part II

Answer 9

Un Turing machine es Turing-completo, pero eso no significa que deba usar uno para el código de producción.

Tratar de hacer cualquier cosa que no sea trivial con las plantillas es en mi experiencia desordenada, fea y sin sentido. No tiene forma de "depurar" su "código", los mensajes de error en tiempo de compilación serán crípticos y, por lo general, en los lugares más improbables, y puede obtener 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 geniales para la generación de código genérico (clases de contenedor, contenedores de clase, mezclas), pero no - en mi opinión, la integridad de Turing de las plantillas es NO ÚTIL en la práctica.

Answer 10

Un ejemplo que es razonablemente útil es una clase de relación. Hay algunas variantes flotando alrededor. Capturar el caso D == 0 es bastante simple con sobrecargas parciales. La verdadera computación está en calcular el GCD 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 se calculan centímetros (5) * kilómetros (5), en el momento de la compilación se multiplicará la proporción < 1,100> y la proporción < 1000,1>. Para evitar el desbordamiento, desea una relación < 10,1> en lugar de una relación < 1000,100>.

Answer 11

He hecho una máquina de turing en C++ 11. Las características que C++ 11 agrega no son significativas para la máquina de turing de hecho. Solo proporciona listas de reglas de longitud arbitraria usando plantillas variadic, en lugar de usar metaprogramació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!"); 
} 

Answer 12

El ejemplo factorial en realidad no muestra que las plantillas estén completas, al igual que muestra que admiten la Recursividad primitiva. La forma más fácil de demostrar que las plantillas están completas es mediante la tesis Church-Turing, es decir, implementando una máquina de Turing (desordenada y un poco inútil) o las tres reglas (app, 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 comprendes que las plantillas C++ permiten programación funcional pura en tiempo de compilación, un formalismo expresivo, potente y elegante pero también muy complicado de escribir si tienes poca experiencia. También observe cuántas personas encuentran que el simple hecho de obtener un código muy templado a menudo puede requerir un gran esfuerzo: este es exactamente el caso con los lenguajes funcionales (puros), que hacen que la compilación sea más difícil pero sorprendentemente producen código que no requiere depuración.

Answer 13

sólo otro ejemplo de cómo no se debe programa:

 
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) { } 

mensaje en C++ templates are turing complete

Answer 14

Para dar un ejemplo no trivial: http://gitorious.org/metatrace, C++ compila trazador de rayos tiempo.

Tenga en cuenta que C++ 0x añadirá un no-plantilla, en tiempo de compilación, instalación de Turing completo en forma de constexpr:

constexpr unsigned int fac (unsigned int u) { 
     return (u<=1) ? (1) : (u*fac(u-1)); 
} 

Usted puede utilizar constexpr-expresión en todas partes donde se necesita compilar constantes de tiempo , pero también puede llamar al constexpr -funciones con parámetros no const.

Una cosa interesante es que esto finalmente permitir que el tiempo de compilación aritmética de punto flotante, aunque la norma establece explícitamente que la aritmética de punto flotante en tiempo de compilación no tienen que coincidir en tiempo de ejecución aritmética de punto flotante:

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; 
} 

Se no se especifica si el valor de f() será verdadero o falso.

Answer 15

Bueno, aquí hay un tiempo de compilación de Turing aplicación Máquina en marcha un 4 por el estado de 2 símbolos ocupada castor

#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 plazo prueba: 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