構造化プログラミング

出典: フリー百科事典『ウィキペディア(Wikipedia)』
構造化から転送)
移動先: 案内検索

構造化プログラミング(こうぞうかプログラミング、structured programming)とは、1960年代後半にエドガー・ダイクストラらによって提唱された仮想機械モデルに基づく段階的詳細化法を用いたプログラミングのことを言う。歴史的経緯から、構造化プログラミングはIBMのMillsの提案に由来するgoto-lessプログラミングとして一部分を切り取られた形で広く知られている[1][2][3]

概要

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

歴史

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

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

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

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

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

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

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

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

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

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

三つの構造化文

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

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

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

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

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

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

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

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

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

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

goto論争

ダイクストラの主張

構造化プログラミングを提唱するダイクストラは、理論の帰結から、goto文を使うべきでないとする。

ダイクストラによる“Go To Statement Considered Harmful”[8]の趣旨は次の通りである。

人間が時間によって変化するプロセスを把握する能力は、プログラムの静的な関係を把握する能力に比べて劣っているため、静的なプログラムテキストの構造と時間によって変化するプロセスの構造をなるべく近づけるのが重要である。

そのためにはプロセスの進捗を表す簡潔な指標が必要がある。指標とは例えば実行中の行番号・その時点でのスタックトレース・行番号とループを回った回数のペアなどである。

例えば、1人が部屋に入るごとにカウンタを増やしていくプログラムにおいて、カウンタが室内の人数-1である瞬間はどこにあるのかという問いに答える際に、簡潔な指標があればすぐ答えられるが、簡潔な指標がなければ正確な答えは難しくなる。

goto文を無条件に許してしまうと簡潔な指標は得られなくなってしまうため、高水準プログラミング言語においてはgoto文は廃止するべきである。

以上が“Go To Statement Considered Harmful”の趣旨である。

その一方で、ダイクストラは“Structured Programming”[4]においてはgoto文には触れていないとクヌースは指摘している[6]。実際に“Structured Programming”においては“sequencing should be controlled by alternative, condtional and repetitive clauses and procedure calls, rather than by statements transferring control to labelled points.”との1文があるのみでそれ以外では触れていない。

また、3つの基本構造についても、“Go To Statement Considered Harmful”においては“I do not claim that the clauses mentioned (引用者註: 順次・分岐・手続き呼び出し・反復) are exhaustive in the sense that they will satisfy all needs”とし、プロセスの進捗を表す簡潔な指標が存在する限りは3つの基本構造には固執していない。

goto擁護派

一方、goto文を使わずに3つの基本構造による代替を行うと、理論上は同値であっても実際にはプログラムの実行速度や記憶容量の点で性能が劣化する場合があることを示し、goto文を擁護する意見もあった[48]

ACMの年次大会(1972)の討論会では、トップダウンでプログラムを分割するよりgoto文を使う方が適した事例があり、証明には関心がないという意見(William Wait)や、goto文を残せば選択の余地があるが、無くしてしまうと必要になったとき困るだろうという意見(Guy Steel)などが出された[12]

条件文とgoto文を正しく使うことで、FORTRANでもALGOLの基本機能を実現できることを例に挙げ、プログラマは必要な機能がプログラミング言語で直接表現できないとき、どのように実装するか工夫できるべきであるという主張もあった(S.W.スリア)[33]

中立派

特殊な場合にはgotoを使った方がプログラムの正当性を証明しやすくなると考える人もいる。例えばドナルド・クヌースは、著書「文芸的プログラミング」の中でそのような例をいくつかあげている[6]

こうした理由から、goto文を撲滅するのではなく上手に使い分けるべきだと考える人もいるテンプレート:誰

goto文論争が不毛なのは、「構造化プログラミングの観点からgoto文を使うのは望ましくない」という結論は真だが、「goto文を使わなければ構造化プログラミングになる」というわけではない点である。構造化プログラミングの本質の一つは、状態遷移の適切な表現方法とタイミングを見極めることである[49]。これはプログラムの良し悪しを決める永遠の命題であるといっていいテンプレート:要出典

現在C言語を除く主流派の言語では、そのままのgoto文はほとんど見られなくなった。替わりにbreak文continue文、もしくは例外処理のような特殊脱出(去勢されたgotoとも呼ばれるテンプレート:要出典)をサポートし、単純な構造化制御だけでは弱いと考えられる部分を補っている。また、Scheme等でサポートされている継続は「引数付きgoto」と呼ばれることもあるテンプレート:誰2。またクロージャコードブロック継続のような強力な制御機構を持つ言語ではそもそも抽象度の低いgoto文を使う必要性は低い。例えばHaskellにおいてはモナドを利用して例外や非決定性計算などの様々な制御構造を表現できるテンプレート:要出典。またSmalltalkIoにおいても制御構造はブロックを扱うメソッドとして表現しているテンプレート:要出典

