コンテンツにスキップ

英文维基 | 中文维基 | 日文维基 | 草榴社区

利用者:I.hidekazu/ミルズの構造化プログラミング

「構造化プログラミング」によって制御フローのジャングルが小さな詳細レベル（関数に相当する）に分割・整理され、“うまく”構造化された流れ図

ミルズの構造化プログラミング（ミルズのこうぞうかプログラミング、英: Mills' structured programming）とは、ソフトウェアの複雑な制御フローを連接・選択・繰り返しおよびネスティング（nesting）の多層化[1]によって整理しながらプログラミングを行う段階的詳細化法を言う[2]。

エドガー・ダイクストラの構造化プログラミングの主張[3]をIBMのハーラン・ミルズ（Harlan D. Mills）が敷衍したもので、構造化定理に基づいて単純にgoto文を使用しないgoto-lessプログラミングと理解されていることが多い[4]。

概要

[編集]
初期のフローチャート 。現代の規格化されたフローチャートと異なり、一見しただけでは、どこからどう読めばよいか把握することが困難である。 "Planning and coding of problems for an electronic computing instrument," 1947 から
制御処理が順次プログラムである「連接」・「選択」・「繰り返し」に限定された現代的なフローチャート（なお、ネストはされていない）。上から下に人間の思考過程に沿った形でプログラムの処理過程を理解することができる。

プログラムの設計手法としてのフローチャート（flow chart; 流れ図）は、歴史的には1947年にHerman Goldstine及びフォン・ノイマンによって導入されたものである[5]。フローチャートの導入は、それまでのほとんど設計をおこなわず直接プログラミングを行う職人芸的手法を改善するものであったが[6]、当時のプログラミング作法を反映して各制御のエリアの記載方法に統一性がなく、一つの入力に対して二つの出力があったり、必ずしも上から下に読めるように定められておらず、小規模ソフトウェアであれば一人の人間の力で把握することはできるものの、大規模なものとなればその把握は実質的に不可能なものであった。

大規模プログラムの開発に関心を持っていた[7]オランダのエドガー・ダイクストラは、仕様通り正しく動く大規模ソフトェア開発の困難さを、この巨大になったときその把握が人間の能力を超えてしまう当時の制御処理方法の無秩序さに求め、ソフトウェア開発において構成要素である各制御処理は、抽象化したとき『頭に一つの入口を持ち尻尾に一つの出口』を持つ順次プログラム（sequential program）に限定すべきと主張した[8][9]。そのため順次プログラムの構成を自動的に破壊してしまうgoto文は害があると主張し論争を巻き起こすこととなった（goto文論争[10]）。

各制御処理を順次プログラムに限定してしまえば、そのソフトウェアの設計におけるフローチャートは上から下に読めるものとなり、文書を読むように人間の思考の流れとプログラムの進行の流れとが一致することになる。さらにその構成要素の順次プログラムは、経験的に[11]、連接（concatenation）・選択（selection）・繰り返し（repetition）の３種類に分けられるとし、その正しさは、一人の人間が最初の２つに対しては数え上げ推論（enumaration）、３つめに対しては数学的帰納法（mathematical induction）を適用することで確認できると主張した[12]。

上記道具立てを使用すれば、原理的には大規模ソフトウェアであっても開発することができ、そのプログラムの正しさの証明も理解（understanding a proof of correctness of the program）[13]することができる[14]。しかしながら、記憶力という人間の能力の限界によってこれを巨大ソフトウェアの全要素に対して実行することは現実的ではない。これを解決する手段としてダイクストラが提案したのが抽象（abstract）であったが、あまり認知されなかった[15]。

IBMのハーラン・ミルズは、上記ダイクストラの構造化プログラミングの考え方を単純に要約するために、ソフトウェアの問題を制御フローの問題と同一視した上で、

試行錯誤のコンピュータプログラミング技術をソフトウェア工学へと変える革命のきっかけとなったのは、Dijkstraの構造化プログラミング(1)の考え方である。構造化プログラミングは、どんどん複雑化するソフトウェアの問題を取り扱うため、２０年間以上も食い止められることなく増殖し続けてきた制御フローのジャングルを整理することに成功した。制御フローのジャングルは、どんなに複雑なソフトウェアでも３つの基本的な構造、順次（begin-end）、選択（if-then-else）と反復（while-do）で設計でき、しかもその構造は何重にもネストできる（構造化プログラミングの構造）という驚くべき主張で置き換えられた。 — H.D.Mills, R.C.Linger, a.R.Hevner, “ボックス構造化情報システム（1987）” p.1(p.187) Tom DeMarco, Timothy Lister(編著)、児玉公信(監訳) 編『ソフトウェアエンジニアリング論文集80's』翔泳社、2006年、pp.187-219頁。 収録

