本質的複雑度は、Thomas J. McCabe, Sr.が1976年に発表した、引用数の多い論文（巡回複雑度を導入したことで知られる）で定義された数値的尺度である。McCabeは、本質的複雑度を、単一のエントリポイントと単一の終了ポイントを持つすべての構造化プログラミング制御構造（if-then-elseループやwhileループなど）をプレースホルダーの単一ステートメントに反復的に置き換え（縮小）た後の縮小CFG（制御フローグラフ）の巡回複雑度と定義した。[1] : 317 [2] : 80
McCabe の縮約プロセスは、制御構造 (およびそれに含まれる実際のステートメント) をサブルーチン呼び出しで概念的に置き換えることをシミュレートすることを意図しており、そのため、制御構造には単一のエントリ ポイントと単一の終了ポイントが必要です。[1] : 317 (今日では、このようなプロセスはリファクタリングという包括的な用語に含まれます。) すべての構造化プログラムは、McCabe によって定義されたように、明らかに本質的複雑度が 1 です。なぜなら、それらはすべて、トップレベルのサブルーチンへの単一の呼び出しに反復的に縮約できるからです。[1] : 318 McCabe が論文で説明しているように、彼の本質的複雑度メトリックは、特定のプログラムがこの理想 (完全に構造化されていること) からどれだけ離れているかを測る尺度を提供するために設計されました。[1] : 317 したがって、非構造化プログラムでのみ得られる 1 を超える本質的複雑度数値は、構造化プログラミングの理想からさらに離れていることを示しています。[1] : 317
構造化プログラムへの還元可能性に関する様々な概念間の混乱を避けるために、McCabeの論文が、構造化プログラム定理の改良（または代替的な見方）を示したS. Rao Kosarajuの1973年の論文について簡単に議論し、その文脈の中で展開していることに注意することが重要です。1966年のBöhmとJacopiniの独創的な論文は、すべてのプログラムは構造化プログラミング構造（別名D構造：シーケンス、if-then-else、whileループ）のみを使用して[書き換え]ることができることを示しましたが、ランダムプログラムを構造化プログラムに変換する際には、追加の変数を導入する（およびテストで使用する）必要があり、一部のコードが重複する可能性があります。[3]
論文の中で、ボームとヤコピニは、ある種の非構造化プログラムを構造化プログラムに変換するために、そのような追加の変数を導入する必要があるかどうかについては推測したが、証明はしなかった。[4] : 236 現在わかっているプログラムの例として、内部に 2 つの条件付き終了があるループがある。ボームとヤコピニの推測に対処するために、コサラジュは、ボームとヤコピニが使用したチューリング同値よりも制限の厳しいプログラム縮約の概念を定義した。基本的に、コサラジュの縮約の概念では、2 つのプログラムが同じ入力を与えられた場合に同じ値を計算する (または終了しない) 必要があるという明白な要件に加えて、2 つのプログラムが同じ基本アクションと述語を使用する必要がある (後者は条件文で使用される式として理解される)。これらの制限のため、コサラジュの縮約では追加の変数の導入は許可されない。これらの変数に代入すると新しい基本アクションが作成され、その値をテストすると条件文で使用される述語が変更されます。このより制限的な縮約の概念を用いて、コサラジュはボームとヤコピニの予想、すなわち2つの出口を持つループは追加の変数を導入せずに構造化プログラムに変換することはできないという予想を証明しましたが、さらに進んで、（ループからの）多段階ブレークを含むプログラムは階層構造を形成することを証明しました。そのため、深さnの多段階ブレークを持つプログラムは、やはり追加の変数を導入せずに、深さn未満の多段階ブレークを持つプログラムに縮約することはできません。[4] [5]
McCabe は論文の中で、Kosaraju の結果を踏まえ、非構造化プログラムの本質的な特性を制御フローグラフの観点から捉える方法を見つけようとしたと述べています。[1] : 315 彼はまず、最小の非構造化プログラムに対応する制御フローグラフ (ループへの分岐、ループからの分岐、およびそれらの if-then-else 対応部分を含む) を特定し、それを用いてKratowski の定理に類似した定理を定式化します。その後、プログラムの制御フローグラフが構造化されているかどうかという問いに対して、はい/いいえの答えではなく、尺度による答え (McCabe の言葉を借りれば「プログラムの構造化の尺度」) を与えるために、本質的複雑性の概念を導入します。[1] : 315 最後に、McCabe が CFG を縮小するために用いた縮約の概念は、Kosaraju のフローチャート縮約の概念とは異なります。 CFGで定義された縮約はプログラムの入力を意識せず、また気にも留めず、単純にグラフ変換を行う。[6]
たとえば、次の C プログラム フラグメントは、内部のifステートメントとfor を削減できるため、つまり構造化プログラムであるため、基本的な複雑度は 1 です。
i = 0 ; i < 3 ; i ++の場合{ a [ i ] == 0 ) b [ i ] + = 2の場合; }
以下のCプログラムの断片は、本質的複雑度が4であり、CFGは既約です。このプログラムは、zの最初の行がすべて0である行を見つけ、そのインデックスを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]
参照
参考文献
- ^ abcdefg マッケイブ (1976 年 12 月)。 「複雑さの尺度」。ソフトウェアエンジニアリングに関する IEEE トランザクション(4): 308–320。doi : 10.1109 /tse.1976.233837。S2CID 9116234。
- ^ http://www.mccabe.com/pdf/mccabe-nist235r.pdf [裸の URL PDF ]
- ^ David Anthony Watt、William Findlay (2004). 『プログラミング言語設計コンセプト』 John Wiley & Sons. p. 228. ISBN 978-0-470-85320-7。
- ^ ab S. Rao Kosaraju (1974年12月). 「構造化プログラムの解析」. Journal of Computer and System Sciences . 9 (3): 232– 255. doi :10.1016/S0022-0000(74)80043-7.
- ^ 同じ結果のより現代的な扱いについては、Kozen, The Böhm–Jacopini Theorem is False, Propositionallyを参照。
- ^ McCabe は 315 ページと 317 ページに 2 つの定義を脚注で示しています。
- ^ Steven S. Muchnick (1997). 『Advanced Compiler Design Implementation』 モーガン・カウフマン. pp. 196–197 and 215. ISBN 978-1-55860-320-2。