Ist der C99 Präprozessor Turing abgeschlossen?

https://stackoverflow.com/questions/3136686

01-10-2019
|

Frage

Nach der Entdeckung der Boost-Präprozessor Fähigkeiten ich fragte mich: Ist der C99 Präprozessor Turing komplette

Wenn nicht, was bedeutet es fehlt nicht in Frage kommen?

Lösung

Hier ist ein Beispiel des Missbrauchs der Präprozessor eine Turing-Maschine zu implementieren. Beachten Sie, dass ein externer Build-Skript benötigt wird, um den Prä-Prozessor der Ausgabe zurück in seinen Eingang zu füttern, so dass der Prä-Prozessor an und für mich ist Turing nicht vollständig. Dennoch ist es ein interessantes Projekt.

Aus der Beschreibung des zuvor verknüpften Projektes:

der Präprozessor ist nicht Turing vollständig, zumindest nicht, wenn das Programm wird nur einmal vorverarbeitet. Dies gilt auch, wenn Das Programm darf sich aufzunehmen. (Der Grund dafür ist dass für ein bestimmtes Programm, hat der Präprozessor nur eine endliche Anzahl der Zustände, sowie einen Stapel der Orte besteht, die die Datei wurde von eingeschlossen. Dies ist nur ein Pushdown-Automaten).

Die Antwort von Paul Fultz II ist sehr beeindruckend und sicherlich näher, als ich der Präprozessor dachte jemals bekommen könnte, aber es ist nicht eine echte Turing-Maschine. Der C-Präprozessor hat bestimmte Grenzen, die es von der Ausführung eines beliebigen Programms wie eine Turing-Maschine verhindern könnte, auch wenn man unendlich Speicher und Zeit hatte. Abschnitt 5.2.4.1 der C spec gibt folgende Mindestgrenzen für einen C-Compiler:

63 Verschachtelungsebenen von geklammerten Ausdrücke innerhalb einer vollen Ausdruck

63 signifikante Anfangszeichen in einer internen Kennung oder ein Makroname

4095 Makroidentifizierer gleichzeitig in einer Vorverarbeitung Übersetzungseinheit definiert

4095 Zeichen in einer logischen Quellenleitung

Der Zählermechanismus erfordert unter einer Makrodefinition pro Wert, so dass die Naheinstellgrenze Definition wird begrenzen, wie oft können Sie Schleife (EVAL(REPEAT(4100, M, ~)) undefiniertes Verhalten ergeben würden). Dies stellt im Wesentlichen eine Obergrenze für die Komplexität des Programms, dass Sie ausführen können. Die Verschachtelung und die Komplexität der Multi-Level-Erweiterungen können auch eine der anderen Grenzen stoßen.

Dies ist grundlegend anders als die „unendliches Gedächtnis“ Begrenzung. In diesem Fall sagt die Spezifikation ausdrücklich, dass eine standardkonforme C-Compiler nur an diesen Grenzen entsprechen erforderlich ist, auch wenn es unendlich viel Zeit hat, Speicher, etc. Jede Eingabedatei diese Grenzen überschreiten, können in einer nicht vorhersehbaren oder nicht definierten Weise verarbeitet werden (oder abgelehnt geradezu). Einige Implementierungen können höhere Grenzen haben oder keine Grenzen überhaupt, aber das ist „Umsetzung spezifisch“ betrachtet und nicht Teil des Standards. Es kann möglich sein, Paul Fultz II-Verfahren zu implementieren so etwas wie eine Turing-Maschine auf einig spezifischen Compiler Implementierung , das hat keine endlichen Grenzen, aber in einem allgemeinen Sinne von „kann dies auf jedem beliebigen getan werden, zu verwenden, standardkonforme C99 pre-Prozessor“, lautet die Antwort nein. Da hier die Grenze in die Sprache integriert ist selbst und nicht nur ein Nebeneffekt unserer Unfähigkeit, einen unendlichen Computer zu konstruieren, sage ich, dass Turing Vollständigkeit bricht.

Andere Tipps

Nun Makros nicht erweitern direkt rekursiv, aber es gibt Möglichkeiten, wie wir dies umgehen können.

Der einfachste Weg, Rekursion im Preprocessor zu tun, ist ein latenter Ausdruck zu verwenden. Ein latenter Ausdruck ist ein Ausdruck, der mehr Scans vollständig zu erweitern erfordert:

#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

Warum ist das wichtig? Nun, wenn ein Makro gescannt und erweitert, es schafft einen Sperr Kontext. Diese Deaktivierung Zusammenhang wird ein Token führen, die auf den aktuell wachsenden Makro bezieht sich auf blau lackiert werden. Somit kann, sobald seine blau gestrichen, wird das Makro nicht mehr erweitern. Aus diesem Grunde Makros nicht rekursiv erweitern. Jedoch nur ein behindernder Kontext existiert während einer Abtastung, so durch eine Erweiterung aufzuschieben wir unsere Makros immer blau lackiert verhindern können. Wir werden nur mehr Scans auf den Ausdruck anwenden müssen. Wir können das mit dieser EVAL Makro tun:

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

