|
# 1969年に計算機科学者の[[エドガー・ダイクストラ|ダイクストラ]]が発表した論文<ref name="structured_programming" />。構造化プログラミング（''structured programming''）という言葉はこれが初出となる。内容はプログラムの構造設計に関するものであり、抽象から細部へのトップダウン設計、抽象データ＋抽象ステートメントのモジュール、細部ジョイントといった考え方が提唱されていた。
#1966年に計算機科学者の[[コラド・ベーム|ベーム]]とヤコピーニが発表した論文。内容はコーディングに関するものであり、順次、選択（if-then-else）、反復（while）の三つの制御文であらゆる[[制御フローグラフ|フローグラフ]]をカバーできると提唱し、その数学的証明が添えられていた。goto文と共にbreak文とcontinue文も排除したのが要点であり（3）との相違点でもある。本来はベームとヤコピーニの証明と呼ぶべきものだが、後年に幾つかの事情から[[構造化定理|構造化定理（''structured theorem）'']]として紹介された為にダイクストラの構造化プログラミングとの混同を招く事になった。
#1958年に公開された「[[ALGOL|ALGOL 58]]」などを先例とする[[プログラミングパラダイム]]の一つ。goto文を多用する非構造化プログラミング（''unstructured programming''）の対義語である。順次、選択、反復といった制御フローとサブルーチンをブロック単位で記述し、それらを直列または入れ子状に配置する事でプログラムの構造化を実現するという考え方である。プログラミング言語を分類する際のカテゴリ名として使われる事が多い。
今日の構造化プログラミングに対する一般的な認識は（3）になっている。しかし（1）の[[エドガー・ダイクストラ|ダイクストラ]]が提唱した理論が本来の意味での「'''構造化プログラミング'''」であり本項では（1）について説明する。（2）については「'''[[構造化定理]]'''」が該当記事になる。
== 一般認識としての構造化プログラミング ==
正確な定義をさて置くと、国内における構造化プログラミングの一般認識はコーディングレベルのテーマであり、プログラム文全体にブロック単位の制御構造（''control structures''）を導入する事を意味する。ブロックは括弧記号またはBEGIN&ENDなどで区切られた一行以上のステートメントのかたまりである。視覚的に判別しやすいブロックの起点と終点が自動的にフロージャンプの位置指定になるので、結果的に無差別ジャンプのgoto文を使わないで済むようになる。制御構造には以下の四種がある。
# 順次（''sequence''）ステートメントを順々に処理する。
# 選択（''selection''）条件式の結果に従って次に実行するステートメントまたはブロックを選択してフロー分岐する。
# 反復（''repetition''）特定の状態になるまでステートメントまたはブロック内を繰り返す。状態の確認はループ起点時またはループ終点時の二通りある。
# サブルーチン（''subroutine''）これをコールした次のステートメントにリターンする事を前提にして対象ブロックの起点にジャンプする。終点に達すると自動的にリターンする他、その途中の任意の位置でもリターンできる。
== 概要 ==
後半では'''抽象'''（''abstraction''）と'''細部'''（''refinement''）という二つの対になる言葉が定義され、プログラム全体をピラミッド風に階層分割して上の方を抽象化、下の方を細部化とした。ダイクストラは、下の方の部品から上の方の統合枠に向かって作り上げていく従来の開発手順を'''段階的抽象'''（''step-wise abstraction''）と呼び、テスト結果と進捗状況を明確にする堅実な手段であるとしながらも、あえてこれとは逆方向の開発手順を提唱した。細部からの開発手順は各部品間の依存関係を生みやすく、これがテスト回数の指数的な増加につながり、ひいてはソフトウェア危機の元凶になっていると見なしたからである。抽象から細部に向かうという上から下への（''from top to bottom''）開発手順は当時馴染みが無かったので、if文のthen節とelse節をそれぞれ抽象化した例えで実現可能な事が説明された。順次、選択、反復のいわゆる構造化フローに触れられたのはこの文節だけである。
抽象階層からプログラムを構築する為の手段として、[[ALGOL]]プログラムのInteger型の扱いを参考にしたダイクストラは、'''細部ジョイント'''（''joint refinement''）というプログラム概念を提示した。これは抽象階層では仕様決定できない実装データ（=細部データ）を扱うための仕組みである。細部ジョイントが扱う表わすデータは'''''抽象データ'''''（''abstract data structures''）と定義され、それを抽象階層向けに出力ないし入力する仲介ルーチンは'''抽象ステートメント'''（''abstract statements''）とされた。抽象データとそれに関連する抽象ステートメントをひとまとめにしたいわゆる[[モジュール]]をダイクストラは'''真珠'''（''pearl''）と呼んだ。細部ジョイントはオブジェクト指向における[[インタフェース (抽象型)|インターフェース]]、真珠は[[クラス (コンピュータ)|クラス]]に相当するものと考えてよい。同論上で[[Simula|Simula67]]のclass構文も引き合いに出されている。
各真珠は互いに依存関係がない独立したモジュールなので連結または分離時の副作用が無く、これによりテスト回数の指数的な増加を回避できるとされた。真珠は細部ジョイントによって抽象から細部に向けて順々に連結されてプログラム全体を構築する。細部ジョイントを糸に見立てたこの数珠繋ぎの「構造化」をダイクストラは'''真珠のネックレス'''（''necklaces strung from pearls''）と呼んだ。真珠は細部ジョイントから随時切り離して必要に応じた別の真珠に交換する事も出来るので、テスト回数を増やす事なく移植や仕様変更にも柔軟に対応できるものとされた。いずれの眼目もプログラムの正当性（''correctness''）を証明（''demonstration''）する為のテスト作業量を軽減する事にある。これがダイクストラの唱える構造化プログラミングの趣旨である。
ダイクストラも“Go To Statement Considered Harmful”においては最後の段落で、goto文の（論理的な）余分さを証明したようだと軽く触れたのみであり、作られるフローチャートは元のものより正しさの証明が簡単になるとは思えないためジャンプを含まないフローチャートの機械的な作成は推奨しないとした。
== ダイクストラによるプログラムの正しさの検証手法 ==
コンピュータは与えたプログラムに応じてそれを計算し結果を出力するという装置であるが、プログラムに誤りがあると、当初の意図した命題（仕様）を肯定しないものとなる{{#tag:ref|たとえば、一律に個々の構成要素が正しい確率を p とすると、N 個の構成要素からなるプログラム全体が正しい確率 P は、安直に計算すれば、
: P = p<sup>N</sup>
となり、 N が大きいプログラム（大規模なソフトウェア）においては、誤りの混入により命題（仕様）を肯定しない可能性は飛躍的に高まることがわかる。|group="注釈"}}。
プログラマは、正しいプログラムを作り出すばかりでなく、納得のいくやり方で正しさを証明することも仕事の一つであるという立場を取っていた<ref>[[#構造化プログラミング(1975) |構造化プログラミング(1975)]] p.6</ref>ダイクストラは、プログラムの正しさの納得のいく証明を遂行するための手法を導入した<ref>これは計算機や大規模プログラムを一種のブラックボックス化された機械装置とみなしてテストによって正しさを確認する手法ではない。ダイクストラは、テストはプログラムに対する疑いを全て取り除くには不十分であることを主張していた。[[#構造化プログラミング(1975)|構造化プログラミング(1975)]] p.5 <br />
これについてダイクストラは「テストはバグの存在を示すには有効だが、バグが存在しないことは証明できない」という表現を好んで用いた。
*E.W.ダイクストラ, “謙虚なプログラマ”, ''ACMチューリング賞講演集'', 木村泉 訳, 共立出版, 1989, pp.23-43.
*[http://www.cs.utexas.edu/users/EWD/transcriptions/EWD02xx/EWD273.html E.W.Dijkstra, "The Programming Task Considered as an Intellectual Challenge", 1969.]
*[http://www.cs.utexas.edu/users/EWD/transcriptions/EWD02xx/EWD288.html E.W.Dijkstra, "Concern for Correctness as a Guiding Principle for Program Composition", 1970.]
*[http://www.cs.utexas.edu/users/EWD/transcriptions/EWD03xx/EWD361.html E.W.Dijkstra, "Programming as a discipline of mathematical nature", 1973.]
</ref>。ただし、その検証<ref>D.グリースはプログラムの正しさの証明を、抽象的なレベルでは正当性証明、具体的なレベルではプログラムの検証と言葉を使い分けているが、ここでは厳密な区別はしない。
*金山裕 編, "構造的プログラミング −批判と支持−", ''bit'', Vol.7, Issue 7, 1975, pp.6-13, 共立出版.</ref>を実行するためには対象となるプログラムは「うまく構造化」されていなくてはならず、その「うまく構造化」されたプログラムを開発する手法が'''構造化プログラミング'''である{{#tag:ref|すなわち、プログラム検証と構造化プログラミングとは不可分の関係にある。|group="注釈"}}<ref>所与のプログラムの正しさを後付けで証明することは、はじめから証明を意識して作られたプログラムの場合より難しいことが経験的に知られている、と言われる。
*E.W.Dijkstra, "Programming methodologies, their objectives and their nature", ''Structured Programming'', Infotech state of the art report, 1976, pp.205-212, Infotech International.</ref>。
; ダイクストラの三つの知性の道具
# 数え上げ推論（enumeration）：一人の人間の能力でできる範囲でプログラムの命令の妥当性を一つ一つ確認していく作業
# 数学的帰納法（mathematical induction）：while文など計算機特有の多数の繰り返し文についてのみ数学的帰納法を用いて確認する作業
# 抽象（abstraction）：プログラムのブロックなどに名前をつけ、さらに中身を見ないで正しいと仮定することで検証作業を後回しにする操作
'''プログラムの正しさに関する様々な意見'''
構造化プログラミングの支持者らは、プログラムの正しさの重要性と証明の方法や表明(assertion)の使い方について熱心に説いた<ref name="the_science_of_programming" /><ref name="structured_programming_72" /><ref name="how_to_solve_it_by_computer">R.Geoff Dromey, ''How to Solve it by Computer'', Prentice Hall, 1982. </ref><ref name="the_craft_of_programming">[http://www.cs.cmu.edu/~jcr/craftprog.html John C. Reynolds, ''The Craft of Programming'', Prentice-Hall, 1981.]</ref>。
ダイクストラは、プログラミングと同時にプログラムの証明を（わずかに証明を先行して）進めることを推奨している<ref name="a_discipline_of_programming">E.W.ダイクストラ, ''プログラミング原論 ― いかにしてプログラムをつくるか'', 浦昭治訳, サイエンス社, 1983. </ref>。そのようなアプローチでプログラムの正当性の問題にあたれば、複雑な問題であっても知的管理が可能であると述べた{{#tag:ref|ダイクストラはプログラミングと証明を並行するのに適した、最弱事前条件をによる検証方法を考案した。ホーア論理は作り終わったものは証明できるが、これから作るプログラムについては指標を与えてくれない<ref name="software_cleanroom">二木厚吉 監修, ''ソフトウェアクリーンルーム手法'', 日科技連, 1997. </ref>。|group="注釈"}}。
また、プログラムの証明に対する反論も存在する。マイケル・ジャクソンは、個々のプログラムに証明を付けることは現実的には難しいだろうと述べている<ref name="bit1979_software_design">マイケル・ジャクソン, 吉村鉄太郎, 山崎利治, 大野徇郎, "ソフトウェア設計哲学", ''bit'', Vol.11, Issue 2, 1979, pp.4-12, 共立出版.</ref>{{#tag:ref|ジャクソンは構造化プログラミング手法の一つであるジャクソン法で有名なコンピュータ・コンサルタント。|group="注釈"}}。
==脚注==
| 