エドガー・ダイクストラ

エドガー・ダイクストラは、オランダ人の計算機科学者。1972年、プログラミング言語の基礎研究への貢献に対してチューリング賞を受賞。構造化プログラミングの提唱者。1984年から2002年に亡くなるまでテキサス大学オースティン校の計算機科学の Schlumberger Centennial Chair を務めた。

2002年の死の直前、プログラム計算の自己安定化についての仕事に対して ACM PODC Influential Paper Award を授与された。この賞は翌年からダイクストラを称えてダイクストラ賞と呼ばれるようになった。

エズガー・ダイクストラと表記されることもある。オランダ語での発音は、IPA表記で /ˈɛtsxər ˈwibə ˈdɛɪkstra/}} で、エツハー・ウィベ・デイクストラに近い。

1. 生涯
-----

ロッテルダム生まれ。ライデン大学で理論物理学を学んだが、コンピュータ科学の方に興味があることに気が付くのに時間はかからなかった。最初にアムステルダムの国立数学研究所  に職を得たが、オランダのアイントホーフェン工科大学で教授職を得る。1970年代初期にはバロースのフェローとしても働いた。その後、アメリカのテキサス大学オースティン校に移り、2000年に引退した。

彼のコンピュータ科学に関する貢献としては、グラフ理論の最短経路問題におけるダイクストラ法、逆ポーランド記法とそれに関連する操車場アルゴリズム、初期の階層型システムの例であるTHEマルチプログラミングシステム、銀行家のアルゴリズム、排他制御のためのセマフォの考案などがある。分散コンピューティング分野では自己安定化というシステムの信頼性を保証する手法を提案した。ダイクストラ法は SPF  で使われており、それがOSPFやIS-ISといったルーティングプロトコルで使われている。操車場アルゴリズムやセマフォに代表されるが、鉄道を使用した説明でも知られる。

1950年代には、当時の他のコンピュータ科学者やプログラマたちと同様、機械語ないし、FORTRANのような当時一般的だった非構造的な言語によってプログラミングをしていたが、その後早くから大規模なプログラムをバグが無いように書くことの困難さについて警鐘を鳴らした一人であった。1960年代後半に「構造化プログラミング」を掲げ、プログラミングの改善について多くの文献や発言を残した。当時のプログラミングでは、ループや条件分けなどの、あらゆる制御構造を「goto文一本槍」で書くしかなかったわけだが、その問題点を指摘した "A Case against the GO TO Statement" という文章をしたためる。

しかしその主張は「goto文除去運動」といったように単純化されて捉えられることも多く、クヌースによれば1971年には、情報処理国際連合の国際会議で会った後藤英一が、いつも「除去」されて困るとジョークを言っていた、という。

前述の "A Case against the GO TO Statement" はコンピュータ科学の国際学会ACMに投稿され、『Go To 文は有害とみなされる』 という刺激的な題名で学会誌にレターとして掲載された。刺激的な題名はダイクストラ本人が付けたものではなく、当時編集を担当していたニクラウス・ヴィルトが付けたもので、すぐに掲載できるレター扱いを決めたのもヴィルトである。これは後に、"considered harmful" というフレーズが業界の定番となった原点でもある。1972年には、アントニー・ホーアとオーレ＝ヨハン・ダールとの共著で、"Structured Programming" という題名の書籍に、3人のそれぞれの主要分野に基づく、よりよいプログラミングについてまとめた。

以上のような立場から、BASICを教育に使うことにも強く反対し、mentally mutilated beyond hope of regenerationといった強い調子で否定する言葉を残している。ほぼ同じことをマイコン普及初期の1984年にも述べている。これも、当時に少年期を過ごし、BASICを使っていた現代のコンピュータ科学者などが、「私は無事だったようです」等とネタにすることがある。

ダイクストラは ALGOL 60 のファンとしても知られ、最初のコンパイラを実装したチームにも参加していた。そのコンパイラ開発に関わった Jaap Zonneveld とダイクストラはプロジェクトが完了するまで髭を剃らないという誓いを立てた。それは、世界初の再帰をサポートしたコンパイラの1つである。

