Ist der C99-Präprozessor Turing fertig?

73

Nachdem ich die Funktionen des Boost-Präprozessors entdeckt hatte, fragte ich mich: Ist der C99-Präprozessor Turing vollständig?

Wenn nicht, was fehlt es, um sich nicht zu qualifizieren?

Anycorn
quelle
7
Das Fehlende in CPP für die Vollständigkeit ist im Wesentlichen die Rekursion, da sie ohne sie nicht wiederholt werden kann (und wirklich eine ziemlich begrenzte Bedingung hat, da Sie Teile eines Makros nicht bedingt erweitern können)
Spudd86

Antworten:

34

Hier ist ein Beispiel für den Missbrauch des Präprozessors zur Implementierung einer Turing-Maschine. Beachten Sie, dass ein externes Build-Skript erforderlich ist, um die Ausgabe des Präprozessors in seine Eingabe zurückzugeben, sodass der Präprozessor an und für sich nicht vollständig ist. Trotzdem ist es ein interessantes Projekt.

Aus der Beschreibung des zuvor verknüpften Projekts:

Der Präprozessor ist nicht vollständig, zumindest nicht, wenn das Programm nur einmal vorverarbeitet wird. Dies gilt auch dann, wenn das Programm sich selbst einschließen darf. (Der Grund dafür ist, dass der Präprozessor für ein bestimmtes Programm nur eine begrenzte Anzahl von Zuständen sowie einen Stapel hat, der aus den Stellen besteht, von denen die Datei aufgenommen wurde. Dies ist nur ein Push-Down-Automat.)

Die Antwort von Paul Fultz II ist ziemlich beeindruckend und sicherlich näher, als ich dachte, dass der Präprozessor jemals bekommen könnte, aber es ist keine echte Turing-Maschine. Der C-Präprozessor hat bestimmte Grenzen, die verhindern, dass er ein beliebiges Programm wie eine Turing-Maschine ausführt, selbst wenn Sie unendlich viel Speicher und Zeit haben. Abschnitt 5.2.4.1 der C-Spezifikation enthält die folgenden Mindestgrenzen für einen C-Compiler:

  • 63 Verschachtelungsebenen von Ausdrücken in Klammern innerhalb eines vollständigen Ausdrucks
  • 63 signifikante Anfangszeichen in einem internen Bezeichner oder einem Makronamen
  • 4095 Makrokennungen, die gleichzeitig in einer Vorverarbeitungsübersetzungseinheit definiert sind
  • 4095 Zeichen in einer logischen Quellzeile

Der folgende Zählermechanismus erfordert eine Makrodefinition pro Wert, sodass die Begrenzung der Makrodefinition die Anzahl der Schleifen begrenzt ( EVAL(REPEAT(4100, M, ~))was zu undefiniertem Verhalten führen würde). Dies begrenzt im Wesentlichen die Komplexität des Programms, das Sie ausführen können. Die Verschachtelung und Komplexität der mehrstufigen Erweiterungen kann auch eine der anderen Grenzen erreichen.

Dies unterscheidet sich grundlegend von der Einschränkung "unendlicher Speicher". In diesem Fall besagt die Spezifikation ausdrücklich, dass ein standardkonformer C-Compiler diese Grenzwerte nur einhalten muss, selbst wenn er unendlich viel Zeit, Speicher usw. hat. Jede Eingabedatei, die diese Grenzwerte überschreitet, kann auf unvorhersehbare oder undefinierte Weise verarbeitet werden (oder direkt abgelehnt). Einige Implementierungen haben möglicherweise höhere oder gar keine Grenzwerte, dies wird jedoch als "implementierungsspezifisch" angesehen und ist nicht Teil des Standards. Es kann möglich sein, die Methode von Paul Fultz II zu verwenden, um so etwas wie eine Turing-Maschine auf einer bestimmten Compiler-Implementierung zu implementierendas hat keine endlichen Grenzen, aber im allgemeinen Sinne von "kann dies auf jedem beliebigen, standardkonformen C99-Vorprozessor durchgeführt werden" lautet die Antwort nein. Da die Grenze hier in die Sprache selbst eingebaut ist und nicht nur ein Nebeneffekt unserer Unfähigkeit ist, einen unendlichen Computer zu konstruieren, sage ich, dass dies die Vollständigkeit von Turing bricht.

bta
quelle
12
Diese Antwort ist falsch, wie die 77-Punkte-Antwort unten ausführlich zeigt. Bitte akzeptiere es nicht und akzeptiere die nützlichere Antwort, danke.
Nachtpool
Wenn Sie die 115-Punkte-Antwort von Paul Fultz II unten meinen: Sie bestätigt diese Antwort.
Reinierpost
1
Die Grenze liegt in der Sprache selbst, aber nicht aufgrund der Spezifikation, sondern weil wir die Scans schreiben müssen, um den Algorithmus in der Sprache selbst zu bewerten. Es gibt keinen Mechanismus, um eine unendliche Anzahl von Scans anzuwenden.
Paul Fultz II
141

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

