構造化プログラミング

出典: フリー百科事典『ウィキペディア(Wikipedia)』
移動先: 案内検索

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

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

概要[ソースを編集]

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

ダイクストラによるプログラムの正しさの検証手法[ソースを編集]

計算機(computer)は与えたプログラムに応じてそれを計算し結果を出力するという装置であるが、プログラムに誤りがあると、当初の意図した命題(仕様)を肯定しないものとなる[注釈 1]

プログラマは、正しいプログラムを作り出すばかりでなく、納得のいくやり方で正しさを証明することも仕事の一つであるという立場を取っていた[5]ダイクストラは、プログラムの正しさの納得のいく証明を遂行するための手法を導入した[6]。ただし、その検証[7]を実行するためには対象となるプログラムは「うまく構造化」されていなくてはならず、その「うまく構造化」されたプログラムを開発する手法が構造化プログラミングである[注釈 2][8]

そして、その手法とは、文の解釈過程そのものであり[注釈 3]、文(プログラム)を文節分けし、以下の三つのやり方を用いて文法の妥当性、個々の単語(名詞、動詞)の妥当性確認を再帰的に繰り返していくというものである[注釈 4]

ダイクストラの三つの知性の道具
  1. 数え上げ推論(enumeration):一人の人間の能力でできる範囲でプログラムの命令の妥当性を一つ一つ確認していく作業
  2. 数学的帰納法(mathematical induction):while文など計算機特有の多数の繰り返し文についてのみ数学的帰納法を用いて確認する作業
  3. 抽象(abstraction):プログラムのブロックなどに名前をつけ、さらに中身を見ないで正しいと仮定することで検証作業を後回しにする操作

プログラムの正しさに関する様々な意見[ソースを編集]

構造化プログラミングの支持者らは、プログラムの正しさの重要性と証明の方法や表明(assertion)の使い方について熱心に説いた[9][10][11][12]。 ダイクストラは、プログラミングと同時にプログラムの証明を(わずかに証明を先行して)進めることを推奨している[13]。そのようなアプローチでプログラムの正当性の問題にあたれば、複雑な問題であっても知的管理が可能であると述べた[注釈 5]

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

構造化プログラミングの構成要素[ソースを編集]

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

三つの構造化文[ソースを編集]

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

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

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

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

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


歴史[ソースを編集]

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

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

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

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

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

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

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

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

脚注[ソースを編集]

注釈[ソースを編集]

  1. ^ たとえば、一律に個々の構成要素が正しい確率を p とすると、N 個の構成要素からなるプログラム全体が正しい確率 P は、安直に計算すれば、
    P = pN
    となり、 N が大きいプログラム(大規模なソフトウェア)においては、誤りの混入により命題(仕様)を肯定しない可能性は飛躍的に高まることがわかる。
  2. ^ すなわち、プログラム検証と構造化プログラミングとは不可分の関係にある。
  3. ^ ダイクストラ自身は「数学の証明」になぞらえたが、これは技巧的な点が強調される傾向が強くなるため適切ではない。
  4. ^ 自然言語の文の場合、労力の観点から厳密に用語の正統性を確認することはまれであるが、プログラムの場合、一回一回全部原始的な概念にまで立ち戻るという行為を行うというところが大きな違いである。
  5. ^ ダイクストラはプログラミングと証明を並行するのに適した、最弱事前条件をによる検証方法を考案した。ホーア論理は作り終わったものは証明できるが、これから作るプログラムについては指標を与えてくれない[14]
  6. ^ ジャクソンは構造化プログラミング手法の一つであるジャクソン法で有名なコンピュータ・コンサルタント。
  7. ^ ソフトウェア危機の始まりと構造化プログラミングの歴史について[9]の第23章に詳しい。
  8. ^ このカンファレンスの発表が「構造化プログラミング」という語の元であるという主張の出典は[22]