1968年には、THEと呼ばれるマルチプログラミング方式のオペレーティングシステムの構造に関する論文と、"Cooperating Sequential Processes" についての論文を発表している。

1970年代になると、ダイクストラの主要な興味は形式的検証に移っていった。当時の一般的手法は、とりあえずプログラムを書いてからその正当性を数学的に証明するというものであった。ダイクストラはこれに対して、検証に時間がかかって面倒であるし、プログラムの開発手法に何ら洞察を与えない点が問題であるとした。一方「検証とプログラミングを同時に行う」のが「プログラム導出」と呼ばれる別の手法である。まず、プログラムの動作に関する数学的な「仕様」を記述し、その仕様に数学的な変換を加えて最終的にプログラムを導き出す。このように作成されたプログラムは「構造上正しい」ことが知られている。ダイクストラの後期の仕事は、この数学的手法を効率化することに関係している。2001年のインタビューで彼は「優雅さ」への渇望について述べていた。すなわち、完全さを求めるのではなく、思考を精神的に処理することが正しいアプローチであると。彼はたとえ話としてモーツァルトとベートーヴェンの作曲法を対比させている。

ダイクストラは分散コンピューティングの先駆者の1人でもある。例えば、彼の "Self-stabilizing Systems in Spite of Distributed Control" という論文は自己安定化というサブフィールドを創始した。

コンピュータ科学やプログラミングについての彼の意見は広範囲に及んだ。例えば、あるデータ構造の複数のインスタンスを処理している場合、経験則としてそのロジックをループ内にカプセル化すべきだと示唆し、また、プログラミングが本来非常に難しく複雑であり、プログラマはその複雑性をうまく管理するために可能な限り技巧と抽象化を利用する必要がある、という主張をした。

「コンピュータ科学」という用語が、実際には必要な抽象的性質について当を得ていない、とする以下のような発言もあった。

A confusion of even longer standing came from the fact that the unprepared included the electronic engineers that were supposed to design, build, and maintain the machines. The job was actually beyond the electronic technology of the day, and, as a result, the question of how to get and keep the physical equipment more or less in working condition became in the early days the all-overriding concern. As a result, the topic became —primarily in the USA— prematurely known as "computer science" —which, actually is like referring to surgery as "knife science"— and it was firmly implanted in people's minds that computing science is about machines and their peripheral equipment. Quod non.仕事は実のところ当時の電子工学技術の域を超えていて、物理的装置を動作可能にしてその状態を保つことが当初は何にも増して重要な課題だった。結果として特にアメリカでは「コンピュータ科学」という用語が時期尚早な形で使われるようになり、それが計算機と周辺機器についての科学であるという概念が人々の心に強く植えつけられた。Quod non

長年の癌との戦いの末、2002年8月6日、オランダのニューネンで亡くなった。

2. ダイクストラの箴言
------------

以下の言葉は、「ダイクストラの箴言」として引用されることが多い。

3. EWD と手書き文書
-------------

彼はまた、万年筆で慎重に原稿を書く習慣があることでも知られていた。ダイクストラは原稿に自分のイニシャルである //EWD//という記号と番号を付与したため、彼の原稿は一般に EWD と呼ばれている。ダイクストラ自身によれば、アムステルダムの数学研究所を離れてアイントホーフェン工科大学に移った後、この習慣が始まったという。アイントホーフェンに移った後、ダイクストラは1年以上何も書けない状態が続いた。自分を省みたダイクストラは、数学研究所の元同僚が理解するようなことを書けばアイントホーフェンの同僚には理解されず、アイントホーフェンの同僚が望むようなことを書けば数学研究所の元同僚に軽蔑されるという懸念があることを発見する。そこで彼は自分自身のためだけに書くことを決め、EWDが生まれた。ダイクストラは新たに EWD を書き上げると、そのコピーを同僚に配布した。それがさらにコピーされて世界中に配布されていき、計算機科学界全体に広がったのである。主題は計算機科学か数学であるが、一部は旅行記だったり、手紙だったり、講演記録だったりする。1300以上のEWDが電子化され、テキサス大学のダイクストラのアーカイブで検索・入手可能である。

