44

C ++テンプレート メタプログラミングはチューリング完全ですが、プリプロセッサ メタプログラミングは完全ではありません。

C++11 は、constexpr 関数の計算という新しい形式のメタプログラミングを提供します。この形式の計算はチューリング完全ですか? constexpr関数は再帰や条件演算子(?:)が許されているので、そうなのかなと思っているのですが、詳しい方に確認していただきたいです。

4

3 に答える 3

60

tl;dr: constexprC++11 では、言語の仕様にバグがあるためチューリング完全ではありませんでしたが、そのバグは標準の後のドラフトで対処されており、clang は既に修正を実装しています。

constexprは、ISO C++11 国際標準で指定されているように、チューリング完全ではありません。スケッチ証明:

  • 特定の一連の引数 に対するすべてのconstexpr関数fの結果 (または非終了) はa...、 の値によってのみ決定されます。a...
  • 定数式内で構築できるすべての引数値は、次の[basic.types]p10いずれかのリテラル型である必要があります。
    • スカラー型、
    • 参照、
    • リテラル型の配列、または
    • クラスタイプ
  • 上記の各ケースには、有限の値のセットがあります。
    • スカラーの非ポインター型の場合、これは簡単に続きます。
    • ポインターまたは参照を定数式で使用するには、アドレスまたは参照定数式によって初期化する必要があるため、静的記憶域期間を持つオブジェクトを参照する必要があります。このオブジェクトは、どのプログラムでも有限量しか存在しません。
    • 配列の場合、境界は定数でなければならず、各メンバーは結果が続く定数式によって初期化される必要があります。
    • クラス型の場合、有限数のメンバーがあり、各メンバーはリテラル型であり、結果が続く定数式によって初期化される必要があります。
  • したがって、受け取ることができる可能な入力のセットa...はf有限であるため、有限に記述されconstexprたシステムは有限状態マシンであり、したがってチューリング完全ではありません。

しかし、C++11 標準の公開以降、状況は変わりました。

Johannes Schaub のstd::max() および std::min() not constexprへの回答で説明されている問題は、コアの問題 1454 として C++ 標準化委員会に報告されました。2012 年 2 月の WG21 会議で、これは標準であり、選択された解決策には、一時オブジェクトを指定するポインターまたは参照メンバーを使用してクラス型の値を作成する機能が含まれていました。これにより、無制限の量の情報を関数によって蓄積および処理でき、評価をチューリング完全constexprにするのに十分ですconstexpr(実装が無制限の深さへの再帰をサポートしていると仮定します)。

コアの問題 1454 の提案された解決策を実装するコンパイラのチューリング完全性を実証するためにconstexpr、clang のテスト スイート用のチューリング マシン シミュレータを作成しました。

http://llvm.org/svn/llvm-project/cfe/trunk/test/SemaCXX/constexpr-turing.cpp

g++ と clang の両方のトランク バージョンは、このコアの問題の解決策を実装していますが、g++ の実装は現在、このコードを処理できません。

于 2012-03-02T05:39:26.427 に答える
8

これらを見てください。サンプルをコンパイルしたところ、GCC 4.6 で動作しました: コンパイル時の計算、コンパイル時の文字列の解析 - パート I、コンパイル時の文字列の解析 - パート II

于 2012-02-08T22:48:35.333 に答える
1

実際のコンピューターの制限 (有限のメモリや MAX_INT の有限の値など) を考慮すると、当然、constexpr (および C++ 全体) はチューリング完全ではありません。

しかし、この制限を取り除けば、たとえば、int を完全に任意の正の整数と考えると、そうです。C++ の constexpr 部分はチューリング完全になります。部分再帰関数を表現するのは簡単です。

0、S(n) = n+1 およびセレクター I_n^m(x_1, ..., x_n) = x_m および重ね合わせは明らかに constexpr を使用して表現できます。

プリミティブ再帰は、次のように直接実行できます。

constexpr int h(int x1, ..., int xn, int y) {
  return (xn == 0) ? f(x1, ..., xn) : g(x1, ..., xn, y-1, h(x1, ..., xn, y-1));
}

部分再帰には、簡単なトリックが必要です。

constexpr int h(int x1, ... int xn, int y = 0) {
  return (f(x1, ... xn, y) == 0) ? y : h(x1, ..., xn, y+1);
}

したがって、部分再帰関数を constexpr として取得します。

于 2012-02-21T12:52:11.093 に答える