(Translated by https://www.hiragana.jp/)
構造化プログラミング - Wikipedia コンテンツにスキップ

構造こうぞうプログラミング

出典しゅってん: フリー百科ひゃっか事典じてん『ウィキペディア(Wikipedia)』

構造こうぞうプログラミングこうぞうかプログラミングえい: structured programming)は、コンピュータプログラム処理しょり手順てじゅん明瞭めいりょう平易へいい判読はんどくせい向上こうじょう目的もくてきにしたプログラミング手法しゅほうである。一般いっぱんてきには順接じゅんせつ分岐ぶんき反復はんぷく三種さんしゅ制御せいぎょ構造こうぞう(control structures)によって処理しょりながれを記述きじゅつすることと認識にんしきされている[1][2]制御せいぎょ構造こうぞう制御せいぎょ構文こうぶん構造こうぞうぶん(structured statement)、制御せいぎょフローぶん(control flow statement)ともばれる。また、プログラムを任意にんい分割ぶんかつした部分ぶぶんプログラム(サブルーチンコードブロック)の階層かいそうてきわせによるプログラムの構造こうぞうしている。

このプログラミング手法しゅほう普及ふきゅう貢献こうけんしたのは、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)の総称そうしょうである。ステートメントは命令めいれいコードのいちぎょう意味いみする。コードブロックはいちぎょう以上いじょうのステートメントをまとめたものである。サブルーチンはいちぎょう以上いじょうのステートメントまたはいち以上いじょうのコードブロックを内包ないほうしている。部分ぶぶんプログラムは直列ちょくれつじょうまたはじょう配置はいちされる。その実行じっこう順序じゅんじょ決定けっていするものが制御せいぎょ構文こうぶんであり、以下いかみっつがある。

  1. 順次じゅんじ(sequence)部分ぶぶんプログラムを順々じゅんじゅん実行じっこうする。
  2. 選択せんたく(selection)条件じょうけんしき導出どうしゅつした状態じょうたいしたがい、つぎ実行じっこうする部分ぶぶんプログラムを選択せんたくして分岐ぶんきする。
  3. 反復はんぷく(repetition)条件じょうけんしき導出どうしゅつした特定とくてい状態じょうたいあいだ部分ぶぶんプログラムをかえ実行じっこうする。
順次じゅんじ選択せんたく反復はんぷく描写びょうしゃあおはNSダイアグラム、みどりはフローチャート)

制御せいぎょ構造こうぞう導入どうにゅうは1960ねん公開こうかいの「ALGOL60」までさかのぼれるが、当時とうじひろ使つかわれていたFORTRANCOBOLでの正式せいしき導入どうにゅうは1977ねん以降いこうだったので、おおくの開発かいはつ現場げんばでは馴染なじみのないものであった。1966ねんコラド・ベームらが「順次じゅんじ選択せんたく反復はんぷく」のフロー万能ばんのうせい数学すうがくてき証明しょうめいしたが、それはあくまで論理ろんりてき研究けんきゅうだった。それを参考さんこうにしたとされるダイクストラの1968ねん投書とうしょ「gotoぶん有害ゆうがい」はいわゆるgotoぶん論争ろんそうこしたが、同時どうじ制御せいぎょ構造こうぞうへの関心かんしんおおきくたかめた。1970年代ねんだい、gotoぶん多用たようされる開発かいはつ現場げんばでの制御せいぎょ構造こうぞう普及ふきゅう重視じゅうししていたIBMしゃハーラン・ミルズは、1969ねんにダイクストラが発表はっぴょうしていた論文ろんぶん題名だいめいから知名度ちめいどていた「構造こうぞうプログラミング」を自社じしゃ技術ぎじゅつセミナーマーケティングに活用かつようするために、上述じょうじゅつのベームらの数学すうがくてき証明しょうめいを「構造こうぞう定理ていり」という独自どくじのタイトルで復刻ふっこくさせて、かれらがすすめるフローチャート制御せいぎょ構造こうぞう裏付うらづ理論りろんにした。こうして構造こうぞうプログラミングは、IBMしゃ提唱ていしょうする構造こうぞう定理ていり論拠ろんきょにした制御せいぎょ構造こうぞうもちいるプログラミング手法しゅほうとして世間せけん定着ていちゃくすることになった。

