C++ plantillas Turing-completas?

templates template-meta-programming

Question

Me dijeron 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 explota esta propiedad?

¿Este hecho es útil en la práctica?

Answer 1

" Las plantillas de C ++ son Turing completas " 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 2

Bueno, aquí hay una implementación de Turing Machine en tiempo de compilación ejecutando un castor ocupado de 2 símbolos de 4 estados

#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 a 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

Answer 3

Creo que se llama meta-programación de plantillas .

Answer 4

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 la segunda parte de la pregunta:
¿Este hecho es útil en la práctica?

Respuesta corta: más o menos.

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

Para obtener una buena programación usando una meta-programación de plantillas que sea 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.

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 las características del código ''

Answer 5

El diseño Book Modern C ++ - Programación genérica y patrón de diseño de Andrei Alexandrescu es el mejor lugar para obtener experiencia práctica con patrones de programación genéricos útiles y potentes.

Answer 6

El ejemplo factorial en realidad no muestra que las plantillas estén completas, tanto como 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 una programación funcional pura en tiempo de compilación, un formalismo que es 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 7

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 8

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 completamente la definición recursiva hasta que alcanza una respuesta.

Answer 9

Para dar un ejemplo no trivial: http://gitorious.org/metatrace , un rastreador de tiempo de compilación de C ++.

Tenga en cuenta que C ++ 0x agregará una instalación que no es de plantilla, en 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 constexpr cualquier lugar donde necesite constantes de tiempo de compilación, pero también puede llamar a constexpr -functions con parámetros no const.

Una cosa interesante es que esto finalmente permitirá el cálculo del tiempo de compilación en coma flotante, aunque el estándar establece explícitamente que las aritméticas de punto flotante en tiempo de compilación no tienen que coincidir con las aritméticas de coma flotante en 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;
}

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

Answer 10

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 realice una mejor optimización que para las implementaciones sin plantilla, ya que el algoritmo FFT usa muchas constantes (por ejemplo, tablas sin).

parte I

Parte II

Answer 11

Puede ser útil si desea calcular constantes en tiempo de compilación, al menos en teoría. Echa un vistazo a la metaprogramación de la plantilla .

Answer 12

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

Las publicaciones en las plantillas de C ++ se están completando

Answer 13

También es divertido señalar que es un lenguaje puramente funcional aunque casi imposible de depurar. Si miras la publicación de James , verás lo que quiero decir con que es funcional. 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 14

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 tiempo de compilación se multiplicará la relación <1,100> y la proporción <1000,1>. Para evitar el desbordamiento, desea una proporción <10,1> en lugar de una relación <1000,100>.

Answer 15

Una máquina de Turing es Turing-completa, pero eso no significa que deba usar una para el código de producción.

Tratar de hacer cualquier cosa que no sea trivial con las plantillas es en mi experiencia desordenado, feo e inútil. 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, mix-ins), pero no; en mi opinión, la integridad de Turing de las plantillas NO ES ÚTIL en la práctica.