構造化プログラミング
構造化プログラミング(こうぞうかプログラミング)とは、命令的プログラムの文脈において、階層的に抽象化されたプログラムの組み合わせとしてプログラムを記述する手法である。1967年[要出典]、エドガー・ダイクストラらによって提唱された。
全体的な機能から詳細機能へと順に開発するトップダウン式と小さな機能をまとめて大きな機能単位をつくるボトムアップ式の開発方法がある[注釈 1]。
サブルーチン分割や構造化制御をサポートするプログラミング言語を構造化言語と呼ぶ場合があるが、現在の言語水準では特に明示されない場合でも、ほとんどの言語は構造化されているといえる。典型的な構造化言語はCやPascalといったいわゆるALGOL系の言語であろう。一方構造化されていないプログラミング言語としてはFORTRAN 77以前のFORTRAN、COBOL-76以前のCOBOL、N88-BASICなどの古いBASICが挙げられる。
ドナルド・クヌースがアントニー・ホーアに構造化プログラミングの簡潔な定義を求めたところ、ホーアは次のように返答した[2]。“the systematic use of abstraction to control a mass of detail, and also a means of documentation which aids program design.”
オブジェクト指向でも、基本的な処理の流れは構造化から変わりない。
歴史
コンピュータが実用化され、その有用性が認められるようになるにつれ、その上で動作するプログラムは次第に大規模なものとなっていった。大規模なプログラムを矛盾なく正当に動作するように記述することは一般にとても困難である。
1960年代ではプログラムはフローチャートによる設計が広く採用されており、goto文も広く使われていた[2]。その一方でgoto文の多用はプログラムの質を下げるという性質や、多くのプログラムはgotoを使わずに記述できるという性質が経験則として知られていた。例えば1959年にはハインツ・ツェマネクはgoto文に関する疑問を抱いており、後のダイクストラの考えに影響を与えた[3]。また1960年からD. V. Schorreはgoto文を使わず、フローチャートではなくインデントで構造を表したアウトラインテキストでプログラムを記述していた[2]。
そして1966年コラド・ベームとジュゼッペ・ヤコピーニによって、任意のフローチャートは基本フローチャートの組み合わせによる等価なフローチャートに変換できるという定理が示された[4]。この定理は後に構造化定理と呼ばれるようになった[誰によって?]。ヤコピーニは3種の基本構造(順次・反復・分岐)に分解する手法と2種(順次・反復)に分解する手法を示したが、今日単に構造化定理と言った場合前者を指す。
そのような背景の元、1968年にダイクストラは“Go To Statement Considered Harmful”[3]という記事を発表し、大きな反響を呼んだ[5]。この記事が構造化プログラミングの提唱であるとする場合も多い[誰によって?]。
「構造化プログラミング(Structured Programming)」という語は1969年に開催されたカンファレンス“Software Engineering Techniques”においてダイクストラが提唱した[1][注釈 2]。ダイクストラはこの論文においてはgoto文についてはほとんど触れず、どのようなプログラム構造であればプログラムが大きくなったとしても苦労を強いることなくプログラムの正しさを証明できるか、そのような良く構造化されたプログラムを課題が与えられた際にどうやって作成できるのかという観点に立った。その上で大きな文(例えば1つのif else文)を1つの抽象文としてみなし、さらにそれらの組合せも抽象文として階層的に扱う手法を提案した。また、データの抽象化の重要性も主張した上で、抽象データとそれを扱う抽象文を他の部分と分離し、抽象データの実装が変わったとしても変更はそれを扱う抽象文の変更のみになるようにするべきと主張した。
構造化プログラミングの構成要素
ダイクストラは“Go To Statement Considered Harmful”[3]および“Structured Programming”[1]において、好ましい構造として手続き呼び出しの他に、順次・反復・分岐の3つを挙げた。
- 順次
- 順接、順構造とも言われる。プログラムに記された順に、逐次処理を行なっていく。プログラムの記述とコンピュータの動作経過が一致するプログラム構造である。
- 反復
- 一定の条件が満たされている間処理を繰り返す。
- 分岐
- ある条件が成立するなら処理Aを、そうでなければ処理Bを行なう。
また、“Structured Programming”[1]や“Structured Programming with go to Statements”[2]においては抽象データ構造の重要性も主張されている。加えて1972年、オルヨハン・ダール、ダイクストラ、ホーアによる書籍“Structured Programming”[6]においてはSimulaによる初期のオブジェクト指向の考え方も紹介されている。これらの考え方は後の本格的なオブジェクト指向へと発展する。例えばC++の開発者であるビャーネ・ストロヴストルップはオブジェクト指向について解説した記事“What Is Object-Oriented Programming?”[7]において抽象データ構造の発展としてオブジェクト指向を解説し、そのための手段としてSimulaの機能を紹介している。
なおダイクストラの論文などから「goto文の排除が構造化プログラミングである」と誤解されるケースも多いが、goto文をなくしただけで処理の見通しが良くなるわけではない。クヌースは良い構造が重要であり、良い構造はFORTARN, COBOL, アセンブリ言語でも記述できるとした[2]。そしてヤコピーニの定理を使ってgoto文を消去したプログラムについては、反復がプログラム全体の振る舞いを含んでしまうため、抽象化レベルという点では無意味であるとした[2]。また、ダイクストラも“Go To Statement Considered Harmful”においては最後の段落で、goto文の(論理的な)余分さを証明したようだと軽く触れたのみであり、作られるフローチャートは元のものより見透しが良くなるとは思えないためジャンプを含まないフローチャートの機械的な作成は推奨しないとした。
実際、ヤコピーニの論文はフローチャートやそれによって表現されるプログラム・関数・チューリングマシンなどの理論的側面に注目している。これは任意の論理回路がNAND素子の組み合わせによって表現できるとか、λ式がSおよびKという名の2つのコンビネータによって表現できるとかいった研究に近い。回路設計者が直接NANDを組み合わせて電子回路を設計しないのと同じように、ヤコピーニの研究は良いプログラムの作成を(少なくとも直接的には)意図していない。
goto論争
ダイクストラの主張
構造化プログラミングを提唱するダイクストラは、理論の帰結から、goto文を使うべきでないとする。
ダイクストラによる“Go To Statement Considered Harmful”[3]の趣旨は次の通りである。
人間が時間によって変化するプロセスを把握する能力は、プログラムの静的な関係を把握する能力に比べて劣っているため、静的なプログラムテキストの構造と時間によって変化するプロセスの構造をなるべく近づけるのが重要である。
そのためにはプロセスの進捗を表す簡潔な指標が必要がある。指標とは例えば実行中の行番号・その時点でのスタックトレース・行番号とループを回った回数のペアなどである。
例えば、1人が部屋に入るごとにカウンタを増やしていくプログラムにおいて、カウンタが室内の人数-1である瞬間はどこにあるのかという問いに答える際に、簡潔な指標があればすぐ答えられるが、簡潔な指標がなければ正確な答えは難しくなる。
goto文を無条件に許してしまうと簡潔な指標は得られなくなってしまうため、高水準プログラミング言語においてはgoto文は廃止するべきである。
以上が“Go To Statement Considered Harmful”の趣旨である。
その一方で、ダイクストラは“Structured Programming”[1]においてはgoto文には触れていないとクヌースは指摘している[2]。実際に“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つの基本構造による代替を行うと、理論上は同値であっても実際にはプログラムの実行速度や記憶容量の点で性能が劣化する場合がある[2]。また、特殊な場合にはgotoを使った方がプログラムを見通しやすくなると考える人もいる。例えばドナルド・クヌースも、著書「文芸的プログラミング」の中でそのような例をいくつかあげている。
こうした理由から、goto文を撲滅するのではなく上手に使い分けるべきだと考える人もいる[誰?]。
goto文論争が不毛なのは、「構造化プログラミングの観点からgoto文を使うのは望ましくない」という結論は真だが、「goto文を使わなければ構造化プログラミングになる」というわけではない点である。構造化プログラミングの本質は、状態遷移の適切な表現方法とタイミングを見極めることであり[要出典]、これはプログラムの良し悪しを決める永遠の命題であるといっていい[要出典]。
現在C言語を除く主流派の言語では、そのままのgoto文はほとんど見られなくなった。替わりにbreak文、continue文、もしくは例外処理のような特殊脱出(去勢されたgotoとも呼ばれる[要出典])をサポートし、単純な構造化制御だけでは弱いと考えられる部分を補っている。また、Scheme等でサポートされている継続は「引数付きgoto」と呼ばれることもある[誰によって?]。またクロージャやコードブロック、継続のような強力な制御機構を持つ言語ではそもそも抽象度の低いgoto文を使う必要性は低い。例えばHaskellにおいてはモナドを利用して例外や非決定性計算などの様々な制御構造を表現できる[要出典]。またSmalltalkやIoにおいても制御構造はブロックを扱うメソッドとして表現している[要出典]。
一方で、例えば1999年から設計されたD言語はgoto文を含んでいる[8]。また、PHPも2009年にリリースされた5.3において制限された形ではあるがgoto文が追加された[9]。これはgoto文を支持する者[誰?]が少なからず存在する事実を示す例である。
その他の話題
それまでの職人芸的なプログラミングの時代から、構造化プログラミングというパラダイムの提唱によって、プログラミング技法の体系化を試みるプログラミング工学という学問が芽生えたと言っても過言では無いだろう[要検証]。
なお、論文“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")を付けられた。その編集者とはニクラウス・ヴィルトであった、と述べている。
注釈
参照元
- ^ 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
- ^ a b c d e f g h i 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
- ^ a b c d 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
- ^ 金藤栄孝, 二木厚吉, “多重ループからの脱出でのgoto文の是非：Hoare理論の観点から”, 情報処理学会論文誌, Vol. 45, Issue 3, 2004, pp. 770-784.
- ^ 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
- ^ Language Reference Goto Statement
- ^ PHP マニュアル goto