¿La metaprogramación del preprocesador C++ es Turing-completa?

Question

Sé que la metaprogramación de plantillas C++ es Turing-completa. ¿Lo mismo vale para la metaprogramación de preprocesador?

Answer 1

No. El preprocesador de C++ no permite un estado ilimitado. Solo tiene un número finito de estados de encendido/apagado, más una pila de inclusión. Esto lo convierte en un autómata pushdown, no en una máquina de turing (esto también ignora el hecho de que la recursión del preprocesador es limitada, pero también lo es la recursión de la plantilla).

Sin embargo, si dobla sus definiciones un poco, esto es posible invocando el preprocesador varias veces - al permitir que el preprocesador genere un programa que vuelve a invocar el preprocesador, y que se repite externamente, es indeed possible to make a turing machine with the preprocessor. El ejemplo vinculado utiliza C, pero debe ser adaptable a C++ con la suficiente facilidad.

Answer 2

Las macros de pozo no se expanden recursivamente directamente, pero hay formas en que podemos evitar esto.

La manera más fácil de hacer recursividad en el preprocesador es usar una expresión diferida. Una expresión diferida es una expresión que requiere más análisis para expandir completamente:

#define EMPTY() 
#define DEFER(id) id EMPTY() 
#define OBSTRUCT(...) __VA_ARGS__ DEFER(EMPTY)() 
#define EXPAND(...) __VA_ARGS__ 

#define A() 123 
A() // Expands to 123 
DEFER(A)() // Expands to A() because it requires one more scan to fully expand 
EXPAND(DEFER(A)()) // Expands to 123, because the EXPAND macro forces another scan 

¿Por qué es esto importante? Bueno, cuando se escanea y se expande una macro, crea un contexto de deshabilitación. Este contexto de desactivación hará que un token, que se refiere a la macro que se está expandiendo actualmente, se pinte en azul. Por lo tanto, una vez que esté pintada de azul, la macro ya no se expandirá. Esta es la razón por la cual las macros no se expanden recursivamente. Sin embargo, un contexto de deshabilitación solo existe durante un escaneo, por lo que posponiendo una expansión podemos evitar que nuestras macros se pinten de azul. Solo necesitaremos aplicar más escaneos a la expresión. Podemos hacer que el uso de este EVAL macro:

#define EVAL(...) EVAL1(EVAL1(EVAL1(__VA_ARGS__))) 
#define EVAL1(...) EVAL2(EVAL2(EVAL2(__VA_ARGS__))) 
#define EVAL2(...) EVAL3(EVAL3(EVAL3(__VA_ARGS__))) 
#define EVAL3(...) EVAL4(EVAL4(EVAL4(__VA_ARGS__))) 
#define EVAL4(...) EVAL5(EVAL5(EVAL5(__VA_ARGS__))) 
#define EVAL5(...) __VA_ARGS__ 

Ahora bien, si queremos implementar un REPEAT macro utilizando la recursividad, primero necesitamos algunos operadores de incremento y decremento para manejar Estado:

#define CAT(a, ...) PRIMITIVE_CAT(a, __VA_ARGS__) 
#define PRIMITIVE_CAT(a, ...) a ## __VA_ARGS__ 

#define INC(x) PRIMITIVE_CAT(INC_, x) 
#define INC_0 1 
#define INC_1 2 
#define INC_2 3 
#define INC_3 4 
#define INC_4 5 
#define INC_5 6 
#define INC_6 7 
#define INC_7 8 
#define INC_8 9 
#define INC_9 9 

#define DEC(x) PRIMITIVE_CAT(DEC_, x) 
#define DEC_0 0 
#define DEC_1 0 
#define DEC_2 1 
#define DEC_3 2 
#define DEC_4 3 
#define DEC_5 4 
#define DEC_6 5 
#define DEC_7 6 
#define DEC_8 7 
#define DEC_9 8 

siguiente que necesitamos un poco más de macros para hacer la lógica:

#define CHECK_N(x, n, ...) n 
#define CHECK(...) CHECK_N(__VA_ARGS__, 0,) 

#define NOT(x) CHECK(PRIMITIVE_CAT(NOT_, x)) 
#define NOT_0 ~, 1, 

#define COMPL(b) PRIMITIVE_CAT(COMPL_, b) 
#define COMPL_0 1 
#define COMPL_1 0 

#define BOOL(x) COMPL(NOT(x)) 

#define IIF(c) PRIMITIVE_CAT(IIF_, c) 
#define IIF_0(t, ...) __VA_ARGS__ 
#define IIF_1(t, ...) t 

#define IF(c) IIF(BOOL(c)) 

#define EAT(...) 
#define EXPAND(...) __VA_ARGS__ 
#define WHEN(c) IF(c)(EXPAND, EAT) 

Ahora con todas estas macros podemos escribir una macro recursiva REPEAT. Usamos una macro REPEAT_INDIRECT para referirnos a ella recursivamente. Esto evita que la macro se vea pintada de azul, ya que se expandirá en una exploración diferente (y utilizando un contexto de desactivación diferente). Usamos OBSTRUCT aquí, lo que retrasará la expansión dos veces. Esto es necesario porque el condicional WHEN aplica ya un escaneo.

#define REPEAT(count, macro, ...) \ 
    WHEN(count) \ 
    (\ 
     OBSTRUCT(REPEAT_INDIRECT)() \ 
     (\ 
      DEC(count), macro, __VA_ARGS__ \ 
     ) \ 
     OBSTRUCT(macro) \ 
     (\ 
      DEC(count), __VA_ARGS__ \ 
     ) \ 
    ) 
#define REPEAT_INDIRECT() REPEAT 

//An example of using this macro 
#define M(i, _) i 
EVAL(REPEAT(8, M, ~)) // 0 1 2 3 4 5 6 7 

Ahora, este ejemplo está limitado a 10 repeticiones, debido a las limitaciones del contador. Al igual que un contador de repetición en una computadora estaría limitado por la memoria finita. Se pueden combinar varios contadores de repetición para solucionar esta limitación, como en una computadora. Por otra parte, podríamos definir una macro FOREVER:

#define FOREVER() \ 
    ? \ 
    DEFER(FOREVER_INDIRECT)()() 
#define FOREVER_INDIRECT() FOREVER 
// Outputs question marks forever 
EVAL(FOREVER()) 

Este tratará de salida ? para siempre, pero con el tiempo detendremos porque no hay más exploraciones que se aplica. Ahora la pregunta es, si le diéramos un número infinito de escaneos, ¿se completaría este algoritmo? Esto se conoce como el problema de detención, y la integridad de Turing es necesaria para demostrar la indecibilidad del problema de detención.Como puede ver, el preprocesador puede actuar como un lenguaje completo de Turing, pero en lugar de estar limitado a la memoria finita de una computadora, está limitado por el número finito de escaneos aplicados.