Plantillas C ++ Turing-complete?

Respuestas:

110

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 '

Martin York
fuente
36
Dang there fueron conceptos (poof)
Martin York
5
Solo tengo un pequeño problema con el ejemplo proporcionado: no explota la integridad (completa) de Turing del sistema de plantillas de C ++. Factorial también se puede encontrar usando funciones recursivas primitivas, que no son turing-complete
Dalibor Frivaldsky
4
y ahora tenemos conceptos lite
nurettin
1
En 2017, estamos empujando los conceptos aún más atrás. Aquí hay esperanza para 2020.
DeiDei
2
@MarkKegel 12 años después: D
Victor
181

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!");
}
Johannes Schaub - litb
fuente
131
Usted tiene demasiado tiempo en sus manos.
Mark Kegel
2
Parece ceceo excepto con una palabra certin que reemplaza todos esos paréntesis.
Simon Kuang
1
¿Está la fuente completa disponible públicamente en algún lugar, para el lector curioso? :)
OJFord
1
Solo el intento merece mucho más crédito :-) Este código se compila (gcc-4.9) pero no da salida; un poco más de información, como una publicación de blog, sería genial.
Alfred Bratterud
2
@OllieFord Encontré una versión en una página de pastebin y la volví a pegar aquí: coliru.stacked-crooked.com/a/de06f2f63f905b7e .
Johannes Schaub - litb
13

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.

James Curran
fuente
1
Umm ... ¿no necesitas tener "plantilla <>" en la línea antes de la estructura Factorial <0> para indicar la especialización de la plantilla?
paxos1977
11

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.

Sebastián Mach
fuente
8

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.


fuente
Oye, ¿a qué tres reglas te refieres, me pregunto, con "app, abs, var"? Supongo que los dos primeros son la aplicación de funciones y la abstracción (definición lambda (?)) Respectivamente. ¿Es eso así? ¿Y cuál es el tercero? ¿Algo que tenga que ver con variables?
Wizek
Personalmente, creo que sería mejor que un lenguaje admita Primitive Recursion en el compilador que Turing Complete, ya que un compilador para un lenguaje que admita Primitive Recursion en tiempo de compilación podría garantizar que cualquier compilación se completará o fallará, pero uno cuyo proceso de construcción es Turing Complete no puede, excepto restringiendo artificialmente la construcción para que no sea Turing Complete.
supercat
5

Creo que se llama metaprogramación de plantillas .

Tom Ritter
fuente
2
Este es el lado útil. La desventaja es que dudo que la mayoría de la gente (y ciertamente no yo) llegue a comprender ni siquiera un pequeño porcentaje de lo que sucede en la mayoría de esas cosas. Es un material horriblemente ilegible e imposible de mantener.
Michael Burr
3
Ese es el inconveniente de todo el lenguaje C ++, creo. Se está convirtiendo en un monstruo ...
Federico A. Ramponi
C ++ 0x promete hacer mucho más fácil (y en mi experiencia, el mayor problema son los compiladores que no lo admiten completamente, lo que C ++ 0x no ayudará). Parece que los conceptos en particular aclararán las cosas, como deshacerse de muchas cosas de SFINAE, que son difíciles de leer.
Aprobado el
@MichaelBurr El comité de C ++ no se preocupa por las cosas ilegibles y que no se pueden mantener; simplemente les encanta agregar funciones.
Sapphire_Brick
4

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

Víctor Komarov
fuente
3

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


fuente
2

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

Precio de Matt
fuente
1

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>.

MSalters
fuente
0

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.

Roddy
fuente
4! puede tener 24, pero ¿cuál es MY_FAVORITE_MACRO_VALUE? ? Bien, tampoco creo que sea una buena idea.
Jeffrey L Whitledge
0

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

lsalamon
fuente
para los curiosos, la respuesta para x es pow (5,17 de profundidad);
fluyó el
Lo cual es mucho más simple de ver cuando se da cuenta de que los argumentos de la plantilla A y B no hacen nada y los eliminan, y luego reemplazan toda la suma con K17<Depth+1>::x * 5.
David Stone