「構造化プログラミング」の版間の差分
削除された内容 追加された内容
編集の要約なし |
m 外部リンクの修正 http:// -> https:// (www.cs.cmu.edu) (Botによる編集) |
||
| (10人の利用者による、間の14版が非表示) | |||
| 1行目: | 1行目: | ||
{{プログラミング・パラダイム}} |
{{プログラミング・パラダイム}} |
||
'''構造化プログラミング''' |
{{読み仮名|'''構造化プログラミング'''|こうぞうかプログラミング|{{lang-en-short|structured programming}}}}は、[[コンピュータプログラム]]の処理手順の明瞭化、平易化、判読性向上を目的にした[[プログラミング]]手法である。一般的には順接、分岐、反復の三種の'''制御構造'''（control structures）によって処理の流れを記述することと認識されている<ref>{{Cite web|和書|title=構造化プログラミングとは - IT用語辞典|url=http://e-words.jp/w/%E6%A7%8B%E9%80%A0%E5%8C%96%E3%83%97%E3%83%AD%E3%82%B0%E3%83%A9%E3%83%9F%E3%83%B3%E3%82%B0.html|website=IT用語辞典 e-Words|accessdate=2020-06-01|language=ja}}</ref><ref>{{Cite web|和書|title=構造化プログラミング - 意味・説明・解説 : ASCII.jpデジタル用語辞典|url=https://yougo.ascii.jp/caltar/%E6%A7%8B%E9%80%A0%E5%8C%96%E3%83%97%E3%83%AD%E3%82%B0%E3%83%A9%E3%83%9F%E3%83%B3%E3%82%B0|website=yougo.ascii.jp|accessdate=2020-06-01}}</ref>。[[制御構造]]は'''制御構文'''、構造化文（structured statement）、制御フロー文（control flow statement）とも呼ばれる。また、プログラムを任意に分割した部分プログラム（[[サブルーチン]]と[[コードブロック]]）の階層的な組み合わせによるプログラムの構造化も指している。 |
||
このプログラミング手法の普及に貢献したのは、計算機科学者[[エドガー・ダイクストラ]]による |
このプログラミング手法の普及に貢献したのは、1968年の計算機科学者[[エドガー・ダイクストラ]]による[[Association for Computing Machinery|ACM]]機関紙への投書「Go To Statement Considered Harmful」と言われている。しかし同じくダイクストラが、1969年度[[NATO]]ソフトウェア工学会議で発表した論文「Structured Programming」との混同を招いてこちら側の名称で知られるようになった。現在に到るまでの国内外の多くの書籍で、構造化プログラミングは制御構文に関する説明に結び付けられている。なお、1969年の論文内容は[[正当性 (計算機科学)|プログラム正当性]][[プログラム検証|検証]]のための設計技法を扱っており、[[トップダウン設計]]、段階的な抽象化、階層的なモジュール化、抽象データ構造と抽象ステートメントを連携させる共同詳細化といった考え方が提唱されていた<ref name="structured_programming">[http://homepages.cs.ncl.ac.uk/brian.randell/NATO/nato1969.PDF 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.]</ref>。 |
||
== 制御構文 == |
== 制御構文 == |
||
{{main|ミルズの構造化プログラミング}} |
{{main|ミルズの構造化プログラミング}} |
||
[[制御構造|制御構文]] |
[[制御構造|制御構文]]（control structures）とは、[[goto文]]によるフロー分岐やループ表現を、[[if文]]の選択構文や[[while文]]の反復構文に置き換えるためのプログラム記法を意味している。ラベル先にジャンプするというgoto文の機能を、if文やwhile文は「特定のコード群だけを実行する」という概念に置き換えている。goto文を用いた制御フローは、(1)データの照合/比較の結果にしたがって次の実行コード群を選択するパターンと、(2)データの照合/比較の結果が任意条件を満たしているならば実行コード群を反復するパターンの、二通りに集約されることが経験則で知られていたので、これを専用の記号で形式化したのが制御構文であった。 |
||
コード群とは命令コード |
コード群とは命令コード（instruction code）のまとまりであり、[[構造化定理]]では部分プログラム（subprogram）と定義されている。部分プログラムは[[ステートメント]]（statement）[[コードブロック]]（code block）[[サブルーチン]]（subroutine）の総称である。ステートメントは命令コードの一行を意味する。コードブロックは一行以上のステートメントをまとめたものである。サブルーチンは一行以上のステートメントまたは一個以上のコードブロックを内包している。部分プログラムは直列状または入れ子状に配置される。その実行順序を決定するものが制御構文であり、以下の三つがある。 |
||
#'''順次''' |
#'''順次'''（sequence）部分プログラムを順々に実行する。 |
||
#'''選択''' |
#'''選択'''（selection）条件式が導出した状態に従い、次に実行する部分プログラムを選択して分岐する。 |
||
#'''反復''' |
#'''反復'''（repetition）条件式が導出した特定の状態の間、部分プログラムを繰り返し実行する。 |
||
| ⚫ | |||
| ⚫ | 制御構造の導入は1960年公開の「[[ALGOL|ALGOL60]]」まで遡れるが、当時広く使われていた[[FORTRAN]]や[[COBOL]]での正式導入は1977年以降だったので、多くの開発現場では馴染みのないものであった。1966年に[[コラド・ベーム]]らが「順次・選択・反復」のフロー万能性を数学的に証明したが、それはあくまで論理的研究だった。それを参考にしたとされる[[エドガー・ダイクストラ|ダイクストラ]]の1968年の投書「goto文は有害」はいわゆるgoto文論争を引き起こしたが、同時に制御構造への関心を大きく高めた。1970年代、goto文が多用される開発現場での制御構造の普及を重視していた[[IBM]]社の[[ハーラン・ミルズ]]は、1969年にダイクストラが発表していた論文題名から知名度を得ていた「構造化プログラミング」を自社の技術セミナーマーケティングに活用するために、上述のベームらの数学的証明を「[[構造化定理]]」という独自のタイトルで復刻させて、彼らが勧める[[フローチャート]]制御構造の裏付け理論にした。こうして構造化プログラミングは、[[IBM|IBM社]]が提唱する[[構造化定理]]を論拠にした制御構造を用いるプログラミング手法として世間に定着することになった。 |
||
制御構造を導入したプログラミング言語を指しての「構造化言語」というワードが浮上したのは1970年代からであり、これは当時のgoto文中心だった[[FORTRAN]]や[[COBOL]]や[[BASIC]]を意識してそれと線引きするための用語として存在していた。 |
|||
| ⚫ | |||
| ⚫ | |||
== 構造化設計 == |
== 構造化設計 == |
||
{{main|段階的詳細化法}} |
{{main|段階的詳細化法}} |
||
[[ファイル:6 Decomposition Structure.svg|サムネイル|構造化設計の一例]] |
[[ファイル:6 Decomposition Structure.svg|サムネイル|構造化設計の一例]] |
||
上述の[[制御構文]]をコーディング視点の下流工程テクニックとすると、構造化設計 |
上述の[[制御構文]]をコーディング視点の下流工程テクニックとすると、構造化設計（structured design）はプログラムデザイン視点の上流工程テクニックであり、こちらも構造化プログラミングと呼ばれるものである。構造化設計では、[[サブルーチン]]（subroutine）をまとめたサブルーチン複合体と、データ要素をまとめた[[データ構造]]（data structure）が主要な役割を果たしている。[[段階的詳細化法|段階的詳細化]]に則ったサブルーチン複合体の階層的な組み合わせと、それに必要なデータ構造を連携させてプログラム全体を構築するというテクニックが構造化設計である。サブルーチン複合体は[[モジュール|プログラムモジュール]]（program module）とも読み替えられ、モジュール[[凝集度]]と[[結合度]]もここから生まれている。 |
||
1974年頃から当初は[[IBM|IBM社]]が主導する形で、いずれも構造化（structured）が接頭辞につく数々のテクニックが発表されるようになり、1975年発表「[[ジャクソンの構造化プログラミング]] -Jackson structured programming(JSP)-」、1975年発表「構造化設計 -structured design(SD)-」、1978年発表「構造化分析 -structured analysis(SA)-」、1981年発表「[[構造化分析設計技法]] -structured analysis and design technique(SADT)-」、1980年代発表「[[SSADM|構造化体系分析設計手法]] -structured systems analysis and design method(SSADM)-」、1989年発表「モダン構造化分析 -modern structured analysis-」などが広く普及している。著名な専門家としては、グレンフォード・マイヤーズ、ラリー・コンスタンティン、マイケル・ジャクソン、[[エドワード・ヨードン]]、[[トム・デマルコ]]などがいる。これらは「構造化開発」と総称されるようになり、1980年代までのソフトウェア開発の主流になった。 |
|||
この構造化設計と[[エドガー・ダイクストラ|ダイクストラ]]の構造化プログラミングの違いは、前者が |
この構造化設計と、[[エドガー・ダイクストラ|ダイクストラ]]の構造化プログラミングの違いは、前者がサブルーチン複合体とデータ構造の連携を中心にしたテクニックであるのに対して、後者は専属サブルーチンを通して扱われる抽象データ構造を中心にしたテクニックであるという点である。後者では、段階的に抽象化した各モジュールの階層的な連結と、抽象データ構造と抽象ステートメントを連携させる共同詳細化といった考え方が提示されており、この詳細については後節で述べられる。ダイクストラが提唱した抽象（abstraction）指向の構造化は、その思想の[[アバンギャルド|前衛性]]から1970年代を通して理解を得られることはなく、発案者本来の構造化プログラミングは上流工程視点からも普及することはなかった。 |
||
== 歴史 == |
== 歴史 == |
||
'''第一幕''' |
'''第一幕''' |
||
構造化プログラミングの誕生は、1960年代から浮上した[[ソフトウェア危機]]問題と密接に結びついている。ソフトウェア危機とはコンピュータ性能の進化に伴うソフトウェア要求度の高まりが、プログラムサイズの際限無い肥大化と複雑化を招き、近いうちに現実的な期間内でのプログラム開発が不可能になるだろうとする悲観的予測である{{#tag:ref|[[ソフトウェア危機]]の始まりと構造化プログラミングの歴史について<ref name="the_science_of_programming"/>の第23章に詳しい。|group="注釈"}}。実際に1960年代のソフトウェア開発現場では仕様不一致、納期遅れ、予算超過といった事態が頻発していた<ref name="the_science_of_programming">{{cite book |first=D.|last=グリース |authorlink=:en:David Gries|title=プログラミングの科学 |translator=筧捷彦 |publisher=培風館 |year=1991 |isbn=4563007943}}</ref>。当時のプログラムは[[goto文]]を多用するタコ足[[フローチャート]]によるものが大半だったので<ref name="program_design_chap6sec1">山崎利治, "流れ図", ''プログラムの設計'', 共立出版, 1990, pp.110-113. ISBN 4320023781</ref>、すぐに[[スパゲティコード]]化することが多く、複雑怪奇なジャングルフロー図と化しているものも珍しくなかった<ref name="structured_programming_with_go_to_statements">{{Cite journal|last=Knuth|first=D. E.|year=1974|title=Structured Programming with go to Statements Computing Surveys|journal=ACM, New York, NY, USA|volume=6|number=4|pages=261-301|id={{citeseerx|10.1.1.103.6084}}|authorlink=ドナルド・クヌース}}</ref>。1959年に計算機科学者[[ハインツ・ツェマネク]]は、goto文の多用に警鐘を鳴らす論文を発表している。1960年に公開されたプログラミング言語「[[ALGOL|ALGOL60]]」は、BEGINとENDで区切られた[[コードブロック]]を制御するIF選択文とFOR反復文を初めて提供していた。計算機科学者[[ニクラウス・ヴィルト]]はこれらを構造化文（structured statement）と呼んだ<ref name="systematic_programming">N.ヴィルト, ''系統的プログラミング/入門'', 野下浩平, 筧捷彦, 武市正人 訳, 近代科学社, 1978. </ref>。1966年に計算機科学者[[コラド・ベーム]]とジュゼッペ・ヤコピーニは、あらゆるフローチャートは順次・選択・反復の組み合わせで表現できることの数学的証明をし、これは[[構造化定理|ベームとヤコピーニの証明]]と呼ばれた<ref name="flow_diagrams_turing_machines_and_languages_with_only_two_formation_rules">{{Cite journal|last=Böhm|first=C.|last2=Jacopini|first2=G|year=1966|title=Flow Diagrams, Turing Machines And Languages With Only Two Formation Rules|journal=Communications of the ACM|volume=9|issue=5|pages=366-371|id={{citeseerx|10.1.1.119.9119}}| |
構造化プログラミングの誕生は、1960年代から浮上した[[ソフトウェア危機]]問題と密接に結びついている。ソフトウェア危機とはコンピュータ性能の進化に伴うソフトウェア要求度の高まりが、プログラムサイズの際限無い肥大化と複雑化を招き、近いうちに現実的な期間内でのプログラム開発が不可能になるだろうとする悲観的予測である{{#tag:ref|[[ソフトウェア危機]]の始まりと構造化プログラミングの歴史について<ref name="the_science_of_programming"/>の第23章に詳しい。|group="注釈"}}。実際に1960年代のソフトウェア開発現場では仕様不一致、納期遅れ、予算超過といった事態が頻発していた<ref name="the_science_of_programming">{{cite book |first=D.|last=グリース |authorlink=:en:David Gries|title=プログラミングの科学 |translator=筧捷彦 |publisher=培風館 |year=1991 |isbn=4563007943}}</ref>。当時のプログラムは[[goto文]]を多用するタコ足[[フローチャート]]によるものが大半だったので<ref name="program_design_chap6sec1">山崎利治, "流れ図", ''プログラムの設計'', 共立出版, 1990, pp.110-113. ISBN 4320023781</ref>、すぐに[[スパゲティコード]]化することが多く、複雑怪奇なジャングルフロー図と化しているものも珍しくなかった<ref name="structured_programming_with_go_to_statements">{{Cite journal|last=Knuth|first=D. E.|year=1974|title=Structured Programming with go to Statements Computing Surveys|journal=ACM, New York, NY, USA|volume=6|number=4|pages=261-301|id={{citeseerx|10.1.1.103.6084}}|authorlink=ドナルド・クヌース}}</ref>。1959年に計算機科学者[[ハインツ・ツェマネク]]は、goto文の多用に警鐘を鳴らす論文を発表している。1960年に公開されたプログラミング言語「[[ALGOL|ALGOL60]]」は、BEGINとENDで区切られた[[コードブロック]]を制御するIF選択文とFOR反復文を初めて提供していた。計算機科学者[[ニクラウス・ヴィルト]]はこれらを構造化文（structured statement）と呼んだ<ref name="systematic_programming">N.ヴィルト, ''系統的プログラミング/入門'', 野下浩平, 筧捷彦, 武市正人 訳, 近代科学社, 1978. </ref>。1966年に計算機科学者[[コラド・ベーム]]とジュゼッペ・ヤコピーニは、あらゆるフローチャートは順次・選択・反復の組み合わせで表現できることの数学的証明をし、これは[[構造化定理|ベームとヤコピーニの証明]]と呼ばれた<ref name="flow_diagrams_turing_machines_and_languages_with_only_two_formation_rules">{{Cite journal |last=Böhm |first=C. |last2=Jacopini |first2=G |year=1966 |title=Flow Diagrams, Turing Machines And Languages With Only Two Formation Rules |journal=Communications of the ACM |volume=9 |issue=5 |pages=366-371 |id={{citeseerx |10.1.1.119.9119}} |publisher=ACM, New York, NY, USA }}</ref>。計算機科学者[[ドナルド・クヌース]]は、これらの潮流を構造化文の第一幕と定義した<ref name="structured_programming_with_go_to_statements" />。 |
||
'''第二幕''' |
'''第二幕''' |
||
1968年、計算機科学者[[エドガー・ダイクストラ]]の[[Association for Computing Machinery|ACM]]機関紙への投書「Go To Statement Considered Harmful<ref name="go_to_statement_considered_harmful">{{Cite journal |
1968年、計算機科学者[[エドガー・ダイクストラ]]の[[Association for Computing Machinery|ACM]]機関紙への投書「Go To Statement Considered Harmful -goto文は有害-<ref name="go_to_statement_considered_harmful">{{Cite journal|author=E. Dijkstra|year=1968|title=Go To Statement Considered Harmful|journal=Communications of the ACM|volume=11|issue=3|pages=147-148|id={{citeseerx|10.1.1.132.875}}|authorlink=エドガー・ダイクストラ}}</ref>」は、その物議を醸す題名でコンピュータプログラミング界隈にいわゆるgoto文論争を巻き起こした<ref name="bit1975_go_to_statement_considered_harmful">{{cite|author=E.W.ダイクストラ|authorlink=エドガー・ダイクストラ|title=GO TO 論争：第1部 go to 文有害説|translator=木村泉|journak=bit|volume=7|issue=5|year=1975|pages=6-9|publisher=共立出版}}</ref><ref name="bit1975_goto_controversy">{{cite |editor=B.リーヴェンワス編 |title=GO TO 論争：第2部 GO TO 論争 |translator=木村泉 訳 |journal=bit |volume=7 |issue=5 |year=1975 |pages=10-26 |publisher=共立出版 }}</ref>。これは構造化文の認知度を高めることに貢献している<ref name="bit1975_explanation">木村泉, "GO TO 論争：第3部 解説", ''bit'', Vol.7, Issue 5, 1975, pp.27-39, 共立出版.</ref>。これを構造化文の第二幕と定義したクヌースは「第二幕はそのムーブメントの大きさによって、多くの人にとっての第一幕になった」と評した<ref>有澤誠訳『文芸的プログラミング』p.45</ref>。1968年度開催の[[北大西洋条約機構|NATO]]ソフトウェア工学会議で[[ソフトウェア危機]]は正式な用語になり<ref name="software_engineering_conferences1968">[http://homepages.cs.ncl.ac.uk/brian.randell/NATO/nato1968.PDF B. Randell and J.N. Buxton, (Eds.), ''Software Engineering'', NATO Scientific Affairs Division, Brussels, Belgium, 1969.]</ref>、産業界と計算機科学共通の懸案事項になった<ref name="from_craft_to_scientific_discipline" />。翌69年度開催の同会議においてダイクストラは「Structured Programming -構造化プログラミング-<ref name="structured_programming" />」と題した論文を寄稿した。これが「構造化プログラミング」の正式な初出である。その論旨はソフトウェア危機解決策としての[[正当性 (計算機科学)|ソフトウェア正当性]][[プログラム検証|検証技術]]の確立であり、プログラムを適切に分割し抽象化して良く構造化（well-structured）しておけば、プログラムサイズ拡大に関係なくその[[正当性 (計算機科学)|正当性]]を[[プログラム検証|証明]]できるとしていた。その具体的手法としては[[トップダウン設計とボトムアップ設計|トップダウン設計]]、段階的な[[抽象化 (計算機科学)|抽象化]]、階層的な[[モジュール|モジュール化]]、抽象データ構造と抽象ステートメントを連携させる共同詳細化などが挙げられていた。goto文抑制など構造化文に関する事柄は数行に留まっていたが{{#tag:ref|"statements transferring control to labelled points" という言葉で一応 goto 文に触れている<ref name="structured_programming" />|group="注釈"}}、goto文論争に熱心なプログラマの間ではこの論文を昨年の投書の延長と見る向きも少なからず存在していた。後年のダイクストラは構造化プログラミングという言葉を作った際に二つの失敗をしたと述べている。商標登録しなかった事と、厳密な定義化を避けた事である<ref name="also_speech_dijkstra">和田英一, "ダイクストラかく語りき", ''bit'', Vol.9, Issue 1, 1977, pp.4-6, 共立出版. </ref><ref name="from_craft_to_scientific_discipline">{{cite |naid=110002753409 |author=E.W.ダイクストラ |title=プログラミング−工芸から科学へ |journal=情報処理 |volume=18 |number=12 |year=1977 |page=1248-1256 |publisher=情報処理学会 }}</ref>。 |
||
'''第三幕''' |
'''第三幕''' |
||
1960年代からの構造化文第一幕の潮流は、産業プログラム界隈にも影響を及ぼしており、こちらでは制御構造 |
1960年代からの構造化文第一幕の潮流は、産業プログラム界隈にも影響を及ぼしており、こちらでは制御構造（control structures）などの名義で[[フローチャート]]に導入されていた。産業コンピュータ市場の最大手である[[IBM|IBM社]]の上席研究員[[ハーラン・ミルズ]]は制御構造を重視し、[[ニューヨーク・タイムズ社]]のニュースアーカイブシステム構築プロジェクトで大きな成功を収めた。順次・選択・反復の制御構造は、IBM社のプログラミング規範をまとめたImproved Programming Technologies通称「IPT」に採用され、後に同社の技術セミナーなどを通して広く流布されるようになった<ref name="program_design_chap6sec2">山崎利治, "構造的プログラミング", ''プログラムの設計'', 共立出版, 1990, pp.113-142. </ref><ref name="tamai_40years_se">{{cite|url=http://www.graco.c.u-tokyo.ac.jp/~tamai/pub/40yearsSE.pdf|format=PDF|author=玉井哲雄|title=ソフトウェア工学の40年|journal=情報処理|volume=49|number=7|year=2008|pages=777-784|naid=110006830060}}</ref>。1970～71年頃から計算機科学者デビッド・ハレルは、前述のベームとヤコピーニの数学的証明に「[[構造化定理|Structure theorem]] -構造化定理-''」''という全く新しい題名を付けて主に産業ソフトウェア開発界隈で紹介した<ref name="sp_theory_and_practice">Linger,R.C., Mills, H.D., Witt, B.I., ''Structured Programming: Theory and Practice'', Addison-Wesly, 1979. </ref><ref name=":0" group="注釈">[http://www.wisdom.weizmann.ac.il/~dharel/SCANNED.PAPERS/OnFolkTheorems.pdf Harel,David (1980)."On Folk Theorems"(PDF)]のP381の左列の中央にハーラン・ミルズ（Harlan Mills）が未公表の講義資料の中で "The Structure Theorem" と名付けたことが書かれている。この資料の出典[67]が1972年のため構造化定理が発明されたのは1970年代初頭と推測される。</ref>。ハレルはこの命名が実はハーラン・ミルズの提案であったことを後に明かしている<ref name=":0">{{Cite journal|last=Harel|author=|first=David|year=|date=1980-07-01|title=On folk theorems|url=http://portal.acm.org/citation.cfm?doid=358886.358892|journal=Communications of the ACM|volume=23|issue=7|page=|pages=379–389}}</ref>。構造化定理はIPTの合理性を裏付ける根拠として盛んに引用されたので、構造化（Structured）プログラミングと言えばIBM社の発明品だと信じるプログラマたちも続出した<ref name="classics_in_software_engineering">Edward Nash Yourdon ed., "Introduction (Chief Programmer Team Management of Production Programming)", ''Classics in Software Engineering'', YOURDON inc., 1979, pp.63-64. </ref>。IBM社が1974年頃から発表するようになった所属研究員たちによるプログラム開発方法論の数々にも構造化（Structured）の接頭辞が付けられていたが、それらは抽象化を重視するダイクストラの構造化とは異なり、サブルーチン複合体とデータ構造を適切に連携させるための[[構造化分析設計技法|構造化]]であった。その違いを指摘して本来のダイクストラ方式を改めて紹介する動きもあったが、抽象化指向のダイクストラ理論は産業界ではむしろ不人気でさえあった<ref name="problems_of_programming_methodology">{{cite journal|author=木村泉|year=1975|title=プログラミング方法論の問題点：超職業的プログラミングについて|journal=情報処理|volume=16|number=10|pages=841-847|publisher=情報処理学会|naid=110002720277}}</ref><ref name="algorithm_representation_theory">木村泉, 米澤明憲, ''算法表現論'', 岩波書店, 1982. </ref><ref name="out_of_thier_minds">D.シャシャ, C.ラゼール, "エズガー・W・ダイクストラ", ''コンピュータの時代を開いた天才たち'', 鈴木良尚 訳, 竹内郁雄 監訳, 日経BP社, 1998, pp.61-74. ISBN 4822280462</ref>。クヌースの言葉を借りれば、構造化文の第三幕は[[IBM|IBM社]]と[[ハーラン・ミルズ]]がプロモートした制御構造の舞台になり、構造化プログラミングに対する世間一般の認識はこちらの方で定着するようになった。 |
||
'''終幕''' |
'''終幕''' |
||
後年、ダイクストラは自身が作った構造化プログラミングという言葉に不快感を示して避けるようになった<ref name="three_days_with_dijkstra">中山晴康, "ダイクストラ教授との3日間", ''bit'', Vol.9, Issue 1, 1977, pp.7-9, 共立出版. </ref>。この言葉を作った時、彼はプログラミングが手工芸から科学へ発展することを期待していた<ref name="also_speech_dijkstra" />。しかし構造化プログラミングという言葉は実利を求めるために使われるようになった<ref name="three_days_with_dijkstra" />。次のような逸話がある。[[構造化分析設計技法]]の第一人者[[エドワード・ヨードン]]の事務所にセミナー依頼の電話がかかってきた。プロジェクトメンバー全員に構造化プログラミングを1日で叩きこんで欲しいという内容である。それが終わったらプロジェクト期間を半分にするという。その理由は「構造化プログラミングは生産性を2倍にするという話ですから」であった<ref name="managing_the_structured_techniques">Edward Nash Yourdon, ''構造化手法によるソフトウェア開発'', 黒田純一郎, 渡部研一 訳, 日経BP社, 1987. </ref>。 |
後年、ダイクストラは自身が作った構造化プログラミングという言葉に不快感を示して避けるようになった<ref name="three_days_with_dijkstra">中山晴康, "ダイクストラ教授との3日間", ''bit'', Vol.9, Issue 1, 1977, pp.7-9, 共立出版. </ref>。この言葉を作った時、彼はプログラミングが手工芸から科学へ発展することを期待していた<ref name="also_speech_dijkstra" />。しかし構造化プログラミングという言葉は実利を求めるために使われるようになった<ref name="three_days_with_dijkstra" />。次のような逸話がある。[[構造化分析設計技法|構造化開発]]の第一人者[[エドワード・ヨードン]]の事務所にセミナー依頼の電話がかかってきた。プロジェクトメンバー全員に構造化プログラミングを1日で叩きこんで欲しいという内容である。それが終わったらプロジェクト期間を半分にするという。その理由は「構造化プログラミングは生産性を2倍にするという話ですから」であった<ref name="managing_the_structured_techniques">Edward Nash Yourdon, ''構造化手法によるソフトウェア開発'', 黒田純一郎, 渡部研一 訳, 日経BP社, 1987. </ref>。 |
||
== ダイクストラの構造化プログラミング == |
== ダイクストラの構造化プログラミング == |
||
「Structured Programming」という |
「Structured Programming」という言葉を作ったのは計算機科学者[[エドガー・ダイクストラ]]であり、1969年のNATOソフトウェア工学会議で発表された論文が初出とされている。彼は2001年のノートで自分が作り出した「構造化プログラミング」という用語は結局異なる解釈で持ち去られてしまったと述べている<ref>{{Cite web|url=https://www.cs.utexas.edu/users/EWD/transcriptions/EWD13xx/EWD1308.html|title=What led to “Notes on Structured Programming”|accessdate=2020-1|publisher=}}</ref>。 |
||
ダイクストラが提唱した構造化プログラミングは、[[正当性 (計算機科学)|プログラム正当性]][[プログラム検証|検証]]技術の確立を |
ダイクストラが提唱した構造化プログラミングは、[[正当性 (計算機科学)|プログラム正当性]][[プログラム検証|検証]]技術の確立を原点にして構想された数々のプログラム開発理論の複合体である。遅くとも1967年からその構想は始められていた。1968年の[[goto文]]に依存しないシーケンスの制御、1969年の[[トップダウン設計とボトムアップ設計|トップダウン設計]]、[[抽象化 (計算機科学)|抽象化]]、[[モジュール化]]、共同詳細化から始まり、1972年には抽象データ構造、情報隠蔽、階層的プログラム構造といった考えも取り上げられていた<ref name="languages_for_structured_programming">{{cite journal|last=筧|first=捷彦|year=1975|title=ストラクチャード・プログラミング用言語|journal=情報処理|volume=16|number=10|page=856-863|publisher=情報処理学会|naid=110002720279}}</ref><ref name="problems_of_programming_methodology" /><ref name="program_design_chap6sec2" />。1972年の共著は、ダイクストラの第一章・構造化プログラミングから始まり、[[オーレ＝ヨハン・ダール|オルヨハン・ダール]]の第三章・階層的プログラム構造で締め括られている。[[オーレ＝ヨハン・ダール|ダール]]は[[オブジェクト指向プログラミング言語]]の草創[[Simula|Simula67]]の開発者である。 |
||
=== 1968年の投書「goto文は有害」 === |
=== 1968年の投書「goto文は有害」 === |
||
{{main|goto文#goto文論争}}1968年の |
{{main|goto文#goto文論争}}1968年の[[Association for Computing Machinery|ACM]]機関紙への投書「Go To Statement Considered Harmful<ref name="go_to_statement_considered_harmful" />」は、そのセンセーショナルなタイトルで当時のプログラマの間に大きな論争を巻き起こした。その要約は次の通りである。 |
||
# プログラマの仕事は正しいプログラムを作り上げた時に終結し、コンピュータにそのプログラム実行が委託されるとプログラマの手を離れて、コンピュータ内の動作形態であるプロセスに作り替えられることになる。 |
|||
* 人間が時間によって変化するプロセスを把握する能力は、プログラムの静的な関係を把握する能力に比べて劣っているため、静的なプログラムテキストの構造と時間によって変化するプロセスの構造をなるべく近づけるのが重要である。 |
|||
# 私たち人間の能力は、静的なプログラムの内容を把握するのには向いているが、コンピュータ内で逐一変化していく動的なプロセスの状態を把握することには向いていない。従って私たちは静的なプログラムと動的なプロセスの間にあるギャップを埋めなければならない。 |
|||
* そのためにはプロセスの進捗を表す簡潔な指標が必要がある。指標とは例えば実行中の行番号・その時点でのスタックトレース・行番号とループを回った回数のペアなどである。 |
|||
# そのためには、動的なプロセスの動態指標（dynamic index）と正確に対応できる静的なプログラムの文体指標（textual index）の表現が必要になる。goto先ラベルはその要求を満たしていない。「if B then A」「if B then A1 else A2」の選択節や「while B repeat A」「repeat A until B」の反復節の方が適している。 |
|||
* 例えば、1人が部屋に入るごとにカウンタを増やしていくプログラムにおいて、カウンタが室内の人数-1である瞬間はどこにあるのかという問いに答える際に、簡潔な指標があればすぐ答えられるが、簡潔な指標がなければ正確な答えは難しくなる。 |
|||
#gotoとラベルを用いた選択文と反復文の記述では、状態判定とジャンプが個々に並べられるので、これはプログラムの混乱の原因になる。特にラベルの多用は取り除かれるべきであり、それに伴ってgotoの使用数も削減される。 |
|||
* goto文を無条件に許してしまうと簡潔な指標は得られなくなってしまうため、高水準プログラミング言語においてはgoto文は廃止するべきである。 |
|||
#ただし、前述の節（clause、選択節と反節復）使用の徹底であらゆる必要性をまかなえるという訳ではない。goto文の論理冗長性は証明されているが、goto文削減がそのままフロー明瞭化に繋がる保証はないので推奨まではしない。 |
|||
この投書は、当時のソフトウェア開発現場で横行していたgoto先ラベルの安易な使用に警鐘を鳴らすためのものであったが、添えられた学術的注釈と文芸的比喩の数々が却って読み手の理解を妨げてしまい、冒頭のタイトル印象のみを先走りさせて、goto文論争を発生させることになった。この投書は比較的さり気ないもので、当時のダイクストラが方々の現場で目にしていたラベル多用をたしなめたい所感から書かれていた。ダイクストラが記していた元々の題名はA case against goto statement（goto文への訴え）であり、その時の編集者によって挑戦的なタイトルにすげ替えられていたのが事の真相である<ref>{{Cite web|title=E.W. Dijkstra Archive: What led to "Notes on Structured Programming" (EWD1308)|url=https://www.cs.utexas.edu/users/EWD/transcriptions/EWD13xx/EWD1308.html|website=www.cs.utexas.edu|accessdate=2021-08-16}}</ref>。 |
|||
なお、”I do not claim that the clauses mentioned are exhaustive in the sense that they will satisfy all needs”（前述の制御構造で全てが事足りるという訳ではない）ともしており、プロセスの進捗を表す簡潔な指標が存在する限りは3つの基本構造に固執してはいない。「構造化プログラミングの観点からgoto文を使うのは望ましくない」ものの「単にgoto文を使わなければ見通しが良くなる」という考えは否定されており、goto文の有無のみに固執するのは不毛である。構造化プログラミングの本質の一つは、状態遷移の適切な表現方法とタイミングを見極めることである<ref name="a_method_of_programming">E.W.ダイクストラ, W.H.J.フェイエン, ''プログラミングの方法'', 玉井浩 訳, サイエンス社, 1991.</ref>。ダイクストラも最後の段落で、goto文の(論理的な)余分さを証明したようだと軽く触れたのみであり、作られるフローチャートは元のものより正しさの証明が簡単になるとは思えないためジャンプを含まないフローチャートの機械的な作成は推奨しないとしていた。この投書の題名と内容の齟齬については後節「ダイクストラの後述」で説明されている。 |
|||
goto文論争はプログラミング分野の一つの流行として1970年代から80年代までの長きに渡って続いており、多くのプログラマにとっても馴染み深いテーマになっている。[[goto文]]と[[構造化定理]]の応酬はプログラミング談義の定番でもあった。ダイクストラは後年の著作で自分が提唱した構造化プログラミングの本質の一つは、この投書のテーマであった状態遷移の適切な表現方法と把握手段の確立としている<ref name="a_method_of_programming">E.W.ダイクストラ, W.H.J.フェイエン, ''プログラミングの方法'', 玉井浩 訳, サイエンス社, 1991.</ref>。 |
|||
=== 1969年の論文「構造化プログラミング」 === |
=== 1969年の論文「構造化プログラミング」 === |
||
| 66行目: | 69行目: | ||
論文の前半では、プログラムサイズの肥大化に伴い、各プログラム部品およびそれらを組み合わせた際のプログラムの正当性（''program correctness''）の立証（''demonstration''）に必要な労力が指数的に増加して完遂が不可能になるという[[ソフトウェア危機]]の問題について述べている。ダイクストラはプログラムの正しさに対して証明を与える従来の研究を分析して、証明の手続きを考えずに書かれたプログラムは証明に必要な労力がプログラムのサイズに対して爆発するとし、「与えられたプログラムに対してどうやって証明をするか」ではなく「証明がしやすいプログラムの構造とは何か」についてフォーカスするとした。 |
論文の前半では、プログラムサイズの肥大化に伴い、各プログラム部品およびそれらを組み合わせた際のプログラムの正当性（''program correctness''）の立証（''demonstration''）に必要な労力が指数的に増加して完遂が不可能になるという[[ソフトウェア危機]]の問題について述べている。ダイクストラはプログラムの正しさに対して証明を与える従来の研究を分析して、証明の手続きを考えずに書かれたプログラムは証明に必要な労力がプログラムのサイズに対して爆発するとし、「与えられたプログラムに対してどうやって証明をするか」ではなく「証明がしやすいプログラムの構造とは何か」についてフォーカスするとした。 |
||
後半ではそのための方法について説明している。まず推論しやすい構造として、ステートメントが順に並んだだけのものを挙げている。また、if文1つだけも推論しやすいとしている。しかし、if文がN個並んだ場合、そのままでは2のN乗ステップの推論が必要であるとしている。そこでif文を抽象ステートメントで1つずつ置き換える'''段階的抽象化'''（''step-wise abstraction''）により、Nに比例する推論で正しさを示せるとした。また、そのためには制御のジャンプを制限し、制御構造は順次の他に、選択、反復、および手続き呼び出しに限るべきとしている（順次、選択、反復のいわゆる制御構造（''control structures''）に触れているのはこの文節だけであ |
後半ではそのための方法について説明している。まず推論しやすい構造として、ステートメントが順に並んだだけのものを挙げている。また、if文1つだけも推論しやすいとしている。しかし、if文がN個並んだ場合、そのままでは2のN乗ステップの推論が必要であるとしている。そこでif文を抽象ステートメントで1つずつ置き換える'''段階的抽象化'''（''step-wise abstraction''）により、Nに比例する推論で正しさを示せるとした。また、そのためには制御のジャンプを制限し、制御構造は順次の他に、選択、反復、および手続き呼び出しに限るべきとしている（なお、順次、選択、反復のいわゆる制御構造（''control structures''）に触れているのはこの文節だけである）。この例のように詳細なプログラムを'''抽象化'''（''abstraction''）していくのではなく、逆に抽象的なプログラムから始めて'''詳細化'''（''refinement''）していくというやり方を示している。 |
||
詳細化の際には'''共同詳細化'''（''joint-refinement''）という考え方が示されている。これは抽象データ構造の詳細化と共にそれを扱う抽象ステートメントを同時に詳細化し、それを1つのプログラムテキストのユニットに分離するというものである。このユニットをダイクストラは真珠(pearl)と呼んだ。また、抽象的な真珠が1段階具体的な真珠に依存し、その真珠がさらに具体的な真珠に依存していったものをネックレスに例えた。そしてネックレスの上部は下部に関わらず正しさを証明することができ、また下部を取り替えることでプログラムのバリエーションを労力をかけずに作れるとした。 |
詳細化の際には'''共同詳細化'''（''joint-refinement''）という考え方が示されている。これは抽象データ構造の詳細化と共にそれを扱う抽象ステートメントを同時に詳細化し、それを1つのプログラムテキストのユニットに分離するというものである。このユニットをダイクストラは真珠(pearl)と呼んだ。また、抽象的な真珠が1段階具体的な真珠に依存し、その真珠がさらに具体的な真珠に依存していったものをネックレスに例えた。そしてネックレスの上部は下部に関わらず正しさを証明することができ、また下部を取り替えることでプログラムのバリエーションを労力をかけずに作れるとした。 |
||
=== 1972年の共著「構造化プログラミング」 === |
=== 1972年の共著「構造化プログラミング」 === |
||
1972年の共著「Structured Programming<ref name="structured_programming_72">O.-J. Dahl and E. W. Dijkstra and C. A. R. Hoare, ''Structured Programming'', Academic Press, London, 1972</ref>」は計算機科学界の錚々たる三名による三章構成で、第一章はエドガー・ダイクストラの「structured programming」、第二章は[[アントニー・ホーア]]の「data structuring」、第三章は[[オルヨハン・ダール]]の「hierarchical program structures」となっていた。結びの章の「階層 |
1972年の共著「Structured Programming<ref name="structured_programming_72">O.-J. Dahl and E. W. Dijkstra and C. A. R. Hoare, ''Structured Programming'', Academic Press, London, 1972</ref>」は計算機科学界の錚々たる三名による三章構成で、第一章はエドガー・ダイクストラの「structured programming」、第二章は[[アントニー・ホーア]]の「data structuring」、第三章は[[オルヨハン・ダール]]の「hierarchical program structures」となっていた。結びの章の「階層的プログラム構造」を著したダールは[[Simula|Simula67]]の開発者である。Simula67はオブジェクト指向プログラミングの草分けであり、この章名から[[継承 (プログラミング)|継承]]によるクラス階層構造を重視していたことがうかがえる。ダイクストラの構造化プログラミングは、制御構文と構造化定理と構造化設計の影に隠れながらも、Simula67をモデルにしたオブジェクト指向プログラミング発展の歴史に組み込まれて受け継がれていったと言える。1983年に[[C++]]を開発した[[ビャーネ・ストロヴストルップ]]は「What Is Object-Oriented Programming?<ref name="what_is_object-oriented_programming">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</ref>」において、オブジェクト指向を抽象データ構造と階層的プログラム構造の発展形として解説し、同時にSimula67の言語仕様を紹介している。 |
||
ダイクストラ提唱の構造化プログラミングを支持する[[ドナルド・クヌース]]は、1974年に自著「Structured Programming with go to Statements<ref name="structured_programming_with_go_to_statements" />」を |
ダイクストラ提唱の構造化プログラミングを支持する[[ドナルド・クヌース]]は、1974年に自著「Structured Programming with go to Statements<ref name="structured_programming_with_go_to_statements" />」を発表し、その中でgoto-lessの本質に関する補足と解説を加えている。これは当時のgoto文論争に一つの区切りを付けるものであったが、幅広い認知を得るには到らずにgoto文論争は1980年代になっても散発的に繰り広げられた。1970年代後半から[[マイクロコンピュータ|マイコン]]が普及して[[BASIC]]などを扱うパーソナルユーザーが増えると、goto命令を使わないのが構造化プログラミングといった見解が取り上げられて再び議論が始まるなど、この論争の影響は後年まで根強く残っている<ref group="注釈">直接は無関係だが、ダイクストラはBASIC批判の急先鋒でもあった。マイコン普及以前の1970年代に既に、BASICでプログラミング教育をすべきでない、と強く主張している（[https://en.wikiquote.org/wiki/Edsger%20W.%20Dijkstra#How_do_we_tell_truths_that_might_hurt?_(1975) wikiquote:Edsger W. Dijkstra#How do we tell truths that might hurt? (1975)]）。</ref>。 |
||
=== プログラム正当性検証のための構造化（1967年のノート） === |
|||
ダイクストラは、プログラマは正しいプログラムを作り出すばかりでなく納得のいくやり方で正しさを証明（[[プログラム検証|検証]]）することも仕事の一つであるという立場を取っていた<ref>[[構造化プログラミング#構造化プログラミング(1975)|構造化プログラミング(1975)]] p.6</ref>。プログラムがどんなに巨大化しても良く構造化（well-structured）されていれば、サイズに関係なくその[[正当性 (計算機科学)|正当性]]を[[プログラム検証|検証]]<ref>D.グリースはプログラムの正しさの証明を、抽象的なレベルでは正当性証明、具体的なレベルではプログラムの検証と言葉を使い分けているが、ここでは厳密な区別はしない。 |
|||
*金山裕 編, "構造的プログラミング −批判と支持−", ''bit'', Vol.7, Issue 7, 1975, pp.6-13, 共立出版.</ref>できるというのが彼の信念であった{{#tag:ref|すなわち、プログラム検証と構造化プログラミングとは不可分の関係にある。|group="注釈"}}<ref>所与のプログラムの正しさを後付けで証明することは、はじめから証明を意識して作られたプログラムの場合より難しいことが経験的に知られている、と言われる。 |
|||
*E.W.Dijkstra, "Programming methodologies, their objectives and their nature", ''Structured Programming'', Infotech state of the art report, 1976, pp.205-212, Infotech International.</ref>。well-formed formula（[[論理式 (数学)|論理式]]）に因んでいるwell-structuredには、[[数理論理学]]の[[証明論]]をソースコードにも導入する意図が込められていた。1967年のノート「Towards Correct Programs」でダイクストラは、良く構造化するための三つのメンタルツール（mental tool）をこのように示している。 |
|||
# 列挙（enumeration）： 一人の人間の能力でできる範囲でプログラムの命令の妥当性を一つ一つ確認していく作業 |
|||
# 数学的帰納（mathematical induction）： while文など計算機特有の多数の繰り返し文についてのみ数学的帰納法を用いて確認する作業 |
|||
# 抽象（abstraction）： プログラムのブロックなどに名前をつけ、さらに中身を見ないで正しいと仮定することで検証作業を後回しにする操作 |
|||
プログラムが正しいことを確認するには、それを証明しなければならない<ref name="structured_programming" />{{#tag:ref|D.グリースはプログラムの正しさの証明を、抽象的なレベルでは正当性証明、具体的なレベルではプログラムの検証と言葉を使い分けているが<ref name="bit1975_structured_programming">金山裕 編, "構造的プログラミング −批判と支持−", ''bit'', Vol.7, Issue 7, 1975, pp.6-13, 共立出版.</ref>、ここでは厳密な区別はしない。|group="注釈"}}。テストはプログラムに対する疑いを全て取り除くには不十分であるという意見が上がった<ref name="systematic_programming">N.ヴィルト, ''系統的プログラミング/入門'', 野下浩平, 筧捷彦, 武市正人 訳, 近代科学社, 1978. </ref><ref name="how_to_solve_it_by_computer">R.Geoff Dromey, ''How to Solve it by Computer'', Prentice Hall, 1982. </ref>。これについてダイクストラは「テストはバグの存在を示すには有効だが、バグが存在しないことは証明できない」という表現を好んで用いた<ref name="structured_programming" /><ref name="the_humble_programmer">E.W.ダイクストラ, “謙虚なプログラマ”, ''ACMチューリング賞講演集'', 木村泉 訳, 共立出版, 1989, pp.23-43. </ref><ref name="ewd273">[http://www.cs.utexas.edu/users/EWD/transcriptions/EWD02xx/EWD273.html E.W.Dijkstra, "The Programming Task Considered as an Intellectual Challenge", 1969.]</ref><ref name="ewd288">[http://www.cs.utexas.edu/users/EWD/transcriptions/EWD02xx/EWD288.html E.W.Dijkstra, "Concern for Correctness as a Guiding Principle for Program Composition", 1970.]</ref><ref name="ewd361">[http://www.cs.utexas.edu/users/EWD/transcriptions/EWD03xx/EWD361.html E.W.Dijkstra, "Programming as a discipline of mathematical nature", 1973.]</ref>。構造化プログラミングの支持者らは、プログラムの正しさの重要性と証明の方法や表明(assertion)の使い方について熱心に説いた<ref name="the_science_of_programming" /><ref name="structured_programming_72" /><ref name="systematic_programming" /><ref name="how_to_solve_it_by_computer" /><ref name="the_craft_of_programming">[https://www.cs.cmu.edu/~jcr/craftprog.html John C. Reynolds, ''The Craft of Programming'', Prentice-Hall, 1981.]</ref>。理想的にはテストだけに依存せず、プログラムの正しさの証明も与えるべきだと言われている<ref name="proving_programs_correct">ロバート B.アンダーソン, ''演習プログラムの証明'', 有沢誠 訳, 近代科学社, 1980. </ref><ref name="basic_theorem_of_programs">小野寛晰, ''プログラムの基礎理論'', サイエンス社, 1975. </ref>。所与のプログラムの正しさを後付けで証明することは、はじめから証明を意識して作られたプログラムの場合より難しいことが経験的に知られている<ref name="programming_methodologies">E.W.Dijkstra, "Programming methodologies, their objectives and their nature", ''Structured Programming'', Infotech state of the art report, 1976, pp.205-212, Infotech International.</ref>。ダイクストラは、プログラミングと同時にプログラムの証明を（わずかに証明を先行して）進めることを推奨している<ref name="a_discipline_of_programming">E.W.ダイクストラ, ''プログラミング原論 ― いかにしてプログラムをつくるか'', 浦昭治訳, サイエンス社, 1983. </ref>。そのようなアプローチでプログラムの正当性の問題にあたれば、複雑な問題であっても知的管理が可能であると述べた{{#tag:ref|ダイクストラはプログラミングと証明を並行するのに適した、最弱事前条件をによる検証方法を考案した。ホーア論理は作り終わったものは証明できるが、これから作るプログラムについては指標を与えてくれない<ref name="software_cleanroom">二木厚吉 監修, ''ソフトウェアクリーンルーム手法'', 日科技連, 1997. </ref>。|group="注釈"}}。しかし形式的な証明は、時として非人間的な長さの記述になることもダイクストラは認めている<ref name="a_discipline_of_programming" /><ref name="from_craft_to_scientific_discipline" />。同氏は、プログラムの証明が形式的であることにはこだわらないという意見を明らかにした<ref name="a_discipline_of_programming" /><ref name="structured_programming_with_go_to_statements" />{{#tag:ref|形式化にとらわれない点では（当時のダイクストラの）構造化プログラミングは[[形式手法]]と趣きが異なる。なおプログラムの正しさの証明とはウォークスルーやインスペクションによるレビューではなく、帰納法や最弱事前条件による検証を指す。 |
|||
形式的でない証明の方法については、ロバートの「プログラムの証明」<ref name="proving_programs_correct"/>が良い入門書の一つである。|group="注釈"}}。 |
|||
=== 構造化定理との関係 === |
=== 構造化定理との関係 === |
||
{{main|構造化定理}}1970年代初頭に{{仮リンク|デビッド・ハレル|en|David Harel|label=}}は、1966年に発表されていたベームとヤコピーニの証明に、[[構造化定理]] |
{{main|構造化定理}}1970年代初頭に計算機科学者{{仮リンク|デビッド・ハレル|en|David Harel|label=}}は、1966年に発表されていた[[コラド・ベーム|ベーム]]とヤコピーニの数学証明に、[[構造化定理]]（Structure theorem）という全く新しいタイトルを付けて主に産業ソフトウェア開発界隈で紹介した。ハレルが後に明かしたところによると「構造化定理」という名称は、当時[[IBM|IBM社]]の上席プログラマーであった[[ハーラン・ミルズ]]の提案だったという<ref name=":0" />。ダイクストラの提唱内容とは全く異なる、制御構造（順次・選択・反復）主体の構造化プログラミングは、IBM社のIPT（Improved Programming Technologies）に採用されており、同社主催の技術セミナーなどを通して当時のプログラマに広く流布されていた。その中で恐らく意図的にダイクストラのそれと名称を似せた「構造化定理」は、彼らが勧める制御構造の合理性を数学的にも証明した根拠として盛んに引用されていた。このような経緯から制御構造の使用と構造化定理は同一視されるようになり、ダイクストラのgoto文有害説から誤解された構造化プログラミングとも同一視されるようになった。goto文論争の中で引き合いに出されていた構造化定理もまた、ベームとヤコピーニから見れば誤解であった。 |
||
なお、ベームとヤコピーニの証明は、フローチャートやそれによって表現されるプログラム・関数・チューリングマシンなどの理論的側面に注目している。これは任意の論理回路が[[否定論理積|NAND]]素子の組み合わせによって表現できるとか、[[ラムダ計算| |
なお、ベームとヤコピーニの証明は、フローチャートやそれによって表現されるプログラム・関数・チューリングマシンなどの理論的側面に注目している。これは任意の論理回路が[[否定論理積|NAND]]素子の組み合わせによって表現できるとか、[[ラムダ計算|ラムダ式]]がSとKの2つの[[SKIコンビネータ計算|コンビネータ]]によって表現できるとかいった研究に近い。回路設計者が直接NANDを組み合わせて電子回路を設計しないのと同じように、構造化定理は良いプログラムの作成を（少なくとも直接的には）意図していない。ハレルも構造化定理は実際の内容以上に引用されて民間伝承定理（folk theorem）化していると指摘していた<ref name=":0" />。 |
||
=== ダイクストラの後述 === |
=== ダイクストラの後述 === |
||
ダイクストラは2001年のノート「[https://www.cs.utexas.edu/users/EWD/transcriptions/EWD13xx/EWD1308.html What led to “Notes on Structured Programming”]」(構造化プログラミング表記の由来）でこのように述べている。 |
ダイクストラは2001年のノート「[https://www.cs.utexas.edu/users/EWD/transcriptions/EWD13xx/EWD1308.html What led to “Notes on Structured Programming”]」(構造化プログラミング表記の由来）でこのように述べている。 |
||
1968年の自分は「A case against goto statement」(goto文 |
1968年の自分は「A case against goto statement」(goto文への訴え）と題した記事（article）をCommunications of the ACM（[[Association for Computing Machinery|ACM]]の機関紙）に投稿したが、当期の刊行を急ぐ編集担当者の意向で投書（letter to the Editor）にされる事になり、更にその担当者独自の考えで「The goto statement considered harmful」(goto文は有害）という全く新しい題名を付けられた。その担当者とは[[ニクラウス・ヴィルト]]であった。また、自分が提唱した構造化プログラミングの本質的内容の普及を好まない某社が[[ハーラン・ミルズ]]の主導で、まるでgoto文を廃止するかのようなプログラミング手法へと矮小化し、構造化プログラミングという用語まで持ち去ってしまった。 |
||
==脚注== |
==脚注== |
||
| 94行目: | 111行目: | ||
* {{citation | author=D.L.Parnas | year=1971 | title=Information Distribution Aspects of Design Methodology | url=http://cseweb.ucsd.edu/~wgg/CSE218/Parnas-IFIP71-information-distribution.PDF }} |
* {{citation | author=D.L.Parnas | year=1971 | title=Information Distribution Aspects of Design Methodology | url=http://cseweb.ucsd.edu/~wgg/CSE218/Parnas-IFIP71-information-distribution.PDF }} |
||
* {{citation | author=B.H.Liskov, S.N.Zilles | year=1974 | title=Programming with Abstract Data Type | url=http://www.znu.ac.ir/members/afsharchim/lectures/p50-liskov.pdf }} |
* {{citation | author=B.H.Liskov, S.N.Zilles | year=1974 | title=Programming with Abstract Data Type | url=http://www.znu.ac.ir/members/afsharchim/lectures/p50-liskov.pdf }} |
||
* {{Citation |title=多重ループからの脱出でのgoto文の是非 : Hoare理論の観点から | author=金藤 栄孝,二木 厚吉 | year=2004 | url=https:// |
* {{Citation |title=多重ループからの脱出でのgoto文の是非 : Hoare理論の観点から | author=金藤 栄孝,二木 厚吉 | year=2004 | url=https://cir.nii.ac.jp/crid/1050001337883766784}} |
||
* {{Citation |title=有限状態機械に基づくプログラミングでのgoto文使用の是非 : Hoare論理の観点から | author=金藤 栄孝,二木 厚吉 | year=2004 |url=https:// |
* {{Citation |title=有限状態機械に基づくプログラミングでのgoto文使用の是非 : Hoare論理の観点から | author=金藤 栄孝,二木 厚吉 | year=2004 |url=https://cir.nii.ac.jp/crid/1050845762813857792}} |
||
* {{Citation |title=システム設計言語DEAPLANについて | author=林 達也 | url=https:// |
* {{Citation |title=システム設計言語DEAPLANについて | author=林 達也 | url=https://cir.nii.ac.jp/crid/1050001337879972224}} |
||
* {{Citation |和書| title=プログラミングの科学 | author=D.グリース | translator=筧捷彦 | year=1991 | publisher=培風館}} |
* {{Citation |和書| title=プログラミングの科学 | author=D.グリース | translator=筧捷彦 | year=1991 | publisher=培風館}} |
||
* {{Citation |和書| chapter=第2章 go to文を用いた構造化プログラミング | title=文芸的プログラミング | author=Donald E. Knuth | translator=有澤誠 | year=1994 | publisher=アスキー}} |
* {{Citation |和書| chapter=第2章 go to文を用いた構造化プログラミング | title=文芸的プログラミング | author=Donald E. Knuth | translator=有澤誠 | year=1994 | publisher=アスキー}} |
||
| 105行目: | 122行目: | ||
*[[制御構文]] |
*[[制御構文]] |
||
*[[構造化定理]] |
*[[構造化定理]] |
||
| ⚫ | |||
*[[SSADM|構造化体系分析設計手法]] |
|||
*[[ジャクソンの構造化プログラミング]] |
*[[ジャクソンの構造化プログラミング]] |
||
| ⚫ | |||
*[[段階的詳細化法]] |
*[[段階的詳細化法]] |
||
*[[ALGOL]] |
|||
'''関連人物''' |
'''関連人物''' |
||
2024年11月29日 (金) 21:27時点における最新版
| プログラミング・パラダイム |
|---|
このプログラミング手法の普及に貢献したのは、1968年の計算機科学者エドガー・ダイクストラによるACM機関紙への投書「Go To Statement Considered Harmful」と言われている。しかし同じくダイクストラが、1969年度NATOソフトウェア工学会議で発表した論文「Structured Programming」との混同を招いてこちら側の名称で知られるようになった。現在に到るまでの国内外の多くの書籍で、構造化プログラミングは制御構文に関する説明に結び付けられている。なお、1969年の論文内容はプログラム正当性検証のための設計技法を扱っており、トップダウン設計、段階的な抽象化、階層的なモジュール化、抽象データ構造と抽象ステートメントを連携させる共同詳細化といった考え方が提唱されていた[3]。
制御構文
[編集]→詳細は「ミルズの構造化プログラミング」を参照
制御構文（control structures）とは、goto文によるフロー分岐やループ表現を、if文の選択構文やwhile文の反復構文に置き換えるためのプログラム記法を意味している。ラベル先にジャンプするというgoto文の機能を、if文やwhile文は「特定のコード群だけを実行する」という概念に置き換えている。goto文を用いた制御フローは、(1)データの照合/比較の結果にしたがって次の実行コード群を選択するパターンと、(2)データの照合/比較の結果が任意条件を満たしているならば実行コード群を反復するパターンの、二通りに集約されることが経験則で知られていたので、これを専用の記号で形式化したのが制御構文であった。
コード群とは命令コード（instruction code）のまとまりであり、構造化定理では部分プログラム（subprogram）と定義されている。部分プログラムはステートメント（statement）コードブロック（code block）サブルーチン（subroutine）の総称である。ステートメントは命令コードの一行を意味する。コードブロックは一行以上のステートメントをまとめたものである。サブルーチンは一行以上のステートメントまたは一個以上のコードブロックを内包している。部分プログラムは直列状または入れ子状に配置される。その実行順序を決定するものが制御構文であり、以下の三つがある。
- 順次（sequence）部分プログラムを順々に実行する。
- 選択（selection）条件式が導出した状態に従い、次に実行する部分プログラムを選択して分岐する。
- 反復（repetition）条件式が導出した特定の状態の間、部分プログラムを繰り返し実行する。
制御構造の導入は1960年公開の「ALGOL60」まで遡れるが、当時広く使われていたFORTRANやCOBOLでの正式導入は1977年以降だったので、多くの開発現場では馴染みのないものであった。1966年にコラド・ベームらが「順次・選択・反復」のフロー万能性を数学的に証明したが、それはあくまで論理的研究だった。それを参考にしたとされるダイクストラの1968年の投書「goto文は有害」はいわゆるgoto文論争を引き起こしたが、同時に制御構造への関心を大きく高めた。1970年代、goto文が多用される開発現場での制御構造の普及を重視していたIBM社のハーラン・ミルズは、1969年にダイクストラが発表していた論文題名から知名度を得ていた「構造化プログラミング」を自社の技術セミナーマーケティングに活用するために、上述のベームらの数学的証明を「構造化定理」という独自のタイトルで復刻させて、彼らが勧めるフローチャート制御構造の裏付け理論にした。こうして構造化プログラミングは、IBM社が提唱する構造化定理を論拠にした制御構造を用いるプログラミング手法として世間に定着することになった。
制御構造を導入したプログラミング言語を指しての「構造化言語」というワードが浮上したのは1970年代からであり、これは当時のgoto文中心だったFORTRANやCOBOLやBASICを意識してそれと線引きするための用語として存在していた。
構造化設計
[編集]→詳細は「段階的詳細化法」を参照
上述の制御構文をコーディング視点の下流工程テクニックとすると、構造化設計（structured design）はプログラムデザイン視点の上流工程テクニックであり、こちらも構造化プログラミングと呼ばれるものである。構造化設計では、サブルーチン（subroutine）をまとめたサブルーチン複合体と、データ要素をまとめたデータ構造（data structure）が主要な役割を果たしている。段階的詳細化に則ったサブルーチン複合体の階層的な組み合わせと、それに必要なデータ構造を連携させてプログラム全体を構築するというテクニックが構造化設計である。サブルーチン複合体はプログラムモジュール（program module）とも読み替えられ、モジュール凝集度と結合度もここから生まれている。
1974年頃から当初はIBM社が主導する形で、いずれも構造化（structured）が接頭辞につく数々のテクニックが発表されるようになり、1975年発表「ジャクソンの構造化プログラミング -Jackson structured programming(JSP)-」、1975年発表「構造化設計 -structured design(SD)-」、1978年発表「構造化分析 -structured analysis(SA)-」、1981年発表「構造化分析設計技法 -structured analysis and design technique(SADT)-」、1980年代発表「構造化体系分析設計手法 -structured systems analysis and design method(SSADM)-」、1989年発表「モダン構造化分析 -modern structured analysis-」などが広く普及している。著名な専門家としては、グレンフォード・マイヤーズ、ラリー・コンスタンティン、マイケル・ジャクソン、エドワード・ヨードン、トム・デマルコなどがいる。これらは「構造化開発」と総称されるようになり、1980年代までのソフトウェア開発の主流になった。
この構造化設計と、ダイクストラの構造化プログラミングの違いは、前者がサブルーチン複合体とデータ構造の連携を中心にしたテクニックであるのに対して、後者は専属サブルーチンを通して扱われる抽象データ構造を中心にしたテクニックであるという点である。後者では、段階的に抽象化した各モジュールの階層的な連結と、抽象データ構造と抽象ステートメントを連携させる共同詳細化といった考え方が提示されており、この詳細については後節で述べられる。ダイクストラが提唱した抽象（abstraction）指向の構造化は、その思想の前衛性から1970年代を通して理解を得られることはなく、発案者本来の構造化プログラミングは上流工程視点からも普及することはなかった。
歴史
[編集]第一幕
構造化プログラミングの誕生は、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]。
ダイクストラの構造化プログラミング
[編集]「Structured Programming」という言葉を作ったのは計算機科学者エドガー・ダイクストラであり、1969年のNATOソフトウェア工学会議で発表された論文が初出とされている。彼は2001年のノートで自分が作り出した「構造化プログラミング」という用語は結局異なる解釈で持ち去られてしまったと述べている[27]。
ダイクストラが提唱した構造化プログラミングは、プログラム正当性検証技術の確立を原点にして構想された数々のプログラム開発理論の複合体である。遅くとも1967年からその構想は始められていた。1968年のgoto文に依存しないシーケンスの制御、1969年のトップダウン設計、抽象化、モジュール化、共同詳細化から始まり、1972年には抽象データ構造、情報隠蔽、階層的プログラム構造といった考えも取り上げられていた[28][22][17]。1972年の共著は、ダイクストラの第一章・構造化プログラミングから始まり、オルヨハン・ダールの第三章・階層的プログラム構造で締め括られている。ダールはオブジェクト指向プログラミング言語の草創Simula67の開発者である。
1968年の投書「goto文は有害」
[編集]→詳細は「goto文 § goto文論争」を参照
1968年のACM機関紙への投書「Go To Statement Considered Harmful[9]」は、そのセンセーショナルなタイトルで当時のプログラマの間に大きな論争を巻き起こした。その要約は次の通りである。
- プログラマの仕事は正しいプログラムを作り上げた時に終結し、コンピュータにそのプログラム実行が委託されるとプログラマの手を離れて、コンピュータ内の動作形態であるプロセスに作り替えられることになる。
- 私たち人間の能力は、静的なプログラムの内容を把握するのには向いているが、コンピュータ内で逐一変化していく動的なプロセスの状態を把握することには向いていない。従って私たちは静的なプログラムと動的なプロセスの間にあるギャップを埋めなければならない。
- そのためには、動的なプロセスの動態指標（dynamic index）と正確に対応できる静的なプログラムの文体指標（textual index）の表現が必要になる。goto先ラベルはその要求を満たしていない。「if B then A」「if B then A1 else A2」の選択節や「while B repeat A」「repeat A until B」の反復節の方が適している。
- gotoとラベルを用いた選択文と反復文の記述では、状態判定とジャンプが個々に並べられるので、これはプログラムの混乱の原因になる。特にラベルの多用は取り除かれるべきであり、それに伴ってgotoの使用数も削減される。
- ただし、前述の節（clause、選択節と反節復）使用の徹底であらゆる必要性をまかなえるという訳ではない。goto文の論理冗長性は証明されているが、goto文削減がそのままフロー明瞭化に繋がる保証はないので推奨まではしない。
この投書は、当時のソフトウェア開発現場で横行していたgoto先ラベルの安易な使用に警鐘を鳴らすためのものであったが、添えられた学術的注釈と文芸的比喩の数々が却って読み手の理解を妨げてしまい、冒頭のタイトル印象のみを先走りさせて、goto文論争を発生させることになった。この投書は比較的さり気ないもので、当時のダイクストラが方々の現場で目にしていたラベル多用をたしなめたい所感から書かれていた。ダイクストラが記していた元々の題名はA case against goto statement（goto文への訴え）であり、その時の編集者によって挑戦的なタイトルにすげ替えられていたのが事の真相である[29]。
goto文論争はプログラミング分野の一つの流行として1970年代から80年代までの長きに渡って続いており、多くのプログラマにとっても馴染み深いテーマになっている。goto文と構造化定理の応酬はプログラミング談義の定番でもあった。ダイクストラは後年の著作で自分が提唱した構造化プログラミングの本質の一つは、この投書のテーマであった状態遷移の適切な表現方法と把握手段の確立としている[30]。
1969年の論文「構造化プログラミング」
[編集]1969年度NATOソフトウェア工学会議に寄稿されたこの「Structured Programming[3]」は、プログラム正当性の効率的な検証技術に重点を置き、当時問題視されていたコードサイズの際限なき肥大化によるソフトウェア危機の解決策として従来のボトムアップ設計からトップダウン設計への移行を推奨していた。
論文の前半では、プログラムサイズの肥大化に伴い、各プログラム部品およびそれらを組み合わせた際のプログラムの正当性（program correctness）の立証（demonstration）に必要な労力が指数的に増加して完遂が不可能になるというソフトウェア危機の問題について述べている。ダイクストラはプログラムの正しさに対して証明を与える従来の研究を分析して、証明の手続きを考えずに書かれたプログラムは証明に必要な労力がプログラムのサイズに対して爆発するとし、「与えられたプログラムに対してどうやって証明をするか」ではなく「証明がしやすいプログラムの構造とは何か」についてフォーカスするとした。
後半ではそのための方法について説明している。まず推論しやすい構造として、ステートメントが順に並んだだけのものを挙げている。また、if文1つだけも推論しやすいとしている。しかし、if文がN個並んだ場合、そのままでは2のN乗ステップの推論が必要であるとしている。そこでif文を抽象ステートメントで1つずつ置き換える段階的抽象化（step-wise abstraction）により、Nに比例する推論で正しさを示せるとした。また、そのためには制御のジャンプを制限し、制御構造は順次の他に、選択、反復、および手続き呼び出しに限るべきとしている（なお、順次、選択、反復のいわゆる制御構造（control structures）に触れているのはこの文節だけである）。この例のように詳細なプログラムを抽象化（abstraction）していくのではなく、逆に抽象的なプログラムから始めて詳細化（refinement）していくというやり方を示している。
詳細化の際には共同詳細化（joint-refinement）という考え方が示されている。これは抽象データ構造の詳細化と共にそれを扱う抽象ステートメントを同時に詳細化し、それを1つのプログラムテキストのユニットに分離するというものである。このユニットをダイクストラは真珠(pearl)と呼んだ。また、抽象的な真珠が1段階具体的な真珠に依存し、その真珠がさらに具体的な真珠に依存していったものをネックレスに例えた。そしてネックレスの上部は下部に関わらず正しさを証明することができ、また下部を取り替えることでプログラムのバリエーションを労力をかけずに作れるとした。
1972年の共著「構造化プログラミング」
[編集]1972年の共著「Structured Programming[31]」は計算機科学界の錚々たる三名による三章構成で、第一章はエドガー・ダイクストラの「structured programming」、第二章はアントニー・ホーアの「data structuring」、第三章はオルヨハン・ダールの「hierarchical program structures」となっていた。結びの章の「階層的プログラム構造」を著したダールはSimula67の開発者である。Simula67はオブジェクト指向プログラミングの草分けであり、この章名から継承によるクラス階層構造を重視していたことがうかがえる。ダイクストラの構造化プログラミングは、制御構文と構造化定理と構造化設計の影に隠れながらも、Simula67をモデルにしたオブジェクト指向プログラミング発展の歴史に組み込まれて受け継がれていったと言える。1983年にC++を開発したビャーネ・ストロヴストルップは「What Is Object-Oriented Programming?[32]」において、オブジェクト指向を抽象データ構造と階層的プログラム構造の発展形として解説し、同時にSimula67の言語仕様を紹介している。
ダイクストラ提唱の構造化プログラミングを支持するドナルド・クヌースは、1974年に自著「Structured Programming with go to Statements[6]」を発表し、その中でgoto-lessの本質に関する補足と解説を加えている。これは当時のgoto文論争に一つの区切りを付けるものであったが、幅広い認知を得るには到らずにgoto文論争は1980年代になっても散発的に繰り広げられた。1970年代後半からマイコンが普及してBASICなどを扱うパーソナルユーザーが増えると、goto命令を使わないのが構造化プログラミングといった見解が取り上げられて再び議論が始まるなど、この論争の影響は後年まで根強く残っている[注釈 4]。
プログラム正当性検証のための構造化（1967年のノート）
[編集]ダイクストラは、プログラマは正しいプログラムを作り出すばかりでなく納得のいくやり方で正しさを証明（検証）することも仕事の一つであるという立場を取っていた[33]。プログラムがどんなに巨大化しても良く構造化（well-structured）されていれば、サイズに関係なくその正当性を検証[34]できるというのが彼の信念であった[注釈 5][35]。well-formed formula（論理式）に因んでいるwell-structuredには、数理論理学の証明論をソースコードにも導入する意図が込められていた。1967年のノート「Towards Correct Programs」でダイクストラは、良く構造化するための三つのメンタルツール（mental tool）をこのように示している。
- 列挙（enumeration）： 一人の人間の能力でできる範囲でプログラムの命令の妥当性を一つ一つ確認していく作業
- 数学的帰納（mathematical induction）： while文など計算機特有の多数の繰り返し文についてのみ数学的帰納法を用いて確認する作業
- 抽象（abstraction）： プログラムのブロックなどに名前をつけ、さらに中身を見ないで正しいと仮定することで検証作業を後回しにする操作
プログラムが正しいことを確認するには、それを証明しなければならない[3][注釈 6]。テストはプログラムに対する疑いを全て取り除くには不十分であるという意見が上がった[7][37]。これについてダイクストラは「テストはバグの存在を示すには有効だが、バグが存在しないことは証明できない」という表現を好んで用いた[3][38][39][40][41]。構造化プログラミングの支持者らは、プログラムの正しさの重要性と証明の方法や表明(assertion)の使い方について熱心に説いた[4][31][7][37][42]。理想的にはテストだけに依存せず、プログラムの正しさの証明も与えるべきだと言われている[43][44]。所与のプログラムの正しさを後付けで証明することは、はじめから証明を意識して作られたプログラムの場合より難しいことが経験的に知られている[45]。ダイクストラは、プログラミングと同時にプログラムの証明を（わずかに証明を先行して）進めることを推奨している[46]。そのようなアプローチでプログラムの正当性の問題にあたれば、複雑な問題であっても知的管理が可能であると述べた[注釈 7]。しかし形式的な証明は、時として非人間的な長さの記述になることもダイクストラは認めている[46][15]。同氏は、プログラムの証明が形式的であることにはこだわらないという意見を明らかにした[46][6][注釈 8]。
構造化定理との関係
[編集]→詳細は「構造化定理」を参照
1970年代初頭に計算機科学者デビッド・ハレルは、1966年に発表されていたベームとヤコピーニの数学証明に、構造化定理（Structure theorem）という全く新しいタイトルを付けて主に産業ソフトウェア開発界隈で紹介した。ハレルが後に明かしたところによると「構造化定理」という名称は、当時IBM社の上席プログラマーであったハーラン・ミルズの提案だったという[20]。ダイクストラの提唱内容とは全く異なる、制御構造（順次・選択・反復）主体の構造化プログラミングは、IBM社のIPT（Improved Programming Technologies）に採用されており、同社主催の技術セミナーなどを通して当時のプログラマに広く流布されていた。その中で恐らく意図的にダイクストラのそれと名称を似せた「構造化定理」は、彼らが勧める制御構造の合理性を数学的にも証明した根拠として盛んに引用されていた。このような経緯から制御構造の使用と構造化定理は同一視されるようになり、ダイクストラのgoto文有害説から誤解された構造化プログラミングとも同一視されるようになった。goto文論争の中で引き合いに出されていた構造化定理もまた、ベームとヤコピーニから見れば誤解であった。
なお、ベームとヤコピーニの証明は、フローチャートやそれによって表現されるプログラム・関数・チューリングマシンなどの理論的側面に注目している。これは任意の論理回路がNAND素子の組み合わせによって表現できるとか、ラムダ式がSとKの2つのコンビネータによって表現できるとかいった研究に近い。回路設計者が直接NANDを組み合わせて電子回路を設計しないのと同じように、構造化定理は良いプログラムの作成を（少なくとも直接的には）意図していない。ハレルも構造化定理は実際の内容以上に引用されて民間伝承定理（folk theorem）化していると指摘していた[20]。
ダイクストラの後述
[編集]ダイクストラは2001年のノート「What led to “Notes on Structured Programming”」(構造化プログラミング表記の由来）でこのように述べている。
1968年の自分は「A case against goto statement」(goto文への訴え）と題した記事（article）をCommunications of the ACM（ACMの機関紙）に投稿したが、当期の刊行を急ぐ編集担当者の意向で投書（letter to the Editor）にされる事になり、更にその担当者独自の考えで「The goto statement considered harmful」(goto文は有害）という全く新しい題名を付けられた。その担当者とはニクラウス・ヴィルトであった。また、自分が提唱した構造化プログラミングの本質的内容の普及を好まない某社がハーラン・ミルズの主導で、まるでgoto文を廃止するかのようなプログラミング手法へと矮小化し、構造化プログラミングという用語まで持ち去ってしまった。
脚注
[編集]注釈
- ^ ソフトウェア危機の始まりと構造化プログラミングの歴史について[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.
参考文献
[編集]- E.W.ダイクストラ; C.A.R.ホーア; O.-J.ダール 著、野下浩平 訳『構造化プログラミング』サイエンス社、1975年。
- 落水 浩一郎『ソフトウェア工学実践の基礎 －分析・設計・プログラミング』。
- D.L.Parnas (1975), Use of the concept of transparency in the design of hierarchically structured systems
- D.L.Parnas (1971), Information Distribution Aspects of Design Methodology
- B.H.Liskov, S.N.Zilles (1974), Programming with Abstract Data Type
- 金藤 栄孝,二木 厚吉 (2004), 多重ループからの脱出でのgoto文の是非 : Hoare理論の観点から
- 金藤 栄孝,二木 厚吉 (2004), 有限状態機械に基づくプログラミングでのgoto文使用の是非 : Hoare論理の観点から
- 林 達也, システム設計言語DEAPLANについて
- D.グリース 著、筧捷彦 訳『プログラミングの科学』培風館、1991年。
- Donald E. Knuth 著、有澤誠 訳「第2章 go to文を用いた構造化プログラミング」『文芸的プログラミング』アスキー、1994年。
- E.W.ダイクストラ 著、浦昭治 訳『プログラミング原論 ― いかにしてプログラムをつくるか』サイエンス社、1983年。
- E.W.ダイクストラ; W.H.J.フェイエン 著、玉井浩 訳『プログラミングの方法』サイエンス社、1991年。
関連項目
[編集]関連人物