出典[ソースを編集]

  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 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. ^ 構造化プログラミング(1975) p.6
  6. ^ これは計算機や大規模プログラムを一種のブラックボックス化された機械装置とみなしてテストによって正しさを確認する手法ではない。ダイクストラは、テストはプログラムに対する疑いを全て取り除くには不十分であることを主張していた。構造化プログラミング(1975) p.5
    これについてダイクストラは「テストはバグの存在を示すには有効だが、バグが存在しないことは証明できない」という表現を好んで用いた、といわれる。
  7. ^ D.グリースはプログラムの正しさの証明を、抽象的なレベルでは正当性証明、具体的なレベルではプログラムの検証と言葉を使い分けているが、ここでは厳密な区別はしない。
    • 金山裕 編, "構造的プログラミング −批判と支持−", bit, Vol.7, Issue 7, 1975, pp.6-13, 共立出版.
  8. ^ 所与のプログラムの正しさを後付けで証明することは、はじめから証明を意識して作られたプログラムの場合より難しいことが経験的に知られている、と言われる。
    • E.W.Dijkstra, "Programming methodologies, their objectives and their nature", Structured Programming, Infotech state of the art report, 1976, pp.205-212, Infotech International.
  9. ^ a b c グリース, D. 筧捷彦訳訳 (1991). プログラミングの科学. 培風館. ISBN 4563007943. 
  10. ^ a b O.-J. Dahl and E. W. Dijkstra and C. A. R. Hoare, Structured Programming, Academic Press, London, 1972
  11. ^ R.Geoff Dromey, How to Solve it by Computer, Prentice Hall, 1982.
  12. ^ John C. Reynolds, The Craft of Programming, Prentice-Hall, 1981.
  13. ^ E.W.ダイクストラ, プログラミング原論 ― いかにしてプログラムをつくるか, 浦昭治訳, サイエンス社, 1983.
  14. ^ 二木厚吉 監修, ソフトウェアクリーンルーム手法, 日科技連, 1997.
  15. ^ マイケル・ジャクソン, 吉村鉄太郎, 山崎利治, 大野徇郎, "ソフトウェア設計哲学", bit, Vol.11, Issue 2, 1979, pp.4-12, 共立出版.
  16. ^ 筧, 捷彦 (1975). “ストラクチャード・プログラミング用言語”. 情報処理 (情報処理学会) 16 (10): 856-863. NAID 110002720279. 
  17. ^ a b 木村泉 (1975). “プログラミング方法論の問題点:超職業的プログラミングについて”. 情報処理 (情報処理学会) 16 (10): 841-847. NAID 110002720277. 
  18. ^ a b 山崎利治, "構造的プログラミング", プログラムの設計, 共立出版, 1990, pp.113-142.
  19. ^ 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. 
  20. ^ N.ヴィルト, 系統的プログラミング/入門, 野下浩平, 筧捷彦, 武市正人 訳, 近代科学社, 1978.
  21. ^ C.A.R.Hoare, "Structured programming in introductory programming courses", Structured Programming, Infotech state of the art report, 1976, pp.257-263, Infotech International.
  22. ^ 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. 
  23. ^ 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
  24. ^ 山崎利治, "流れ図", プログラムの設計, 共立出版, 1990, pp.110-113. ISBN 4320023781
  25. ^ 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. 
  26. ^ Linger,R.C., Mills, H.D., Witt, B.I., Structured Programming: Theory and Practice, Addison-Wesly, 1979.
  27. ^ E.W.ダイクストラ 木村泉 訳訳 (1975), GO TO 論争:第1部 go to 文有害説, 7, 共立出版, pp. 6-9 
  28. ^ B.リーヴェンワス編, ed. (1975), “GO TO 論争:第2部 GO TO 論争”, bit (共立出版) 7 (5): 10-26 
  29. ^ 木村泉, "GO TO 論争:第3部 解説", bit, Vol.7, Issue 5, 1975, pp.27-39, 共立出版.
  30. ^ B. Randell and J.N. Buxton, (Eds.), Software Engineering, NATO Scientific Affairs Division, Brussels, Belgium, 1969.
  31. ^ a b c “プログラミング−工芸から科学へ”, 情報処理 (情報処理学会) 18 (12): 1248-1256, (1977), NAID 110002753409 
  32. ^ a b 和田英一, "ダイクストラかく語りき", bit, Vol.9, Issue 1, 1977, pp.4-6, 共立出版.
  33. ^ a b 玉井哲雄 (2008), “ソフトウェア工学の40年” (PDF), 情報処理 49 (7): 777-784, NAID 110006830060, http://www.graco.c.u-tokyo.ac.jp/~tamai/pub/40yearsSE.pdf 
  34. ^ Edward Nash Yourdon ed., "Introduction (Chief Programmer Team Management of Production Programming)", Classics in Software Engineering, YOURDON inc., 1979, pp.63-64.
  35. ^ 木村泉, 米澤明憲, 算法表現論, 岩波書店, 1982.
  36. ^ D.シャシャ, C.ラゼール, "エズガー・W・ダイクストラ", コンピュータの時代を開いた天才たち, 鈴木良尚 訳, 竹内郁雄 監訳, 日経BP社, 1998, pp.61-74. ISBN 4822280462
  37. ^ 玉井哲雄, "ソフトウェア産業とソフトウェア研究の沈滞状況について", SEAMAIL, Vol.11, No.3, 1997, pp.2-5.
  38. ^ 玉井哲雄, "9th ICSEに参加して", SEAMAIL, Vol.2, No.7, 1987, pp.22-25.
  39. ^ a b 中山晴康, "ダイクストラ教授との3日間", bit, Vol.9, Issue 1, 1977, pp.7-9, 共立出版.
  40. ^ Edward Nash Yourdon, 構造化手法によるソフトウェア開発, 黒田純一郎, 渡部研一 訳, 日経BP社, 1987.

参考文献[ソースを編集]

関連項目[ソースを編集]

関連人物[ソースを編集]