影響と改良

ウィキペディア小見出し辞書

影響と改良

出典: フリー百科事典『ウィキペディア（Wikipedia）』 (2020/07/06 11:41 UTC 版)

「構造化定理」の記事における「影響と改良」の解説

ベーム-ヤコピーニの証明は、プログラムを改良するよりもプログラムを不明瞭にする可能性が高かったので、ソフトウェア開発のために構造化プログラミングを採用するかどうかという疑問を解決しなかった。 それどころか議論の始まりを告げることになった。エドガー・ダイクストラの有名な文書「Go To Statement Considered Harmful（英語版）（Go to 文は有害と考えられる）」は1968年にその議論に続いた。 幾人かの研究者はベーム-ヤコピーニの結論に対して純粋な手段を取った。そして、ループの途中にある break と return ですらベーム-ヤコピーニの証明に必要とされていないので悪い実践であると主張した。したがって全てのループは単一の脱出ポイントを持つべきだと主張した。この純粋な手段はPascalプログラミング言語（1968～1969に設計）で具体化された。Pascalは1990年代中頃まで大学の入門的なプログラミングの講義をするために好まれたツールであった。 エドワード・ヨードンは、構造化プログラミングの流行が始まった時からの議論に基づいて、1970年代に非構造化プログラムを機械的に構造化プログラムに変換することに哲学的な反対があったと述べている。実用本位の対照的なこととして、そのような変換が既存のプログラムの大きなコードに役立ったということもあった。機械的変換のための最初の提案の一つは、エドワード・アッシュクロフト（Edward Ashcroft）とゾハル・マンナ（英語版）（Zohar Manna）による1971年の論文であった。 ベーム-ヤコピーニの定理の直接的応用は、構造化チャートに導入されている余分なローカル変数（訳注：ループ途中脱出用のフラグのことだろうか？）といくつかの重複コードという結果になったのかもしれない。後者の問題は、この状況で loop and a half problem と呼ばれている（訳注：なぜ後者の問題なのかは英語版に書かれていない）。Pascal はこれらの問題の両方に影響されており、エリック・S・ロバーツ（英語版）（Eric S. Roberts）によって引用された経験的研究に従っている。学生プログラマーであるロバーツは、いくつかの単純な問題（配列の中から1つの要素を検索する機能も含む）のために Pascal で適切な解法を公式化することに困難を感じた。ロバーツによって引用されたヘンリー・シャピロ（Henry Shapiro）による1980年の研究は、Pascal が提供する制御構造だけを使うと、適切な解法を得られた課題は20%だけだった。一方、ループの途中に return を書くことを許せば、この問題のために不適切なコードを書く課題は存在しなかった。 1973年、S.ラオ・コサラジュ（英語版）（S. Rao Kosaraju）は、任意の深さで multi-level break （多重ループから複数階層を一気に脱出できる break）を使えるようにすれば、構造化プログラミングにおいて余分な変数の追加を回避できることを証明した。さらにコサラジュは「プログラムの厳密な階層が存在する。それは現在 コサラジュ階層（Kosaraju hierarchy） と呼ばれている。n はあらゆる整数である。深さ n の1つの multi-level break を含んでいるプログラムは、n よりも小さい深さの multi-level break を使ったプログラムとして書き換えることはできない」ということを証明した。コサラジュは BLISSプログラミング言語の multi-level break の仕組みを引き合いに出している。leave label という形式の multi-level break は、実際に BLISS-11 で導入されていた。最初の BLISS は single-level break （一階層しか脱出できない break）のみを採用していた。BLISS言語ファミリーは制約のない goto を提供していなかった。Javaプログラミング言語は、後に同様にこの手法を採用している:960–965。 コサラジュの論文から得られる単純な結論は、あるプログラムが2つの異なる脱出口を持つループを含んでいないときだけ（変数を追加せずに）あるプログラムを構造化プログラムへ変換できるということである。変換可能性はコサラジュによって定義された。大雑把に言うと、同一の機能を処理し、同じ「基本動作」を使い、そして元のプログラムと同様であると断言できることである。しかし、元のプログラムと異なる制御フロー構造を使うことができる（これはベーム-ヤコピーニの使ったものよりも狭い概念の変換可能性である）。この結論に触発されて、コサラジュが頻繁に引用する循環的複雑度の概念を導入した論文の第6節において、トーマス・J・マッケイブ（Thomas J. McCabe）は非構造化プログラムの制御フローグラフ（CFG : Control Flow Graph）のためのクラトフスキーの定理（英語版）と類似したものを記述した。つまり、プログラムのCFGを非構造化にする最小の誘導部分グラフである。これらの部分グラフは自然言語で非常に良く説明できる。それらは以下のものである。 ループの外へ分岐（ループサイクルテストからの分岐以外） ループの中へ分岐 決定の中へ分岐（すなわち、if分岐の中へ入る） 決定の外へ分岐 マッケイブはこれらの4つのグラフが部分グラフとして登場するときに独立していないことを実際に明らかにした。プログラムが非構造化になるための必要十分条件は、そのCFGがこれらの4つのグラフから3つ選んで作った部分集合のどれか1組を部分グラフとして持つことである（訳注：4つのグラフのうち3つのグラフがCFGに含まれていたら非構造化になるということ）。彼は、もしも非構造化プログラムがこれらの4つの部分グラフの1つを含んでいるならば、その非構造化プログラムは4つの部分グラフからもう1つの異なる部分グラフを含まなければならないということも明らかにした。この後者の結論は、非構造化プログラミングの制御フローが一般的にスパゲティプログラムと呼ばれるものにどのようにしてなっていくのかを説明するのに役立つ。マッケイブは、あるプログラムが与えられたとき、それが理想の構造化プログラムからどの程度かけ離れているのかを定量化する数値測定手段も考案した。マッケイブは彼の測定手段を Essential complexity（英語版） と呼んだ。 マッケイブの構造化プログラミングにおける禁止グラフ（英語版）の特徴づけは不完全であると考えることができる。少なくともダイクストラのD構造（訳注：D構造の意味不明）は、建設用ブロックと見なされている:274–275[要説明]。 1990年まで既存プログラムのほとんどの構造を維持しながら goto を削除するためにかなり多くの提案された手法が存在した。この問題への様々な手段はいくつかの等価の概念も提案した。それらの概念は上で議論された民間伝承的定理のような結果を避けるために単純なチューリングマシン等価（英語版）よりも厳密である。選ばれた等価の概念の厳密性は必要とされる制御フローの最小セットを要求する。ライル・ラムショウ（Lyle Ramshaw）による1988年の JACM (Journal of the ACM)（英語版） の論文は、それまでのその分野を調査しており、さらに自身の手法も提案している。ラムショウのアルゴリズムは、Java仮想マシンコードがオフセットとして表現された対象を持つ分岐命令を持つので、Javaの逆コンパイラの例のために使われた。しかし、上位レベルのJava言語だけは multi-level の break と continue 文を持っている。 Ammarguellat (1992年)は、ループの一箇所からの脱出を強制するために後戻りする変換手法を提案した。