80

Boost プリプロセッサの機能を発見した後、私は疑問に思いました: C99 プリプロセッサのチューリングは完全ですか?

そうでない場合、資格がないために何が欠けていますか?

4

4 に答える 4

155

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

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

#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-10T00:44:10.433 に答える
41

これは、チューリング マシンを実装するためにプリプロセッサを悪用する例です。プリプロセッサの出力を入力に戻すには、外部ビルド スクリプトが必要であることに注意してください。そのため、プリプロセッサ自体は完全なチューリングではありません。それでも、それは興味深いプロジェクトです。

前にリンクされたプロジェクトの説明から：

少なくともプログラムが一度だけ前処理された場合、プリプロセッサはチューリング完全ではありません。これは、プログラムがそれ自体を含めることが許可されている場合でも当てはまります。(その理由は、特定のプログラムの場合、プリプロセッサには限られた数の状態と、ファイルがインクルードされた場所から構成されるスタックしかないためです。これはプッシュダウン オートマトンにすぎません。)

Paul Fultz II による回答は非常に印象的で、プリプロセッサがこれまでに得ることができると思っていたよりも確かに近いですが、それは真のチューリング マシンではありません。C プリプロセッサには特定の制限があり、メモリと時間が無限にある場合でも、チューリング マシンのように任意のプログラムを実行することはできません。C 仕様のセクション 5.2.4.1 には、C コンパイラの次の最小制限が示されています。

  • 完全な式内の括弧で囲まれた式の 63 のネスト レベル
  • 内部識別子またはマクロ名の最初の 63 文字
  • 1 つの前処理翻訳単位で同時に定義される 4095 のマクロ識別子
  • 論理ソース行に 4095 文字

以下のカウンタ メカニズムでは、値ごとにマクロ定義が必要なため、マクロ定義の制限により、ループできる回数が制限されます (EVAL(REPEAT(4100, M, ~))未定義の動作が発生します)。これは基本的に、実行できるプログラムの複雑さに上限を設けます。マルチレベル展開のネスティングと複雑さは、他の制限の 1 つにも達する可能性があります。

これは、「無限メモリ」の制限とは根本的に異なります。この場合、仕様では、標準に準拠した C コンパイラは、たとえ無限の時間やメモリなどを持っていても、これらの制限に準拠することだけが要求されると具体的に述べられています。これらの制限を超える入力ファイルは、予測不可能または未定義の方法で処理される可能性があります。 （または完全に拒否されました）。一部の実装では、より高い制限があるか、まったく制限がない場合がありますが、それは「実装固有」と見なされ、標準の一部ではありません。Paul Fultz II の方法を使用して、特定のコンパイラ実装でチューリング マシンのようなものを実装できる可能性があります。これには有限の制限はありませんが、「標準に準拠した任意の C99 プリプロセッサでこれを実行できるか」という一般的な意味では、答えはノーです。ここでの制限は言語自体に組み込まれており、無限のコンピューターを構築できないことによる単なる副作用ではないため、チューリングの完全性が損なわれると言います。

于 2010-06-28T23:10:43.833 に答える
10

チューリングを完全にするためには、決して終わらないかもしれない再帰を定義する必要があります - それらをmu-recursive operatorと呼びます。

このような演算子を定義するには、定義された識別子の無限の空間が必要です (各識別子が有限回評価される場合) 。これは、結果が見つかるまでの時間の上限をアプリオリに知ることができないためです。コード内の演算子の数が限られているため、無制限の数の可能性をチェックできる必要があります。

したがって、このクラスの関数は C プリプロセッサでは計算できません。C プリプロセッサでは、定義されたマクロの数が限られており、それぞれが 1 回しか展開されないためです。

C プリプロセッサは、Dave Prosser のアルゴリズム(1984 年に WG14 チームのために Dave Prosser によって作成された) を使用します。このアルゴリズムでは、最初の展開の瞬間にマクロが青く塗られます。再帰呼び出し (または相互再帰呼び出し) では展開されません。最初の展開が開始された時点で既に青く塗られているからです。したがって、有限数の前処理行では、関数 (マクロ) を無限に呼び出すことは不可能であり、これが mu 再帰演算子の特徴です。

C プリプロセッサは、シグマ再帰演算子のみを計算でき ます。

詳細については、Marvin L. Minsky (1967) の計算のコースを参照してください -- Computation: Finite and Infinite Machines、Prentice-Hall, Inc. Englewood Cliffs, NJ など。

于 2016-05-26T14:11:38.257 に答える
4

それは制限内で完全なチューリングです (すべてのコンピューターは無限の RAM を持っていないため)。Boost Preprocessorでできることの種類を確認してください。

質問の編集に応じて編集します。

Boost の主な制限は、コンパイラ固有の最大マクロ展開深度です。また、再帰を実装するマクロ (FOR...、ENUM... など) は真に再帰的ではなく、ほぼ同一のマクロの集まりのおかげで再帰的に見えるだけです。全体像としては、この制限は、実際に再帰的な言語で最大スタック サイズを設定することと何ら変わりはありません。

限られたチューリング完全性 (チューリング互換性?) に本当に必要なのは、反復/再帰 (同等の構造) と条件付き分岐の 2 つだけです。

于 2010-06-28T22:52:32.453 に答える