c++ c++11 metaprogramming computation-theory constexpr

c++ - ¿Es el cálculo de Turing basado en constexpr completo?



c++11 metaprogramming (3)

Sabemos que la metaprogramación de la plantilla de C ++ está completa , pero no la metaprogramación del preprocesador .

C ++ 11 nos ofrece una nueva forma de metaprogramación: el cálculo de las funciones constexpr. ¿Es esta forma de computación Turing-completa? Estoy pensando que desde la recursión y el operador condicional (? :) están permitidos en las funciones constexpr, lo sería, pero me gustaría que alguien con más experiencia lo confirme.

Si tomamos en cuenta las restricciones de las computadoras reales, como la memoria finita y el valor finito de MAX_INT, entonces, por supuesto, constexpr (y también la totalidad de C ++) no es Turing-complete.

Pero si eliminamos esta restricción, por ejemplo, si pensamos en int como un entero positivo completamente arbitrario, entonces sí, la parte constante de C ++ se completará con Turing. Es fácil expresar cualquier función recursiva parcial.

0, S (n) = n + 1 y los selectores I_n ^ m (x_1, ..., x_n) = x_m y la superposición obviamente se pueden expresar usando constexpr.

La recursión primitiva se puede hacer de manera directa:

constexpr int h(int x1, ..., int xn, int y) { return (xn == 0) ? f(x1, ..., xn) : g(x1, ..., xn, y-1, h(x1, ..., xn, y-1)); }

Y para una recursión parcial necesitamos un simple truco:

constexpr int h(int x1, ... int xn, int y = 0) { return (f(x1, ... xn, y) == 0) ? y : h(x1, ..., xn, y+1); }

Entonces obtenemos cualquier función de recursión parcial como constexpr.

tl; dr: constexpr en C ++ 11 no se completó con Turing, debido a un error en la especificación del lenguaje, pero ese error se solucionó en los últimos borradores de la norma y Clang ya implementa la solución.

constexpr , como se especifica en la norma internacional ISO C ++ 11, no es Turing-complete. Prueba de boceto:

  • El resultado (o no terminación) de cada función constexpr en una secuencia particular de argumentos, a... , está determinado solo por los valores de a...
  • Cada valor de argumento que se puede construir dentro de una expresión constante debe ser de un tipo literal, que por [basic.types]p10 es:
    • un tipo escalar,
    • una referencia,
    • una matriz de tipo literal, o
    • un tipo de clase
  • Cada uno de los casos anteriores tiene un conjunto finito de valores.
    • Para un tipo escalar, sin puntero, esto sigue trivialmente.
    • Para que un puntero o referencia se use en una expresión constante, debe inicializarse mediante una dirección o una expresión constante de referencia, por lo que debe referirse a un objeto con una duración de almacenamiento estática, de la cual solo hay una cantidad finita en cualquier programa.
    • Para una matriz, el límite debe ser una constante, y cada miembro debe inicializarse mediante una expresión constante, de la que sigue el resultado.
    • Para un tipo de clase, hay un número finito de miembros, y cada miembro debe ser de tipo literal e inicializado por una expresión constante, de la que sigue el resultado.
  • Por lo tanto, el conjunto de posibles entradas a... que f puede recibir es finito, por lo que cualquier sistema constexpr descrito constexpr es una máquina de estados finitos y, por lo tanto, no está completo en Turing.

Sin embargo, desde la publicación del estándar C ++ 11, la situación ha cambiado.

El problema descrito en la respuesta de Johannes Schaub a std :: max () y std :: min () no constexpr se informó al comité de estandarización de C ++ como un problema central de 1454. En la reunión de WG21 de febrero de 2012, decidimos que esto era un defecto en el estándar y la resolución elegida incluían la capacidad de crear valores de tipos de clase con punteros o miembros de referencia que designan temporarios. Esto permite que se acumule y procese una cantidad ilimitada de información mediante una función constexpr , y es suficiente para que la evaluación constexpr completa (suponiendo que la implementación admita la recursión a una profundidad ilimitada).

Para demostrar la integridad de Turing de constexpr para un compilador que implementa la resolución propuesta del problema principal 1454, escribí un simulador de Turing-machine para el conjunto de pruebas de Clang:

http://llvm.org/svn/llvm-project/cfe/trunk/test/SemaCXX/constexpr-turing.cpp

Las versiones troncales de g ++ y clang implementan la resolución de este problema central, pero la implementación de g ++ actualmente no puede procesar este código.