Plantillas C ++ Turing-complete?

Me dijeron que el sistema de plantillas en C ++ está 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 este hecho útil en la práctica?

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 este hecho útil en la práctica?

Respuesta corta: algo así.

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

Producir una buena programación utilizando metaprogramación de plantillas que sea realmente útil para que otros la usen (es decir, una biblioteca) es realmente difícil (aunque factible). Para ayudar a impulsar, incluso tiene MPL también conocido como (Meta biblioteca de programación). Pero intente depurar un error del compilador en el código de su plantilla y le espera un viaje largo y duro.

Pero un buen ejemplo práctico de cómo se usa para algo útil:

Scott Meyers ha estado trabajando en extensiones del lenguaje C ++ (uso el término libremente) usando las facilidades de plantillas. Puede leer sobre su trabajo aquí ' Aplicación de funciones de código '

Hice una máquina de turing en C ++ 11. Las características que agrega C ++ 11 no son significativas para la máquina de turing. Solo proporciona listas de reglas de longitud arbitraria usando plantillas variadas, en lugar de usar metaprogramación macro perversa :). Los nombres de las condiciones se utilizan para generar un diagrama en stdout. He eliminado ese código para que la muestra sea breve.

#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 ++ 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!

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 llega a una respuesta.

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

Tenga en cuenta que C ++ 0x agregará una función de turing completa, en tiempo de compilación y sin plantilla en forma de constexpr:

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

Puede usar constexpr-expression en cualquier lugar donde necesite compilar constantes de tiempo, pero también puede llamar a constexpr-functions con parámetros no constantes.

Una cosa interesante es que esto finalmente permitirá la matemática de punto flotante en tiempo de compilación, aunque el estándar establece explícitamente que la aritmética de punto flotante en tiempo de compilación no tiene que coincidir con la aritmética de punto 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.

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

El ejemplo factorial en realidad no muestra que las plantillas estén completas en Turing, tanto como muestra que admiten la recursividad primitiva. La forma más fácil de demostrar 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 se comprende que las plantillas C ++ permiten una programación funcional pura en tiempo de compilación, un formalismo que es expresivo, poderoso y elegante pero también muy complicado de escribir si se tiene poca experiencia. Observe también cuántas personas encuentran que solo obtener código con muchas plantillas a menudo puede requerir un gran esfuerzo: este es exactamente el caso de los lenguajes funcionales (puros), que hacen 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 .

Bueno, aquí hay una implementación de Turing Machine en tiempo de compilación que ejecuta un castor ocupado de 4 estados 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 ejecución 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

Puede consultar este artículo del Dr. Dobbs sobre una implementación de FFT con plantillas que no creo que sean tan 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 utiliza muchas constantes (tablas sin, por ejemplo)

parte I

Parte II

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 se descubrió.

Puede resultar útil si desea calcular constantes en tiempo de compilación, al menos en teoría. Consulte la metaprogramación de plantillas .

Un ejemplo que es razonablemente útil es una clase de razón. Hay algunas variantes flotando. Detectar 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 utiliza estas proporciones en 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 la relación <1000,1>. Para evitar el desbordamiento, desea una proporción <10,1> en lugar de una proporción <1000,100>.

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

En mi experiencia, intentar hacer algo que no sea trivial con las plantillas es desordenado, feo 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 generalmente en los lugares más improbables, y puede lograr los mismos beneficios de rendimiento de diferentes maneras. (Pista: 4! = 24). Peor aún, su código es incomprensible para el programador promedio de C ++ y probablemente no será 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 clases, combinaciones), pero no, en mi opinión, la integridad de Turing de las plantillas NO ES ÚTIL en la práctica.

Solo otro ejemplo de cómo no programar:

plantilla <int Depth, int A, typename B>
struct K17 {
    estática constante int x =
    K17 <Profundidad + 1, 0, K17 <Profundidad, A, B>> :: x
    + K17 <Profundidad + 1, 1, K17 <Profundidad, A, B>> :: x
    + K17 <Profundidad + 1, 2, K17 <Profundidad, A, B>> :: x
    + K17 <Profundidad + 1, 3, K17 <Profundidad, A, B>> :: x
    + K17 <Profundidad + 1, 4, K17 <Profundidad, A, B>> :: x;
};
plantilla <int A, typename B>
struct K17 <16, A, B> {estática constante int x = 1; };
estática constante int z = K17 <0,0, int> :: x;
void main (vacío) {}

Publicar en C ++ las plantillas se están completando