Der einfachste Weg, eine Rekursion im Präprozessor durchzuführen, ist die Verwendung eines verzögerten Ausdrucks. Ein verzögerter Ausdruck ist ein Ausdruck, für dessen vollständige Erweiterung mehr Scans erforderlich sind:

#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? Wenn ein Makro gescannt und erweitert wird, entsteht ein deaktivierender Kontext. Durch das Deaktivieren des Kontexts wird ein Token, das sich auf das aktuell expandierende Makro bezieht, blau dargestellt. Sobald es blau gestrichen ist, wird das Makro nicht mehr erweitert. Aus diesem Grund werden Makros nicht rekursiv erweitert. Ein deaktivierender Kontext ist jedoch nur während eines Scans vorhanden. Wenn Sie also eine Erweiterung verschieben, können Sie verhindern, dass unsere Makros blau angezeigt werden. Wir müssen nur mehr Scans auf den Ausdruck anwenden. Wir können das mit diesem EVALMakro machen:

#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 ein REPEATMakro mithilfe der Rekursion implementieren möchten, benötigen wir zunächst einige Inkrementierungs- und Dekrementierungsoperatoren, um den Status zu verarbeiten:

#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, um Logik zu machen:

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

Mit all diesen Makros können wir jetzt ein rekursives REPEATMakro schreiben . Wir verwenden ein REPEAT_INDIRECTMakro, um rekursiv auf sich selbst zurückzugreifen. Dies verhindert, dass das Makro blau gezeichnet wird, da es bei einem anderen Scan erweitert wird (und einen anderen Deaktivierungskontext verwendet). Wir verwenden OBSTRUCThier, wodurch die Erweiterung zweimal verschoben wird. Dies ist erforderlich, da die Bedingung WHENbereits einen Scan anwendet.

#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

Dieses Beispiel ist aufgrund der Einschränkungen des Zählers auf 10 Wiederholungen beschränkt. Genau wie ein Wiederholungszähler in einem Computer durch den endlichen Speicher begrenzt wäre. Wie bei einem Computer können mehrere Wiederholungszähler kombiniert werden, um diese Einschränkung zu umgehen. Darüber hinaus könnten wir ein FOREVERMakro definieren :

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

Dies wird versuchen, für ?immer auszugeben , wird aber irgendwann aufhören, weil keine Scans mehr angewendet werden. Die Frage ist nun, ob dieser Algorithmus abgeschlossen wäre, wenn wir unendlich viele Scans durchführen würden. Dies ist als Stoppproblem bekannt, und die Vollständigkeit von Turing ist erforderlich, um die Unentscheidbarkeit des Stoppproblems zu beweisen. Wie Sie sehen können, kann der Präprozessor als vollständige Turing-Sprache fungieren, aber anstatt auf den endlichen Speicher eines Computers beschränkt zu sein, wird er stattdessen durch die endliche Anzahl der angewendeten Scans begrenzt.

Paul Fultz II
quelle
7
...Beeindruckend. Sehr beeindruckend! Hier dachte ich, dass der C99-Präprozessor definitiv nicht vollständig war. +1 für
unkonventionelles
+1 Eine ziemlich kreative Art zu zeigen, dass der Präprozessor Symbole auf einem Band scannen kann ;-) (Dank des Mods für das Akzeptieren der Markierung zum Entfernen des Wikis!).
PP
Mir gefällt, wie dies O (log (N)) - Makros verwendet, um N-mal zu rekursieren. Dies ist besser als der Boost-Präprozessor, der O (N) -Makros verwendet.
qbt937
5
Die begrenzte Anzahl von Scans ist analog zu einem Computer mit begrenztem Speicher nicht analog. Das Wesentliche an der Vollständigkeit von Turing ist, dass die Spezifikation der Berechnungen selbst keine Einschränkungen enthält, selbst wenn sie tatsächlich auf einer Maschine mit begrenzter Kapazität ausgeführt werden.
Reinierpost
1
@Paul Fultz II Weil Sie a priori über diese Funktion Bescheid wissen, wird sie beendet, es wurde bewiesen. Sie brauchen also nur eine begrenzte Zeit, um fertig zu werden. Die mu-rekursiven Funktionen, wie die Suche nach einer Lösung einer beliebigen Gleichung, können nicht mit cpp berechnet werden. Ich sagte, dass cpp die Klasse von mu rekursiv nicht berechnen kann, kein bestimmtes Funktionsbeispiel über Sie weiß bereits viele Dinge.
Alinsoar
5

Um Turing vollständig zu machen, muss man eine Rekursion definieren, die möglicherweise nie beendet wird - man nennt sie mu-rekursiven Operator .

Um einen solchen Operator zu definieren, benötigt man einen unendlichen Raum definierter Bezeichner (falls jeder Bezeichner eine endliche Anzahl von Malen ausgewertet wird), da man a priori keine obere Zeitgrenze kennen kann, in der das Ergebnis gefunden wird. Bei einer endlichen Anzahl von Operatoren im Code muss man in der Lage sein, eine unbegrenzte Anzahl von Möglichkeiten zu prüfen.