一方で、例えば1999年から設計されたD言語はgoto文を含んでいる[50]。また、PHPも2009年にリリースされた5.3において制限された形ではあるがgoto文が追加された[51]テンプレート:誰範囲が少なからず存在する事実を示す例である。

その他の話題

それまでの職人芸的なプログラミングの時代から、構造化プログラミングというパラダイムの提唱によって、プログラミング技法の体系化を試みるプログラミング工学という学問が芽生えたと言っても過言では無いだろうテンプレート:要検証

なお、論文“Go To Statement Considered Harmful”は、その半ば挑戦的な題名がプログラミング以外の様々な分野に及んで評判となり、それをもじった様々な “~ Considered Harmful”といった論説やジョークが生まれたen:Considered harmful 。極めつきは、何かが有害であることだけが強調される題名の有害性を指摘した“‘Considered Harmful’ Essays Considered Harmful”であろう。

ダイクストラは What led to “Notes on Structured Programming” (『「構造化プログラミングに関する覚え書き」へと導いたもの』)で、“A case against goto statement” (『Goto 文が不利な場合』)と題した論文を投稿したが、出版を早めるために編集者により “letter to the Editor” (『編集者への手紙』)と改題され、その過程でその編集者独自の考案で新たなタイトル("The goto statement considered harmful")を付けられた。その編集者とはニクラウス・ヴィルトであった、と述べている。

同じくWhat led to "Notes on Structured Programming" においてダイクストラは、Millsによって矮小化されたgoto文廃止という概念のもと、IBMが用語としての「構造化プログラミング」を盗用したと語っている。

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

脚注

注釈

テンプレート:Reflist

出典

テンプレート:Reflist

参考文献

関連項目

