はじめに
ダイクストラの「構造化プログラミング」について歴史を年表としてまとめてみた。
技術革新は基礎研究の積み重ねによるものだ。このことをもっと理解してもらいたいという考えが、この年表をつくった私の動機である。(初版2023/02/02)
注意事項として、
- 年表の正確さは保証できない
- 年表に関する質問は一切受け付けない
- 事実を裏付ける当事者のヒアリング調査はやっていない
- 内容が後日修正されることがある
- 引用は自由、ただし、それで発生する問題について責任は持たない
年表 (1957年～1978年)
1957年、ジャクソンが「待ち行列ネットワーク（待ち行列*1網、queueing network)」を提唱
1958年、コンウェイが「コルーチン (コルティン、共進譜、coroutine)」を提唱*2
同年、ダイクストラが学位論文「Communication with an Automatic Computer (自動機械での通信）」*3を発表
1959年、デッカーがダイクストラに対して、クリティカルセクション競合問題に関する解決法の正しさを証明*4
1960年、ナウアたちがプログラミング言語「ALGOL60」をリリース
同年、ニゴールがヨーロッパの学会で「離散事象ネットワーク*5（discrete event network)」のアイデアを発表
1965年、二ゴールとダールがプログラミング言語「SIMULA Ⅰ」をリリース。その言語で「new構文」と「疑似並列 (quasi-parallel)」を使ってコルーチンを実装
同年、ホーアが「レコードクラス(record class)」*6を提唱
同年、ダイクストラが「ダイクストラ・メッセージ(message)」を提唱。これはデッカーのアイデアに基づく。メッセージをプロセス同士でやりとりして、譲り合う仕組みを紹介*7
1966年、ダイクストラがNATO（北大西洋条約機構）主催のSummer School(Vilard-de-Lans)で「 Cooperating sequential processes（協調する逐次プロセス）」を報告。同報告書でダイクストラ・メッセージを使った「セマフォ(semaphores)」*8を提唱*9
同年、ダールがSummer School(Vilard-de-Lans)で「オブジェクトクラス(対象クラス、object class)」を提唱。これはレコードクラスを参考にしている*10
1967年、ダールとニゴールがプログラミング言語「SIMULA67」をリリース。オブジェクトクラスとメソッド*11とコルーチンとnew構文などを実装
同年、科学者たちがヨーロッパの学会で「virtual quantity」を提唱。「SIMULA67」で値呼び(call by value)だったメソッドの接頭語に「virtual」を付けることで名前呼び(call by name)にすることが可能となった
同年、フロイドが「Assigning Meanings to Programs」を発表
1968年、ダールとニゴールが論文「Class And SubClass Declaration」を発表。SIMULA67の「オブジェクト(対象、object)」やクラス、「サブクラス(部分クラス、subclass)」の概念を解説
同年、ダイクストラがトップダウン方式とボトムアップ方式の「階層構造 (hierarchical structure)」を提唱*12
1969年8月、ダイクストラがNATOの国際会合において、「構造化プログラミング」と題する研究報告の中で「 抽象データ構造 (abstract data structure)」を提唱。以降、毎年異なる内容の「構造化プログラミング」を報告し始める (原典1)
同年、ダイクストラが国際会合(ローマ）で「構造化プログラミング」を報告(原典2)。複数の物理機械の上に、複数の仮想機械たちがつながった階層モデルをつくる「洗練(refinement)」を解説
同年、ナウアが「アクション(作用、action)」と「クラスター(cluster)」を提唱
同年8月、ホーアが「An axiomatic basis for computer programming」*13を発表。これはフロイドのアイデアに基づく
1970年、ウィルトがプログラミング言語「PASCAL」をリリース。レコードと「ポインタ(pointer)」と「動的アロケータ(動的割付け、dynamic allocator)」を実装
同年、ホーアが論文「データ構造化序論」を発表 (原典3)。構造化プログラミングを数学理論で解説
同年、ダールがNATO主催のSummer School(Marktoberdorf)でSIMULA67について講義 (原典4)
1971年、ウィルトが「段階的洗練(step-wise refinement)」を提唱 (原典5)。これはダイクストラの洗練に基づく
同年、ホーアが「不変量 (invariant)」*14をプログラミングの正当性証明に導入*15
1972年、ダイクストラ、ホーア、ダールの三人が「構造化プログラミング」の書籍を出版。クラスの連接(継承)と抽象概念のダイクストラ階層構造を結びつける 。
「構造化プログラミング」書籍版の主な特徴
- 原典1～5をコピー加筆したもの
- 制御構造の3パターン「分解(decomposition)」と不変量を用いた証明の関連付け
- 抽象化とデータ型の関連付け (制御構造の3パターンをデータ構造化に見いだす）
- SIMULA67言語の解説
- クラスの連接（継承）とダイクストラ階層構造の関連付け
- クラスプログラミングによるダイクストラ法 (Leeのアルゴリズム)の実装
- オブジェクトクラスとコルーチンを通じて離散事象シミュレーションとセマフォの関連性を指摘
同年、パーナスが「モジュール化(modularization)」と「情報隠蔽(information hiding)」による分解をダイクストラ階層構造と関連付ける*16
1973年、リスコフが自身の論文で「抽象データ型(abstract data type)」を提唱。これは構造化プログラミングに基づく
1975年、サイエンス社が「構造化プログラミング」の邦訳版を日本で出版。これは1972年の書籍版を翻訳したもの
1978年、ホーアがダイクストラの研究とダールのクラスを紹介した論文「Communication Sequential Process（通信逐次プロセス 、通称、CSP)」を発表
訂正など
追記(2023年4月1日)
Algol Wの記述に誤りがあったので、削除
追記(2023年2月25日)
1972年のパルナス関連を年表へ追加。そのほか、「構造化プログラミング」でコルーチンが紹介されていることに触れる記述を年表へ追加
追記(2023年4月8日)
文中の「パルナス」の表記を「パーナス」に変更
*1:英語では、queueing、あるいは、waiting-line
*2:『KUNUTH The Art of Computer Programming 基本算法/基礎概念』(D.E.Knuth 著、廣瀬健 訳、サイエンス社、1989年9月) p.240
*3: (2) p.242
*4:
E.W. Dijkstra Archive: What led to "Notes on Structured Programming" (EWD1308)
*5:離散事象ネットワークのモデルは待ち行列ネットワークであり、「中継点（station)」間を客が移動するネットワーク構造である。中継点には「待ち行列部 (queuing part)」と「サービス部 (service part)」が備わっている。後に「ネットワーク」の文言が外される
*6:「RECORD HANDLING」（C. A. R. Hoare著、Elliott Bros. (London) Ltd. 1965年7月） https://archive.computerhistory.org/resources/text/algol/ACM_Algol_bulletin/1061032/p39-hoare.pdf 閲覧日2020年1月25日
*7:「 Solution of a problem in concurrent programming control」(E. W. Dijkstra著、 『Communications of the ACM』 Volume 8 Issue 9 1965年9月)
*8:注意点として、セマフォには2種類の意味がある。一つは、三本の腕木を使って手旗信号のように通信する機械(主にフランス語、オランダ語）と、もう一つは、一本の腕木を操作して赤青を切り替える鉄道の腕木式信号機(主に英語）
*9:「E.W.Dijkstra Archive: Cooperating sequential processes (EWD 123)」(E. W. Dijkstra 著、transcribed by Nick James and Ham Richards、revised Tue, 4 Dec 2007） https://www.cs.utexas.edu/users/EWD/transcriptions/EWD01xx/EWD123.html 閲覧日2020年6月16日
*10:「The Birth of Object Orientation: the Simula Languages∗」(Ole-Johan Dahl 著、2001年6月pp.3-4）https://www.mn.uio.no/ifi/english/about/ole-johan-dahl/bibliography/the-birth-of-object-orientation-the-simula-languages.pdf 閲覧日2020年11月5日
*11:メソッドは当時、手続きの遠隔識別((remote identification)と呼ばれていた
*12:「The Structure of the "THE"-Multiprogramming」(Edsger W. Dijkstra 著、Technological University, Eindhoven, The Netherlands、1968年5月)
https://doi.org/10.1145/800001.811672
https://klevas.mif.vu.lt/~liutauras/books/Dijkstra%20-%20The%20structure%20of%20the%20THE%20multiprogramming%20system.pdf 閲覧日2020年3月19日
*13:「An axiomatic basis for computer programming」C. A. R. Hoare著、 Communications of the ACM Volume 12 Issue 10、Oct. 1969 https://dl.acm.org/doi/10.1145/363235.363259
*14:「不変量」あるいは「不変式」は数学用語。不変条件とは訳さない
*15:「Proof of a program: FIND」 C. A. R. Hoare著、Communications of the ACM Volume 14< Issue 1 Jan. 1971 pp 39–45 https://doi.org/10.1145/362452.362489
*16:「On the Criteria To Be Used in Decomposing Systems into Modules」D.L. Parnas著、Communications of the ACM Volume 15 Number 12、December 1972
