構造化プログラミング
出典: フリー百科事典『ウィキペディア(Wikipedia)』 (2023/05/29 14:26 UTC 版)
歴史
第一幕
構造化プログラミングの誕生は、1960年代から浮上したソフトウェア危機問題と密接に結びついている。ソフトウェア危機とはコンピュータ性能の進化に伴うソフトウェア要求度の高まりが、プログラムサイズの際限無い肥大化と複雑化を招き、近いうちに現実的な期間内でのプログラム開発が不可能になるだろうとする悲観的予測である[注釈 1]。実際に1960年代のソフトウェア開発現場では仕様不一致、納期遅れ、予算超過といった事態が頻発していた[4]。当時のプログラムはgoto文を多用するタコ足フローチャートによるものが大半だったので[5]、すぐにスパゲティコード化することが多く、複雑怪奇なジャングルフロー図と化しているものも珍しくなかった[6]。1959年に計算機科学者ハインツ・ツェマネクは、goto文の多用に警鐘を鳴らす論文を発表している。1960年に公開されたプログラミング言語「ALGOL60」は、BEGINとENDで区切られたコードブロックを制御するIF選択文とFOR反復文を初めて提供していた。計算機科学者ニクラウス・ヴィルトはこれらを構造化文(structured statement)と呼んだ[7]。1966年に計算機科学者コラド・ベームとジュゼッペ・ヤコピーニは、あらゆるフローチャートは順次・選択・反復の組み合わせで表現できることの数学的証明をし、これはベームとヤコピーニの証明と呼ばれた[8]。計算機科学者ドナルド・クヌースは、これらの潮流を構造化文の第一幕と定義した[6]。
第二幕
1968年、計算機科学者エドガー・ダイクストラのACM機関紙への投書「Go To Statement Considered Harmful -goto文は有害-[9]」は、その物議を醸す題名でコンピュータプログラミング界隈にいわゆるgoto文論争を巻き起こした[10][11]。これは構造化文の認知度を高めることに貢献している[12]。これを構造化文の第二幕と定義したクヌースは「第二幕はそのムーブメントの大きさによって、多くの人にとっての第一幕になった」と評した[13]。1968年度開催のNATOソフトウェア工学会議でソフトウェア危機は正式な用語になり[14]、産業界と計算機科学共通の懸案事項になった[15]。翌69年度開催の同会議においてダイクストラは「Structured Programming -構造化プログラミング-[3]」と題した論文を寄稿した。これが「構造化プログラミング」の正式な初出である。その論旨はソフトウェア危機解決策としてのソフトウェア正当性検証技術の確立であり、プログラムを適切に分割し抽象化して良く構造化(well-structured)しておけば、プログラムサイズ拡大に関係なくその正当性を証明できるとしていた。その具体的手法としてはトップダウン設計、段階的な抽象化、階層的なモジュール化、抽象データ構造と抽象ステートメントを連携させる共同詳細化などが挙げられていた。goto文抑制など構造化文に関する事柄は数行に留まっていたが[注釈 2]、goto文論争に熱心なプログラマの間ではこの論文を昨年の投書の延長と見る向きも少なからず存在していた。後年のダイクストラは構造化プログラミングという言葉を作った際に二つの失敗をしたと述べている。商標登録しなかった事と、厳密な定義化を避けた事である[16][15]。
第三幕
1960年代からの構造化文第一幕の潮流は、産業プログラム界隈にも影響を及ぼしており、こちらでは制御構造(control structures)などの名義でフローチャートに導入されていた。産業コンピュータ市場の最大手であるIBM社の上席研究員ハーラン・ミルズは制御構造を重視し、ニューヨーク・タイムズ社のニュースアーカイブシステム構築プロジェクトで大きな成功を収めた。順次・選択・反復の制御構造は、IBM社のプログラミング規範をまとめたImproved Programming Technologies通称「IPT」に採用され、後に同社の技術セミナーなどを通して広く流布されるようになった[17][18]。1970~71年頃から計算機科学者デビッド・ハレルは、前述のベームとヤコピーニの数学的証明に「Structure theorem -構造化定理-」という全く新しい題名を付けて主に産業ソフトウェア開発界隈で紹介した[19][注釈 3]。ハレルはこの命名が実はハーラン・ミルズの提案であったことを後に明かしている[20]。構造化定理はIPTの合理性を裏付ける根拠として盛んに引用されたので、構造化(Structured)プログラミングと言えばIBM社の発明品だと信じるプログラマたちも続出した[21]。IBM社が1974年頃から発表するようになった所属研究員たちによるプログラム開発方法論の数々にも構造化(Structured)の接頭辞が付けられていたが、それらは抽象化を重視するダイクストラの構造化とは異なり、サブルーチン複合体とデータ構造を適切に連携させるための構造化であった。その違いを指摘して本来のダイクストラ方式を改めて紹介する動きもあったが、抽象化指向のダイクストラ理論は産業界ではむしろ不人気でさえあった[22][23][24]。クヌースの言葉を借りれば、構造化文の第三幕はIBM社とハーラン・ミルズがプロモートした制御構造の舞台になり、構造化プログラミングに対する世間一般の認識はこちらの方で定着するようになった。
終幕
後年、ダイクストラは自身が作った構造化プログラミングという言葉に不快感を示して避けるようになった[25]。この言葉を作った時、彼はプログラミングが手工芸から科学へ発展することを期待していた[16]。しかし構造化プログラミングという言葉は実利を求めるために使われるようになった[25]。次のような逸話がある。構造化開発の第一人者エドワード・ヨードンの事務所にセミナー依頼の電話がかかってきた。プロジェクトメンバー全員に構造化プログラミングを1日で叩きこんで欲しいという内容である。それが終わったらプロジェクト期間を半分にするという。その理由は「構造化プログラミングは生産性を2倍にするという話ですから」であった[26]。
- ^ ソフトウェア危機の始まりと構造化プログラミングの歴史について[4]の第23章に詳しい。
- ^ "statements transferring control to labelled points" という言葉で一応 goto 文に触れている[3]
- ^ Harel,David (1980)."On Folk Theorems"(PDF)のP381の左列の中央にハーラン・ミルズ(Harlan Mills)が未公表の講義資料の中で "The Structure Theorem" と名付けたことが書かれている。この資料の出典[67]が1972年のため構造化定理が発明されたのは1970年代初頭と推測される。
- ^ 直接は無関係だが、ダイクストラはBASIC批判の急先鋒でもあった。マイコン普及以前の1970年代に既に、BASICでプログラミング教育をすべきでない、と強く主張している(wikiquote:Edsger W. Dijkstra#How do we tell truths that might hurt? (1975))。
- ^ すなわち、プログラム検証と構造化プログラミングとは不可分の関係にある。
- ^ D.グリースはプログラムの正しさの証明を、抽象的なレベルでは正当性証明、具体的なレベルではプログラムの検証と言葉を使い分けているが[36]、ここでは厳密な区別はしない。
- ^ ダイクストラはプログラミングと証明を並行するのに適した、最弱事前条件をによる検証方法を考案した。ホーア論理は作り終わったものは証明できるが、これから作るプログラムについては指標を与えてくれない[47]。
- ^ 形式化にとらわれない点では(当時のダイクストラの)構造化プログラミングは形式手法と趣きが異なる。なおプログラムの正しさの証明とはウォークスルーやインスペクションによるレビューではなく、帰納法や最弱事前条件による検証を指す。 形式的でない証明の方法については、ロバートの「プログラムの証明」[43]が良い入門書の一つである。
- ^ “構造化プログラミングとは - IT用語辞典”. IT用語辞典 e-Words. 2020年6月1日閲覧。
- ^ “構造化プログラミング - 意味・説明・解説 : ASCII.jpデジタル用語辞典”. yougo.ascii.jp. 2020年6月1日閲覧。
- ^ a b c d e f 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.
- ^ a b c グリース, D. 筧捷彦訳 (1991). プログラミングの科学. 培風館. ISBN 4563007943
- ^ 山崎利治, "流れ図", プログラムの設計, 共立出版, 1990, pp.110-113. ISBN 4320023781
- ^ a b c d 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.
- ^ a b c N.ヴィルト, 系統的プログラミング/入門, 野下浩平, 筧捷彦, 武市正人 訳, 近代科学社, 1978.
- ^ Böhm, C.; Jacopini, G (1966). “Flow Diagrams, Turing Machines And Languages With Only Two Formation Rules”. Communications of the ACM (ACM, New York, NY, USA) 9 (5): 366-371. CiteSeerx: 10.1.1.119.9119.
- ^ a b E. Dijkstra (1968). “Go To Statement Considered Harmful”. Communications of the ACM 11 (3): 147-148. CiteSeerx: 10.1.1.132.875.
- ^ E.W.ダイクストラ 木村泉訳 (1975), GO TO 論争:第1部 go to 文有害説, 7, 共立出版, pp. 6-9
- ^ B.リーヴェンワス編, ed. (1975), “GO TO 論争:第2部 GO TO 論争”, bit (共立出版) 7 (5): 10-26
- ^ 木村泉, "GO TO 論争:第3部 解説", bit, Vol.7, Issue 5, 1975, pp.27-39, 共立出版.
- ^ 有澤誠訳『文芸的プログラミング』p.45
- ^ B. Randell and J.N. Buxton, (Eds.), Software Engineering, NATO Scientific Affairs Division, Brussels, Belgium, 1969.
- ^ a b c E.W.ダイクストラ (1977), “プログラミング−工芸から科学へ”, 情報処理 (情報処理学会) 18 (12): 1248-1256, NAID 110002753409
- ^ a b 和田英一, "ダイクストラかく語りき", bit, Vol.9, Issue 1, 1977, pp.4-6, 共立出版.
- ^ a b 山崎利治, "構造的プログラミング", プログラムの設計, 共立出版, 1990, pp.113-142.
- ^ 玉井哲雄 (2008), “ソフトウェア工学の40年” (PDF), 情報処理 49 (7): 777-784, NAID 110006830060
- ^ Linger,R.C., Mills, H.D., Witt, B.I., Structured Programming: Theory and Practice, Addison-Wesly, 1979.
- ^ a b c Harel, David (1980-07-01). “On folk theorems”. Communications of the ACM 23 (7): 379–389 .
- ^ Edward Nash Yourdon ed., "Introduction (Chief Programmer Team Management of Production Programming)", Classics in Software Engineering, YOURDON inc., 1979, pp.63-64.
- ^ a b 木村泉 (1975). “プログラミング方法論の問題点:超職業的プログラミングについて”. 情報処理 (情報処理学会) 16 (10): 841-847. NAID 110002720277.
- ^ 木村泉, 米澤明憲, 算法表現論, 岩波書店, 1982.
- ^ D.シャシャ, C.ラゼール, "エズガー・W・ダイクストラ", コンピュータの時代を開いた天才たち, 鈴木良尚 訳, 竹内郁雄 監訳, 日経BP社, 1998, pp.61-74. ISBN 4822280462
- ^ a b 中山晴康, "ダイクストラ教授との3日間", bit, Vol.9, Issue 1, 1977, pp.7-9, 共立出版.
- ^ Edward Nash Yourdon, 構造化手法によるソフトウェア開発, 黒田純一郎, 渡部研一 訳, 日経BP社, 1987.
- ^ “What led to “Notes on Structured Programming””. 2020年1月閲覧。
- ^ 筧, 捷彦 (1975). “ストラクチャード・プログラミング用言語”. 情報処理 (情報処理学会) 16 (10): 856-863. NAID 110002720279.
- ^ “E.W. Dijkstra Archive: What led to "Notes on Structured Programming" (EWD1308)”. www.cs.utexas.edu. 2021年8月16日閲覧。
- ^ E.W.ダイクストラ, W.H.J.フェイエン, プログラミングの方法, 玉井浩 訳, サイエンス社, 1991.
- ^ a b O.-J. Dahl and E. W. Dijkstra and C. A. R. Hoare, Structured Programming, Academic Press, London, 1972
- ^ 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
- ^ 構造化プログラミング(1975) p.6
- ^ D.グリースはプログラムの正しさの証明を、抽象的なレベルでは正当性証明、具体的なレベルではプログラムの検証と言葉を使い分けているが、ここでは厳密な区別はしない。
- 金山裕 編, "構造的プログラミング −批判と支持−", bit, Vol.7, Issue 7, 1975, pp.6-13, 共立出版.
- ^ 所与のプログラムの正しさを後付けで証明することは、はじめから証明を意識して作られたプログラムの場合より難しいことが経験的に知られている、と言われる。
- E.W.Dijkstra, "Programming methodologies, their objectives and their nature", Structured Programming, Infotech state of the art report, 1976, pp.205-212, Infotech International.
- ^ 金山裕 編, "構造的プログラミング −批判と支持−", bit, Vol.7, Issue 7, 1975, pp.6-13, 共立出版.
- ^ a b R.Geoff Dromey, How to Solve it by Computer, Prentice Hall, 1982.
- ^ E.W.ダイクストラ, “謙虚なプログラマ”, ACMチューリング賞講演集, 木村泉 訳, 共立出版, 1989, pp.23-43.
- ^ E.W.Dijkstra, "The Programming Task Considered as an Intellectual Challenge", 1969.
- ^ E.W.Dijkstra, "Concern for Correctness as a Guiding Principle for Program Composition", 1970.
- ^ E.W.Dijkstra, "Programming as a discipline of mathematical nature", 1973.
- ^ John C. Reynolds, The Craft of Programming, Prentice-Hall, 1981.
- ^ a b ロバート B.アンダーソン, 演習プログラムの証明, 有沢誠 訳, 近代科学社, 1980.
- ^ 小野寛晰, プログラムの基礎理論, サイエンス社, 1975.
- ^ E.W.Dijkstra, "Programming methodologies, their objectives and their nature", Structured Programming, Infotech state of the art report, 1976, pp.205-212, Infotech International.
- ^ a b c E.W.ダイクストラ, プログラミング原論 ― いかにしてプログラムをつくるか, 浦昭治訳, サイエンス社, 1983.
- ^ 二木厚吉 監修, ソフトウェアクリーンルーム手法, 日科技連, 1997.
構造化プログラミングと同じ種類の言葉
- 構造化プログラミングのページへのリンク