エドガー・ダイクストラ

エドガー・ダイクストラ
エドガー・ダイクストラ
	Edsger Wybe Dijkstra (1930-2002)
生誕	1930年5月11日; オランダロッテルダム
死没	2002年8月6日（72歳没）; オランダニューネン
研究分野	計算機科学
研究機関	オランダ国立情報数学研究所（英語版）; アイントホーフェン工科大学; テキサス大学オースティン校
博士課程; 指導教員	Adriaan van Wijngaarden
博士課程; 指導学生	Nico Habermann; Jan L.A. van de Snepscheut
主な業績	ダイクストラ法; 構造化プログラミング; THEマルチプログラミングシステム; セマフォ
主な受賞歴	チューリング賞
	プロジェクト:人物伝
	テンプレートを表示

エドガー・ダイクストラ（エツハー・ウィベ・デイクストラ、Edsger Wybe Dijkstra, オランダ語発音: [/ˈɛtsxər ˈwibə ˈdɛɪkstra/] 1930年 5月11日 - 2002年 8月6日）は、オランダ人の計算機科学者。1972年、プログラミング言語の基礎研究への貢献に対してチューリング賞を受賞。構造化プログラミングの提唱者。1984年から2002年に亡くなるまでテキサス大学オースティン校の計算機科学の Schlumberger Centennial Chair を務めた。

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

生涯

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

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

1950年代には、当時の他のコンピュータ科学者やプログラマたちと同様、機械語ないし、FORTRANのような当時一般的だった非構造的な言語によってプログラミングをしていたが、その後早くから大規模なプログラムをバグが無いように書くことの困難さについて警鐘を鳴らした一人であった。1960年代後半に「構造化プログラミング」を掲げ、プログラミングの改善について多くの文献や発言を残した。当時のプログラミングでは、ループや条件分けなどの、あらゆる制御構造を「goto文一本槍」で書くしかなかったわけだが、その問題点を指摘した "A Case against the GO TO Statement"^[1] という文章をしたためる（注: ダイクストラには、ホーアやクヌースなど、似た問題意識を持っていた他のコンピュータ科学者らとの手紙や学会関係の集まりでの交流にもとづき、改訂を重ねたことにより、いくつかのバージョンのある文章が多い）。

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

前述の "A Case against the GO TO Statement" はコンピュータ科学の国際学会ACMに投稿され、『Go To 文は有害とみなされる』("Go To Statement Considered Harmful") という刺激的な題名で学会誌（CACM）にレターとして掲載された（この出来事は、やはりクヌースによれば「go to文除去の話の二番目の場面は，多くの人たちが第一幕だと思っている事実」^[3]となった）。刺激的な題名はダイクストラ本人が付けたものではなく、当時編集を担当していたニクラウス・ヴィルトが付けたもので、すぐに掲載できるレター扱いを決めたのもヴィルトである。これは後に、"considered harmful" というフレーズが業界の定番となった原点でもある。1972年には、アントニー・ホーアとオーレ＝ヨハン・ダールとの共著で、"Structured Programming" という題名の書籍に、3人のそれぞれの主要分野（ホーアはホーア論理が著名なように形式手法、ダールはSimulaの設計者の一人であり、データ抽象（後のオブジェクト指向につながる）に関して解説した）に基づく、よりよいプログラミングについてまとめた。

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

ダイクストラは ALGOL 60 のファンとしても知られ、最初のコンパイラを実装したチームにも参加していた。そのコンパイラ開発に関わった Jaap Zonneveld とダイクストラはプロジェクトが完了するまで髭を剃らないという誓いを立てた^[5]。それは、世界初の再帰をサポートしたコンパイラの1つである^[6]（現代では戻り番地や引数をスタックに積む、という再帰できるようにするための処理は、空気のように当たり前のことになっているので特記事項である意味がわからないかもしれないが、それ以前にあったコンパイラ、例えば「世界最初のコンパイラ」と言われることのあるひとつである、IBMによるFORTRANコンパイラは、理由あって^{[※ 1]}最適化等は追求していたものの、実行時に関数を再帰呼出しすることはサポートしていなかった）。

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

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

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

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

「コンピュータ科学」という用語が、（情報理論などといった）実際には必要な抽象的性質について当を得ていない、とする以下のような発言もあった（EWD924、なお日本では「情報科学」など、ある程度それを補うような語が併用されている）。

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.^[9]
（訳）（コンピュータを操作するという）仕事は実のところ当時の電子工学技術の域を超えていて、物理的装置を動作可能にしてその状態を保つことが当初は何にも増して重要な課題だった。結果として特にアメリカでは「コンピュータ科学」という用語が時期尚早な形で使われるようになり（実際、それは外科を「ナイフ科学」と呼ぶようなものである）、それが計算機と周辺機器についての科学であるという概念が人々の心に強く植えつけられた。Quod non（ラテン語で「それは正しくない」）

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

ダイクストラの箴言

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

Program testing can be a very effective way to show the presence of bugs, but is hopelessly inadequate for showing their absence. Edsger W. Dijkstra "The Humble Programmer (1972)"

EWD と手書き文書

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

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

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

栄誉・受賞歴

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

