¿Está completo el cálculo basado en Constexpr?

Question

Sabemos que C++ template metaprogramming is Turing complete, pero preprocessor metaprogramming is not.

C++ 11 nos ofrece una nueva forma de metaprogramación: el cálculo de las funciones constexpr. ¿Esta forma de cálculo es Turing completa? Estoy pensando que, dado que la recursividad 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.

Answer 1

tl; dr: constexpr en C++ 11 no era Turing-completo, debido a un error en la especificación del lenguaje, pero ese error se ha abordado en versiones posteriores del estándar, y clang ya implementa la solución .

constexpr, como se especifica en el estándar internacional ISO C++ 11, no es Turing-complete. prueba Bosquejo:

• resultado Cada función constexprf 's (o no terminación) en una secuencia particular de argumentos, a..., se determina sólo por los valores de a...
• Cada valor de argumento que puede ser construido dentro de una expresión constante debe ser de un tipo literal, que por [basic.types]p10 es o bien:
  • 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, no puntero, esto sigue trivialmente.
  • Para que un puntero o referencia se use en una expresión constante, debe inicializarse mediante una dirección o expresión de constante de referencia, por lo que debe referirse a un objeto con duración de almacenamiento estático, del 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, a partir de la cual se obtiene 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, a partir de la cual se obtiene el resultado.
• Por lo tanto, el conjunto de posibles entradas a... que f puede recibir es finito, por lo que cualquier constexpr sistema descrito finitamente-es una máquina de estado finito, y por lo tanto no se Turing completo.

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 al std::max() and std::min() not constexpr se comunicó al comité de normalización de C++ como cuestión central 1454. En la reunión WG21 de febrero de 2012, decidimos que era un defecto en el estándar y la resolución elegida incluía la capacidad para crear valores de tipos de clase con puntero o miembros de referencia que designan temporales. Esto permite que una cantidad ilimitada de información sea acumulada y procesada por una función constexpr, y es suficiente para realizar la evaluación constexpr de Turing-complete (suponiendo que la implementación sea compatible con la recursión a una profundidad ilimitada).

Con el fin de demostrar la Turing-integridad de constexpr de un compilador que implementa la propuesta de resolución del problema central 1454, escribí un simulador de Turing-máquina para el conjunto de pruebas de sonido metálico:

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

versiones del tronco tanto de g ++ como de clang implementan la resolución de este problema central, pero la implementación de g ++ actualmente no puede procesar este código.

Answer 2

Echa un vistazo a estos. He compilado los ejemplos y trabajan en GCC 4.6: Compile-time computations, Parsing strings at compile-time - Part I, Parsing strings at compile-time - Part II

Answer 3

Si tomamos en cuenta las restricciones de ordenador real - como la memoria finita y un valor finito de MAX_INT - entonces, por supuesto, constexpr (y también todo el C++) no es Turing-completo.

Pero si eliminamos esta restricción, por ejemplo, si pensamos en int como un entero positivo completamente arbitario, entonces sí, una parte constestable de C++ será completa. 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 puede expresar usando constexpr.

recursividad primitiva se puede hacer que camino recto:

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 recursividad parcial necesitamos un truco sencillo:

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

por lo que tenemos una función parcial recursividad como constexpr.