C99プリプロセッサチューリングは完了していますか？

https://stackoverflow.com/questions/3136686

01-10-2019
|

質問

発見した後プリプロセッサの機能をブーストします私は自分が疑問に思っていました：C99プリプロセッサチューリングは完了していますか？

そうでない場合、資格を得ることができないことは何に欠けていますか？

解決

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

前述のプロジェクトの説明から：

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

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

63完全な表現内の括弧付き式のネスティングレベル

63内部識別子またはマクロ名の重要な初期文字

4095マクロ識別子は、1つの前処理翻訳ユニットで同時に定義されています

論理ソースラインの4095文字

以下のカウンターメカニズムには値ごとのマクロ定義が必要なため、マクロ定義の制限はループできる回数を制限します（EVAL(REPEAT(4100, M, ~)) 未定義の動作が得られます）。これにより、基本的に実行できるプログラムの複雑さにキャップが表示されます。マルチレベルの拡張の営巣と複雑さは、他の制限の1つにも当たる可能性があります。

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

他のヒント

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

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

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

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

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

チューリングを完了するには、決して終わらないかもしれない再帰を定義する必要があります - 人はそれらを呼び出します MU-Recursiveオペレーター.

そのようなオペレーターを定義するには、定義された識別子の無限のスペースが必要です（各識別子が有限数の回数で評価された場合） アプリオリ 結果が見つかった時間の上限。コード内に有限の数のオペレーターを使用すると、無制限の数の可能性を確認できる必要があります。

それで このクラスの関数は、cプリプロセッサで計算することはできません cプリプロセッサには、定義されたマクロの数が限られており、それぞれが一度だけ拡張されるためです。

Cプリプロセッサはを使用します Dave Prosserのアルゴリズム（1984年にWG14チームのためにDave Prosserによって書かれました）。このアルゴリズムでは、最初の拡張の瞬間にマクロが青く塗られます。最初の拡張が開始された瞬間にすでに青色に塗られているため、再帰コール（または相互再帰コール）はそれを拡張しません。したがって、有限数の前処理ラインでは、MU-Recursive演算子を特徴付ける機能の無限の呼び出し（マクロ）を作成することは不可能です。

Cプリプロセッサは計算のみを計算できます Sigma-Recursiveオペレーター .

詳細については、の計算コースを参照してください Marvin L. Minsky（1967） - 計算：有限および無限のマシン, 、Prentice-Hall、Inc。Englewood Cliffs、ニュージャージーなど

制限内で完全にチューリングがあります（無限のRAMがないため、すべてのコンピューターと同様）。あなたができることの種類をチェックしてくださいブーストプリプロセッサ.

質問編集に応じて編集：

ブーストの主な制限は、コンパイラ固有の最大マクロ拡張深度です。また、再帰を実装するマクロ（...、列挙...など）は本当に再帰的ではありません。全体像では、この制限は、実際に再帰的な言語で最大のスタックサイズを持つことと変わりません。

限られたチューリングの完全性（チューリング互換性？）に本当に必要な2つのことは、反復/再帰（同等の構成要素）と条件付き分岐です。

ライセンス： CC-BY-SA と帰属

所属していません StackOverflow