構造化プログラミング
構造化プログラミング（こうぞうかプログラミング、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においてはモナドを利用して例外や非決定性計算などの様々な制御構造を表現できるテンプレート:要出典。またSmalltalkやIoにおいても制御構造はブロックを扱うメソッドとして表現しているテンプレート:要出典。
一方で、例えば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]。
脚注
注釈
出典
参考文献
- テンプレート:Cite book
- テンプレート:Cite book
- テンプレート:Citation
- テンプレート:Citation
- テンプレート:Citation
- テンプレート:Citation
- テンプレート:Citation
- テンプレート:Citation
- テンプレート:Citation
- テンプレート:Citation
- テンプレート:Citation
- テンプレート:Citation
- テンプレート:Citation
関連項目
- Simula
- 抽象データ型
- 抽象化 (計算機科学)
- ジャクソン流構造化プログラミング
- プログラム検証
関連人物
引用エラー: 「注釈」という名前のグループの <ref> タグがありますが、対応する <references group="注釈"/> タグが見つからない、または閉じる </ref> タグがありません