制御せいぎょ構造こうぞう導入どうにゅうしたプログラミング言語げんごしての「構造こうぞう言語げんご」というワードが浮上ふじょうしたのは1970年代ねんだいからであり、これは当時とうじのgotoぶん中心ちゅうしんだったFORTRANCOBOLBASIC意識いしきしてそれと線引せんひきするための用語ようごとして存在そんざいしていた。

構造こうぞう設計せっけい[編集へんしゅう]

構造こうぞう設計せっけいいちれい

上述じょうじゅつ制御せいぎょ構文こうぶんをコーディング視点してん下流かりゅう工程こうていテクニックとすると、構造こうぞう設計せっけい(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ぶん有害ゆうがい[編集へんしゅう]

1968ねんACM機関きかんへの投書とうしょ「Go To Statement Considered Harmful[9]」は、そのセンセーショナルなタイトルで当時とうじのプログラマのあいだおおきな論争ろんそうこした。その要約ようやくつぎとおりである。

  1. プログラマの仕事しごとただしいプログラムをつくげたとき終結しゅうけつし、コンピュータにそのプログラム実行じっこう委託いたくされるとプログラマのはなれて、コンピュータない動作どうさ形態けいたいであるプロセスにつくえられることになる。
  2. わたしたち人間にんげん能力のうりょくは、静的せいてきなプログラムの内容ないよう把握はあくするのにはいているが、コンピュータない逐一ちくいち変化へんかしていく動的どうてきなプロセスの状態じょうたい把握はあくすることにはいていない。したがってわたしたちは静的せいてきなプログラムと動的どうてきなプロセスのあいだにあるギャップをめなければならない。
  3. そのためには、動的どうてきなプロセスの動態どうたい指標しひょう(dynamic index)と正確せいかく対応たいおうできる静的せいてきなプログラムの文体ぶんたい指標しひょう(textual index)の表現ひょうげん必要ひつようになる。gotoさきラベルはその要求ようきゅうたしていない。「if B then A」「if B then A1 else A2」の選択せんたくぶしや「while B repeat A」「repeat A until B」の反復はんぷくぶしほうてきしている。
  4. gotoとラベルをもちいた選択せんたくぶんはん復文ふくぶん記述きじゅつでは、状態じょうたい判定はんていとジャンプが個々ここならべられるので、これはプログラムの混乱こんらん原因げんいんになる。とくにラベルの多用たようのぞかれるべきであり、それにともなってgotoの使用しようすう削減さくげんされる。
  5. ただし、前述ぜんじゅつふし(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)をこのようにしめしている。

  1. 列挙れっきょ(enumeration): 一人ひとり人間にんげん能力のうりょくでできる範囲はんいでプログラムの命令めいれい妥当だとうせいひとひと確認かくにんしていく作業さぎょう
  2. 数学すうがくてき帰納きのう(mathematical induction): whileぶんなど計算けいさん特有とくゆう多数たすうかえぶんについてのみ数学すうがくてき帰納きのうほうもちいて確認かくにんする作業さぎょう
  3. 抽象ちゅうしょう(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ぶん廃止はいしするかのようなプログラミング手法しゅほうへと矮小わいしょうし、構造こうぞうプログラミングという用語ようごまでってしまった。

脚注きゃくちゅう[編集へんしゅう]

注釈ちゅうしゃく

  1. ^ ソフトウェア危機ききはじまりと構造こうぞうプログラミングの歴史れきしについて[4]だい23しょうくわしい。
  2. ^ "statements transferring control to labelled points" という言葉ことば一応いちおう goto ぶんれている[3]
  3. ^ Harel,David (1980)."On Folk Theorems"(PDF)のP381のひだりれつ中央ちゅうおうにハーラン・ミルズ(Harlan Mills)が公表こうひょう講義こうぎ資料しりょうなかで "The Structure Theorem" と名付なづけたことがかれている。この資料しりょう出典しゅってん[67]が1972ねんのため構造こうぞう定理ていり発明はつめいされたのは1970年代ねんだい初頭しょとう推測すいそくされる。
  4. ^ 直接ちょくせつ無関係むかんけいだが、ダイクストラはBASIC批判ひはん急先鋒きゅうせんぽうでもあった。マイコン普及ふきゅう以前いぜんの1970年代ねんだいすでに、BASICでプログラミング教育きょういくをすべきでない、とつよ主張しゅちょうしている(wikiquote:Edsger W. Dijkstra#How do we tell truths that might hurt? (1975))。
  5. ^ すなわち、プログラム検証けんしょう構造こうぞうプログラミングとは不可分ふかぶん関係かんけいにある。
  6. ^ D.グリースはプログラムのただしさの証明しょうめいを、抽象ちゅうしょうてきなレベルでは正当せいとうせい証明しょうめい具体ぐたいてきなレベルではプログラムの検証けんしょう言葉ことば使つかけているが[36]、ここでは厳密げんみつ区別くべつはしない。
  7. ^ ダイクストラはプログラミングと証明しょうめい並行へいこうするのにてきした、さいじゃく事前じぜん条件じょうけんをによる検証けんしょう方法ほうほう考案こうあんした。ホーア論理ろんりつくわったものは証明しょうめいできるが、これからつくるプログラムについては指標しひょうあたえてくれない[47]
  8. ^ 形式けいしきにとらわれないてんでは(当時とうじのダイクストラの)構造こうぞうプログラミングは形式けいしき手法しゅほうおもむきがことなる。なおプログラムのただしさの証明しょうめいとはウォークスルーやインスペクションによるレビューではなく、帰納きのうほうさいじゃく事前じぜん条件じょうけんによる検証けんしょうす。 形式けいしきてきでない証明しょうめい方法ほうほうについては、ロバートの「プログラムの証明しょうめい[43]入門にゅうもんしょひとつである。

出典しゅってん

  1. ^ 構造こうぞうプログラミングとは - IT用語ようご辞典じてん”. IT用語ようご辞典じてん e-Words. 2020ねん6がつ1にち閲覧えつらん
  2. ^ 構造こうぞうプログラミング - 意味いみ説明せつめい解説かいせつ : ASCII.jpデジタル用語ようご辞典じてん”. yougo.ascii.jp. 2020ねん6がつ1にち閲覧えつらん
  3. ^ 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.
  4. ^ a b c グリース, D. かけいとし彦訳 (1991). プログラミングの科学かがく. 培風館ばいふうかん. ISBN 4563007943 
  5. ^ 山崎やまざき利治としはる, "なが", プログラムの設計せっけい, 共立きょうりつ出版しゅっぱん, 1990, pp.110-113. ISBN 4320023781
  6. ^ 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. CiteSeerx10.1.1.103.6084. 
  7. ^ a b c N.ヴィルト, 系統けいとうてきプログラミング/入門にゅうもん, 野下のげ浩平こうへい, かけいとし彦, 武市たけいち正人まさと やく, 近代きんだい科学かがくしゃ, 1978.
  8. ^ 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. CiteSeerx10.1.1.119.9119. 
  9. ^ a b E. Dijkstra (1968). “Go To Statement Considered Harmful”. Communications of the ACM 11 (3): 147-148. CiteSeerx10.1.1.132.875. 
  10. ^ E.W.ダイクストラ 木村きむらいずみやく (1975), GO TO 論争ろんそうだい1 go to ぶん有害ゆうがいせつ, 7, 共立きょうりつ出版しゅっぱん, pp. 6-9 
  11. ^ B.リーヴェンワスへん, ed. (1975), “GO TO 論争ろんそうだい2 GO TO 論争ろんそう”, bit (共立きょうりつ出版しゅっぱん) 7 (5): 10-26 
  12. ^ 木村きむらいずみ, "GO TO 論争ろんそうだい3 解説かいせつ", bit, Vol.7, Issue 5, 1975, pp.27-39, 共立きょうりつ出版しゅっぱん.
  13. ^ 有澤ありさわまことやく文芸ぶんげいてきプログラミング』p.45
  14. ^ B. Randell and J.N. Buxton, (Eds.), Software Engineering, NATO Scientific Affairs Division, Brussels, Belgium, 1969.
  15. ^ a b c E.W.ダイクストラ (1977), “プログラミング−工芸こうげいから科学かがくへ”, 情報処理じょうほうしょり (情報処理じょうほうしょり学会がっかい) 18 (12): 1248-1256, NAID 110002753409 
  16. ^ a b 和田わだ英一ひでかず, "ダイクストラかくかたりき", bit, Vol.9, Issue 1, 1977, pp.4-6, 共立きょうりつ出版しゅっぱん.
  17. ^ a b 山崎やまざき利治としはる, "構造こうぞうてきプログラミング", プログラムの設計せっけい, 共立きょうりつ出版しゅっぱん, 1990, pp.113-142.
  18. ^ 玉井たまい哲雄てつお (2008), “ソフトウェア工学こうがくの40ねん (PDF), 情報処理じょうほうしょり 49 (7): 777-784, NAID 110006830060, http://www.graco.c.u-tokyo.ac.jp/~tamai/pub/40yearsSE.pdf 
  19. ^ Linger,R.C., Mills, H.D., Witt, B.I., Structured Programming: Theory and Practice, Addison-Wesly, 1979.
  20. ^ a b c Harel, David (1980-07-01). “On folk theorems”. Communications of the ACM 23 (7): 379–389. http://portal.acm.org/citation.cfm?doid=358886.358892. 
  21. ^ Edward Nash Yourdon ed., "Introduction (Chief Programmer Team Management of Production Programming)", Classics in Software Engineering, YOURDON inc., 1979, pp.63-64.
  22. ^ a b 木村きむらいずみ (1975). “プログラミング方法ほうほうろん問題もんだいてんちょう職業しょくぎょうてきプログラミングについて”. 情報処理じょうほうしょり (情報処理じょうほうしょり学会がっかい) 16 (10): 841-847. NAID 110002720277. 
  23. ^ 木村きむらいずみ, 米澤よねざわ明憲あきのり, 算法さんぽう表現ひょうげんろん, 岩波書店いわなみしょてん, 1982.
  24. ^ D.シャシャ, C.ラゼール, "エズガー・W・ダイクストラ", コンピュータの時代じだいひらいた天才てんさいたち, 鈴木すずきりょうなお わけ, 竹内たけうち郁雄いくお 監訳かんやく, 日経にっけいBPしゃ, 1998, pp.61-74. ISBN 4822280462
  25. ^ a b 中山なかやま晴康はるやす, "ダイクストラ教授きょうじゅとの3日間にちかん", bit, Vol.9, Issue 1, 1977, pp.7-9, 共立きょうりつ出版しゅっぱん.
  26. ^ Edward Nash Yourdon, 構造こうぞう手法しゅほうによるソフトウェア開発かいはつ, 黒田くろだ純一郎じゅんいちろう, 渡部わたなべ研一けんいち やく, 日経にっけいBPしゃ, 1987.
  27. ^ What led to “Notes on Structured Programming””. 2020ねん1がつ閲覧えつらん
  28. ^ かけい, とし彦 (1975). “ストラクチャード・プログラミングよう言語げんご”. 情報処理じょうほうしょり (情報処理じょうほうしょり学会がっかい) 16 (10): 856-863. NAID 110002720279. 
  29. ^ E.W. Dijkstra Archive: What led to "Notes on Structured Programming" (EWD1308)”. www.cs.utexas.edu. 2021ねん8がつ16にち閲覧えつらん
  30. ^ E.W.ダイクストラ, W.H.J.フェイエン, プログラミングの方法ほうほう, 玉井たまいひろし やく, サイエンスしゃ, 1991.
  31. ^ a b O.-J. Dahl and E. W. Dijkstra and C. A. R. Hoare, Structured Programming, Academic Press, London, 1972
  32. ^ 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
  33. ^ 構造こうぞうプログラミング(1975) p.6
  34. ^ D.グリースはプログラムのただしさの証明しょうめいを、抽象ちゅうしょうてきなレベルでは正当せいとうせい証明しょうめい具体ぐたいてきなレベルではプログラムの検証けんしょう言葉ことば使つかけているが、ここでは厳密げんみつ区別くべつはしない。
    • 金山かなやまひろし へん, "構造こうぞうてきプログラミング −批判ひはん支持しじ−", bit, Vol.7, Issue 7, 1975, pp.6-13, 共立きょうりつ出版しゅっぱん.
  35. ^ 所与しょよのプログラムのただしさをこうけで証明しょうめいすることは、はじめから証明しょうめい意識いしきしてつくられたプログラムの場合ばあいよりむずかしいことが経験けいけんてきられている、とわれる。
    • E.W.Dijkstra, "Programming methodologies, their objectives and their nature", Structured Programming, Infotech state of the art report, 1976, pp.205-212, Infotech International.
  36. ^ 金山かなやまひろし へん, "構造こうぞうてきプログラミング −批判ひはん支持しじ−", bit, Vol.7, Issue 7, 1975, pp.6-13, 共立きょうりつ出版しゅっぱん.
  37. ^ a b R.Geoff Dromey, How to Solve it by Computer, Prentice Hall, 1982.
  38. ^ E.W.ダイクストラ, “謙虚けんきょなプログラマ”, ACMチューリングしょう講演こうえんしゅう, 木村きむらいずみ やく, 共立きょうりつ出版しゅっぱん, 1989, pp.23-43.
  39. ^ E.W.Dijkstra, "The Programming Task Considered as an Intellectual Challenge", 1969.
  40. ^ E.W.Dijkstra, "Concern for Correctness as a Guiding Principle for Program Composition", 1970.
  41. ^ E.W.Dijkstra, "Programming as a discipline of mathematical nature", 1973.
  42. ^ John C. Reynolds, The Craft of Programming, Prentice-Hall, 1981.
  43. ^ a b ロバート B.アンダーソン, 演習えんしゅうプログラムの証明しょうめい, 有沢ありさわまこと やく, 近代きんだい科学かがくしゃ, 1980.
  44. ^ 小野おのひろし晰, プログラムの基礎きそ理論りろん, サイエンスしゃ, 1975.
  45. ^ E.W.Dijkstra, "Programming methodologies, their objectives and their nature", Structured Programming, Infotech state of the art report, 1976, pp.205-212, Infotech International.
  46. ^ a b c E.W.ダイクストラ, プログラミング原論げんろん ― いかにしてプログラムをつくるか, うら昭治しょうじやく, サイエンスしゃ, 1983.
  47. ^ 二木ふたき厚吉こうきち 監修かんしゅう, ソフトウェアクリーンルーム手法しゅほう, にち科技かぎれん, 1997.

参考さんこう文献ぶんけん[編集へんしゅう]

関連かんれん項目こうもく[編集へんしゅう]

関連かんれん人物じんぶつ

外部がいぶリンク[編集へんしゅう]