Loading article…
本質的複雑性は、トーマス・J・マッケイブ・シニアが1976年に発表した、引用数の多い論文（循環的複雑性の概念を導入したことでよく知られている）で定義された数値尺度である。マッケイブは、すべての構造化プログラミング制御構造、すなわち単一のエントリポイントと単一のエグジットポイントを持つ構造（例えばif-then-elseループやwhileループ）をプレースホルダーの単一ステートメントで繰り返し置き換え（縮小）した後の、縮小されたCFG（制御フローグラフ）の循環的複雑性を本質的複雑性と定義した。[ 1 ] : 317 [ 2 ] : 80
マッケイブの削減プロセスは、制御構造（およびそれらに含まれる実際のステートメント）をサブルーチン呼び出しで概念的に置き換えることをシミュレートすることを目的としており、そのため制御構造には単一のエントリポイントと単一の出口ポイントが必要となります。[ 1 ] : 317 （今日では、このようなプロセスはリファクタリングという包括的な用語で呼ばれます。）マッケイブが定義したように、すべての構造化プログラムは、トップレベルのサブルーチンへの単一の呼び出しに反復的に削減できるため、明らかに本質的複雑度は1です。[ 1 ] : 318マッケイブが論文で説明しているように、彼の本質的複雑度指標は、特定のプログラムがこの理想（完全に構造化されていること）からどれだけ離れているかを測定するために設計されました。[ 1 ] : 317したがって、非構造化プログラムでのみ得られる1より大きい本質的複雑度は、それらが構造化プログラミングの理想からさらに遠ざかっていることを示しています。[ 1 ] : 317
構造化プログラムへの還元可能性に関するさまざまな概念の混同を避けるために、マッケイブの論文は、構造化プログラム定理の改良（または別の見解）を示したS.ラオ・コサラジュによる1973年の論文について簡単に議論し、その文脈で運用されていることに注意することが重要です。ベームとヤコピニによる1966年の画期的な論文は、すべてのプログラムは構造化プログラミング構成要素（別名D構造：シーケンス、if-then-else、while-loop）のみを使用して[再]書きできることを示しましたが、ランダムプログラムを構造化プログラムに変換する際には、追加の変数を導入（およびテストで使用）する必要があり、一部のコードが重複する可能性があります。[ 3 ]
論文の中で、Böhm と Jacopini は、ある種の非構造化プログラムを構造化プログラムに変換するには、そのような追加変数を導入する必要があると推測したが、それを証明しなかった。 [ 4 ] : 236このような追加変数を必要とするプログラムの例 (現在ではわかっている) は、内部に 2 つの条件付き終了があるループである。Böhm と Jacopini の推測に対処するために、Kosaraju は、Böhm と Jacopini が使用したチューリング等価性よりも制限的なプログラム還元の概念を定義した。本質的に、Kosaraju の還元の概念は、2 つのプログラムが同じ入力に対して同じ値を計算する (または終了しない) という明白な要件に加えて、2 つのプログラムが同じプリミティブアクションと述語 (後者は条件で使用される式として理解される) を使用する必要があることを課している。これらの制限のため、Kosaraju の還元では追加変数の導入は許可されない。これらの変数に代入すると新しいプリミティブアクションが作成され、その値をテストすると条件文で使用される述語が変更されます。このより制限的な還元概念を使用して、Kosaraju は Böhm と Jacopini の予想、つまり 2 つの出口を持つループは追加の変数を導入せずに構造化プログラムに変換できないことを証明しましたが、さらに進んで、多段階ブレーク (ループから) を含むプログラムは階層を形成し、追加の変数を導入せずに、深さnの多段階ブレークを持つプログラムをn未満の深さの多段階ブレークを持つプログラムに還元できないプログラムを常に見つけることができることを証明しました。[ 4 ] [ 5 ]
マッケイブは論文の中で、コサラジュの結果を踏まえ、非構造化プログラムの制御フローグラフの本質的な特性を捉える方法を見つけようとしたと述べている。[ 1 ] : 315彼はまず、最小の非構造化プログラムに対応する制御フローグラフ（ループへの分岐、ループからの分岐、およびそれらのif-then-else対応を含む）を特定し、それを用いてクラトフスキーの定理に類似した定理を定式化し、その後、プログラムの制御フローグラフが構造化されているか否かという質問に対して、はい/いいえの答えではなく、尺度による答え（彼の言葉では「プログラムの構造化の尺度」）を与えるために、本質的複雑性の概念を導入した。[ 1 ] : 315最後に、マッケイブがCFGを縮小するために用いた縮小の概念は、コサラジュのフローチャート縮小の概念とは異なる。 CFG上で定義された縮約は、プログラムの入力について知ることも気にすることもなく、単なるグラフ変換である。[ 6 ]
例えば、次のCプログラムの断片は、内部のif文とfor文を簡略化できるため、構造化プログラムであり、本質的な複雑度は1です。
for ( i = 0 ; i < 3 ; i ++ ) { if ( a [ i ] == 0 ) b [ i ] += 2 ; }以下のC言語プログラムの断片は、本質的な計算量が4であり、その文脈自由文法（CFG）は既約です。このプログラムは、zの中で全てがゼロである最初の行を見つけ、そのインデックスをiに格納します。そのような行がない場合は、iに-1を格納します。
for ( i = 0 ; i < m ; i ++ ) { for ( j = 0 ; j < n ; j ++ ) { if ( z [ i ][ j ] != 0 ) goto non_zero ; } goto found ; non_zero : } i = -1 ; found :部分グラフの逐次的な縮約（最終的には、良好な性質を持つ CFG の場合は単一のノードに縮約）による CFG の縮約可能性の考え方は、現代のコンパイラ最適化でも使用されています。ただし、構造化プログラミングの単一エントリおよび単一出口の制御構造の概念は、自然ループの概念に置き換えられています。自然ループは、「単一エントリ、複数出口のループで、内部からエントリに戻る分岐が 1 つだけある」と定義されます。自然ループに縮約できない CFG の領域は、不適切領域と呼ばれます。これらの領域は、CFG の複数エントリ、強連結成分という、かなり単純な定義になります。したがって、最も単純な不適切領域は、2 つのエントリポイントを持つループです。複数の出口は、現代のコンパイラでは解析上の問題を引き起こしません。不適切領域（ループへの複数エントリ）は、コードの最適化において追加の困難を引き起こします。[ 7 ]