C++プリプロセッサはメタプログラミングTuring-completeですか？

Question

私はC++テンプレートのメタプログラミングがTuring-completeであることを知っています。プリプロセッサのメタプログラミングにも同じことがありますか？

Answer 1

いいえ.C++プリプロセッサは、無制限の状態を許可していません。有限数のオン/オフ状態とインクルードスタックしかありません。これはチューリングマシンではなく、プッシュダウンオートマトンになります（これは、プリプロセッサの再帰が制限されているという事実も無視しますが、テンプレートの再帰もそうです）。

しかし、定義を少し曲げると、これはプリプロセッサを複数回呼び出すことによって可能です。プリプロセッサにプリプロセッサを再起動するプログラムを生成させ、外部にループすると、indeed possible to make a turing machine with the preprocessorになります。リンクされた例ではCを使用していますが、C++に容易に適応できるはずです。

Answer 2

ウェルマクロは再帰的に直接展開されませんが、これを回避する方法があります。

プリプロセッサで再帰を行う最も簡単な方法は、遅延式を使用することです。遅延式は、完全に展開するためにスキャンがさらに必要な式です。

#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 

なぜこれが重要ですか？マクロがスキャンされて展開されると、無効なコンテキストが作成されます。この無効化コンテキストにより、現在展開中のマクロを参照するトークンが青色に塗りつぶされます。したがって、一度その塗られた青、マクロはもはや拡張されません。これは、マクロが再帰的に展開されない理由です。ただし、無効にするコンテキストは1回のスキャン中にのみ存在するため、展開を延期することで、マクロが青く塗られないようにすることができます。表現にもっと多くのスキャンを適用するだけです。我々は行うことができ、このEVALマクロ使用：我々が必要

#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 

次へ：私たちが最初に私たちは状態を処理するために、いくつかのインクリメント必要、REPEATマクロ使って再帰を実装したい場合は今

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

を私たちは、再帰的REPEATマクロを書くことができ、すべてのこれらのマクロで今

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

：さらにいくつかのマクロは、ロジックを実行します。 REPEAT_INDIRECTマクロを使用して、再帰的に自身を参照します。これにより、マクロが青色に塗りつぶされるのを防ぎます。なぜなら、それは異なるスキャンで展開され、異なる無効化コンテキストを使用するためです。ここではOBSTRUCTを使用します。これにより、展開が2回延期されます。これは、条件付きWHENが既に1回のスキャンを適用するために必要です。

#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 

この例では、カウンタの制限により10回のリピートに制限されています。コンピュータのリピートカウンタのように、有限のメモリによって制限されます。コンピュータのように、複数のリピートカウンタを組み合わせてこの制限を回避することもできます。

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

これは永遠に出力?にしようとしますが、適用されて、それ以上のスキャンがないので、最終的に停止します。さらに、我々はFOREVERマクロを定義することができます。ここで問題となるのは、無限の数のスキャンを与えた場合、このアルゴリズムは完了するでしょうか？これは停止問題として知られており、停止問題の決定不能性を証明するにはチューリング完全性が必要です。あなたが見ることができるように、プリプロセッサはチューリング完全言語として機能することができますが、コンピュータの有限メモリに限らず、適用されるスキャンの有限数によって制限されます。