ミルズの構造化プログラミング

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

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

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

概要

初期のフローチャート 。現代の規格化されたフローチャートと異なり、一見しただけでは、どこからどう読めばよいか把握することが困難である。 "Planning and coding of problems for an electronic computing instrument," 1947 から

制御処理が順次プログラムである「連接」・「選択」・「繰り返し」に限定された現代的なフローチャート（なお、ネストはされていない）。上から下に人間の思考過程に沿った形でプログラムの処理過程を理解することができる。

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

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

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

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

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頁。 収録

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

構造化文（structured statement）

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

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

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

抽象（abstraction）の一例

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

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

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

全体のプログラムの証明　＝

「抽象処理Rの詳細レベル０の証明」 × 「抽象処理Rの詳細レベル１の証明」

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

構造化定理（the structure theorem）

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

構造化定理（the structure theorem）

任意の固有プログラム（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.

参考文献

• E.W.ダイクストラ; C.A.R.ホーア; O.-J.ダール 著、野下浩平 訳『構造化プログラミング』サイエンス社、1975年。 
• 河村 一樹『ソフトウェア工学入門』近代科学社、1995年。 （改訂版は内容が異なる）
• Richard C. Linger,Harlan D. Mills,Bernard I. Wit (1979). IBM Corporation. ed. Structured Programming: Theory and Practice. Addison-Wesley. https://trace.tennessee.edu/cgi/viewcontent.cgi?article=1008&context=utk_harlan 

関連項目

• 構造化プログラミング
• 構造化定理 - goto文
• 段階的詳細化法
• IBM - ハーラン・ミルズ
• エドガー・ダイクストラ