6

C++ テンプレート メタプログラミングがチューリング完全であることは知っています。同じことがプリプロセッサのメタプログラミングにも当てはまりますか?

4

2 に答える 2

18

マクロは再帰的に直接拡張することはありませんが、これを回避する方法はいくつかあります。

プリプロセッサで再帰を行う最も簡単な方法は、遅延式を使用することです。据え置き式は、完全に展開するためにより多くのスキャンを必要とする式です。

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

次に、ロジックを実行するためにさらにいくつかのマクロが必要です。

#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マクロを作成できます。マクロを使用して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回の繰り返しに制限されています。コンピュータのリピートカウンタが有限のメモリによって制限されるのと同じように。コンピューターの場合と同様に、複数の繰り返しカウンターを組み合わせて、この制限を回避することができます。さらに、FOREVERマクロを定義することもできます。

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

これは永久に出力しようとします?が、適用されているスキャンがなくなるため、最終的には停止します。ここで問題となるのは、スキャンを無限に行うと、このアルゴリズムは完了するのでしょうか。これは停止問題として知られており、チューリング完全性は停止問題の決定不能性を証明するために必要です。ご覧のとおり、プリプロセッサはチューリング完全言語として機能できますが、コンピュータの有限メモリに制限されるのではなく、適用されるスキャンの有限数によって制限されます。

于 2012-05-10T19:09:50.613 に答える
13

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

ただし、定義を少し曲げると、プリプロセッサを複数回呼び出すことで可能になります。プリプロセッサがプリプロセッサを再呼び出しするプログラムを生成できるようにし、外部でループすることで、プリプロセッサ。リンクされた例では C を使用していますが、C++ にも簡単に適応できるはずです。

于 2011-09-22T01:19:16.037 に答える