Le complet C99 préprocesseur Turing?

https://stackoverflow.com/questions/3136686

01-10-2019
|

Question

Après avoir découvert les capacités du Boost préprocesseur Je me suis demandé: est-C99 préprocesseur complète Turing

Sinon, qu'est-ce que ce manque de ne pas se qualifier?

La solution

est un exemple d'avoir abusé de la préprocesseur pour mettre en œuvre une machine de Turing. Notez qu'un script de compilation externe est nécessaire pour alimenter le dos dans son entrée de sortie du préprocesseur, de sorte que le préprocesseur en soi n'est pas complète Turing. Pourtant, il est un projet intéressant.

De la description du projet ci-lié:

préprocesseur est pas Türing complète, du moins pas si le programme est prétraité qu'une seule fois. Cela est vrai même si le programme est autorisé à se comprendre. (La raison que pour un programme donné, le préprocesseur a seulement fini nombre d'états, en plus d'un empilement constitué par les endroits qui le fichier a été inclus à partir. Ceci est seulement un automate de poussée vers le bas.)

La réponse de Paul Fultz II est assez impressionnant et certainement plus que ce que je pensais que le préprocesseur pourrait jamais arriver, 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 une machine de Turing pourrait, même si vous aviez la mémoire et le temps infini. Section 5.2.4.1 du C spec donne les limites minimales suivantes pour un compilateur C:

63 niveaux d'imbrication d'expressions dans une expression parenthésées complète

63 caractères initiaux importants dans un identificateur interne ou un nom de macro

4095 identifiants de macros défini simultanément dans une unité de traduction de prétraitement

4095 caractères dans une ligne de source logique

Le mécanisme de compteur ci-dessous exige une définition de macro par valeur, de sorte que la limite de définition de macro limitera le nombre de fois que vous pouvez boucle (EVAL(REPEAT(4100, M, ~)) produirait un comportement non défini). Cela met essentiellement un plafond sur la complexité du programme que vous pouvez exécuter. L'imbrication et la complexité des extensions multi-niveaux peuvent frapper l'une des autres limites aussi bien.

Ceci est fondamentalement différent de la limitation « mémoire infinie ». Dans ce cas, la spécification dit expressément qu'un compilateur de standards conformes C est nécessaire uniquement pour se conformer à ces limites, même si elle a le temps infini, mémoire, etc. Tout fichier d'entrée dépassant ces limites peuvent être traitées de manière imprévisible ou non définie (ou carrément rejeté). Certaines mises en œuvre peuvent avoir des limites plus élevées, ou pas de limite du tout, mais qui est considéré comme « la mise en œuvre spécifique » et ne fait pas partie de la norme. Il est possible d'utiliser la méthode de Paul Fultz II pour mettre en œuvre quelque chose comme une machine de Turing sur une implémentation du compilateur spécifique qui n'a pas de limites finies, mais dans un sens général de « peut-il être fait sur tout arbitraire, normes conformes C99 pré-processeur », la réponse est non. Étant donné que la limite est construit ici dans la langue elle-même et non pas simplement un effet secondaire de notre incapacité à construire un ordinateur infini, je dis que les pauses Turing complet.

Autres conseils

macros Eh bien ne se développent pas directement récursive, mais il y a des façons dont nous pouvons travailler autour de cela.

La meilleure façon de faire 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 d'examens pour développer pleinement:

#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 quand une macro est numérisé et l'expansion, il crée un contexte invalidant. Ce contexte désactivation entraînera un jeton, qui fait référence à la macro actuellement en expansion, à peindre en bleu. Ainsi, une fois son peint en bleu, la macro ne sera plus développer. Voilà pourquoi les macros ne se développent pas récursive. Cependant, un contexte invalidante existe seulement pendant un balayage, donc en reportant une expansion, nous pouvons empêcher nos macros de devenir peint en bleu. Nous allons simplement besoin d'appliquer plus d'examens à l'expression. Nous pouvons le faire en utilisant cette 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__