ダイクストラの空想上の副業として、空想上の企業 Mathematics Inc. の会長という仕事があった。この企業はコンピュータのプログラム製造を商業化したソフトウェア企業のように、数学の定理を製造することを商業化した会社である。彼は Mathematics Inc. の様々な活動や課題を考案し、それをEWDシリーズのいくつかの文書で発表している。この空想上の企業はリーマン予想の証明を製造したが、リーマン予想が正しいと仮定して様々な証明を行ってきた数学者たちからロイヤルティーを徴収するという難題に直面する。証明そのものは企業秘密trade secret}}である。同社の証明の多くは急いで生産され、同社はそれらの保守に追われることになった。より成功した成果として、ピタゴラスの定理の標準的証明があり、100以上存在した既存の証明群を置換した。ダイクストラは Mathematics Inc. について「これまでに考案された最もエキサイティングで最もみじめなビジネス」と評した。EWD 443  では彼の想像した会社が世界の75%のシェアを獲得したとされている。

ダイクストラはソフトウェアについて様々な発明をしたが、自分のコンピュータを所有したのは比較的遅く、しかもめったに使わなかった。1972年以降のEWDはほとんどが手書きである。講義の際は黒板にチョークで書き、オーバーヘッドプロジェクタも滅多に使わなかった。アップルのMacintoshを購入してからも、電子メールとWebブラウザ以外には使わなかった。

4. 栄誉・受賞歴
---------

以下のような賞と栄誉を受けている。

1971年 - オランダ王立芸術科学アカデミー会員
1971年 - 英国コンピュータ学会特別フェロー
1972年 - チューリング賞 
1975年 - アメリカ芸術科学アカデミー 海外名誉会員
1976年 - 名誉学位
1982年 - IEEE Computer Society コンピュータパイオニア賞
1994年 - Association for Computing Machinery フェロー
2001年 - 名誉博士号
2002年 - C&C賞

5. 著作
-----

. “Letters to the editor: go to statement considered harmful”. //Communications of the ACM// 11 : 147–148. 10.1145/362929.362947}}. 0001-0782}}.  - Go To 文は有害だと考えられる
. “The Humble Programmer”. //Communications of the ACM// 15 : 859–866. 10.1145/355604.361591}}.  PDF, 1972年のチューリング賞講演
. “How do we tell truths that might hurt?”. SIGPLAN Notice 17 : 13–15. 10.1145/947923.947924}}. 0362-1340}}. 
//From My Life// 
, //Guarded commands, nondeterminacy and formal derivation of program//. //Communications of the ACM//, 18:453–457.
, //A Discipline of Programming//, Prentice-Hall Series in Automatic Computation, ISBN 0-13-215871-X — Guarded Command Language
//Selected Writings on Computing: A Personal Perspective//, Texts and Monographs in Computer Science, Springer-Verlag, 1982, ISBN 0-387-90652-5
//A Method of Programming//, E.W. Dijkstra, W.H.J. Feijen, trsl. by J. Sterringa, Addison Wesley 1988, ISBN 0-201-17536-3
Carel S. Scholten との共著 . //Predicate Calculus and Program Semantics//. Springer-Verlag ISBN 0-387-96957-8 — 述語変換意味論
O.-J. Dahl, C. A. R. Hoare との共著 //Structured Programming//, Academic Press, London, 1972 ISBN 0-12-200550-3
//Notes on Structured Programming// がベースになっている。また、エイト・クイーンをバックトラッキングを使って解く構造化された例がある。

6. 注釈
-----

7. 出典
-----

8. 参考文献
-------

[1] Digidome
[2]  //Formal Aspects of Computing// の死亡記事
[3] by David Gries
[4] by J Strother Moore
[5] by Mario Szegedy
[6]
[7]

9. 関連項目
-------

ダイクストラ法
食事する哲学者の問題
銀行家のアルゴリズム
Guarded Command Language と述語変換意味論
セマフォ

10. 外部リンク
---------

[8] ちえの和Web
[9], Charles Babbage Institute, University of Minnesota, Minneapolis.
[10]
[11], Charles Babbage Institute, University of Minnesota. - ダイクストラは1973年からバロースで研究者として働いていた。
[12] Video interview, 2001-04-10