関連人物

  • 金藤栄孝, 二木厚吉, “多重ループからの脱出でのgoto文の是非:Hoare理論の観点から”, 情報処理学会論文誌, Vol. 45, Issue 3, 2004, pp. 770-784.
  • 金藤栄孝, 二木厚吉, “有限状態機械に基づくプログラミングでのgoto文使用の是非 : Hoare論理の観点から”, 情報処理学会論文誌, Vol. 45, Issue 9, 2004, pp. 2124-2137.
  • H.D.Mills, R.C.Linger, a.R.Hevner, “ボックス構造化情報システム”, ソフトウェアエンジニアリング論文集80's, Tom DeMarco, Timothy Lister編著, 児玉公信 監訳, 翔泳社, 2006, pp.187-219.
  • 4.0 4.1 4.2 4.3 4.4 4.5 4.6 4.7 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.0 5.1 5.2 D.グリース, プログラミングの科学, 筧捷彦訳, 培風館, 1991.
  • 6.0 6.1 6.2 6.3 6.4 6.5 6.6 6.7 6.8 D. E. Knuth, “Structured Programming with go to Statements”, In Computing Surveys, Vol. 6, No. 4, ACM, New York, NY, USA, 1974, pp. 261-301.
  • 山崎利治, "流れ図", プログラムの設計, 共立出版, 1990, pp.110-113.
  • 8.0 8.1 8.2 8.3 E. Dijkstra. “Go To Statement Considered Harmful”, In Communications of the ACM, Vol. 11, Issue 3, ACM, New York, NY, USA, 1968, pp. 147-148.
  • C. Böhm and G Jacopini. “Flow Diagrams, Turing Machines And Languages With Only Two Formation Rules” In Communications of the ACM, Vol. 9, Issue 5, ACM, New York, NY, USA, 1966, pp. 366-371
  • Linger,R.C., Mills, H.D., Witt, B.I., Structured Programming: Theory and Practice, Addison-Wesly, 1979.
  • E.W.ダイクストラ, "GO TO 論争:第1部 go to 文有害説", 木村泉 訳, bit, Vol.7, Issue 5, 1975, pp.6-9, 共立出版.
  • 12.0 12.1 B.リーヴェンワス編, "GO TO 論争:第2部 GO TO 論争", 木村泉 訳, bit, Vol.7, Issue 5, 1975, pp.10-26, 共立出版.
  • 13.0 13.1 木村泉, "GO TO 論争:第3部 解説", bit, Vol.7, Issue 5, 1975, pp.27-39, 共立出版.
  • B. Randell and J.N. Buxton, (Eds.), Software Engineering, NATO Scientific Affairs Division, Brussels, Belgium, 1969.
  • 15.0 15.1 15.2 15.3 15.4 15.5 E.W.ダイクストラ, "プログラミング−工芸から科学へ", 情報処理, Vol.18, No.12, 1977, pp.1248-1256, 情報処理学会.
  • 16.0 16.1 和田英一, "ダイクストラかく語りき", bit, Vol.9, Issue 1, 1977, pp.4-6, 共立出版.
  • 17.0 17.1 山崎利治, "構造的プログラミング", プログラムの設計, 共立出版, 1990, pp.113-142.
  • 18.0 18.1 玉井哲雄, "ソフトウェア工学の40年", 情報処理, Vol.49, No.7, 2008, pp.777-784.
  • Edward Nash Yourdon ed., "Introduction (Chief Programmer Team Management of Production Programming)", Classics in Software Engineering, YOURDON inc., 1979, pp.63-64.
  • 木村泉, 米澤明憲, 算法表現論, 岩波書店, 1982.
  • 21.0 21.1 木村泉, "プログラミング方法論の問題点:超職業的プログラミングについて", 情報処理, Vol.16, No.10, 1975, pp.841-847, 情報処理学会.
  • D.シャシャ, C.ラゼール, "エズガー・W・ダイクストラ", コンピュータの時代を開いた天才たち, 鈴木良尚 訳, 竹内郁雄 監訳, 日経BP社, 1998, pp.61-74.
  • 玉井哲雄, "ソフトウェア産業とソフトウェア研究の沈滞状況について", SEAMAIL, Vol.11, No.3, 1997, pp.2-5.
  • 玉井哲雄, "9th ICSEに参加して", SEAMAIL, Vol.2, No.7, 1987, pp.22-25.
  • 25.0 25.1 中山晴康, "ダイクストラ教授との3日間", bit, Vol.9, Issue 1, 1977, pp.7-9, 共立出版.
  • Edward Nash Yourdon, 構造化手法によるソフトウェア開発, 黒田純一郎, 渡部研一 訳, 日経BP社, 1987.
  • 筧 捷彦, "ストラクチャード・プログラミング用言語", 情報処理, Vol.16, No.10, 1975, pp.856-863, 情報処理学会.
  • 28.0 28.1 28.2 N.ヴィルト, 系統的プログラミング/入門, 野下浩平, 筧捷彦, 武市正人 訳, 近代科学社, 1978.
  • 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.0 30.1 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
  • E.W.ダイクストラ, "マイクロコンピュータのインパクト", 川合慧 訳, bit, Vol.7, Issue 6, 1975, pp.4-6, 共立出版.
  • 33.0 33.1 金山裕 編, "構造的プログラミング −批判と支持−", bit, Vol.7, Issue 7, 1975, pp.6-13, 共立出版.
  • 34.0 34.1 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.
  • 40.0 40.1 ロバート 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.
  • 43.0 43.1 43.2 E.W.ダイクストラ, プログラミング原論 ― いかにしてプログラムをつくるか, 浦昭治訳, サイエンス社, 1983.
  • 44.0 44.1 44.2 二木厚吉 監修, ソフトウェアクリーンルーム手法, 日科技連, 1997.
  • 45.0 45.1 淵一博, 新世代プログラミング, 共立出版, 1986.
  • 和田英一, "「構造的...」と「いかにして...」", 情報処理, Vol.16, No.3, 1975, pp.169, 情報処理学会.
  • マイケル・ジャクソン, 吉村鉄太郎, 山崎利治, 大野徇郎, "ソフトウェア設計哲学", bit, Vol.11, Issue 2, 1979, pp.4-12, 共立出版.
  • Frank Rubin, "GOTO Considered Harmful" Considered Harmful, Communications of the ACM, Vol.30, Issue 3, 1987, pp.195-196.
  • E.W.ダイクストラ, W.H.J.フェイエン, プログラミングの方法, 玉井浩 訳, サイエンス社, 1991.
  • Language Reference Goto Statement
  • PHP マニュアル goto
  • 木村泉, "ダイクストラ教授とふた付き命令", bit, Vol.8, Issue 9, 1976, pp.29-34, 共立出版.

  • 引用エラー: 「注釈」という名前のグループの <ref> タグがありますが、対応する <references group="注釈"/> タグが見つからない、または閉じる </ref> タグがありません