構造化定理の民間伝承的定理

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

構造化定理の民間伝承的定理

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

「構造化定理」の記事における「構造化定理の民間伝承的定理」の解説

デイヴィッド・ハレル（David Harel）は、1980年までに出版された大量の論文を再調査した結果として、ベーム-ヤコピーニの証明の内容は民間伝承的定理（folk theorem）として常に誤って伝えられてきたと主張した。ハレルはコンピューターの初期に痕跡を残す2つの論文にこの民間伝承的定理の起源を突き止めた。1つは1946年のノイマン型の説明であり、1つのwhileループを使ってどのようにプログラムカウンターを制御するのかということを説明している。ハレルは、構造化定理の民間伝承バージョンによって使われる単一のループは基本的にノイマン型コンピューターにおけるフローチャートの実行のための操作的意味論を提供しているだけであると言及している。もう一つは、ハレルがこの定理の民間伝承バージョンを追跡して見つけたより古い出典であり、1936年からのスティーヴン・コール・クリーネのNormal form theoremである:383。 民間伝承的定理（Folk theorem） すべてのフローチャートは、変数を付加することを許した上で、単一のwhile-doからなるwhileプログラムと等価である。 このバージョンの定理は、元のプログラムの制御フローの全てを単一のグローバルな while ループに置き換える。このループはプログラムカウンターを模しており、元の非構造化プログラムにおける全てのラベル（フォローチャートの箱型の図形）に行くことができる。 ドナルド・クヌースは文献において、良い構造が重要なのであり、良い構造はFORTRAN, COBOL, アセンブリ言語でも記述できるとした。一方で、（構造化定理により）機械的にgotoを除去する変換を掛けたプログラムとは実際にどんなものになるのか、変換法の一例を示し、1つのループがプログラム全体の振る舞いを含んでしまうため、抽象化レベルという点では無意味であるとした。クヌースがそこで実際に示した、「機械的にgotoを除去」したコードと同様のものが以下であるが、見ればわかるようにgotoを使っていないというだけで、手続きのわかりやすい表現には全くなっていない。曰く「これですべての goto 文を除去できたわけであるが，実際にはすべての構造を失ってしまっている．」というわけである。 同様にブルース・イアン・ミルズはこの手法について「ブロック構造の精神はスタイルであり言語ではない。ノイマン型コンピューターを模することによって、ブロック構造言語の制限の範囲内であらゆるスパゲッティーコードの動きを作ることができる。このことはスパゲッティコードになることを防いでいない。」 p := 1;while p > 0 do begin if p = 1 then begin perform step 1 from the flowchart; p := resulting successor step number of step 1 from the flowchart (0 if no successor); end; if p = 2 then begin perform step 2 from the flowchart; p := resulting successor step of step 2 from the flowchart (0 if no successor); end; ... if p = n then begin perform step n from the flowchart; p := resulting successor step of step n from the flowchart (0 if no successor); end;end.