Le préprocesseur C99 est-il complet à la Turing ?

Question

Après avoir découvert le Renforcer les capacités du préprocesseur Je me suis demandé : Le préprocesseur C99 est-il complet à la Turing ?

Si non, que manque-t-il pour ne pas être qualifié ?

Answer 1

Les macros ne se développent pas directement de manière récursive, mais il existe des moyens de contourner ce problème.

La façon la plus simple de faire de la récursion dans le préprocesseur est d'utiliser une expression différée. Une expression différée est une expression qui nécessite plus de balayages pour se développer complètement :

#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

Pourquoi est-ce important ? Eh bien, lorsqu'une macro est analysée et se développe, elle crée un contexte de désactivation. Ce contexte de désactivation fait en sorte qu'un jeton, qui fait référence à la macro en cours d'expansion, soit peint en bleu. Ainsi, une fois qu'il est peint en bleu, la macro ne se développe plus. C'est pourquoi les macros ne se développent pas de manière récursive. Cependant, un contexte de désactivation n'existe que pendant un seul balayage, donc en différant une expansion, nous pouvons empêcher nos macros de devenir bleues. Nous devrons simplement appliquer plus de balayages à l'expression. Nous pouvons le faire en utilisant ceci 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__

Maintenant, si nous voulons mettre en œuvre un REPEAT La macro utilisant la récursion, nous avons d'abord besoin de quelques opérateurs d'incrémentation et de décrémentation pour gérer l'état :

#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

Ensuite, nous avons besoin de quelques macros supplémentaires pour faire de la logique :

#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)

Maintenant, avec toutes ces macros, nous pouvons écrire une récursive REPEAT macro. Nous utilisons une REPEAT_INDIRECT pour faire référence à elle-même de manière récursive. Cela permet d'éviter que la macro ne soit peinte en bleu, puisqu'elle se développera sur une analyse différente (et en utilisant un contexte de désactivation différent). Nous utilisons OBSTRUCT ici, ce qui reportera deux fois l'expansion. Ceci est nécessaire parce que le conditionnel WHEN applique déjà un scan.

#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

Cet exemple est limité à 10 répétitions, en raison des limites du compteur. Tout comme un compteur de répétitions dans un ordinateur serait limité par la mémoire finie. Plusieurs compteurs de répétition pourraient être combinés ensemble pour contourner cette limitation, tout comme dans un ordinateur. En outre, nous pourrions définir un FOREVER macro :

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

Cela va essayer de produire ? pour toujours, mais s'arrêtera finalement parce qu'il n'y a plus d'analyses en cours. Maintenant, la question est la suivante : si nous lui donnons un nombre infini de balayages, cet algorithme s'arrêtera-t-il ? C'est ce qu'on appelle le problème de la halte, et la complétude de Turing est nécessaire pour prouver l'indécidabilité du problème de la halte. Ainsi, comme vous pouvez le constater, le préprocesseur peut agir comme un langage complet de Turing, mais au lieu d'être limité à la mémoire finie d'un ordinateur, il est limité par le nombre fini de scans appliqués.

Answer 2

Ici est un exemple d'abus du préprocesseur pour implémenter une machine de Turing. Notez qu'une construction externe script est nécessaire pour réinjecter la sortie du préprocesseur dans son entrée, donc le préprocesseur en lui-même n'est pas complet pour Turing. Néanmoins, c'est un projet intéressant.

Extrait de la description du projet susmentionné :

le préprocesseur est no Turing complet, du moins pas si le programme n'est prétraité qu'une seule fois. Ceci est vrai même si le programme est autorisé à s'inclure lui-même. (La raison étant que pour un programme donné, le préprocesseur n'a qu'un nombre fini d'états. d'états, plus une pile constituée des endroits d'où le fichier a été inclus. le fichier a été inclus. Il ne s'agit que d'un automate poussé vers le bas).

La réponse de Paul Fultz II est assez impressionnante et certainement plus proche que je ne le pensais du préprocesseur, mais ce n'est pas une véritable machine de Turing. Le préprocesseur C a certaines limites qui l'empêchent d'exécuter un programme arbitraire comme le ferait une machine de Turing, même si vous aviez une mémoire et un temps infinis. La section 5.2.4.1 de la norme C spec donne les limites minimales suivantes pour un compilateur C :

