c-preprocessor - programa - funcion preprocesador en c++

¿Está completo el preprocesador C99 Turing?

Question

Después de descubrir las capacidades del preprocesador Boost, me pregunté: ¿está completo el preprocesador C99 Turing?

Si no, ¿qué le falta no calificar?

Answer 1

Es Turing completo dentro de los límites (como todas las computadoras, ya que no tienen una RAM infinita). Vea los tipos de cosas que puede hacer con el preprocesador Boost .

Edite en respuesta a las ediciones de preguntas:

La principal limitación de Boost es la profundidad máxima de expansión de macro que es específica del compilador. Además, las macros que implementan la recursión (FOR ..., ENUM ..., etc.) no son verdaderamente recursivas, simplemente aparecen de esa manera gracias a un conjunto de macros casi idénticas. En general, esta limitación no es diferente de tener un tamaño de pila máximo en un lenguaje recursivo.

Las dos únicas cosas que son realmente necesarias para la compleción limitada de Turing (¿compatibilidad con Turing?) Son iteración / recursión (construcciones equivalentes) y ramificación condicional.

Answer 2

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

La forma 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 exploraciones para expandirse por completo:

#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

¿Porque 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 eso usando esta macro EVAL :

#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, si queremos implementar una macro REPEAT utilizando recursión, primero necesitamos algunos operadores de incremento y decremento para manejar el 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

A continuación, necesitamos algunas macros más para hacer 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 REPEAT recursiva. 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 WHEN condicional aplica un análisis ya.

#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. Además, podríamos definir una macro FOREVER :

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

Esto intentará dar salida ? para siempre, pero eventualmente se detendrá porque no se están aplicando más escaneos. 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.

Answer 3

Para ser completo, uno debe definir la recursión que nunca terminará (uno los llama operadores mu-recursivos - https://en.wikipedia.org/wiki/%CE%9C-recursive_function ).

Para definir dicho operador, se necesita un espacio infinito de identificadores (en caso de que cada identificador se evalúe un número finito de veces), ya que no se puede saber a priori un límite superior de tiempo en el que se encuentra el resultado. Con un número finito de operadores dentro del código, uno debe poder verificar un número ilimitado de posibilidades.

Entonces esta clase de funciones no puede ser calculada por el preprocesador C.

El preprocesador C solo puede calcular operadores sigma-recursivos: https://en.wikipedia.org/wiki/Primitive_recursive_function .

Para detalles, ver el curso de computación de Marvin L. Minsky (1967) - Computación: Máquinas finitas e infinitas, Prentice-Hall, Inc. Englewood Cliffs, NJ, etc.

Answer 4

Here hay un ejemplo de abuso del preprocesador para implementar una máquina de Turing. Tenga en cuenta que se necesita un script de compilación externo para devolver la salida del preprocesador a su entrada, por lo que el preprocesador en sí mismo no está completo. Aún así, es un proyecto interesante.

De la descripción del proyecto vinculado anteriormente:

el preprocesador no está completo, al menos no si el programa se preprocesa solo una vez. Esto es cierto incluso si el programa puede incluirse a sí mismo. (La razón es que para un programa dado, el preprocesador tiene solo un número finito de estados, más una pila que consta de los lugares de los que se ha incluido el archivo. Esto es solo un autómata de empuje hacia abajo).

La respuesta de Paul Fultz II es bastante impresionante y ciertamente más cercana de lo que pensé que el preprocesador podría obtener, pero no es una verdadera máquina de Turing. El preprocesador C tiene ciertos límites que le impiden ejecutar un programa arbitrario como podría hacerlo una máquina Turing, incluso si tuviera memoria y tiempo infinitos. La sección 5.2.4.1 de la especificación C proporciona los siguientes límites mínimos para un compilador de C:

• 63 niveles de anidamiento de expresiones entre paréntesis dentro de una expresión completa
• 63 caracteres iniciales significativos en un identificador interno o un nombre de macro
• Identificadores de macro 4095 definidos simultáneamente en una unidad de traducción de preprocesamiento
• 4095 caracteres en una línea fuente lógica

El siguiente mecanismo de contador requiere una macro definición por valor, por lo que el límite de definición de macro limitará la cantidad de veces que puede repetir ( EVAL(REPEAT(4100, M, ~)) generaría un comportamiento indefinido. Esto esencialmente pone un límite a la complejidad del programa que puede ejecutar. La anidación y la complejidad de las expansiones multinivel también pueden afectar a uno de los otros límites.

Esto es fundamentalmente diferente de la limitación de "memoria infinita". En este caso, la especificación dice específicamente que un compilador de C conforme a las normas solo debe cumplir con estos límites, incluso si tiene un tiempo infinito, memoria, etc. Cualquier archivo de entrada que exceda estos límites puede procesarse de manera impredecible o indefinida. (o directamente rechazado). Algunas implementaciones pueden tener límites más altos, o ningún límite en absoluto, pero eso se considera "específico de la implementación" y no parte del estándar. Es posible utilizar el método de Paul Fultz II para implementar algo así como una máquina de Turing en alguna implementación específica del compilador que no tenga límites finitos, pero en un sentido general de "¿se puede hacer esto en cualquier preprocesador C99 arbitrario y conforme a las normas? ", la respuesta es no. Dado que el límite aquí está integrado en el lenguaje en sí y no simplemente como un efecto secundario de nuestra incapacidad para construir una computadora infinita, digo que rompe la integridad de Turing.