1971年 - オランダ王立芸術科学アカデミー会員
1971年 - 英国コンピュータ学会特別フェロー
1972年 - チューリング賞 (Association for Computing Machinery)^[18]
1975年 - アメリカ芸術科学アカデミー海外名誉会員
1976年 - 名誉学位（クイーンズ大学ベルファスト）
1982年 - IEEE Computer Society コンピュータパイオニア賞
1994年 - Association for Computing Machinery フェロー^[19]
2001年 - 名誉博士号（ギリシャの Athens University of Economics & Business）
2002年 - C&C賞

著作

(March 1968). “Letters to the editor: go to statement considered harmful”^{[※ 2]}. Communications of the ACM 11 (3): 147–148. doi:10.1145/362929.362947. ISSN 0001-0782. (EWD215) - Go To 文は有害だと考えられる
(Aug 1972). “The Humble Programmer”^{[※ 3]}. Communications of the ACM 15 (10): 859–866. doi:10.1145/355604.361591. (EWD340) PDF, 1972年のチューリング賞講演
(May 1982). “How do we tell truths that might hurt?”^{[※ 4]}. SIGPLAN Notice 17 (5): 13–15. doi:10.1145/947923.947924. ISSN 0362-1340. (EWD498)
From My Life^{[※ 5]} (EWD1166)
(August 1975), Guarded commands, nondeterminacy and formal derivation of program. Communications of the ACM, 18(8):453–457. ^{[※ 6]}
(1976), 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 との共著 (1990). Predicate Calculus and Program Semantics. Springer-Verlag ISBN 0-387-96957-8 — 述語変換意味論
O.-J. Dahl, C. A. R. Hoare との共著 Structured Programming^{[※ 7]}, Academic Press, London, 1972 ISBN 0-12-200550-3
- Notes on Structured Programming (EWD249)^{[※ 8]}がベースになっている。また、エイト・クイーンをバックトラッキングを使って解く構造化された例がある。

注釈

^ IBMという企業という立場上、顧客に（あるいは社内的にも）「コンパイラの有用性を示す」という目標が絶対であったため、最初から最適化を目指すという普通は無謀と思われるような開発を行わねばならなかった。そのために言語自体の設計から始めたとは言え多大の工数を必要としたが（1954年〜1957年）、目標は無事達成された。
^ ewd215 "A Case against the GO TO Statement."
^ http://www.cs.utexas.edu/users/EWD/ewd03xx/EWD340.PDF "The Humble Programmer."
^ Edsger Dijkstra - How do we tell truths that might hurt?
^ E.W.Dijkstra Archive: "From my Life" (EWD 1166)
^ Guarded commands, nondeterminacy and formal derivation of programs | Communications of the ACM
^ Structured programming: | Guide books
^ ewd249 "NOTES ON STRUCTURED PROGRAMMING"

出典

^ Dijkstra, Edsger W. A Case against the GO TO Statement (EWD-215). E.W. Dijkstra Archive. Center for American History, University of Texas at Austin (original; transcription)
^ 『文芸的プログラミング』 p. 43
^ 『文芸的プログラミング』 p. 45
^ Dijkstra, Edsger W. How do we tell truths that might hurt? (EWD-498). E.W. Dijkstra Archive. Center for American History, University of Texas at Austin (original; transcription)
^ van Emden, Maarten (2008年5月6日). “I remember Edsger Dijkstra (1930–2002)”. 2010年12月22日閲覧。
^ Daylight, E. G. (2011). “Dijkstra's Rallying Cry for Generalization: the Advent of the Recursive Procedure, late 1950s - early 1960s”. The Computer Journal. doi:10.1093/comjnl/bxr002. http://www.dijkstrascry.com/node/4.
^ Dijkstra, Edsger W. Cooperating sequential processes (EWD-123). E.W. Dijkstra Archive. Center for American History, University of Texas at Austin (original; transcription)
^ “Edsger Dijkstra - Discipline in Thought (visit www.catonmat.net for notes)”. Video.google.com. 2012年4月20日閲覧。
^ Dijkstra, Edsger W. On a cultural gap (EWD-924). E.W. Dijkstra Archive. Center for American History, University of Texas at Austin (original; transcription) Dijkstra, E.W. (1986). “On a cultural gap”. The Mathematical Intelligencer 8 (1): 48–52.
^ Goodwins, Rupert (2002年8月8日). “Computer science pioneer Dijkstra dies” 2010年12月22日閲覧。
^ Online EWD archive, University of Texas, http://www.cs.utexas.edu/users/EWD/ .
^ ^a ^b Dijkstra, Edsger W. EWD-475. E.W. Dijkstra Archive. Center for American History, University of Texas at Austin (original; transcription)
^ Dijkstra, Edsger W. EWD-539. E.W. Dijkstra Archive. Center for American History, University of Texas at Austin (original; transcription)
^ Dijkstra, Edsger W. EWD-427. E.W. Dijkstra Archive. Center for American History, University of Texas at Austin (original; transcription)
^ Dijkstra, Edsger W. EWD-433. E.W. Dijkstra Archive. Center for American History, University of Texas at Austin (original; transcription)
^ Dijkstra, Edsger W (1982). Selected Writings on Computing: A Personal Perspective. Berlin: Springer-Verlag. ISBN 978-0-387-90652-2
^ ^a ^b In Memoriam Edsger Wybe Dijkstra (memorial), University of Texas .
^ “A. M. Turing Award”. Association for Computing Machinery. 2011年2月5日閲覧。
^ “ACM Fellows - D”. Association for Computing Machinery. 2011年2月15日閲覧。