Daher kann diese Funktionsklasse vom C-Präprozessor nicht berechnet werden, da im C-Präprozessor eine begrenzte Anzahl definierter Makros vorhanden ist und jedes nur einmal erweitert wird.

Der C-Präprozessor verwendet den Dave Prosser-Algorithmus (1984 von Dave Prosser für das WG14-Team geschrieben). Bei diesem Algorithmus wird ein Makro im Moment der ersten Erweiterung blau gezeichnet. Ein rekursiver Aufruf (oder ein gegenseitiger rekursiver Aufruf) erweitert ihn nicht, da er bereits zu Beginn der ersten Erweiterung blau gestrichen wurde. Mit einer endlichen Anzahl von Vorverarbeitungszeilen ist es daher unmöglich, unendlich viele Funktionen (Makros) aufzurufen, die die mu-rekursiven Operatoren charakterisieren.

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

Einzelheiten finden Sie im Berechnungsverlauf von Marvin L. Minsky (1967) - Berechnung: Endliche und unendliche Maschinen , Prentice-Hall, Inc. Englewood Cliffs, NJ usw.

Alinsoar
quelle
Die Ackerman-Funktion, die nur mu-rekursiv ist, kann im PP implementiert werden, sodass der C-Präprozessor nicht nur auf sigma-rekursive Operatoren beschränkt ist: gist.github.com/pfultz2/80391e8b18abf3225da2242dcc570cec
Paul Fultz II
2
Wie ich im anderen Kommentar sagte, ist es ein Unterschied zwischen dem, was Sie getan haben, eine große (aber begrenzte) Anzahl von Eingaben zu überprüfen und eine unendliche Anzahl zu suchen. Es ist bekannt, dass die Ackerman-Funktion beendet ist. Deshalb kann cpp ihren Wert finden. Es ist unmöglich, einen mu-Operator zu berechnen und cpp turing vollständig zu machen.
Alinsoar
@PaulFultzII Sie müssen Ihren Code ändern, um nach einem größeren Raum von Lösungen zu suchen, während ein mu-Operator festgelegt ist und nach einem unendlichen Raum sucht (so groß, wie es die Hardwareressourcen zulassen).
Alinsoar
Der Algorithmus (dh das AMakro) muss nicht geändert werden, nur die Auswertung muss aktualisiert werden, um weitere Scans hinzuzufügen.
Paul Fultz II
4

Es ist Turing vollständig in Grenzen (wie alle Computer, da sie nicht unendlich viel RAM haben). Schauen Sie sich an, was Sie mit Boost Preprocessor tun können .

Bearbeiten als Antwort auf Fragenänderungen:

Die Hauptbeschränkung von Boost ist die maximale Makroerweiterungstiefe, die compilerspezifisch ist. Außerdem sind die Makros, die die Rekursion implementieren (FOR ..., ENUM ... usw.), nicht wirklich rekursiv. Sie werden dank einer Reihe nahezu identischer Makros nur so angezeigt. Im Großen und Ganzen unterscheidet sich diese Einschränkung nicht von einer maximalen Stapelgröße in einer tatsächlich rekursiven Sprache.

Die einzigen zwei Dinge, die für eine eingeschränkte Turing-Vollständigkeit (Turing-Kompatibilität?) Wirklich notwendig sind, sind Iteration / Rekursion (äquivalente Konstrukte) und bedingte Verzweigung.

Zahnrad
quelle
Hallo. Das war eigentlich der Grund für meine Frage, ich benutze den Präprozessor schon eine Weile.
Anycorn
Das Stöbern im Quellcode von BOOST_PP ist der beste Weg, um herauszufinden, wie es gemacht wird.
Zahnrad
13
Ich glaube, dass Makros keine Rekursion durchführen können. Boost scheint nur sich wie benannt , indem man fest einprogrammierten Makros zu simulieren macro0, macro1.. macro255. Ich bin mir nicht sicher, ob das als "vollständig" gilt. Der Präprozessor hat eine explizite Regel, die es verbietet, von macro255zurück zu macro0:( Es scheint, als würde versucht, einen Verifizierer für vollständig in Klammern gesetzte Ausdrücke mithilfe eines Automaten mit endlichen Zuständen zu erstellen. Er kann für eine begrenzte Anzahl von Klammern verwendet werden, aber das ist kein allgemeiner Verifizierer mehr. Ich habe jedoch keine Ahnung über das Innenleben von boost.pp, daher könnte ich mich wahrscheinlich irren.
Johannes Schaub - litb
@ Johannes Schaub: Ja du hast recht. Ich hatte das mit vararg verwechselt, als ich das anfangs schrieb. Ich habe die Antwort aktualisiert.
Zahnrad
5
@Johannes: Der Chaos-Präprozessor hat keine solchen Makros. Überprüfen Sie es hier: sourceforge.net/projects/chaos-pp
Joe D