とダイクストラの構造化プログラミングを解釈し、さらにミルズ独自の要素も加えたソフトウェア開発技法を提唱した[16]。このミルズが中心となって要約・発展させたソフトウェア開発技法をミルズの構造化プログラミング（Mills' structured programming）と呼ぶ。

構造化文（structured statement）

[編集]

ダイクストラは、従来のフローチャートの進行方向を単線化するため、プログラムは順次プログラムでなくてはならず、さらにその順次プログラムはフローチャートの制御の規律を固守するため[17]、連接（concatenation）・選択（selection）・繰り返し（repetition）の三種類の単位に限定し[18]、goto文は使用しないようにすべきであるとした[19][21]。なお、ニクラウス・ヴィルトはこれらを構造化文(structured statement)と呼んだ [22]

  • 連接（concatenation）
    連接（concatenation）
  • 選択（selection）
    選択（selection）
  • 繰り返し（repetition）
    繰り返し（repetition）

抽象とフローチャートのネスト

[編集]
抽象（abstraction）の一例

たとえ３つの構造化文に限定したとしても、非常に多数の構造化文からなるプログラムに対しては、その規模が人間の能力を超えてしまうものであれば、人間がその挙動の正しさを証明することは困難である。この問題を解決するために行うのがフローチャートのネストである。ネストはプログラミング言語における関数に相当し、長いフローチャートを小さい関数に分けることで人間はその挙動の正しさを証明しやすくなる。

ダイクストラが知性の道具立てとして提示した抽象（abstraction）とは関数に分けることを意味し、プログラムを構成する部分のまとまりに対して変数名をつけるように名前（関数名）をつけることで、正しさを証明すべき箇所を分割する。

例えば、左図のような多数の連接文を含むwhile文の証明は、知性の道具立ての一つである抽象、すなわちフローチャートのネストをすることで、

全体のプログラムの証明　＝
「抽象処理Rの詳細レベル０の証明」 × 「抽象処理Rの詳細レベル１の証明」

の二つの証明に分離して実行することができるようになる。

構造化定理（the structure theorem）

[編集]

ダイクストラのフローチャートに関する提案は、有効に思われたが数学的根拠に乏しかった。代わりにミルズらは、次の構造化定理（the structure theorem）を導入することで、一般的分岐を与える命令（GOTO文）の除去の正当化を行った。

構造化定理（the structure theorem）[23]
任意の固有プログラム（proper program）は、元プログラムの関数と述語それに代入と付加したカウンターによるテストを用いると、｛順次（sequence）、選択（ifthenelse）、繰り返し（whiledo）｝を基本セットとする構造化プログラムと等価な関数となる。

証明の概要

[編集]

証明にあたって肝心な部分は、プログラムの制御フローの全てを単一のグローバルな while ループに置き換え、プログラム全体を常に走査できるようにするところにある。さらに、行番号やラベルに代わってプログラムカウンターと呼ばれる呼び出し位置を指定する変数を付け加えることでgoto文と同等の機能をwhiledoとifthenelseで提供することができる。 

{変換前goto文}
program main(input, output);
label 10, 20, 30, 40;
 begin
        10: writeln('step 1'); goto 30;
        20: writeln('step 2'); goto 40;
        30: writeln('step 3'); goto 20;
        40:
 end.

このプログラムを変換すると以下のようにgoto文無しに書くことができる。 

{変換後}
program main(input, output);
var pcnter : integer;  {プログラムカウンター}
begin
	pcnter := 10;
	while pcnter > 0 do
	begin
		if pcnter = 10 then begin writeln('step 1'); pcnter := 30; end;
		if pcnter = 20 then begin writeln('step 2'); pcnter := 40; end;
		if pcnter = 30 then begin writeln('step 3'); pcnter := 20; end;
		if pcnter = 40 then pcnter := -1; {プログラムカウンターに-1が代入されたらwhiledoから脱出する。}
	end;
end.

脚注

