構造化プログラミングとは、だいたい段階的詳細化法のことだ。

## はじめに
+ **構造化プログラミングとは、段階的詳細化法＋プログラム正当性証明** ・・・＋α（データ構造論、オブジェクト指向）のことである。
+ 特に、段階的詳細化法が肝心。プログラム正当性証明は自分の力量を超えるのでパス。
+ goto文の追放やgoto-lessプログラミング、構造化定理は関係ないという意見も見受けられるがこれは誤解。ハーラン・ミルズも構造化プログラミングの提唱者の一人である。
  →[意外と知られていない構造化プログラミング](https://www.tatapa.org/~takuo/structured_programming/structured_programming.html)とか[翻訳：構造化プログラミングを最初に提唱した文書](https://calculator-cafe.com/readings/Structured_programming/Structured_programming.html)とか。

これから次のような構造の無いフローチャートに対して、構造のあるフローチャートとはどういうものか見ていくことにする。
![RUNCIBLE.png](https://qiita-image-store.s3.ap-northeast-1.amazonaws.com/0/62130/8803dc92-405b-a4b1-9a69-33fd6f7dde52.png)
構造化プログラミング以前のどこからどう読めばいいのかわからない構造の無いフローチャート。
D.Knuth "RUNCIBLE—algebraic translation on a limited computer"から
### 構造化プログラミングの思想の概要
構造化プログラミングとは、ソフトウェア危機（software crisis）が叫ばれたのを受けて出てきた科学的なプログラミング方法である。
ダイクストラが主張したことは、それまでのプログラミングは人間の能力の限界というものを考慮していないので **常人の能力でも可能** なプログラミングに改めようということであった。
その象徴がgoto文で、goto文の多用は一部の天才プログラマには理解可能なものかもしれないが、**常人の能力では** 、goto文で生成されるプログラムの字面と乖離している計算プロセスを追うことができないからである。
そのため、常人の能力でも理解可能・正しさを確認可能な、連接（concatenation）、交代（alternation）、繰り返し（repetition）の制御構文と関数呼び出し（involving）による抽象（abstraction）を付け加えた４要素を原則とするプログラミングをしようとした。

なお、職人芸プログラミングができる天才プログラマがgoto文が多用することは否定していない。

IBM社のハーラン・ミルズは、大規模プログラム開発にあたって、従来一人でやることが常だったプログラミングを、構造化プログラミングの手法を利用して、多数人によるチームで開発できるものに変えた。

![適用前後構造化プログラミング.png](https://qiita-image-store.s3.ap-northeast-1.amazonaws.com/0/62130/e8d548bf-8bb4-12fe-3865-200413fc2a74.png)

人間には、ふつう得意・不得意がある。たとえ、天才プログラマであっても、一人であれば、一日に書けるプログラムの量には限界があるし、得意な機能と知識不足でうまく実装できない機能などが出てくるのは当然である。
大規模かつ非常に多機能なソフトウェアを供給するには天才プログラマの職人芸に頼っているだけでは原理的に無理なのであった。つまり、機能ごとに多人数のプログラマに実装を分業させる必要があった（[分業化ってなに？](https://manabow.com/hayawakari/hayawakari14_1.html)）。その分業を可能にする「構造（structure）」を提供するのが構造化プログラミングであったのである。

ただし、分業化の構造を提供すると言っても、構造化プログラミングはトップダウン形式の分業ができるだけで、ボトムアップ式の再利用・組み立てはできなかった。ボトムアップ式が可能になったのはオブジェクト指向プログラミングが一般的になるまで待たなくてはならなかった。

## おさらい
構造化プログラミングの通説的な説明は知っていること前提の説明。
### 構造化定理（structure theorem）
1966年に、ベームとヤコピーニは、gotoを含むどんなプログラムも、次の３つの基本制御構造
+ 順次（sequential）または連結（concatenation）、
+ 交代（alternation）または選択（selection）、
+ 繰返し（iteration）または反復（repetition）

<img width="200" alt="連接.png" src="https://qiita-image-store.s3.ap-northeast-1.amazonaws.com/0/62130/7ac873bf-0c29-5acb-f5a6-d50b0df32b67.png" />
<img width="200" alt="選択.png" src="https://qiita-image-store.s3.ap-northeast-1.amazonaws.com/0/62130/ede6f2b3-fc87-808d-c2d0-c406bdef9dc6.png" />
<img width="200" alt="繰返し.png" src="https://qiita-image-store.s3.ap-northeast-1.amazonaws.com/0/62130/9006da06-e81b-f6f8-ff16-747ee809f34b.png" />

だけを使って等価なプログラムに変換できるということを主張した（ただし、証明についてはアウトラインだけを示しただけで **実際に証明はしなかった。** 実際に証明をして、「構造化定理」という名称を与えたのはハーラン・ミルズでこの6年後の1972年）。

この基本の制御構造は、構造化文（structured statment）とかダイクストラ（Dijkstra）にちなんでD-構造（D-structure）と呼んだりする。

### goto-lessプログラミング（goto-less programming）
構造化定理によってgoto文を使わずとも任意のプログラムを書くことができることが保証される。

つまりgotoの無いもしくはgotoの少ないプログラミング、すなわちgoto-lessプログラミングが可能となる（goto-lessプログラミングという名称は、ウィリアム A.ウルフ["Programming without the goto"](https://www.cs.tufts.edu/comp/150FP/archive/bill-wulf/oprogramming-without-goto.pdf) によるものが始まり）。

つまりこれは、構造化文を駆使してgoto文を排除することで、例えばgotoがあるということと、フローチャートの標準形がないということから、昔の左側のどこからどう読めばいいかわからないフローチャートも
![新旧フローチャート.png](https://qiita-image-store.s3.ap-northeast-1.amazonaws.com/0/62130/d8f7c30b-275e-4b1b-1e72-6e08d941120e.png)
右図のように上から順に読み下せる標準的なフローチャートでかけるわかりやすいプログラムにすることができる（脚色してます。当然上のフローチャートが直接下のフローチャートに対応するわけではありません。）というものだった。

 **普通このgoto-lessプログラミングが構造化プログラミングと呼ばれることが多い。が、これは実は不十分である。**

## 段階的詳細化法（stepwise refinement）へ
### 呼び出し（involving）による抽象化
プログラミング技術において抽象化の方法は数あれど、構造化プログラミングにおけるメインかつ唯一の抽象化技法は

+ **関数呼び出し** 

であり、この関数呼び出しの活用が構造化プログラミングの肝心なところである。

たとえば、こういうちょっと長めのフローチャートがあったとする。
![簡約可能フローチャート.png](https://qiita-image-store.s3.ap-northeast-1.amazonaws.com/0/62130/9774f5b4-a032-c0c2-35ce-10bd3ae30ef0.png)
C言語のmain関数に全部のアルゴリズムを書いてしまっているプログラムを見ることがあるかもしれないが、それを想像してもらえばいい。goto文を使っていなければ、そのようなプログラムも立派なgoto-lessプログラムである。
しかし、そのようなベタ打ちのプログラムが100行、200行程度であれば許容範囲だが、それも1万行、2万行も続くと今度は解読の困難が発生する。ここで出てくるのがダイクストラ先生の主張した抽象化（abstraction）である。具体的には **関数呼び出し** （手続きの呼び出し、サブルーチンの呼び出しなど呼び方は様々だが関数呼び出しで統一する）である。いろいろごちゃごちゃと説明するよりも以下の図を見てもらう方がわかりやすいだろう。
![関数呼び出しありのフローチャート.png](https://qiita-image-store.s3.ap-northeast-1.amazonaws.com/0/62130/08935490-31e3-45a8-b5b6-182390ed234b.png)

要するに連接（concatenation）された一連のまとまった処理を関数にすることで、処理に名称タグづけ（抽象化）することができる。こうするとなにがうれしいのかというと、タグ付けされた部分は一つの塊として正しいものとして、仕様さえ把握しておけば、元のコードの読解するにあたっては中身に立ち入らなくよくなるのである。つまり人間のコードの読解力を助けるわけである。

たとえば、1万行のベタ打ちmain文のプログラムと、トータルの行数はそれとほぼ同じだが、多数の関数から構成されているもののmain文の行数としては100行で済んでいるプログラムがあった場合、コードを読解するにあたっては後者の方が断然わかりやすいのは明らかだろう。

### トップダウン設計・トップダウン開発
上で示したgoto-lessプログラムを関数呼び出し（involving）で抽象化するという手法は当然繰り返すつまり入れ子にする（ネストする）ことができる。
これは、トップレベルプログラムからどんどん言語の基本命令に近づくように詳細化していくトップダウンの開発を可能にする。これを段階的詳細化法（stepwise refinement）と呼ぶ。分業化も以下の図のようにトップダウンの形で可能になる（ボトムアップ型はできない）。
![トップレベル設計.png](https://qiita-image-store.s3.ap-northeast-1.amazonaws.com/0/62130/ac0a018e-2079-6af8-3193-f3f3cfcdb7fa.png)
![分業化の図.png](https://qiita-image-store.s3.ap-northeast-1.amazonaws.com/0/62130/f6cc2d55-a31a-294c-f101-8dab84a37ed4.png)

最終的に組み合わせたプログラム全体の構造は以下の図のようになる。この整った構造が、構造化プログラミングにおける構造（structure）である。
![段階的詳細化法.png](https://qiita-image-store.s3.ap-northeast-1.amazonaws.com/0/62130/05d14a5b-24ba-5382-e7e8-e4467acb4747.png)
冒頭のKnuthの巨大なフローチャートとどちらが理解しやすいか比較してもらえば歴然である。
## まとめ
+ 構造化プログラミングの構成要素は以下の４要素
    + 順次（sequence）、
    + 選択（selection）、
    + 繰り返し（iteration）、
    + **関数呼び出し（involving）** 
+ 構造化プログラミングで行うトップダウン開発方法を段階的詳細化法という。
+ 段階的詳細化法により、それまでのプログラミングではほとんど困難だった複数人によるプログラミングが可能となる。
+ 構造化プログラミングでいうところの「構造（structure）」とは、この段階的詳細化法によってつくられるgoto-lessプログラムの入れ子構造のことである。
 根拠は以下のハーラン・ミルズのお言葉
> 試行錯誤のコンピュータプログラミング技術をソフトウェア工学へと変える革命のきっかけとなったのは、Dijkstraの構造化プログラミングの考え方である。構造化プログラミングは、どんどん複雑化するソフトウェアの問題を取り扱うため、２０年間以上も食い止められることなく増殖し続けてきた制御フローのジャングルを整理することに成功した。制御フローのジャングルは、どんなに複雑なソフトウェアでも３つの基本的な構造、順次（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頁
### 構造化プログラミングの欠点
+ トップダウン開発しかできない。ボトムアップ開発ができない。関数の再利用があまりできない。
→　オブジェクト指向へ（いつか記事にする）

## 参考資料
* レオナルド H.ワイナー．[構造化プログラミングのルーツ](https://qiita.com/iHdkz/items/3a3306a3311007871755)。
* E.W.ダイクストラ、C.A.R.ホーア、O.-J.ダール、『構造化プログラミング』、サイエンス社、1975年。
* 山崎利治、『プログラムの設計』、共立出版、1990年。
* 河村一樹、『ソフトウェア工学入門』、近代科学社、1995年。