• 63 niveaux d'imbrication d'expressions entre parenthèses dans une expression complète
• 63 caractères initiaux significatifs dans un identifiant interne ou un nom de macro
• 4095 macro-identifiants définis simultanément dans une unité de traduction de prétraitement
• 4095 caractères dans une ligne source logique

Le mécanisme de compteur ci-dessous nécessite une définition de macro par valeur, donc la limite de définition de macro limitera le nombre de fois que vous pouvez boucler ( EVAL(REPEAT(4100, M, ~)) donnerait un comportement indéfini). Cela met essentiellement un plafond sur la complexité du programme que vous pouvez exécuter. L'imbrication et la complexité des expansions multi-niveaux peuvent également atteindre l'une des autres limites.

C'est fondamentalement différent de la limitation de la "mémoire infinie". Dans ce cas, la spécification indique spécifiquement qu'un compilateur C conforme aux normes doit uniquement se conformer à ces limites, même s'il dispose d'un temps, d'une mémoire, etc. infinis. Tout fichier d'entrée dépassant ces limites peut être traité d'une manière imprévisible ou non définie (ou carrément rejeté). Certaines implémentations peuvent avoir des limites plus élevées, ou pas de limites du tout, mais cela est considéré comme "spécifique à l'implémentation" et ne fait pas partie de la norme. Il peut être possible d'utiliser la méthode de Paul Fultz II pour implémenter quelque chose comme une machine de Turing sur une implémentation spécifique du compilateur qui n'a pas de limites finies, mais dans un sens général de "cela peut-il être fait sur n'importe quel pré-processeur C99 arbitraire et conforme aux normes", la réponse est non. Puisque la limite ici est intégrée dans le langage lui-même et n'est pas simplement un effet secondaire de notre incapacité à construire un ordinateur infini, je dis que cela brise la complétude de Turing.

Answer 3

Pour être complet de Turing, il faut définir une récursion qui peut ne jamais se terminer -- on les appelle opérateur mu-récursif .

Pour définir un tel opérateur, il faut un espace infini d'identificateurs définis (dans le cas où chaque identificateur est évalué un nombre fini de fois), car on ne peut pas connaître a priori une limite supérieure de temps dans laquelle le résultat est trouvé. Avec un nombre fini d'opérateurs dans le code, il faut être capable de vérifier un nombre illimité de possibilités.

Alors cette classe de fonctions ne peut pas être calculée par le préprocesseur C car dans le préprocesseur C, le nombre de macros définies est limité et chacune d'entre elles n'est développée qu'une seule fois.

Le préprocesseur C utilise l'option L'algorithme de Dave Prosser (écrit par Dave Prosser pour l'équipe du WG14 en 1984). Dans cet algorithme, une macro est peinte en bleu au moment de la première expansion ; un appel récursif (ou un appel récursif mutuel) ne l'étend pas, car elle a déjà été peinte en bleu au moment où la première expansion commence. Ainsi, avec un nombre fini de lignes de prétraitement, il est impossible de faire des appels infinis de fonctions (macros), ce qui caractérise les opérateurs mu-récursifs.

Le préprocesseur C peut calculer seulement opérateurs sigma-récursifs .

Pour plus de détails, voir le cours de calcul de Marvin L. Minsky (1967) -- L'informatique : Machines finies et infinies Prentice-Hall, Inc. Englewood Cliffs, N.J. etc.

Answer 4

Il est complet selon Turing dans certaines limites (comme le sont tous les ordinateurs puisqu'ils n'ont pas une mémoire vive infinie). Regardez le genre de choses que vous pouvez faire avec Préprocesseur Boost .

Modifier en réponse aux modifications de la question :

La principale limitation de Boost est la profondeur maximale d'expansion des macros, qui est spécifique au compilateur. De plus, les macros qui implémentent la récursion (FOR..., ENUM..., etc.) ne sont pas vraiment récursives, elles ne font qu'apparaître comme telles grâce à un ensemble de macros presque identiques. Dans l'ensemble, cette limitation n'est pas différente de la taille maximale de la pile dans un langage réellement récursif.

Les deux seules choses qui sont vraiment nécessaires pour une complétude limitée de Turing (compatibilité de Turing ?) sont l'itération/récursion (constructions équivalentes) et le branchement conditionnel.