Wenn wir nun eine REPEAT Makro Rekursion implementieren möchten, müssen wir zuerst einige Inkrement- und Dekrement-Operatoren zu Hantiererzustand:

#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

Als nächstes brauchen wir noch ein paar Makros Logik zu tun:

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

Jetzt mit all diesen Makros können wir eine rekursive REPEAT Makro schreiben. Wir verwenden ein REPEAT_INDIRECT Makro rekursiv auf sich selbst zu verweisen. Dies verhindert, dass von der Makro-blau lackiert werden, da sie auf einem anderen Scan (und unter Verwendung eines anderen Sperr Kontextes) erweitern. Wir verwenden OBSTRUCT hier, die zweimal die Expansion verzögern wird. Dies ist notwendig, da die bedingte WHEN gilt ein Scan bereits.

#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

Nun wird dieses Beispiel auf 10 Wiederholungen beschränkt, aufgrund von Einschränkungen des Zählers. Genau wie ein Wiederholungszähler in einem Computer würde durch den Finite-Speicher begrenzt werden. Mehrere Wiederholungszähler könnten miteinander kombiniert werden, um diese Einschränkung zu umgehen, wie in einem Computer. Darüber hinaus konnten wir einen FOREVER Makro definieren:

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

Dies wird zu einer Ausgabe ? versucht immer, aber wird schließlich aufhören, weil es keine weiteren Scans angewandt werden. Nun ist die Frage, ob wir es eine unendliche Anzahl von Scans würde diesen Algorithmus vollständig gegeben hat? Dies ist als das Halteproblem bekannt und Turing Vollständigkeit ist notwendig, um die Unentscheidbarkeit des Halteproblems zu beweisen. So wie Sie sehen können, kann der Präprozessor als Turing komplette Sprache handeln, sondern von dem endlichen Speicher eines Computers begrenzt ist es stattdessen durch die endliche Anzahl von Scans beschränkt angewandt wird.

Um Turing abgeschlossen ist, braucht man Rekursion zu definieren, die nie beenden können - man nennt sie mu rekursive Operator .

So definieren Sie einen solchen Operator braucht man einen unendlichen Raum von definierten Kennungen (in dem Fall, dass jede Kennung eine endliche Anzahl von Malen ausgewertet wird), da man nicht wissen kann, a priori eine Obergrenze von Zeit in die das Ergebnis gefunden. Mit einer endlichen Anzahl von Betreibern innerhalb der Code braucht man in der Lage sein, eine unbegrenzte Anzahl von Möglichkeiten zu überprüfen.

So diese Klasse von Funktionen kann nicht durch die C berechnet werden Präprozessor , weil in C-Präprozessor gibt es eine begrenzte Anzahl von definierten Makros und jeder erweitert wird nur einmal.

Das C-Präprozessor verwendet den Dave Prosser Algorithmus (geschrieben von Dave Prosser für die WG14 Team im Jahr 1984). In diesem Algorithmus wird ein Makro in dem Moment des ersten Expansions blau gestrichen; ein rekursive Aufruf (oder gegenseitiger rekursiven Aufruf) ist es nicht erweitern, da es bereits in dem Moment blau, wenn die erste Erweiterung beginnt gemalt wurde. Also mit einer endlichen Anzahl von Vorverarbeitung Linien ist es unmöglich, unendlich Anrufe von Funktionen (Makros), die da mu-rekursive Operatoren charakterisieren.

Das C-Präprozessor kann nur berechnen Sigma-rekursive Operatoren .

Für Details siehe den Verlauf der Berechnung von Marvin L. Minsky (1967) - Berechnung: endlichen und Unendlichen Maschinen , Prentice-Hall, Inc. Ewood Cliffs, New Jersey etc

Es ist Turing vollständig in Grenzen (wie alle Computer, da sie nicht unendlich RAM). Schauen Sie sich die Art von Dingen aus Sie tun können, mit -Boost Preprocessor .

In Antwort auf Frage Änderungen:

Die wichtigste Einschränkung auf Boost ist die maximale Makroerweiterung Tiefe, die Compiler-spezifisch ist. Außerdem werden die Makros, die Rekursion implementieren (FOR ..., ENUM ..., etc.) sind nicht wirklich rekursiv, erscheinen sie nur auf diese Weise dank einer Reihe von nahezu identische Makros. In dem großen Bild, ist diese Einschränkung nicht anders als eine maximale Stapelgröße in einer tatsächlich rekursive Sprache hat.

Die beiden einzigen Dinge, die wirklich notwendig für eine begrenzte Turing-Vollständigkeit sind (Turing-Kompatibilität?) Sind Iteration / Rekursion (äquivalente Konstrukte) und bedingte Verzweigungen.

Lizenziert unter: CC-BY-SA mit Zuschreibung

Nicht verbunden mit StackOverflow