[編集]
  1. ^ このネストの反復によって構成される多層的な「構造」が構造化プログラミングの言う「良い構造」である。
  2. ^ 河村(1995)pp.112-113、H.D.Mills, R.C.Linger, a.R.Hevner, “ボックス構造化情報システム” p.1(p.187) Tom DeMarco, Timothy Lister(編著)、児玉公信(監訳) 編『ソフトウェアエンジニアリング論文集80's』翔泳社、2006年、pp.187-219頁。 収録
  3. ^ 構造化プログラミング(1972)
  4. ^ ただし、次のような批判がある。
    [2]の表題にあるstructured programming（構造化プログラミング）ということばは、（ダイクストラ）氏の細心かつ厳格なライフスタイルを表現するものとして言い出されたが、のちにIBM社の誇る、Dijkstra教授とはまったく別種の天才 Harlan D.Mills氏によってまったくちがう意味に転用された。プログラマー（職業としてではなく職種としての）に if ... や if ... else ... や while ... だけを使用させ、gotoの使用を禁止すれば、ダメな連中でも少しはましなプログラムを書いてくるだろう、とういうのである。これもまた実におもしろい発想で、広く影響を及ぼしたが、内容はDijkstra流とはほとんど無関係と言ってよい。
    • 木村泉,米澤明憲『算法表現論』 12巻、岩波書店〈岩波講座 情報科学〉、1982年。  pp.57-58
  5. ^ Herman H. Goldstine, John von Neuman (1947), Planning and coding of problems for an electronic computing instrument, https://library.ias.edu/files/pdfs/ecp/planningcodingof0103inst.pdf 
  6. ^ 河村(1995) p.112
  7. ^ 構造化プログラミング(1972)p.2
  8. ^ ダイクストラは作法としてプログラムは順次プログラムであるように記述するべきとしただけで、プログラミング言語に構文論的制約をつけるかどうかについては述べていない。順次プログラムはちょうど数学における"関数"（function）とみることもできることから、構造化プログラミングは関数型プログラミングと親和性が高い（関数型プログラミングは構造化プログラミングとは全く異なる考え方のはずだが？）。[要出典]
  9. ^ ミルズはこれを順次プログラムではなく固有プログラム（proper program）と呼んだ。
  10. ^ 論争だけが取り上げられた結果、goto-lessプログラミングやtop-downプログラミングは構造化プログラミングと同一視されることとなってしまった。筧, 捷彦 (1975). “ストラクチャード・プログラミング用言語”. 情報処理 (情報処理学会) 16 (10): 856-863. NAID 110002720279. 。
  11. ^ 任意の制御構造をもつ順次プログラムがこの３種類の基本制御構造を組み合わせることで実現できるということを主張する構造化定理（structured theorem）は、ダイクストラらが構造化プログラミングを提唱した1972年の７年後の1979年にRichard C. Linger, Bernard I. Witt, H. D. Millsの共著本によって示された。Structured Programming
  12. ^
    いままで３つの型の分解をみてきました。それらは、おのおの連接（concatenatoin）、選択（selection）、繰り返し（repetition）とよべるでしょう。最初の２つは、数え上げの推論で、また最後のは、数学的帰納法で理解されます。 —  E.W. ダイクストラ 、 構造化プログラミング(1972) p.22
  13. ^ ここでプログラムの「検証」（verify）という専門用語を用いたくなるが、ダイクストラ自身は構造化プログラミングの論文の中でこの用語を専門用語として用いておらず、あくまで「プログラムの正しさの証明の理解」と述べている。(E.W.Dijkstra, C.A.R.Hoare & O.-J.Dahl 1972, p. 7)ほか
  14. ^ ダイクストラの構造化プログラミングの範疇においては、ここで、順次プログラムの中にgoto文を一行でも入れてしまうと、数え上げ推論による正しさの確認ができなくなってしまい、「ソフトウェア全体の正しさ」というものが原理的に定義できなくなってしまうのである（ダイクストラはプログラムの自動変換は認めておらず構造化定理はその場合適用できない）。
  15. ^ ダイクストラが提案したのは次の三つであり、それらを駆使できる構造を持ったプログラム開発が構造化プログラミングであった。
    三つの知性の道具
    1. 数え上げ推論（enumeration）：一人の人間の能力でできる範囲でプログラムの命令の妥当性を一つ一つ確認すること
    2. 数学的帰納法（mathematical induction）：while文など計算機特有の繰り返し文についてのみ数学的帰納法を用いて確認すること
    3. 抽象（abstraction）：処理のまとまりに名前をつけた上で詳細化を後回しにし、仮に正しいとしておくこと
  16. ^ StructuredProgramming(1979)
  17. ^ 構造化プログラミング(1972) p.22
    すなわち、人間が把握することができるようにするために３つの種類に限定したのである。
  18. ^ ただし、ダイクストラの構造化文の限定の仕方は数学的ではない。
  19. ^ ダイクストラの構造化プログラミングの範疇では、goto文を含むプログラムの正しさを他者に証明して納得させる方法がないからである。
  20. ^ C.A.R.Hoare, "Structured programming in introductory programming courses", Structured Programming, Infotech state of the art report, 1976, pp.257-263, Infotech International.
  21. ^ goto文を避けて構造化文を用いるようプログラマーに教えることが、構造化プログラミングの伝統的な知恵である[20]
  22. ^ N.ヴィルト, 系統的プログラミング/入門, 野下浩平, 筧捷彦, 武市正人 訳, 近代科学社, 1978.
  23. ^ StructuredProgramming(1979) p.118

参考文献

[編集]

関連項目

[編集]
コンピュータ・プログラミング言語の関連項目
言語水準
言語処理系
言語分類
その他
関連項目
「https://ja-two.iwiki.icu/w/index.php?title=利用者:I.hidekazu/ミルズの構造化プログラミング&oldid=90241198」から取得