Maintenant, si nous voulons mettre en œuvre une macro REPEAT utilisant récursion, nous devons d'abord certains opérateurs et décrémentation incrémentation état de la poignée:

#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, il faut un peu plus de macros pour faire 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 macro REPEAT récursive. Nous utilisons une macro REPEAT_INDIRECT de se référer à lui-même récursive. Cela empêche la macro d'être peints en bleu, car il développera une analyse différente (et en utilisant un contexte invalidant différent). Nous utilisons OBSTRUCT ici, qui reporteront l'expansion à deux reprises. Cela est nécessaire parce que le WHEN conditionnel 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

Maintenant cet exemple est limitée à 10 répétitions, en raison des limites du compteur. Tout comme un compteur de répétition dans un ordinateur serait limité par la mémoire finie. compteurs multiples répétées peuvent être combinés ensemble pour contourner cette limitation, tout comme dans un ordinateur. De plus, nous pourrions définir une macro FOREVER:

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

essayera de ? de sortie pour toujours, mais finira par arrêter parce qu'il n'y a plus d'analyses sont appliquées. Maintenant, la question est, si nous lui avons donné un nombre infini de scans serait-ce complet algorithme? Ceci est connu comme le problème de l'arrêt, et l'exhaustivité de Turing est nécessaire de prouver l'indécidabilité du problème de l'arrêt. Donc, comme vous pouvez le voir, le préprocesseur peut agir comme un langage complet Turing, mais au lieu d'être limité à la mémoire finie d'un ordinateur, il est plutôt limité par le nombre fini de scans appliqués.

Pour être complet, un Turing pour définir les besoins récursion qui ne peut jamais finir - on appelle eux opérateur mu-récursives .

Pour définir une telle une de l'opérateur a besoin d'un espace infini des identificateurs définis (dans le cas où chaque identificateur est évalué un nombre fini de fois), comme on ne peut pas savoir a priori une limite supérieure de temps qui se trouve le résultat. Avec un nombre fini d'opérateurs dans le code dont on a besoin pour être en mesure de vérifier un nombre illimité de possibilités.

cette classe de fonctions ne peut être calculée par le préprocesseur C parce que dans C préprocesseur il y a un nombre limité de macros définies et chacun est étendu qu'une seule fois.

Le préprocesseur C utilise le algorithme de Dave Prosser (écrit par Dave Prosser pour le GT14 équipe en 1984). Dans cet algorithme une macro est peinte en bleu au moment de la première expansion; un appel récursif (ou appel récursif mutuelle) ne se développe pas, comme il a déjà été peinte en bleu au moment où les premiers départs d'expansion. Donc, avec un nombre fini de lignes prétraitements il est impossible de faire des appels infinis de fonctions (macros), qui caractérise les opérateurs mu-récursives.

Le préprocesseur C peut calculer que opérateurs sigma-récursives .

Pour plus de détails voir le cours de calcul de Marvin L. Minsky (1967) - calcul: fini et infini Machines , Prentice-hall, Inc. Englewood Cliffs, NJ etc

Il est complet dans les limites Turing (comme tous les ordinateurs car ils ne disposent pas de RAM infinie). Découvrez le genre de choses que vous pouvez faire avec Boost préprocesseur .

Modifier en réponse à des modifications de question:

La principale limitation de poussée est la profondeur maximale d'extension macro qui est spécifique au compilateur. En outre, les macros qui mettent en œuvre récursion (pour ..., ENUM ..., etc.) ne sont pas vraiment récursive, ils semblent juste de cette façon grâce à un tas de macros quasi identiques. Dans la grande image, cette limitation est pas différent que d'avoir une taille de pile maximale dans une langue réellement récursive.

Les deux seules choses qui sont vraiment nécessaires pour Turing complet limitée (compatibilité Turing?) Sont itération / récursion (construit des équivalents) et branchement conditionnel.

Licencié sous: CC-BY-SA avec attribution

Non affilié à StackOverflow