Es la completa C99 preprocesador de Turing?

https://stackoverflow.com/questions/3136686

01-10-2019
|

Pregunta

Después de descubrir las capacidades de la Boost de preprocesador me pregunté: ¿Es la C99 preprocesador Turing completa ?

Si no es así, ¿qué falta para no calificar?

Solución

Aquí es un ejemplo de abusar del preprocesador para implementar una máquina de Turing. Tenga en cuenta que se necesita un script de construcción externa para realimentar la salida del preprocesador en su entrada, por lo que el preprocesador de por sí no es Turing completo. Aún así, es un proyecto interesante.

A partir de la descripción del proyecto ligado anteriormente:

el preprocesador es no Turing completo, al menos no si el programa es preprocesada sólo una vez. Esto es cierto incluso si el programa se permite incluir en sí. (La razón es que para un programa dado, el preprocesador sólo tiene un número finito número de estados, además de una pila que consiste en los lugares que el archivo se ha incluido a partir. Esto es sólo un autómata de empujar hacia abajo.)

La respuesta de Paul Fultz II es bastante impresionante y sin duda más cerca de lo que pensaba el preprocesador que pudo tener, pero no es una verdadera máquina de Turing. El preprocesador C tiene ciertos límites que le impiden la ejecución de un programa arbitrario como una máquina de Turing podría, incluso si tuviera memoria y el tiempo infinito. Sección 5.2.4.1 de la C spec da los siguientes límites mínimos para un compilador C:

63 niveles de imbricación de las expresiones entre paréntesis dentro de una expresión completa
63 caracteres iniciales significativas en un identificador interno o un nombre de macro

4095 identificadores de macro simultáneamente se define en una unidad de traducción preprocesamiento

4095 caracteres en una línea de fuente lógica

El mecanismo contador a continuación requiere una definición de macro por valor, por lo que el límite de definición de macro limitará el número de veces que se puede bucle (EVAL(REPEAT(4100, M, ~)) produciría un comportamiento indefinido). Esto pone esencialmente un límite en la complejidad del programa que se puede ejecutar. El anidamiento y la complejidad de las expansiones de varios niveles pueden golpear a uno de los otros límites también.

Esto es fundamentalmente diferente de la limitación "memoria infinita". En este caso, la especificación dice específicamente que un compilador normas conformes C sólo se requiere para cumplir con estos límites, incluso si no tiene tiempo infinito, la memoria, etc. Cualquier archivo de entrada que supere estos límites puede ser procesada de una manera impredecible o indefinido (o directamente desestimado). Algunas implementaciones pueden tener límites más altos, o no hay límites en absoluto, sino que se considera "aplicación específica" y no forma parte de la norma. Puede que sea posible utilizar el método de Pablo Fultz II para implementar algo así como una máquina de Turing en alguna aplicación específica compilador que no tiene límites finitos, pero en un sentido general de "se puede hacer esto en cualquier arbitraria, normas conformes C99 "en el procesador pre, la respuesta es no. Dado que el límite aquí está integrado en el lenguaje en sí mismo y no simplemente un efecto secundario de nuestra incapacidad para construir un equipo infinita, digo que rompe Turing completo.

Otros consejos

macros Well no se expanden directamente de forma recursiva, pero hay maneras en que podemos trabajar alrededor de esto.

La forma más fácil de hacer recursividad en el preprocesador es utilizar una expresión diferida. Una expresión diferida es una expresión que requiere más exploraciones de 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 importante esto? Bueno, cuando una macro se escanea y en expansión, que crea un contexto incapacitante. Este contexto deshabilitando causará una ficha, que hace referencia a la macro actualmente en expansión, a ser pintado de azul. Por lo tanto, una vez que su pintado azul, la macro dejará de expandirse. Es por esto que las macros no se expanden de forma recursiva. Sin embargo, la desactivación de un contexto sólo existe durante una exploración, por lo que mediante el aplazamiento de una expansión podemos evitar que nuestros macros se convierta pintado de azul. Sólo tendremos que aplicar más exploraciones para la expresión. Podemos hacer que el uso de 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 bien, si queremos implementar una macro REPEAT utilizando la recursividad, primero necesitamos algunos operadores de incremento y decremento de estado mango:

#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

Lo 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 se puede escribir una macro REPEAT recursiva. Utilizamos una macro REPEAT_INDIRECT para referirse de nuevo a sí mismo de forma recursiva. Esto evita que la macro de ser pintadas de azul, ya que se expandirá en un escáner diferente (y utilizando un contexto diferente incapacitante). Utilizamos OBSTRUCT aquí, que se aplazará la expansión en dos ocasiones. Esto es necesario debido a que el WHEN condicional se aplica una exploración 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á limitada a 10 repeticiones, debido a las limitaciones del contador. Al igual que un contador de repeticiones en un ordenador estaría limitado por la memoria finita. contadores de repetición múltiples pueden ser combinadas para solucionar esta limitación, al igual que en un ordenador. Además, podríamos definir una macro FOREVER:

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

Esto va a tratar de ? de salida para siempre, pero con el tiempo se detendrá, porque no hay más exploraciones que se aplica. Ahora la pregunta es, si es que le dimos un número infinito de exploraciones haría esta completa algoritmo? Esto se conoce como el problema de la parada, y Turing completo es necesario probar la indecidibilidad del problema de la parada. Así como se puede ver, el preprocesador puede actuar como un lenguaje Turing completo, pero en lugar de limitarse a la memoria finita de un ordenador en su lugar se limita por el número finito de ciclos aplicado.

Para ser Turing completo, hay que definir la recursividad que quizá nunca acabar - uno los llama mu-recursivas operador .

Para definir un uno de tales operador necesita un espacio infinito de identificadores definidos (en caso de que cada identificador se evalúa un número finito de veces), como uno no puede saber a priori un límite superior de tiempo en donde se ha encontrado el resultado. Con un número finito de los operadores en el código hay que ser capaz de verificar un número ilimitado de posibilidades.

Entonces esta clase de funciones no puede ser calculada por el preprocesador de C porque en C preprocesador hay un número limitado de macros definidos y cada uno se expande sólo una vez.

El preprocesador C utiliza el algoritmo de Dave Prosser (escrito por Dave Prosser para el WG14 equipo en 1984). En este algoritmo de una macro está pintado de azul en el momento de la primera expansión; una llamada recursiva (o llamada recursiva mutua) no se expande, como ya se ha pintado de azul en el momento en que las primeras aperturas de expansión. Así que con un número finito de líneas de pre-procesamiento es imposible hacer llamadas infinitas de funciones (macros), que caracteriza a los operadores mu-recursivas.

El preprocesador C puede calcular solamente operadores sigma-recursivas .

Para más detalles ver el curso de cálculo de Marvin L. Minsky (1967) - Cálculo: finito e infinito Máquinas , Prentice-Hall, Inc. Englewood Cliffs, NJ, etc.

Es de Turing completa dentro de los límites (como lo son todos los equipos, ya que no tienen memoria RAM infinita). Echa un vistazo a los tipos de cosas que puede hacer con Boost preprocesador .

Editar en respuesta a las ediciones de preguntas:

La principal limitación en Boost es la profundidad de expansión macro máximo que es el compilador específico. Además, las macros que implementan la recursividad (PARA ..., ENUM ..., etc.) no son realmente recursivo, que acaba de aparecer esa manera, gracias a un grupo de macros casi idénticos. En el panorama general, esta limitación no es diferente de tener un tamaño máximo de pila en un lenguaje recursiva.

Las únicas dos cosas que son realmente necesarios para la limitación de Turing-completo (Turing incompatibilidad?) Son iteración / recursividad (construcciones equivalentes) y la bifurcación condicional.

Licenciado bajo: CC-BY-SA con atribución

No afiliado a StackOverflow