ダイクストラは何を変えたのか｜最短経路・OS・セマフォ・構造化プログラミングからたどるコンピュータ科学の誕生

スマートフォンで地図を開き、目的地までの経路を検索する。複数のアプリを同時に動かす。クラウド上のサービスが、何台ものコンピュータにまたがって処理を続ける。私たちは毎日、ごく自然にこうした仕組みを使っています。

その背景にあるコンピュータ科学の歴史をたどると、何度も同じ人物の名前に出会います。エドガー・W・ダイクストラ（Edsger Wybe Dijkstra、1930–2002）です。

ダイクストラと聞いて「ダイクストラ法」を思い浮かべる人は多いでしょう。大学の情報系授業やアルゴリズムの本では、重み付きグラフの最短経路を求める方法として登場します。最短経路アルゴリズムは彼の仕事の一部です。

ダイクストラは、初期のコンピュータのためのプログラムを書き、世界最初期のALGOL 60コンパイラを作り、再帰呼び出しの実装を考え、並行処理の相互排除を研究し、セマフォを導入し、デッドロックを考察し、OSを階層構造で設計し、GOTO文をめぐる論争を起こし、構造化プログラミングを押し広げ、プログラムの正しさを数学的に導く方法を研究し、さらに分散システムが壊れた状態から自力で正常状態へ戻る「自己安定化」という分野まで切り開きました。

彼の仕事を時系列で追うと、コンピュータが強力になり、プログラムが巨大で複雑になるほど、人間はそれをどう理解し、どう正しさを保証すればよいのかという一つの問いが浮かび上がります。ダイクストラは、この「複雑さ」の問題を生涯追い続けました。

---

1．1930年、まだ「コンピュータ科学」が存在しない時代に生まれる

ロッテルダムの科学者一家

エドガー・ワイベ・ダイクストラは1930年5月11日、オランダのロッテルダムに生まれました。

父は化学者、母は数学に秀でた人物でした。後年のダイクストラは、母から受けた数学的助言を何度も回想しています。たとえば16歳のころ、三角法の教科書に並ぶ公式を見て不安になり、母に「三角法は難しいのか」と尋ねたところ、「公式を知りなさい。そして5行以上必要になったら、間違った道にいると思いなさい」という趣旨の答えを受けたと記しています。

後のダイクストラの仕事には、「複雑なものを力ずくで処理するより、短く、明快で、扱いやすい形へ変える」という姿勢が一貫しています。巨大な計算をそのまま押し切るのではなく、適切な抽象化や構造によって、人間が考えられる規模へ変える発想です。

コンピュータ科学者になろうとは考えていなかった

現在なら、大学に「コンピュータ科学」「情報科学」「ソフトウェア工学」といった学科があります。ダイクストラが学生だった1940年代には、そのような学問領域はまだ成立途上でした。

彼はロッテルダムのGymnasium Erasmianumを卒業し、1948年からライデン大学で数学と理論物理学を学びました。進路として想定していたのは理論物理学者です。

一般の学生がコンピュータに触れる機会はほとんどなく、電子計算機そのものが世界的にまだ新しい時代でした。「プログラマー」という職業も成立途上でした。

1950年前後のコンピュータとは何だったのか

第二次世界大戦後、イギリスやアメリカを中心に電子式コンピュータが急速に発展します。ただし、現在のパソコンを小さくしたものを想像すると実態を見誤ります。

初期の電子計算機は巨大で高価で、大学や政府機関、大企業など限られた場所に設置されました。記憶容量はごく小さく、入力には紙テープやパンチカードが使われ、プログラムを実行するにも機械固有の事情を深く理解する必要がありました。

ハードウェアを作ること自体が大事業だったため、プログラミングは機械を動かすための付随作業、あるいは職人的な技能と見られることも多かったのです。

後にダイクストラは、チューリング賞講演『The Humble Programmer』で、プログラミングという職業がいかにゆっくり成立したかを振り返っています。彼の人生は、まさに「プログラミングが職業になる前」から始まりました。

---

2．1951年、物理学者志望の青年がプログラミングに出会う

父が見つけたNatureの記事

転機は1951年に訪れました。ダイクストラの父が科学誌Natureでケンブリッジ大学のプログラミング・サマースクールに関する案内を見つけ、ダイクストラは将来理論物理を研究する際にコンピュータが役立つかもしれないと考えて参加しました。

講習を行ったのは、EDSACの開発で知られるモーリス・ウィルクス（Maurice Wilkes）らでした。

EDSACは1949年に稼働した、初期の実用的なプログラム内蔵方式コンピュータの一つです。現在の感覚では「コンピュータを使う＝既存のOSやアプリの上で操作する」ことですが、この時代は、機械をどう使うか、プログラムをどう表現するか、サブルーチンをどう保存して再利用するかといったこと自体が研究課題でした。

ダイクストラは後年、1951年のこの講習でプログラミングを紹介されたと明確に回想しています。当時の彼にとってプログラミングは、理論物理のための道具になりうる新しい技能でした。しかし、翌年から人生の中心になっていきます。

1952年、Mathematisch Centrumのプログラマーになる

1952年、ダイクストラはアムステルダムのMathematisch Centrum（数学センター、現在のCWI）で働き始めます。本人の回想では、給与上の職名として「programmer」を持ったオランダ最初の人物でした。最初は週2日程度の仕事で、残りの日はライデン大学で理論物理を学び、進路を決めかねていました。

2020年代なら「プログラマーです」「ソフトウェアエンジニアです」と名乗れば職業として通じますが、1950年代前半には、専門職としても学問としても、その位置づけはまだ定まっていない時代でした。ハードウェアは急速に変化し、機械ごとに書き方も異なり、論文誌や教科書も十分に整っていない世界で、ダイクストラは職業人生を始めました。

ARRA、FERTA、ARMAC――「まだ存在しない機械」のためにプログラムを書く

Mathematisch Centrumでは、ARRA、FERTA、ARMACといった初期計算機が開発されました。

ダイクストラの仕事で特徴的なのは、完成した機械を触りながらプログラムを書くのではなく、しばしば「まだ完成していない機械」の仕様をもとにプログラムを考えたことです。

後年のEWD1308で彼は、EDSACで学んだプログラム組織を手本として、ARRAの表記、入出力、ライブラリ構造を考え、その後のFERTA、ARMAC、X1でも似たパターンを踏襲したと振り返っています。

機械の完成前なので、仕様を読み、抽象的な機械を頭の中に作り、その上でプログラムを設計する必要がありました。この経験は、後に彼が「プログラムを実機の偶然的な性質から切り離して考える」「プログラムを数学的対象として扱う」方向へ進む背景の一つになりました。

1955年ごろ――物理か、プログラミングか

理論物理学の勉強とプログラミングの仕事を両立することが次第に難しくなり、ダイクストラは上司のアドリアーン・ファン・ワインガールデン（Adriaan van Wijngaarden）に相談します。

「尊敬される理論物理学者になるのか、それとも、まだ何者なのか分からないプログラマーになるのか」。

1972年のチューリング賞講演でダイクストラは、この会話のあと「別人になった」と表現しています。

ワインガールデンは、プログラミングにはまだ確立した学問的基盤がないが、コンピュータはこれから存在し続ける。そしてダイクストラは、プログラミングを立派な学問にする側に回れるのだと励ましました。

これはダイクストラの人生の最重要場面です。完成した学問に入るのではなく、まだ学問になっていない領域を学問にする。以後の彼の仕事を理解する鍵が、ここにあります。

「プログラマー」が職業欄に存在しなかった

時代を象徴するエピソードとして、1957年に結婚した際、職業欄に「programmer」と書こうとしたところ、その職業が公的記録で認められず、代わりに「theoretical physicist」と記載したという話を本人のインタビューが伝えています。

数十年後には「プログラマー」や「ソフトウェアエンジニア」が世界中で一般的な職業になります。その変化の起点にいたダイクストラは、後にプログラミングを数学的な知的活動として位置づける中心人物になりました。

---

3．1956年、カフェで生まれた「最短経路」――ダイクストラ法

コンピュータの力を一般の人にどう見せるか

1956年、Mathematisch CentrumではARMACというコンピュータの公式披露を予定していました。専門家向けなら巨大な数値計算でも十分ですが、一般の来場者には、問題そのものと答えの意味が直感的に分かる実演が必要でした。

そこでダイクストラが選んだのが、都市間の最短経路です。「ロッテルダムからフローニンゲンまで、どの道を通れば最短か」。地図なら誰でも問題を理解でき、答えが経路として表示されれば、コンピュータが何をしたのかも分かります。

紙も鉛筆も使わず考えた「20分の発明」

ダイクストラは後年、このアルゴリズムをアムステルダムのカフェのテラスで、当時婚約者だったRiaとコーヒーを飲みながら、紙も鉛筆も使わず考えたと回想しています。CWIの紹介では本人の言葉をもとに「20-minute invention」と表現されています。

そもそも「グラフ」とは何か

数学・コンピュータ科学でいうグラフは、次の要素からなるネットワークです。

• 点＝頂点（vertex / node）
• 点と点を結ぶ線＝辺（edge）
• 辺についた距離や時間など＝重み（weight）

たとえば、次の5都市があるとします。

接続	距離
A–B	7
A–C	2
C–B	3
B–D	2
C–D	8
C–E	5
E–D	1

AからDへ行く経路を直感的に探すと、A→B→Dなら9、A→C→Dなら10、A→C→B→Dなら2+3+2=7です。

都市が5個なら候補を比較できますが、1000個、100万個と増えると、すべての経路を列挙する方法では候補数が爆発的に増え、計算量が急増します。

ダイクストラ法の核心

ダイクストラ法は、始点から「現時点で最も近いと確定できる頂点」を一つずつ決めていきます。

Aを始点とします。最初はAまでの距離0だけが確定しており、Aから直接行ける頂点に暫定距離を置きます。

• B：7
• C：2
• D：∞
• E：∞

1. 最小の暫定距離C=2を選び、Cまでの最短距離を2と確定します。
2. Cから先を調べます。C→Bは3なのでA→C→B=5となり、Bの暫定値を7から5へ更新します。C→Dは8なのでD=10、C→Eは5なのでE=7です。
3. 未確定の暫定距離はB=5、E=7、D=10なので、最小のB=5を確定します。
4. BからDへ2なのでA→C→B→D=7となり、Dの暫定値を10から7へ更新します。
5. 未確定値の最小がD=7になったため、AからDへの最短距離は7と確定します。経路はA→C→B→Dです。

なぜ「今いちばん近いもの」を確定してよいのか

この方法は、局所的に最もよさそうな選択を積み重ねる「貪欲法（greedy method）」の代表例として説明されます。標準的なダイクストラ法では、辺の重みが負でないことが前提です。

負の重みがあると、「いま最短だと思って確定した頂点」へ後からもっと短い経路が見つかり、確定済みの距離が更新される可能性があります。そのため、負の重みを含む最短経路問題にはBellman–Ford法など別の方法が使われます。

1959年、たった3ページの論文

ダイクストラが1956年に考えたアルゴリズムの論文発表は1959年でした。本人の回想によれば、当時は離散アルゴリズムが数学として十分な尊敬を得ておらず、適切な投稿先もほとんどなかったからです。

1959年、創刊されたばかりの学術誌『Numerische Mathematik』に「A Note on Two Problems in Connexion with Graphs」を発表します。論文は269–271ページ、わずか3ページです。

論文で扱ったのは、次の二つの問題です。

• 最短経路問題
• 最小全域木（minimum spanning tree）の問題。後者はX1のバックパネル配線で使用する銅線の量を減らす問題から着想したと本人は回想しています。

ただし、ここは歴史上の優先順位を丁寧に区別する必要があります。ダイクストラが1959年論文で示した最小全域木の方法と同等の考え方は、チェコの数学者ヴォイチェフ・ヤルニーク（Vojtěch Jarník）が1930年に発表し、ロバート・プリム（Robert C. Prim）も1957年に独立に発表していました。現在は一般にPrim法、またはJarník–Prim法などと呼ばれます。歴史的優先順位は、Jarník 1930、Prim 1957、Dijkstra 1959の順です。ダイクストラはX1の具体的な配線問題から同じ型のグラフ問題へ独立に到達し、それを最短経路問題と同じ3ページの論文にまとめました。

短い論文なのに、半世紀以上にわたってアルゴリズム研究と教育で読まれることになりました。

「Googleマップはダイクストラ法を使っている」のか

実際の道路ネットワークには、一方通行、右左折制限、時間帯、渋滞、道路階層、交通手段など多くの条件があります。大規模サービスでは、A*、双方向探索、階層化、前処理など、さまざまな高速化・拡張技術を組み合わせることが一般的です。

「ネットワーク上でコスト最小の経路を効率的に探す」という考え方の歴史では、ダイクストラ法が基本的な出発点の一つです。

しかし、これが最大の功績ではない

これほど有名なアルゴリズムを作った人物なら、それだけでも十分に歴史へ名を残しますが、ダイクストラの仕事はここからさらに広がります。

最短経路アルゴリズムを生み出した1950年代後半、彼の目の前ではコンピュータそのものが、単に「計算を速くする」機械から、割り込みを受け、複数の処理を扱い、高級言語を実行する、はるかに複雑な機械へ変化していました。

それに伴い、ダイクストラの研究テーマも「良いアルゴリズムを考える」ことから、「複雑なプログラムを人間はどう制御するか」へ広がっていきます。

---

4．「人間が読み書きできる言語」を機械に理解させる――ALGOL 60と世界最初期のコンパイラ

機械語だけでは、プログラムは大きくできない

初期コンピュータでは、プログラマーは機械に近い命令体系を直接扱いました。

現在のプログラムなら、たとえば「xとyを足してzに入れる」という処理は、人間が比較的読みやすい記法で書けます。しかし機械が直接理解するのは命令コードと数値です。コンピュータごとに命令形式も異なります。

小さなプログラムなら、熟練者が機械の詳細を覚えて書くこともできます。しかしソフトウェアが大きくなれば、そのやり方は限界に達します。

そこで1950年代に重要になったのが高水準プログラミング言語です。FORTRAN、COBOL、ALGOLなどが登場し、人間がより抽象度の高い記述でプログラムを書き、それをコンパイラが機械語へ翻訳する形が広がっていきました。

現在ではコンパイラの存在は当然に見えますが、「人間向けの複雑な言語を、限られた記憶容量しか持たないコンピュータ上で正確に機械語へ変換する」ことは、1950年代末には最先端の難題でした。

ALGOL 60は何が新しかったのか

ALGOLはAlgorithmic Languageの略です。特に1960年に仕様がまとまったALGOL 60は、後世のプログラミング言語史で非常に重要な位置を占めます。

ブロック構造、局所変数、再帰的な手続き呼び出しなど、現代の多くの言語につながる発想を体系的に備えていました。C、Pascal、Adaなど後世の言語設計への影響も大きく、プログラミング言語を「機械の都合だけではなく、アルゴリズムを明確に表現するための形式」として考えるうえで重要な役割を果たします。

ダイクストラはALGOL 60の成立過程に関わり、Mathematisch CentrumでJaap ZonneveldとともにElectrologica X1用のALGOL 60コンパイラを開発しました。CWIの歴史研究では、このDijkstra–Zonneveldコンパイラは1960年夏に稼働した世界最初のALGOL 60コンパイラと位置づけられています。

4K語の記憶にコンパイラを入れる

CWIが後に復元・分析した資料によると、X1のALGOL 60コンパイラは4K語、1語27ビットの記憶空間で動くよう設計されました。

現在のスマートフォンは数GBのメモリを搭載します。1GBを約10億バイトと考えれば、比較すること自体が難しいほど規模が違います。

限られたメモリには、コンパイラ自身のコードに加えて、翻訳作業のための作業領域も必要でした。

この制約の中でALGOL 60の豊かな構造を実装するため、次の問題を一つずつ現実の機械に落とし込みます。

• 変数をどこへ置くか
• 手続き呼び出しをどう管理するか
• 式をどの順番で評価するか
• 一時的な値をどこに保存するか
• 再帰呼び出しをどう実現するか
• 限られたメモリをどう節約するか

火事が怖くて、毎晩原稿を家へ持ち帰った

ダイクストラは後年のEWD1166で、Zonneveldとコンパイラを作っていたころ、Mathematisch Centrumの火災で仕事が失われる事態に備え、二人で同じ原稿のコピーを持ち、毎晩それぞれ自宅へ持ち帰ったと回想しています。

当時のバックアップ手段は紙の複製でした。ソフトウェアが「紙の原稿」として存在した時代を伝えるエピソードです。

再帰とは何か

ALGOL 60で重要だった概念の一つが再帰です。再帰とは、ある手続きが自分自身を呼び出すことです。たとえば階乗では、5! = 5 × 4 × 3 × 2 × 1を一般にn! = n × (n−1)!と定義できます。

プログラムなら、概念的には次のようになります。

factorial(n)
  if n = 0 then 1
  else n * factorial(n - 1)

factorial(5)を呼ぶと、途中でfactorial(4)を呼び、それがfactorial(3)を呼び……というように、自分自身の呼び出しが重なります。各呼び出しは別々のnを持つため、その状態を個別に保存する必要があります。

• factorial(5)のn=5
• factorial(4)のn=4
• factorial(3)のn=3

さらに、「呼び出しが終わったらどこへ戻るか」という戻り先の記録も必要です。

スタック――後に戻るための記憶

このような入れ子の処理を扱うために便利なのがスタックです。皿を重ねる場面を想像すると分かりやすく、新しい皿は一番上に置き、取り出すときも一番上から取ります。最後に入れたものが最初に出るため、LIFO（Last In, First Out）と呼ばれます。

再帰呼び出しでも、呼び出すたびに「現在の状態」と「戻り先」を積み、終了したら一番上から取り出して戻ります。

ダイクストラは1960年の短い論文「Recursive Programming」で、この実装の本質を説明する際に「stack」という語を使いました。

スタックに似た考えは複数の研究者が独立に考えていたと、本人自身も述べています。ダイクストラの重要性は、再帰を含む高級言語の実装という具体的課題の中で、スタックを明確な仕組みとして使い、世界最初期の本格的コンパイラへ落とし込んだことにあります。

コンパイラの仕事が、後の思想につながる

ALGOL 60コンパイラを作る経験から、ダイクストラは、複雑なシステムでは細部をすべて同時に考えるのではなく、一段上の抽象概念を作ってその上で考える必要があると学びます。

スタック、ブロック、手続き、再帰といった概念は、機械の0と1を直接追わなくてもプログラムを考えられるようにします。この「抽象化で複雑さを封じ込める」という考え方は、次のOS研究でさらに大きな意味を持ちます。

---

5．コンピュータが「同時に複数の仕事」を始めた瞬間、問題が爆発する

1台の機械をもっと有効に使いたい

1950年代から1960年代、コンピュータは非常に高価でした。CPUが計算している間は高速でも、紙テープの読み取り、印刷、磁気ドラムからのデータ待ちでは処理が止まります。そこで、一つの仕事が入出力を待っている間に別の仕事を進める「マルチプログラミング」が重要になりました。

計算資源を有効に使える一方、複数の処理を同時進行させると、共有データや実行順序をめぐる新しい問題が生まれます。

100円の残高から、2人が同時に10円引いたら？

共有口座の残高が100円あり、処理Aと処理Bがそれぞれ10円を引くとします。最終的な残高は80円になるはずですが、プログラム内部では次の3段階に分かれているとします。

1. 残高を読む
2. 10を引く
3. 新しい残高を書き戻す

処理Aが100を読み、その直後、Aが90を書き戻す前に処理Bも100を読みます。Aは100−10=90を書き込み、Bも自分が読んだ100をもとに90を書き込みます。結果は80ではなく90となり、一方の更新が消えてしまいます。これが競合状態（race condition）の典型例です。

「同じプログラムなのに毎回結果が違う」

並行処理の厄介な点は、バグが毎回同じように再現するとは限らないことです。Aが先に終わってもBが先に終わっても正しい一方、特定のタイミングで命令が交互に実行されたときだけ壊れることがあります。

初期のリアルタイム割り込みを扱ったダイクストラは、こうした非再現性を身をもって経験しました。EWD1303では、割り込みの瞬間が再現できないため、プログラムの誤りが「たまに起こる機械故障」のように見える恐ろしさを回想しています。

現在のマルチコアCPUや分散システムでも、本質的な難しさは残っています。

クリティカルセクション

共有データを安全に扱うには、「この部分だけは同時に2つの処理が入ってはいけない」という区間を作ります。この区間がクリティカルセクション（critical section）です。先ほどの銀行残高なら、次の一連の処理をまとめて保護します。

• 残高を読む
• 10を引く
• 書き戻す

処理Aがクリティカルセクションにいる間はBが待ち、Aが終了したらBが入ります。すると、Aが100→90、Bが90→80となり、正しい結果になります。

相互排除という問題

一度に一つの処理だけがクリティカルセクションに入れるようにすることを相互排除（mutual exclusion）といいます。

1965年、ダイクストラは「Solution of a Problem in Concurrent Programming Control」という実質わずか1ページの論文で、N個のプロセスに対する相互排除問題を扱いました。短い論文ですが、並行アルゴリズムの歴史では重要な位置を占めます。

ダイクストラが得意だったのは、巨大な現実問題の中から「本質的な問題だけを取り出す」ことでした。コンピュータ全体を説明するのではなく、「N個の独立した処理があり、共有部分に一度に一つしか入れてはいけない。どうするか」という抽象問題にします。

問題を抽象化すれば、特定のプリンターや特定のCPU速度に依存せず、一般的な解法を考えられます。

速度を仮定しない

ダイクストラは、「処理AはBより速い」といった速度比を論理の前提から外しました。プリンターが高速化したり、CPUが交換されたり、別の機械で動かしたりすれば、速度に依存した正しさは崩れます。

そこで、個々の処理の速度は未定義として扱い、必要な同期だけを明示します。この考えはTHE Multiprogramming Systemでも中心になります。ダイクストラにとって良い設計とは、条件を明確にし、その条件のもとで正しいと論理的に説明できることでした。

---

6．セマフォ――「入ってよい数」を数えるだけで、並行処理を整理する

特別な整数を一つ用意する

相互排除を毎回複雑な手順で書く代わりに、ダイクストラはセマフォ（semaphore）という概念を導入しました。EWD123「Cooperating Sequential Processes」では、セマフォを非負整数として扱い、それを操作するP操作とV操作を定義しています。

イメージとしては、「あと何人入れるか」を示す札だと思えば分かりやすいでしょう。値が1なら一人だけ入れ、誰かが入ると0になります。0のときに別の処理が来れば待ち、中にいる処理が出ると1に戻って待機中の処理が進めます。

P操作とV操作

単純化すると、P操作は「利用できる資源があれば一つ取る。なければ待つ」、V操作は「資源を一つ返す」です。

重要なのは、P操作の判定と減算が不可分、つまり途中で別の処理が割り込めない操作として扱われることです。次の二つを別々に実行すると、二つのプロセスが同時に「1だ」と読んでしまい、相互排除が破綻する可能性があります。

1. 値を見る
2. 1減らす

二値セマフォ

相互排除だけが目的なら、値は0か1で足ります。初期値を1にして、クリティカルセクションに入る前にP、出たあとにVを実行します。概念的には次の形です。

P(mutex)
  共有データを扱う
V(mutex)

mutexはmutual exclusionから来た名前で、後世にはmutexという同期プリミティブ自体も一般化します。

一般セマフォは「資源の個数」を表せる

セマフォの値を0と1だけに限定しなければ、複数個ある資源も管理できます。たとえばプリンターが3台ある場合、セマフォの初期値を3にします。

1. 1つ目の処理がPすると値は2になります。
2. 2つ目で1、3つ目で0になります。
3. 4つ目の処理は、資源が返されるまで待ちます。
4. どれかの処理が印刷を終えてVすると値が1になり、待っていた処理が進めます。

セマフォの強さは、相互排除と資源数管理を、非常に小さな抽象概念で表せることです。

producer–consumer問題

EWD123では、セマフォの利用例としてproducer（生産者）とconsumer（消費者）の問題も扱われます。生産者はデータを作ってバッファへ入れ、消費者はバッファから取り出して処理します。ここには少なくとも二つの制約があります。

• バッファが空なら、消費者は取れない
• バッファが満杯なら、生産者は追加できない

さらに、同時にバッファ構造を書き換えると壊れるため、内部操作には相互排除も必要です。

現在の感覚でいえば、動画ストリーミング、ログ処理、メッセージキュー、ネットワーク通信など、作る側と使う側の速度が違う場面は無数にあります。

EWD123の例自体はパンチカードなど当時の機器を背景にしていますが、問題の抽象構造は現在にも残っています。

PとVは何の略？

ダイクストラの初期文書EWD51では、Vはオランダ語のverhogen（増やす）に由来し、PはProbeer te verlagen（減らすことを試みる）から作った造語prolagenに由来すると説明されています。

二つの不可分操作によって並行処理の同期を表現したことが、セマフォの核心です。

セマフォが全部を解決したわけではない

セマフォは強力ですが、使い方を誤ると別の問題を生みます。PしたあとVを忘れれば他の処理が永久に待ち、複数のセマフォを異なる順序で取得すれば、互いに相手が持つ資源を待ち続ける可能性があります。

同期プリミティブを得ても、並行処理の設計問題は残りました。次にダイクストラが向き合うのが、デッドロックです。

---

7．全員が待って、誰も進めない――デッドロック、銀行家アルゴリズム、食事する哲学者

2本の鍵を2人が取り合う

デッドロック（deadlock）とは、複数の処理が互いに必要な資源を待ち続け、誰も進めなくなる状態です。二人の作業員AとBがいて、作業には赤い鍵と青い鍵の両方が必要だとします。

1. Aが赤い鍵を取ります。
2. Bが青い鍵を取ります。
3. Aは青い鍵を待ち、Bは赤い鍵を待ちます。

互いに相手の鍵が返るのを待つため、二人とも作業を完了できず永久に停止します。コンピュータでは「鍵」がメモリ領域、ファイル、プリンター、テープ装置、ロックなどに置き換わります。

EWD123の「Deadly Embrace」

ダイクストラはEWD123で、この状態を「Deadly Embrace」と呼んで説明しました。直訳すれば「死の抱擁」のような表現です。現在はdeadlockという語が一般的ですが、当時は問題を表す語彙そのものが形成されている最中でした。

この時期の仕事からは、現代の教科書で当然のように並ぶ用語が、研究とともに整理されていく過程をたどれます。

Banker’s Algorithm――銀行員なら貸すか？

デッドロックを避ける方法として有名なのがBanker’s Algorithm、銀行家アルゴリズムです。銀行が顧客へ融資する場面を考えます。銀行が貸し出せる資金には上限があり、顧客は「最終的に最大いくら必要になるか」を事前に申告します。

銀行は、今1万円貸せるかどうかだけではなく、その1万円を貸したあとでも、全員が最終的に取引を完了できる安全な順序が残るかを考えます。貸した結果、将来全員があと少しずつ必要になり、誰にも追加融資できなくなるなら危険です。

安全状態と危険状態

簡単な例を考えます。資源が全部で10個あるとします。

• プロセスA：最大7個必要、現在5個保有
• プロセスB：最大5個必要、現在2個保有

現在7個が貸し出され、残り3個です。Aはあと2個で最大需要に達します。Aへ2個渡せば、Aは処理を完了して7個すべて返せると仮定します。すると残り1個だった資源が一気に8個になり、Bも完了できます。

このように「誰かを完了させ、その資源を回収し、次を完了させる」という安全な順序が存在するなら安全状態です。逆に、どのプロセスも完了に必要な追加資源を受け取れない状態へ進む貸し出しは避けます。資源を「持っているかどうか」だけでなく、未来の最大需要まで考えて安全性を判断するのが銀行家アルゴリズムの特徴です。

食事する哲学者問題

デッドロックを説明する古典的問題として、Dining Philosophers Problem（食事する哲学者問題）があります。円卓に5人の哲学者が座り、その間に5本のフォークがあります。一人が食事するには左右2本のフォークが必要です。

全員が同時に左側のフォークを取ると、全員が1本ずつ保持します。しかし2本目は隣の哲学者が持っているため、全員が右側のフォークを待ち続けます。フォークが返らず誰も食事を始められない、完全なデッドロックです。

名前は最初から「哲学者」ではなかった

ダイクストラはEWD1000で、1965年の授業の試験問題として「Dining Quintuple」と呼ぶ問題を出したと回想しています。後にTony Hoareが「Dining Philosophers」という現在有名な名称を与えたとされています。

現在ではOS教科書の定番問題ですが、研究者が教育用に考えた抽象問題が、その後何十年も使われる標準教材へ発展しました。

デッドロックを避ける考え方

食事する哲学者問題には多くの解法があります。

• すべての資源に共通の順序を定め、常にその順序で取得する
• 一度にテーブルへ入れる哲学者を制限する
• 2本そろうときだけ取得する
• 中央の調停者が許可する

並行処理では、個々の処理だけを見て正しくても、全体を組み合わせると停止する可能性があります。ダイクストラが繰り返し扱ったのは、この「局所的には合理的なのに、全体では破綻する」問題でした。

その解決には、システム全体を人間が理解できる形に構造化する必要があります。その壮大な実験が、THE Multiprogramming Systemです。

---

8．OSを「層」に分ける――THE Multiprogramming System

OS全体を一度に理解するのは無理

1962年、ダイクストラはEindhoven University of Technology（当時のTechnological University Eindhoven）へ移り、数学の教授になります。そこで彼のグループが取り組んだ大きなプロジェクトが、EL X8コンピュータ用のTHE Multiprogramming Systemです。THEはTechnische Hogeschool Eindhovenに由来する名称です。

これは、ダイクストラの思想を理解するうえで重要な仕事の一つです。THEシステムでは、「複雑なソフトウェアを、人間が理解可能な形にどう分割するか」を実際のOS設計で試しました。

限られた人数で、高度なシステムを作る

1968年の論文「The Structure of the ‘THE’-Multiprogramming System」で、ダイクストラは開発グループについて「6人が平均して半分程度の時間を使える」という限られた資源だったと説明しています。

そこで彼らは、単に機能を大量に詰め込むのではなく、システム設計という技術そのものから最大限学べるプロジェクトを選びました。

この論文に繰り返し出てくるのが、「構造」です。

速度を捨て、順序だけを見る

OSでは、CPU、磁気ドラム、プリンター、紙テープ装置など、速度の違う機器が同時に動きます。具体的な速度差を設計に利用したくなりますが、ダイクストラたちは論理的な正しさを考える際には速度比を捨て、各処理を「速度が未定義の逐次プロセス」として扱いました。

• データが作られる前に使われない
• 一つの機器へ同時に二つの仕事を割り当てない
• 必要な同期が明示される

といった論理的な関係です。プリンターが将来2倍速になってもプログラムの論理が壊れないよう、ハードウェアの具体的速度に依存しない設計を目指しました。ダイクストラは後年、当時は速度比を捨てること自体を批判されたと回想しています。

0から5までの階層

THEシステムは、厳密な階層構造を持っていました。

原論文ではおおむね次のように説明されています。

レベル	主な役割
0	プロセッサ割り当て、時計割り込み
1	セグメント制御、主記憶とドラム間の管理
2	メッセージ・インタプリタ、操作卓との対話
3	入出力ストリームのバッファリング、周辺機器
4	ユーザープログラム
5	オペレーター（システム外の人間）

重要なのは番号ではなく、上の層が下の層の細部を知らなくてよいことです。

「プロセッサを消す」抽象化

レベル0では、どのプロセスにCPUを割り当てるかを管理します。この層が正しくできれば、上位層は「実際に何個のプロセッサをどう共有しているか」を意識せずに済みます。ダイクストラの表現では、上位から見ると実際のプロセッサのアイデンティティが消えます。

この設計では、上位の問題を解くときに不要な情報を、見えなくすることが抽象化です。

「記憶装置を消す」抽象化

レベル1では、主記憶のページと磁気ドラム上のページを管理します。上位層は、情報がいま主記憶にあるのかドラムにあるのかを直接意識せず、「セグメント」という抽象単位として扱えます。レベル1を越えると、物理的な記憶ページの細部が見えなくなります。

「物理的なコンソールを消す」

レベル2では、オペレーターとの対話を扱います。物理的には一台のコンソールを複数の処理が共有しますが、上位層からは各処理が自分専用の対話手段を持つかのように扱えます。共有資源の物理的事情を下位層へ押し込み、上位層から隠す設計です。

周辺機器を論理的な通信単位へ

レベル3では入出力を扱い、上位のユーザープログラムが個々の紙テープ装置やプリンターの細部を意識しなくてよいようにします。

こうして一段ずつ具体的なハードウェア事情を消していき、レベル4のユーザープログラムは、はるかに単純な世界の上で動けます。

「全部をテストする」は不可能。でも各層なら？

一般的なOSには膨大な状態があります。割り込みの順序、入出力のタイミング、複数プロセスの状態などをすべて組み合わせると、全ケースの網羅は不可能です。

THEシステムでダイクストラたちは、レベル0を徹底的に確認してからレベル1を追加し、次にレベル2……と積み上げました。各段階で下位層を「すでに確立された抽象機械」として扱うことで、検討しなければならない状態数を人間が扱える規模へ抑えます。

原論文でダイクストラは、階層構造によって関連するテストケースを十分小さくし、見落としがないと確信できる形にすることを設計者の責任として論じています。

大規模になるほど、構造が重要になる

THEは比較的小規模な大学のシステムで、産業界からは「小さなプロジェクトだからできた」と見られることもあったようです。ダイクストラは逆に、プロジェクトが大きいほど構造化が必要になると考えました。

大規模になるほど、複雑さを隔離する設計が重要になるという主張は、後のソフトウェア工学全体にも響いていきます。

THEシステムがダイクストラを変えた

後年のEWD1308を読むと、THEの経験が構造化プログラミングへ直結したことが分かります。OSの規模を増やすと組み合わせの複雑さが急激に増えるため、最初から「一度に考えなくてよい構造」を作る発想へ進みました。

この考えが、OSから一般のプログラムへ広がっていきます。

---

9．1968年、「GOTO文は有害」――有名すぎる論争を原文から読み直す

GOTOとは何か

GOTOは、プログラムの実行位置を指定した場所へジャンプさせる命令です。

10: 入力する
    もし正しければ 30 へ行く
20: エラー表示
    10 へ行く
30: 次の処理

初期の言語や機械語では、ジャンプ命令は非常に自然です。CPU自身が条件分岐やジャンプを使って命令を実行するためです。

問題は、自由にジャンプできる仕組みを大規模プログラムで多用したときに起こります。

スパゲッティコード

数十個、数百個のGOTOが互いに飛び交うと、プログラムを上から下へ読んでも実行順序を追いにくくなります。読み手は次のような情報を常に追う必要があります。

• ここにはどこから来る可能性があるのか
• この変数はどの経路を通ったときの値なのか
• このラベルへ飛んだあと、どこへ戻るのか

制御線を図に描けば、麺が絡まったようになります。そこから「スパゲッティコード」という表現が使われるようになりました。

1968年の短い文章

1968年、Communications of the ACMにダイクストラの短い書簡「Go To Statement Considered Harmful」が掲載されました。この題名だけが独り歩きし、「ダイクストラ＝GOTOを嫌った人」というイメージが定着しましたが、原文の論点はもっと深いところにあります。

実は題名を付けたのはダイクストラではない

ダイクストラが提出した原稿EWD215の題名は「A Case against the GO TO Statement」でした。後年のEWD1308で本人は、Communications of the ACMの編集者だったNiklaus Wirthが、迅速に掲載するためLetter to the Editorへ変更し、その際に新しい題名を付けたと回想しています。

「X Considered Harmful」という題名はその後大量に模倣され、コンピュータ分野の定番表現になりました。ダイクストラ自身が考えた題名ではない言葉が、彼の「名言」のように残ったことになります。

ダイクストラが本当に問題にしたもの

EWD215の論点は、プログラムの実行過程を人間が追えるかどうかです。プログラムのテキストは静的ですが、実行は動的なプロセスであり、プログラマーが理解すべきなのは文字列そのものより、そのプログラムが作り出す計算過程です。

そこで重要になるのが、いま実行中のプロセスが、プログラムテキストのどこまで進んだ状態なのかを、人間が簡潔に把握できるかという問題です。

• 順次実行なら、「ここまで実行した」という位置で進行を表せます。
• ループなら、「何回目の反復か」という追加情報で表せます。
• 手続き呼び出しなら、呼び出し階層を追えます。

自由なGOTOが大量にあると、こうした簡単な座標で実行履歴を表現しにくくなります。GOTO批判は、人間が実行過程について推論する能力の問題だったのです。

「GOTOなしで書ける」だけでは不十分

1966年、Corrado BöhmとGiuseppe Jacopiniの結果により、一定の条件のもとで、任意のフローチャート的計算を順次・選択・反復の構造で表現できることが示されました。

これを「だからGOTOは不要」と説明することがあります。

しかしダイクストラ自身はEWD215で、任意のフローチャートを機械的にGOTOなしへ変換しても、元と同じくらい分かりにくいものができるなら意味がないと指摘しています。

構造化プログラミングの目的は、GOTOという文字を消すことではなく、プログラムの構造と実行過程の対応を人間が理解しやすくすることです。

現代言語にもジャンプは残っている

現在のプログラミング言語にも、break、continue、return、例外処理など、通常の逐次実行を途中で変える機能があります。低水準コードではジャンプ命令自体も普通に存在します。

GOTO批判の焦点は、自由なジャンプによって実行過程を追いにくくする制御構造でした。

ダイクストラの問題意識を現代的に読み替えるなら、制御の自由度を増やしたとき、それに見合うだけの理解可能性を保てるかという問いです。この問いは、非同期処理、コールバック、例外、並行処理など現代の複雑な制御でも生きています。

有名な論争は、本丸ではなかった

GOTO論争は目立ちますが、ダイクストラの研究全体から見ると一つの局面です。中心にあったのは、「人間の頭には限界がある」という認識でした。

1969年、彼はその問題を真正面から扱った『Notes on Structured Programming』を書きます。

---

10．構造化プログラミング――本当の敵は「人間が扱えない複雑さ」

1968年、ダイクストラ自身が行き詰まる

技術史を人物の人生から切り離さずに読むと、この時期は重要です。ダイクストラは後年のEWD1166やEWD1308で、1968年前後に深い抑うつ状態に陥ったと回想しています。大学内で自ら作り上げた研究グループが解体されたことなど、職場上の事情も重なりました。

本人は、自分が次に取り組む課題の大きさそのものに怯えていたと気づいたと回想しています。

その課題を彼は、How do we do difficult things?――「難しいことを、私たちはどうやって行うのか」という問いとして捉えました。最短経路、コンパイラ、並行処理、OS――それまでの大仕事が、より一般的な「困難をどう分解し、理解可能にするか」という問題へつながっていきます。

治療として書いた「Notes on Structured Programming」

ダイクストラは、ある意味で自分自身の治療としてEWD249「Notes on Structured Programming」を書いたと回想しています。1969年8月の文書で、当初は20部ほどを海外の友人へ送っただけでした。

ところがコピー機が普及し始めていた時代だったため、本人の知らないところでコピーのコピーが作られ、世界中へ広まります。後年、遠い場所で「5世代目、6世代目のコピー」を大切に持つ人に出会ったとも書いています。インターネットもPDFもない時代の「バイラル文書」でした。

章題から見える、本当の主題

EWD249の冒頭の章題を見ると、構造化プログラミングが単なるコーディング規則でないことが分かります。

• On our inability to do much――私たちは大したことを一度にはできない
• On our mental aids――頭を助ける道具が必要だ
• On understanding programs――プログラムを理解するとは何か

出発点にあるのは、GOTO文を使うかどうかよりも広い「人間が複雑なプログラムをどう理解するか」という問題です。

人間の頭は、コンピュータほど速くならない

コンピュータの性能は急速に上がり、メモリが増えればより大きなプログラムを、CPUが速くなればより複雑な処理を実行できるようになります。一方、人間の短期記憶や注意力には限界があります。

ハードウェアの性能向上によって「作れるもの」が大きくなるほど、人間の理解とのギャップは拡大します。

抽象化――細部を忘れる技術

複雑さに対する最強の道具の一つが抽象化です。

たとえば車を運転するときは、燃料噴射の制御プログラムや変速機内部を意識せず、「アクセルを踏めば加速する」という抽象的インターフェースで扱います。

プログラミングでも同じです。ある処理を手続きや関数としてまとめ、上位からは「この入力を渡せば、この結果を返す」という約束だけを見ます。中身の細部を一時的に忘れられるため、考える対象を減らせます。

正しく設計された抽象化は、人間の有限な頭を守るための技術です。

階層化――一段ずつ考える

THEシステムでも見たように、階層化すると、考えるレベルに必要な情報だけを扱えます。

構造化プログラミングでも、大きな問題を小さな部分へ分け、一段ずつ精密化していく考えが重視されます。最初から数千行の命令を書き始めるのではなく、まず「何を達成したいか」を高いレベルで書き、それを具体的な部分問題へ分け、さらに精密化していきます。

こうして、常に人間が扱える範囲の問題だけを見ます。

「順次・選択・反復」だけが構造化プログラミングではない

教科書では構造化プログラミングを、次の三つの制御構造で説明することがあります。

• 順次
• 選択
• 反復

これは有用な入門説明ですが、ダイクストラのEWD249全体をそれだけに縮めると重要な部分が抜け落ちます。

• プログラムと実行過程の対応
• 正しさをどう論証するか
• 抽象化
• 階層化
• 段階的な精密化
• 人間の認知能力の限界

まで含んでいました。

構造化プログラミングの核心は、プログラムを人間が推論できる構造へ組み立てる方法論にあります。

ソフトウェア危機という時代背景

1968年、NATOの会議などを通して「software engineering」という言葉が広まり、いわゆるソフトウェア危機が強く意識されます。

ハードウェアが進歩し、より大きなソフトウェアが求められる一方、開発は遅れ、予算を超え、バグが増え、保守が困難になる。

必要だったのは、プログラマーの入力速度ではなく設計方法そのものでした。

ダイクストラは後年EWD1284で、1968年のNATO会議を、ソフトウェア危機が公に認識され、プログラミング自体が学問的関心の対象になりうる転換点として振り返っています。

プログラムは、完成してから直すものなのか

構造化によって、プログラムは理解しやすくなります。ダイクストラの関心はさらに、理解しやすいプログラムを作ってテストで誤りを直す方法から、正しさの理由とともにプログラムを構成する方法へ進みました。

正しさの理由と一緒にプログラムを作ることが目標となり、この考えが1970年代の形式手法へつながります。

---

11．1972年チューリング賞――なぜ「ダイクストラ法」ではなく、プログラミング思想が評価されたのか

コンピュータ科学最高峰の賞

1972年、ダイクストラはACM A.M. Turing Awardを受賞しました。チューリング賞は、コンピュータ科学における最も権威ある賞として知られます。受賞理由の核心には、プログラミングを高度な知的・数学的活動として扱い、プログラムを正しく構成する方法を探究したことがありました。

『The Humble Programmer』

受賞講演の題名は『The Humble Programmer（謙虚なプログラマー）』です。題名の「謙虚」は、人間の知的能力の限界を認める姿勢を指します。

コンピュータは非常に高速で膨大な処理を実行できますが、人間の知的能力には厳しい限界があります。巨大な複雑さを頭の中だけで管理しようとせず、複雑さを避け、構造を作り、証明可能な形へ変える必要がある。この思想が「humble」という言葉に込められています。

「テストはバグの存在を示せるが、不在を示せない」

ダイクストラに関連して最も有名な言葉の一つに、テストはバグの存在を示すのには有効だが、バグが存在しないことを示すには不十分だ、という趣旨の主張があります。100万ケースをテストして全部通っても100万1番目の入力で壊れる可能性は残り、並行処理ではめったに起きない命令順序でだけ壊れることもあります。

彼が問題にしたのは、「テストを大量にやれば、それだけで数学的な意味の正しさが保証される」と考えることでした。

「デバッグする」から「構成する」へ

1. とりあえずコードを書く
2. 動かす
3. バグを見つける
4. 直す
5. また動かす

ダイクストラは、この「code first, debug later」の発想を強く警戒しました。

後年のEWD1303でも、世の中がなお「Think first, code later」より「Code first, debug later」に傾いていることを残念がっています。

彼が目指したのは、仕様と論理からプログラムを組み立て、正しさの根拠が設計に埋め込まれている状態です。

チューリング賞までの物語を振り返る

受賞理由は、それまでの歩みに表れています。

• プログラマーという職業さえ曖昧だった1950年代に、完成前の機械のためにプログラムを書いた
• 最短経路のような明快なアルゴリズムを設計した
• ALGOL 60コンパイラで高度な言語を実装した
• 割り込みと並行処理の難しさを経験し、セマフォ、相互排除、デッドロックを整理した
• THEシステムで階層化と抽象化を実践した
• GOTO論争と構造化プログラミングを通して、複雑なプログラムを人間が理解する方法を追究した

ダイクストラは個々の問題を解くだけでなく、「プログラムを書くとは、そもそもどのような知的活動なのか」を学問として扱いました。ここが「最短経路の人」だけでは説明できない最大の理由です。

---

12．「正しいプログラム」を数学から作れるか――最弱事前条件とGuarded Commands

正しいとは何かを、先に書く

1970年代、ダイクストラの研究はさらに形式的になります。専門的に見えますが、考え方は意外に直感的です。

プログラムを書く前に、最終的に何が成り立っていれば成功なのかを決めます。これを事後条件（postcondition）と考え、その結果を必ず得るには開始前に何が成り立っている必要があるかを逆算します。

最も簡単な例

x := x + 1

この処理後にx > 10を必ず成立させたいとします。1増やしたあと10より大きければよいので、処理前には次の条件が必要です。

x > 9

望む結果から実行前の条件を逆算する、これが基本的な考え方です。

weakest precondition――「必要以上に厳しくない条件」

事前条件は、厳しくしようと思えばいくらでも厳しくできます。たとえば先ほどの例でx > 100なら、処理後にx > 10となることは確実です。しかし、それでは実行できる入力を不必要に狭めています。

本当に知りたいのは、結果を保証できる最も弱い、つまり最も制限の少ない事前条件です。これがweakest precondition、最弱事前条件です。

ダイクストラはwp(S, R)という形で、処理Sを実行した結果、事後条件Rを満たすための最弱事前条件を扱いました。

代入を逆向きに読む

y := x + 3

の実行後にy < 10を満たしたいとします。代入後のyはx + 3なので、必要な事前条件は次のように逆算できます。

x + 3 < 10

したがって、

x < 7

です。プログラムを実行して答えを見るのではなく、望む答えから逆向きに必要条件を導きます。

「最大値を求めるプログラム」を仕様から作る

1975年の論文EWD472「Guarded commands, non-determinacy and formal derivation of programs」には、xとyの最大値をmへ入れる非常に小さな例があります。最終条件は概念的に次の三つです。

• mはxかyのどちらか
• mはx以上
• mはy以上

m := xでこの条件を満たすにはx ≥ yが必要です。同様にm := yなら、必要条件はy ≥ xです。

if x ≥ y -> m := x
[] y ≥ x -> m := y
fi

という形が自然に導かれます。仕様から、正しさを保ったままプログラムを導いていくことが、ダイクストラの目指した方向です。

Guarded Commandとは

guarded commandは、条件（guard）と処理を組み合わせたものです。

条件 -> 処理

条件が成立している処理だけが実行候補になり、複数のguardが同時に成立する場合は、どれを選んでも正しい結果になるよう設計できます。ここに非決定性（non-determinacy）が入ります。

「実行順序が一つに決まらない」を恐れない

普通は「同じ入力なら同じ命令順で動く方が分かりやすい」と感じます。実際ダイクストラ自身も、非再現な挙動は機械故障の兆候だと考えていた時代があり、非決定的プログラムに心理的抵抗があったとEWD472で告白しています。

しかし、仕様上どの選択でも正しいなら、実装前の設計段階では選択を固定しない方が簡潔になる場合があります。「どちらを選ぶべきか」を早すぎる段階で決めず、必要な正しさだけを先に確保する。これも抽象化の一種です。

正当性証明は、数学者だけの趣味なのか

完全な形式証明が必要になる場面は限られますが、その考え方は現代のソフトウェア設計にも残っています。

• 関数が受け取ってよい入力条件を明確にする
• 戻り値が満たす条件を定義する
• 不変条件を保つ
• 型によって不正な状態を表現しにくくする
• 契約や仕様から実装を考える
• 重要システムでモデル検査や証明を利用する

「とりあえず動かしてから考える」の反対側にある文化です。

1976年『A Discipline of Programming』

ダイクストラは1976年に『A Discipline of Programming』を刊行します。題名どおり、プログラミングを「discipline」、規律ある学問的活動として扱う本です。彼自身、出版社向けの説明でautomatic computerのprogrammingをscientific disciplineとして扱うと述べ、正当性証明とプログラム導出を中心に置きました。

最短経路アルゴリズムを一つ発明することから始まった研究者が、20年後には「正しいプログラムを生み出すための計算体系」そのものを考えるところまで進んでいました。

---

13．「壊れたら直す」ではなく「勝手に正常へ戻る」――自己安定化という新しい発想

分散システムでは、全体を見張る司令塔がいない

1970年代、ダイクストラの関心は分散システムへ広がります。複数のコンピュータや処理主体が通信しながら動く分散システムでは、中央管理者が全体を把握しない構成もあり、さらに難しい問題が現れます。

• 各ノードが知るのは近くの状態だけ
• メッセージが遅れることがある
• 一部の内部状態が誤ることがある
• システム全体を簡単には再起動できない場合がある

こうした環境で、一時的障害によって内部状態が壊れたあと、誰かが外から修理しなくてもシステム自身が正しい状態へ戻れるか――これが自己安定化の問いです。

1974年、わずか2ページの論文

ダイクストラは1974年、「Self-stabilizing systems in spite of distributed control」をCommunications of the ACMに発表しました。掲載ページは643–644のわずか2ページです。

論文の要旨は非常に野心的で、疎に接続された分散制御システムでも、各ノードの局所的な規則だけによって有限回のステップのうちにシステム全体を望ましい状態へ収束させられると示しました。これが自己安定化（self-stabilization）です。

「正しい状態を保つ」だけでは足りない

通常の正当性議論では、次のように不変条件を保つことを考えます。

1. 最初は正しい状態にある
2. 各処理が規則を守る
3. だから正しい状態が保たれる

しかし現実には、メモリエラー、通信障害、電源異常、ソフトウェアの一時的誤動作などによって前提そのものが壊れることがあります。一度不正状態へ入ると、正しい規則に従い続けても戻れないシステムもあります。

自己安定化では、どんな初期状態から始まってもやがて正しい状態へ入り、その後は正しさを保つことまで要求します。

トークンが一つだけ回る世界

直感的な例として、リング状につながった複数ノードを考えます。各ノードが参照できるのは隣接ノードだけで、理想状態では「いま操作する権利」を表すトークンが一つだけ存在し、それが順番に回ります。

ところが障害によって、次のような不正状態になることがあります。

• トークンが複数あるような状態
• トークンがないように見える状態
• 各ノードの内部値がばらばら

自己安定化アルゴリズムでは、中央管理者が全状態を初期化する代わりに、各ノードが隣の状態を見て局所規則に従うだけで、一定時間後に「正しいトークンが一つだけ循環する状態」へ収束させます。

なぜ「自己修復」なのか

自己安定化のすごさは、正常状態そのものだけでなく、正常状態へ戻る能力をアルゴリズムの性質として持たせることです。

人間社会にたとえるなら、秩序を維持する規則だけでなく、何らかの理由で全員が規則違反状態に陥っても、各人が近隣との単純なルールを守り始めれば社会全体が再び秩序へ収束する仕組みを設計するようなものです。

当初はほとんど注目されなかった

この仕事に対する発表直後の注目は限定的でした。ダイクストラは後年、自己安定化の仕事が長いあいだ十分に注目されず、1980年代になってLeslie Lamportらが重要性を認識したことで研究が広がったと振り返っています。

現在では自己安定化は分散アルゴリズムの一分野として確立しています。2002年にはこの1974年論文がPODC Influential Paper Awardを受賞し、翌2003年から同賞はEdsger W. Dijkstra Prize in Distributed Computingへ改称されました。

1956年の最短経路と1974年の自己安定化を比べる

1956年の最短経路問題は、次のような比較的静的な世界でした。

• グラフ全体が与えられている
• 始点が決まっている
• 辺の重みが分かっている
• 一つのアルゴリズムが全体を計算する

一方、自己安定化が扱うのは次のような世界です。

• 複数主体が独立に動く
• 全体を知る主体がいない
• 状態が壊れている可能性がある
• 局所規則だけで全体性質を生み出す

ダイクストラの研究は、単なる「経路計算の人」では説明できないところまで広がっていました。

それでも主題は同じ

一見すると、最短経路、OS、構造化プログラミング、自己安定化はばらばらです。

しかし共通するものがあります。

• 局所的な規則
• 明確な不変条件
• 抽象化
• 単純な構造
• 数学的に追える推論

によって、巨大な状態空間を扱えるようにする。

対象は変わっても、中心にある問題は「複雑さ」です。

---

14．ダイクストラという研究者――万年筆、手書きEWD、Tuesday Afternoon Club

「EWD123」のEWDとは何か

EWDはEdsger W. Dijkstraの頭文字で、ダイクストラは長年、自分の技術メモ、論考、講演原稿、旅行記、手紙、教育資料などに連番を付けて配布していました。EWD123、EWD249、EWD1308といった番号は、その連番です。

これらは現在「EWD Manuscripts」と呼ばれ、University of Texas at AustinのDijkstra Archiveに大量に保存されています。1,000点を大きく超える文書があり、研究者としての思考の変化を数十年単位で追える稀有な資料群です。

論文になる前の思考まで残っている

普通、歴史上の研究者を調べるときに読めるのは完成した論文や著書が中心ですが、EWDには次のような資料まで残っています。

• 未完成の考察
• 友人への手紙
• 研究会で配ったメモ
• 旅行後の報告
• 講義資料
• 自分の過去への評価

そのため、ダイクストラについては「この論文を発表した」だけでなく、「発表前後に本人が何を悩んでいたのか」までかなり詳しく追えます。

タイプライターの達人が、手書きへ戻る

ダイクストラは若いころから自分でタイプすることを重視していました。EWD1000によれば、1962年にEindhovenへ移る際、新任教授として希望を聞かれ、特殊文字を備えた電動タイプライターを求めて周囲を驚かせたといいます。当時は教授本人がタイプすること自体が珍しかったためです。

ところが後年、彼は手書きの文書を多数作るようになります。EWD1000では、技術文章を書く時間の大半は指を動かす時間ではなく考える時間なので、入力速度を上げても本質的な生産性はあまり変わらないという趣旨の説明をしています。

「タイピングが速ければ論文が速く書ける」という発想自体を疑い、「本当のボトルネックはどこか」を見ようとしたのです。

万年筆で書かれたコンピュータ科学

ダイクストラの手書き文書は非常に整った筆跡で知られます。コンピュータ科学の最先端を扱う研究者が、万年筆で紙に数式と文章を書き、それをコピーして同僚へ送っていました。CWIの紹介によると、その筆跡をもとに「Dijkstra」というフォントまで作られたほどです。

彼にとって文章を書くことは、研究報告であると同時に、考える作業そのものでした。

Tuesday Afternoon Club

Eindhoven時代、火曜日の午後にはTuesday Afternoon Clubという研究会が開かれました。EWD683「To a new member of The Tuesday Afternoon Club」で、ダイクストラは目的を二つ挙げています。

• 自分たちの関心領域が狭くならないよう、計算機科学の重要な進展を追う
• 他人の論文や報告書を読み、評価し、重要そうな問題を一緒に考えることで、研究を行う技術そのものを鍛える

論文を「一文ずつ」読む

David Griesの追悼文には、この研究会の異常なほど丁寧な読み方が記されています。論文を声に出して一文ずつ読み、次の点まで改善できるかを議論したといいます。

• 文の構造
• 言葉遣い
• 全体構成
• 証明
• 技術内容

曖昧な文章は曖昧な思考を生み、記法が悪ければ問題自体が見えにくくなります。ダイクストラにとって、文章・記法・証明・プログラム設計は一つの思考過程として結びついていました。

書き方への厳しさ

彼は簡潔な文章を好み、不要な複雑さを嫌いました。CWIはダイクストラの文章を、conciseness、economy of argument、clarity of expositionで特徴づけています。難しい並行処理の話でも、驚くほど少ない数式と平易な文章で説明することがありました。

この厳しさは他人にも向けられ、同僚の研究や新しい流行に対して非常に辛辣な評価をすることもありました。現在でも引用される挑発的な発言が多くありますが、「毒舌な天才」だけに単純化すると、彼の研究姿勢を捉え損ねます。

彼が強く嫌ったのは、「考えていないのに流行だから採用する」「複雑さを技術力の証明のように扱う」「明確に説明できないものを曖昧な言葉で押し切る」といった態度でした。

考えてから話す人

David Griesは追悼文で、質問をするとダイクストラが1～2分黙り、相手が不安になるほど待ったあと、よく考えられた答えを返したことを回想しています。「すぐ答える」ことより「考えてから答える」ことを優先したのです。

高速なコンピュータを研究した人が、自分自身の思考では速度を競わなかったというのは象徴的です。

Burroughsの「世界最小の研究組織」

1973年、ダイクストラはBurroughs CorporationのResearch Fellowになります。オランダ・Nuenenの自宅で研究し、必要に応じて世界各地を訪問しました。本人は自宅2階の書斎を、「世界で最も小さなBurroughsの研究組織」と表現しています。

企業からかなり自由な研究環境を与えられ、Eindhoven大学との関係も持ちながら、プログラミング方法論や数学的証明を深めていきました。

1984年、テキサスへ

1984年、ダイクストラはUniversity of Texas at Austinへ移り、Schlumberger Centennial Chair in Computer Sciencesを務めます。AustinでもTuesday Afternoon Clubの文化は続き、晩年になるにつれて教育や数学的証明の表現への関心がさらに強くなりました。

写真に残るダイクストラは、黒板の前で説明する教師の姿です。

アルゴリズムの発明者というより、「どう考えれば難しいものを簡潔に扱えるか」を教える人物へ変化していきました。

「コンピュータ科学はコンピュータについての学問ではない」

ダイクストラに帰される有名な考え方の一つが、コンピュータ科学とコンピュータの関係を、天文学と望遠鏡の関係になぞらえるものです。

この言い回しの正確な出典の扱いには注意が必要ですが、Tony Hoareも2010年のDijkstra Memorial Lectureで、ダイクストラがコンピュータそのものよりプログラムを科学的対象として研究したことを強調しています。

ダイクストラは、「計算」「プログラム」「正しさ」「並行性」「分散」「抽象化」といった、機械が変わっても残る構造を研究していました。

---

15．晩年のダイクストラは、若い自分をどう振り返ったのか

歴史家ではない、と自分で断る

晩年のダイクストラは、自分の初期研究を振り返る文書をいくつか残しました。

• EWD1303「My recollections of operating system design」
• EWD1308「What led to ‘Notes on Structured Programming’」

EWD1308の冒頭で彼は、これは記憶に基づく歴史的ノートであり、自分の記憶は選択的なので「専門の歴史家の客観性」を主張しない、と明記しています。本人の回想は貴重な一次資料ですが、何十年も後の記憶でもあるため、当時の論文と後年の回想を区別して読む必要があります。

初期の自分を「保守的なプログラマー」と評する

EWD1308で、1950年代の自分を振り返ったダイクストラは、EDSACで学んだ方式をARRA、FERTA、ARMAC、X1へかなり踏襲したことから、自分を「conservative programmer」と評しています。

後世から見ると革新的な人物ですが、本人は初期の自分を「conservative programmer」と捉えていました。既存のよい仕組みを慎重に使いながら、現実の難問にぶつかるたびに考え方を変えていった人物です。

リアルタイム割り込みが「安心」を壊した

初期のプログラムでは、機械が順番に命令を実行するので、誤りがあっても比較的再現しやすい一方、リアルタイム割り込みが入ると、外部イベントの発生時点によって命令の組み合わせが変わります。ダイクストラは、この経験によって従来の「動かしてデバッグする」という安心感を失いました。

EWD1303では、割り込みのタイミングに依存する非再現性への恐怖が、THEシステムでバグを作らないよう慎重に設計する動機になったと述べています。デバッグでは勝てないと恐れたから、デバッグへ依存しない構造を作ろうとした。この逆説は、ダイクストラの人物像をよく表しています。

自分が数学を避けていたことまで認める

形式手法の代表者となったダイクストラ自身も、初期にはプログラムを扱うための本格的な数学を自分で作ることを避けていた、とEWD1308で振り返っています。Floyd、Hoare、Kingらの仕事から刺激を受け、徐々にプログラムの正しさを数学的に扱う方向へ進みました。

形式的計算への考え方は研究人生の中で形成されたもので、本人も「自分も理解するのが遅かった」と率直に書いています。

間違いを認める研究者

EWD764では、Hoareの最初のプログラム正当性証明を見たとき、記号だらけの「ballet of symbols」は自分の好みではないと強く反発したものの、数年後には自分自身がそのバレエを踊っていた、と回想しています。

ダイクストラは意見の強い人物でしたが、証拠や理解によって考えを変えることもありました。「昔からすべてを見通していた天才」という物語より、研究者としてはるかに面白い姿です。

1999年退職、2002年死去

University of Texas at Austinの公式追悼によると、ダイクストラは1984年から1999年までSchlumberger Centennial Chairを務め、1999年にProfessor Emeritusとなりました。2002年8月6日、長いがん闘病の末、オランダ・Nuenenの自宅で72歳で死去しました。最晩年までEWD文書を書き続けています。

彼が亡くなった時点で、コンピュータ世界は1952年とは完全に変わっていました。プログラマーは世界中に存在し、インターネットが普及し、PCが家庭に入り、OSやコンパイラは巨大産業の基盤になっていました。

一方、彼が半世紀前から警告していた「複雑なソフトウェアを人間がどう理解するのか」という問題は、むしろさらに大きくなっていました。

---

16．まだある重要業績――Shunting-yard、並行ガベージコレクション、終了検出、Smoothsort

ダイクストラの業績には、1961年の数式構文解析、1970年代末にC. S. Scholtenと研究した分散計算の終了検出、複数の研究者と取り組んだ並行ガベージコレクション、1981年のSmoothsortもあります。

いずれも「ダイクストラ法」「セマフォ」「GOTO」ほど一般的な知名度は低いものの、ダイクストラが広い範囲で「複雑な順序や状態を、小さな規則で管理する問題」を扱っていたことが分かります。

人間には簡単な「3 + 4 × 2」が、機械には難しい

私たちは3 + 4 × 2を見れば、掛け算を先にして11と計算します。ではコンピュータが左から3、+、4、×、2と文字を受け取ったときは、どう処理すればよいのでしょうか。単純に左から計算すると3+4=7、7×2=14となり、結果を誤ります。

• 演算子の優先順位
• 括弧
• 左結合・右結合
• まだ実行してはいけない演算子の一時保存

といった要素を扱います。これはコンパイラが式を理解するための基本問題です。

操車場のように演算子を待避させる

ダイクストラが1961年のMathematisch Centrum報告で記述した方法は、後にShunting-yard algorithmと呼ばれるようになりました。shunting yardは鉄道の操車場で、貨車をいったん側線へ入れて順序を組み替えるように、入力された数値と演算子を出力列と一時スタックの間で動かします。

3 + 4 × 2を後置記法へ直すと3 4 2 × +になります。後置記法では演算順序が式の並びに埋め込まれるため、優先順位を別に管理せず処理できます。

1. 3を積みます。
2. 4を積みます。
3. 2を積みます。
4. ×が来たら4×2=8を計算します。
5. +が来たら3+8=11を計算します。

この処理でもスタックが働きます。演算子をすぐ出力してよいか、それともより優先順位の高い演算を先に処理するため待たせるかを、スタックで管理します。

これも「順序の複雑さ」を小さな規則へ変える仕事

Shunting-yardは最短経路やセマフォとは別分野に見えますが、発想には共通点があります。人間が式全体を眺めて直感的に判断している優先順位を、次の少数の要素へ分解します。

• 入力
• 出力
• 演算子スタック
• 優先順位比較

式が大きくなっても、機械は局所的な判断を一つずつ繰り返せば処理できます。「全体を頭の中で抱えず、小さな状態と規則に落とす」というダイクストラらしい仕事です。

分散システムでは「終わった」ことすら分からない

次は、さらに直感に反する問題です。一台のプログラムなら、最後の命令が終われば「処理終了」と判断できます。では、ネットワーク上の多数のコンピュータが互いに仕事を渡し合っている場合はどうでしょうか。

1. AがBへ仕事を依頼します。
2. BがCとDへ仕事を分けます。
3. CがEへ追加作業を頼みます。

ある時点でA自身が何もしていなくても、遠くのEが計算中の可能性があります。さらに、ネットワーク上には未到着のメッセージが残っている可能性もあります。

全ノードをある瞬間に止めて確認できないため、分散した計算全体が本当に終わったことを、誰がどう判断するのかが問題になります。

diffusing computation

ダイクストラとC. S. Scholtenは、仕事がネットワークへ拡散していく計算をdiffusing computationと呼びました。一つの起点が仕事を始め、受け取ったノードがさらに隣へ仕事を委任します。やがて全ノードが何もせず、途中のメッセージもなくなれば計算終了です。

起点が直接取得できる情報は局所的なので、通常の仕事メッセージとは逆向きに完了を知らせるsignalを返す仕組みを重ねます。各辺で「送った仕事の数」と「返ってきた完了信号」の差を管理し、仕事の依存関係が木のように収束していくことを利用して、起点が早すぎず遅すぎず終了を検出できるようにします。

この研究は1979年のEWD文書を経て、1980年にInformation Processing Lettersへ掲載され、今日ではDijkstra–Scholten termination detection algorithmとして知られます。

「停止している」と「終了した」は違う

分散システムで全体の終了を判断するには、個々のノードが静止していることに加えて、通信中のメッセージまで把握する必要があります。

たとえばBが何もしていなくても、Bへ向かう新しい仕事メッセージがネットワーク上にある可能性があります。

全ノードが一時的に待っているだけで、別のメッセージ到着後に再開する可能性もあります。

この「局所的な静止」と「大域的な終了」の違いは、自己安定化と同じく、局所情報から全体性質をどう導くかという問題です。

動いている最中に「不要メモリ」を回収する――On-the-fly garbage collection

もう一つ、ダイクストラの並行処理研究の成熟を示す仕事があります。1970年代半ばにLeslie Lamport、A. J. Martin、C. S. Scholten、E. F. M. Steffensと取り組んだ、on-the-fly garbage collectionです。最終的な論文は1978年のCommunications of the ACMに掲載されました。

ガベージコレクションとは、プログラムが確保したメモリのうち、もうどこからも参照されなくなった領域を見つけて再利用可能にする仕組みです。単純な方式なら、いったん本来の計算を止め、どのデータが生きているかを調べ、不要なものを回収すればよいでしょう。

しかし、大きなシステムで毎回すべてを止めるのは都合が悪い。そこで彼らが挑んだのは、プログラム本体がデータを変更し続けている横で、別の処理が同時に不要データを探すという問題でした。

回収側が「このデータは参照されていない」と判断した直後に、本体側がそこへ新しい参照を作る可能性があります。逆に、本体側が構造を変更している途中を回収側が観察すれば、本当は生きているデータを誤ってゴミと判断する可能性があります。

論文では、データを白・灰・黒のような色で分類し、探索が進むにつれて状態を変えていく方法を使います。中心問題は、互いに独立して進む二つの処理が、共有データを頻繁に変更するにもかかわらず、強い排他制御で全部を止めずに正しさを保てるかという点です。

この研究の過程自体も、ダイクストラらしいエピソードを残しています。初期案EWD492を書いた後、次のTuesday Afternoon Clubで正当性を証明しようとするとバグが見つかりました。EWD500では、その誤りを認めたうえで、並行処理の細かな割り込み順序が意図した不変条件を破ることを説明しています。完成形へ至るまで修正を重ねました。

これは「天才が一度で正しいアルゴリズムを思いついた」という物語の反対です。

解を考える → 正しさを証明しようとする → 証明できない箇所からバグを見つける → 設計を直す。

ダイクストラが主張した「正しさを設計の中心に置く」という態度が、共同研究の実際でも働いていたことが分かります。

ほぼ整列済みなら速くなる――1981年のSmoothsort

ダイクストラは並行処理や形式手法に加え、1981年にはHeapsortを発展させたSmoothsortという整列アルゴリズムも設計しました。

通常のHeapsortは最悪の場合でも効率よく動き、入力の整列度による性能差は小さいアルゴリズムです。

• 最悪の場合はおおむねN log N
• すでに整列しているような最良の場合はN
• その中間では入力の乱れ具合に応じて滑らかに性能が変わる

という性質です。本人は、この滑らかな移行が名前の由来だと説明しています。

Smoothsortは実装も説明も複雑です。Leonardo numbersと呼ばれる数列に基づく木の集合を利用し、Heapsortとは異なる形でヒープ構造を維持するため、初心者向けの最初の教材には不向きです。

ダイクストラは1970年代に「プログラムの正しさをどう導くか」という抽象的な研究を深めた後も、実際のアルゴリズム設計へ戻り、入力の構造を利用しながら最悪時の保証も失わないという具体的な問題を考えていたからです。

さらにEWD796aの末尾では、Carel ScholtenやTuesday Afternoon Clubのメンバーとの議論によって、アルゴリズムのコードだけでなく「どう提示すれば理解できるか」まで改善したことを記しています。解そのものと説明方法を一体として扱っていたことが分かります。

ダイクストラにとって、優れたアルゴリズムとは単に計算量が良いだけではなく、なぜ正しいのか、なぜその構造なのかを人間が追える形で提示できることまで含んでいたと読めます。

1956年から1981年まで、問いがどんどん大きくなる

年代を並べると、ダイクストラの研究対象の広がりが分かります。

• 1956年――一つのグラフ上で最短経路を求める
• 1960年――一つのプログラムの再帰呼び出しを管理する
• 1961年――数式の演算順序を機械的に整理する
• 1960年代半ば――複数の処理を安全に協調させる
• 1968年――OS全体を階層化する
• 1969年――巨大プログラムを人間が理解する方法を考える
• 1970年代――仕様から正しいプログラムを導く
• 1974年――壊れた分散システムを自律回復させる
• 1975～78年――計算を止めずに不要メモリを回収する並行処理を設計する
• 1979年――ネットワークへ拡散した計算が本当に終わったことを検出する
• 1981年――入力の整列度を利用するSmoothsortを設計する

問題の規模は「一つの経路」から「多数の独立主体からなる分散世界」へ広がりましたが、方法論は驚くほど一貫しています。適切な抽象化を選び、状態を最小限にし、不変条件を見つけ、局所的に追える規則で大域的な性質を保証する。

---

17．ダイクストラの功績を、分野別にもう一度整理する

1．最短経路アルゴリズム

現在「ダイクストラ法」と呼ばれる、非負重みのグラフにおける単一始点最短経路アルゴリズムを1956年に考案し、1959年に発表しました。

アルゴリズム教育の基本例となり、経路探索研究の重要な基礎になりました。

2．最小全域木問題へのアルゴリズム

1959年の同じ論文で、グラフの全頂点を最小コストで接続する問題も扱いました。

本人はX1の配線で銅線量を減らす問題との関係を回想しています。

3．ALGOL 60コンパイラ

Jaap ZonneveldとともにElectrologica X1用ALGOL 60コンパイラを開発し、1960年に稼働させました。CWIは世界最初のALGOL 60コンパイラと位置づけています。

4．再帰実装とスタックの普及

ALGOL 60の再帰的手続き呼び出しを実現するための仕組みを研究し、1960年の「Recursive Programming」でstackという語を使って実装の本質を説明しました。

5．相互排除問題

複数プロセスが共有資源を安全に使うためのmutual exclusionを、抽象的な並行プログラミング問題として明確化しました。

6．セマフォ

P操作とV操作を持つsemaphoreを導入し、相互排除、同期、producer–consumerなどを表現する基本プリミティブを示しました。

7．デッドロックとBanker’s Algorithm

複数プロセスが資源を待ち合って停止する問題を整理し、安全状態を保ちながら資源を割り当てるBanker’s Algorithmを示しました。

8．食事する哲学者問題の原型

1965年の試験問題としてDining Quintupleを使い、後にDining Philosophersとして並行処理教育の古典的問題になりました。

9．THE Multiprogramming System

OSを階層的な抽象化レベルへ分け、複雑なシステムを一段ずつ設計・検証する方法を実践しました。

10．GOTO批判

1968年のEWD215で、無制限のGOTOがプログラムの動的な実行過程を人間に追いにくくする問題を論じました。

11．構造化プログラミング

1969年のEWD249などで、プログラムを理解・証明可能にするための構造化、抽象化、段階的精密化を追究しました。

12．プログラミング方法論の学問化

プログラミングを「試行錯誤の技能」ではなく、数学的に扱える知的活動として位置づけることに大きく貢献しました。

13．最弱事前条件とpredicate transformer

処理後に望む条件から、処理前に必要な最弱条件を逆算する方法を体系化しました。

14．Guarded Commands

条件付き処理を非決定性も含めて形式的に扱い、仕様から正しいプログラムを導出する計算体系を発展させました。

15．自己安定化

任意の不正状態から有限時間で正しい状態へ収束する分散システムという概念を1974年に提示し、後の大きな研究分野を生みました。

16．On-the-fly garbage collection

Lamport、Martin、Scholten、Steffensとの共同研究で、計算本体と並行してメモリ回収を進める問題に取り組みました。弱い同期条件のもとで共有データを安全に扱う、細粒度並行処理の代表的研究です。

17．Dijkstra–Scholten終了検出

分散したdiffusing computationについて、局所的な完了信号を集約し、全体の終了を検出する方法をScholtenと示しました。

18．Smoothsort

1981年、ほぼ整列済みの入力では線形時間に近づき、最悪時にはN log Nを保つin-situ整列アルゴリズムSmoothsortを設計しました。

19．教育・研究方法論

Tuesday Afternoon Clubや大量のEWD文書を通して、プログラムだけでなく、論文の書き方、証明、記法、問題設定、研究の進め方そのものへ影響を与えました。

こうして並べると、ダイクストラが「一発の大発明をした人」ではないことがはっきりします。

アルゴリズム、言語処理、OS、並行処理、分散処理、ソフトウェア工学、形式手法、教育――コンピュータ科学の複数の基礎領域にまたがっています。

---

18．なぜ一人の人物が、これほど多くの分野に関われたのか

1950年代だからできた、だけではない

1950年代は現在ほど専門分野が細分化されておらず、一人の研究者が広く関われる時代でした。その中でもダイクストラがアルゴリズムからOS、形式手法、分散処理まで大きな足跡を残せた背景には、仕事に共通する方法があります。

具体的な機械から、抽象問題を取り出す

ダイクストラは、具体的な問題から一般化できる構造を切り出しました。

• ARMACの実演から最短経路問題を取り出す
• OSの資源競合から相互排除問題を取り出す
• 複数装置の停止からDeadly Embraceを取り出す
• 巨大OSから階層化という構造を取り出す
• GOTOだらけのコードから、人間が実行過程を追跡できるかという問題を取り出す
• 分散システムの障害から自己安定化という性質を取り出す

毎回、「この機械固有の困りごと」をそのまま解くのではなく、何が本質かを抽象化して一般問題に変えることで、一つの解決を別の機械・別の時代でも使える知識へ変えました。

名前を付ける力

新しい分野では、問題を解くだけでなく「問題に名前を付ける」ことが重要です。critical section、semaphore、self-stabilizationなど、概念を一語で呼べるようになると、研究者同士が同じ問題を共有して議論でき、曖昧だった現象が研究対象になります。

ダイクストラの貢献には、この「概念を切り出して言葉を与える」力も大きく関わっています。

小さい例を徹底的に考える

彼の有名な論文には驚くほど短いものがあります。

• 最短経路論文は3ページ
• 相互排除論文は1ページ
• 自己安定化論文は2ページ

短い論文でも、問題を本質だけに削り、不要な要素を消してから論じています。複雑な対象を小さなモデルへ変えることも、「難しいことをどう行うか」という一貫した方法でした。

実装と数学の両方を経験した

ダイクストラは理論と実装の両方を経験しました。初期には実際のコンピュータ用プログラムとコンパイラを書き、OSを設計し、後半には数学的な正当性、predicate transformer、証明方法論へ進みました。

Tony HoareはDijkstra Memorial Lectureで、ダイクストラの人生をscienceとengineeringの両面から論じています。

現実の機械の痛みを知っていたから抽象理論の必要性が分かり、抽象理論を重視したから特定機械に閉じない成果を作れた、と見ることができます。

---

19．現代のプログラマーは、ダイクストラの世界からどれほど離れたのか

ハードウェアは桁違いに強くなった

1960年のX1用ALGOL 60コンパイラは、わずか4K語ほどの記憶環境で動きました。現在の開発者は、数GBから数十GBのメモリを搭載したPCを使えます。

• ストレージはTB級
• クラウドでは必要に応じて多数のサーバーを利用できる
• IDEはコード補完やテスト実行を支援し、バージョン管理は変更履歴を保存する
• 生成AIがコードを書く時代になった

ハードウェアと開発環境だけ比べれば、ダイクストラの時代とは別世界です。

しかし「複雑さ」は減ったのか

コンピュータが100万倍強力になれば、プログラミングは100万倍簡単になるのでしょうか。実際には、私たちは強力な計算能力を使って、さらに巨大なものを作っています。

• Webブラウザだけでも膨大なコードから成る
• OSは巨大化している
• クラウドサービスは、ネットワーク、データベース、認証、キャッシュ、キュー、監視、複数地域、外部APIなど多数の要素を組み合わせる
• スマートフォンのアプリ一つでも、OS、ライブラリ、Web API、クラウド、広告、決済、通知など多くの層へ依存する

複雑さは消えたのではなく、形を変えて増えています。

抽象化の成功が、さらに上の複雑さを可能にした

私たちが巨大システムを作れるのは、過去の研究によって多くの細部を抽象化できるようになったからです。

現代の開発者は、CPUの命令コードやメモリチップの電気信号、ネットワークカードへの一ビット単位の送信命令を直接扱う代わりに、OS、コンパイラ、ランタイム、データベース、ライブラリなどの抽象化の上で作業します。

THEシステムで「下の層を消す」ことを考えたダイクストラの問題意識は、現在のソフトウェアスタック全体に通じます。

並行処理はむしろ日常になった

ダイクストラの時代、並行処理は高価なコンピュータを有効利用する先端問題でした。現在では、次のような場面で日常的に現れます。

• 普通のスマートフォンでも複数のCPUコアを使う
• Webサーバーは大量のリクエストを同時に処理する
• データベースでは多数のトランザクションが競合する
• クラウドでは何千台ものサーバーが協調する

race condition、mutual exclusion、deadlock、synchronizationは、より広い開発者に関係する問題になりました。

セマフォは形を変えて残る

現在のプログラミング環境では、mutex、semaphore、condition variable、channel、async/await、transactionなど、多様な同期機構があります。

ダイクストラのセマフォは、「独立した処理の協調を、明示的な同期プリミティブとして扱う」という研究史の初期に大きな位置を占めています。

形式手法も消えていない

一般的なアプリ開発で完全な数学的証明を行う場面は限られます。一方、高信頼性が必要な領域では、形式仕様、モデル検査、定理証明、型システムなどの研究と実践が続いています。

さらに「仕様を明確にする」「不変条件を考える」「テストだけでなく設計で不正状態を減らす」といった考えは、日常的なソフトウェア設計にも広がっています。

自己安定化は、常時稼働世界でさらに意味を持つ

分散サービスは、すべてを止めて初期化し直せない場合があります。一部ノードが再起動したり通信が一時的に切れたりしても、全体として回復し続ける必要があります。

自己安定化という厳密な研究概念の採用範囲は限定的ですが、「障害後にどう正常へ戻るかをシステム性質として設計する」という方向は、現代の耐障害分散システムを理解するうえで非常に重要です。

AI時代にダイクストラを読む意味

生成AIは数十秒で数百行のコードを生成でき、「コードを書く速度」をさらに押し上げます。そこで重要になるのは、生成速度とは別の問いです。

• そのコードを人間は理解できるのか
• 正しいとどう分かるのか
• 仕様は何か
• 異常時にどう振る舞うのか
• 複数の部品を組み合わせたとき、全体として何が保証されるのか

コード生成が速くなればなるほど、理解と検証が新しいボトルネックになる可能性があります。「思考がボトルネックであり、複雑さを構造で抑えなければならない」というダイクストラの問題意識は、AI時代にも重要です。

---

20．よくある誤解を整理する

誤解1　「ダイクストラは最短経路アルゴリズムだけの人」

最も大きな誤解です。ダイクストラ法は代表作ですが、彼の評価は並行処理、OS、構造化プログラミング、形式手法、分散処理まで広がります。1972年チューリング賞の文脈を見ても、プログラミング方法論への貢献が中心です。

誤解2　「Googleマップがそのままダイクストラ法で動いている」

経路探索の歴史的基礎としては重要ですが、現代の大規模経路サービスが教科書どおりの単純なダイクストラ法だけで構成されると断定するのは不正確です。

誤解3　「ダイクストラがスタックを一人で発明した」

再帰実装とstackという用語の歴史で重要ですが、似た仕組みは複数の研究者が独立に考えていました。

誤解4　「構造化プログラミング＝GOTO禁止」

この理解は狭すぎます。ダイクストラの中心課題は、プログラムを人間が理解し、正しさについて推論できるように構造化することでした。

誤解5　「順次・選択・反復だけ使えば、それがダイクストラ流」

三つの制御構造は入門上重要ですが、EWD249の議論は抽象化、理解可能性、証明、階層的構造などより広いものです。

誤解6　「ダイクストラはテストを否定した」

テストそのものを不要だと言った、と読むのは極端です。THEシステムでもテストは行っています。問題にしたのは、有限個のテストだけで「誤りが絶対にない」と論理的に証明できるわけではないことです。

誤解7　「理論家なので実装経験は少ない」

実際には逆で、初期には実機向けプログラム、ALGOL 60コンパイラ、OSなど非常に実践的な仕事をし、その後に形式的・数学的研究へ進みました。

誤解8　「最初から形式手法を信じていた」

本人は、初期に形式数学を恐れ、Hoareの証明にも抵抗があったことを回想しています。形式手法への考え方は、研究人生の中で発展していきました。

誤解9　「GOTO論文の題名は本人の有名なキャッチコピー」

掲載時の題名「Go To Statement Considered Harmful」は編集者Niklaus Wirthが付けたと、本人が後年明記しています。

誤解10　「古い話なので現代には関係ない」

ハードウェアは変わりましたが、複雑さ、並行性、分散、正しさ、抽象化という問題はむしろ拡大しています。

---

21．ダイクストラを知るための一次資料を読む

EWD1166「From my Life」

人生と主要研究を本人が振り返った重要資料です。最短経路をカフェで考えた話、ALGOL 60コンパイラ、自己安定化が長く注目されなかった話など、人物史の核になるエピソードが多数あります。

EWD123「Cooperating Sequential Processes」

並行処理を知るうえで最重要級の資料です。相互排除、P/V操作、セマフォ、bounded buffer、Deadly Embrace、Banker’s Algorithmが一つの流れとして登場し、現代のOS教科書で別々に学ぶ概念が、当時どのように一つの問題群として整理されていたかが分かります。

EWD196「The Structure of the THE-Multiprogramming System」

階層型OS設計、抽象化、検証について読めます。1960年代の実機仕様も詳しく、当時のコンピュータ環境を知る資料としても有用です。

EWD215「A Case against the GO TO Statement」

有名なGOTO論争の原稿です。短く比較的読みやすいため、ネット上の「GOTOは悪」という要約と原文の論点の違いを確認するのに向いています。

EWD249「Notes on Structured Programming」

ダイクストラの思想を知る中核資料です。単なるコーディング規則ではなく、「人間がどのように大きな計算を理解するか」という問題から始まります。

EWD340「The Humble Programmer」

1972年チューリング賞講演です。初期プログラミング史の回想と、プログラミングに対する哲学が一つになっています。

EWD401・EWD418・EWD472

weakest precondition、predicate transformer、guarded commands、program derivationへ進みたい人向けです。技術的には難しくなりますが、ダイクストラ後期の核心を知る資料です。

EWD426「Self-stabilizing systems in spite of distributed control」

わずか2ページの自己安定化論文で、短い文書が新しい研究分野を生みうる典型例です。

EWD683「To a new member of The Tuesday Afternoon Club」

研究会の目的を本人が説明した資料で、技術研究だけでなく「研究する技術」をどう考えていたかが分かります。

EWD1000「Twenty-eight years」

EWD文書の歴史、タイプライター、手書き、Dining Quintupleなど、研究者としての習慣を知る資料です。

EWD1303・EWD1308

最晩年の回想で、若いころの出来事を数十年後の本人がどう評価したかを知ることができます。

---

結論　ダイクストラが変えたのは「最短経路」ではなく、プログラムについて考える方法だった

1930年にダイクストラが生まれたとき、コンピュータ科学はまだ学問として成立する前でした。その後の歩みをたどると、コンピュータ科学そのものが形を整えていく過程と重なります。

• 1951年――理論物理学を学ぶ青年としてEDSACのプログラミング講習に参加
• 1952年――オランダで最初期の職業プログラマーになる
• 1956年――コンピュータの実演のため、カフェで最短経路アルゴリズムを考案
• 1960年――Zonneveldと世界最初期のALGOL 60コンパイラを完成
• 1960年代――相互排除、セマフォ、デッドロックという並行処理の問題を整理
• THE Multiprogramming System――複雑なOSを階層化し、一段ずつ理解・検証できる構造を実践
• 1968年――GOTO文を批判
• 1969年――「Notes on Structured Programming」で、人間の頭が巨大な複雑さを一度には扱えないという問題を正面から扱う
• 1972年――チューリング賞を受賞
• 1970年代――正しいプログラムを仕様と数学から導出する方法へ進む
• 1974年――壊れた分散システムが自律的に正しい状態へ戻る自己安定化を提示

晩年まで、彼は「難しいことをどう考えるか」を研究し続けました。

ダイクストラの功績の核心は、コンピュータが生み出す複雑さを、人間が理解し、制御し、正しさを論じられるようにするための考え方を作ったことにあります。

コンピュータがまだ珍しかった1950年代より、世界中の生活・産業・行政・通信がソフトウェアへ依存する現在の方が、この問いは大きくなっています。生成AIが大量のコードを短時間で作れる時代には、「コードを書く能力」以上に次の点が重要です。

• 何を作るべきか
• 何が正しいのか
• どこまで理解できているのか
• どの複雑さを隠し、どの条件を明示するのか
• 壊れたときにどう回復するのか

ダイクストラが半世紀以上前から追い続けた「プログラムとは何か」「正しく作るとは何か」「難しいことを人間はどう扱うのか」という問いは、コンピュータが強力になった現在、さらに大きくなっています。

ダイクストラの人生をたどることは、そのままコンピュータ科学が一つの学問として成熟していく過程をたどることでもあります。

---

参考文献・一次資料

1. Edsger W. Dijkstra Archive, The University of Texas at Austin
   https://www.cs.utexas.edu/~EWD/welcome.html
2. Edsger W. Dijkstra, EWD1166, “From my Life”
   https://www.cs.utexas.edu/~EWD/transcriptions/EWD11xx/EWD1166.html
3. Edsger W. Dijkstra, “A Note on Two Problems in Connexion with Graphs”, Numerische Mathematik, 1, 269–271, 1959.
4. Edsger W. Dijkstra, EWD123, “Cooperating Sequential Processes”
   https://www.cs.utexas.edu/~EWD/transcriptions/EWD01xx/EWD123.html
5. Edsger W. Dijkstra, “Solution of a Problem in Concurrent Programming Control”, Communications of the ACM, 8(9), 1965.
6. Edsger W. Dijkstra, EWD196, “The Structure of the ‘THE’-Multiprogramming System”
   https://www.cs.utexas.edu/~EWD/transcriptions/EWD01xx/EWD196.html
7. Edsger W. Dijkstra, EWD215, “A Case against the GO TO Statement”
   https://www.cs.utexas.edu/~EWD/transcriptions/EWD02xx/EWD215.html
8. Edsger W. Dijkstra, EWD249, “Notes on Structured Programming”
   https://www.cs.utexas.edu/~EWD/transcriptions/EWD02xx/EWD249/EWD249.html
9. Edsger W. Dijkstra, EWD340, “The Humble Programmer”, ACM Turing Lecture, 1972
   https://www.cs.utexas.edu/~EWD/transcriptions/EWD03xx/%21SV-EWD340.html
10. Edsger W. Dijkstra, EWD401, “The Characterization of Semantics”
    https://www.cs.utexas.edu/~EWD/transcriptions/EWD04xx/EWD401.html
11. Edsger W. Dijkstra, EWD418, “Guarded Commands, Non-determinacy and a Calculus for the Derivation of Programs”
    https://www.cs.utexas.edu/~EWD/transcriptions/EWD04xx/EWD418.html
12. Edsger W. Dijkstra, EWD426, “Self-stabilizing Systems in Spite of Distributed Control”, Communications of the ACM, 17(11), 643–644, 1974
    https://www.cs.utexas.edu/~EWD/transcriptions/EWD04xx/EWD426.html
13. Edsger W. Dijkstra, EWD472, “Guarded Commands, Non-determinacy and Formal Derivation of Programs”, Communications of the ACM, 18(8), 453–457, 1975
    https://www.cs.utexas.edu/~EWD/transcriptions/EWD04xx/EWD472.html
14. Edsger W. Dijkstra, A Discipline of Programming, Prentice-Hall, 1976.
15. Edsger W. Dijkstra, EWD683, “To a new member of The Tuesday Afternoon Club”
    https://www.cs.utexas.edu/~EWD/transcriptions/EWD06xx/EWD683.html
16. Edsger W. Dijkstra, EWD1000, “Twenty-eight years”
    https://www.cs.utexas.edu/~EWD/transcriptions/EWD10xx/EWD1000.html
17. Edsger W. Dijkstra, EWD1303, “My recollections of operating system design”
    https://www.cs.utexas.edu/~EWD/transcriptions/EWD13xx/EWD1303.html
18. Edsger W. Dijkstra, EWD1308, “What led to ‘Notes on Structured Programming’”
    https://www.cs.utexas.edu/~EWD/transcriptions/EWD13xx/EWD1308.html
19. Centrum Wiskunde & Informatica (CWI), “Edsger W. Dijkstra: Brilliant, colourful, and opinionated”
    https://www.cwi.nl/en/about/history/e-w-dijkstra-brilliant-colourful-and-opinionated/
20. F. E. J. Kruseman Aretz, “The Dijkstra-Zonneveld ALGOL 60 compiler for the Electrologica X1”, CWI, 2003
    https://ir.cwi.nl/pub/4155
21. G. M. C. J. T. G. van den Hove d’Ertsenryck, “New Insights from Old Programs: The Structure of The First ALGOL 60 System”, CWI, 2019
    https://ir.cwi.nl/pub/28427
22. University of Texas at Austin Computer Science, “Edsger Wybe Dijkstra: 1930–2002”
    https://www.cs.utexas.edu/news/2002/edsger-wybe-dijkstra-1930-2002
23. David Gries, “How can we explain Edsger W. Dijkstra to those who didn’t know him?”, 2002
    https://www.cs.utexas.edu/~EWD/memorial/gries.html
24. Tony Hoare, “What can we learn from Edsger W. Dijkstra?”, Dijkstra Memorial Lecture, 2010
    https://www.cs.utexas.edu/~EWD/DijkstraMemorialLectures/Tony%20Hoare.html
25. Krzysztof R. Apt and Tony Hoare (eds.), “Edsger W. Dijkstra: a Commemoration”, 2021, E. W. Dijkstra Archive.
26. ACM, A.M. Turing Award, Edsger W. Dijkstra, 1972.
27. Krzysztof R. Apt et al. (eds.), Edsger Wybe Dijkstra: His Life, Work, and Legacy, ACM Books, 2022.
28. Edsger W. Dijkstra, MR35, “ALGOL 60 Translation: An ALGOL 60 Translator for the X1 and Making a Translator for ALGOL 60”, Mathematisch Centrum, 1961.
29. Edsger W. Dijkstra and C. S. Scholten, EWD687, “Termination Detection for Diffusing Computations”, Information Processing Letters, 11(1), 1–4, 1980.
    https://www.cs.utexas.edu/~EWD/transcriptions/EWD06xx/EWD687.html
30. Philip L. Frana, “An Interview with Edsger W. Dijkstra”, OH 330, Charles Babbage Institute, University of Minnesota, 2 August 2001.
    https://conservancy.umn.edu/bitstreams/7a97387c-e045-4647-925c-d6d94a312f6e/download
31. Edsger W. Dijkstra, EWD51, “Multiprogrammering en de X8” (Dutch-English glossary includes the historical P/V terminology).
    https://www.cs.utexas.edu/~EWD/transcriptions/EWD00xx/EWD51.html
32. Edsger W. Dijkstra, EWD764, “Repaying our debts”.
    https://www.cs.utexas.edu/~EWD/transcriptions/EWD07xx/EWD764.html
33. Edsger W. Dijkstra, EWD1284, “Computing Science: Achievements and Challenges”, 1999.
    https://www.cs.utexas.edu/~EWD/transcriptions/EWD12xx/EWD1284.html
34. Edsger W. Dijkstra, Leslie Lamport, A. J. Martin, C. S. Scholten and E. F. M. Steffens, EWD630, “On-the-fly garbage collection: an exercise in cooperation”, Communications of the ACM, 21(11), 966–975, 1978.
    https://www.cs.utexas.edu/~EWD/transcriptions/EWD06xx/EWD630.html
35. Edsger W. Dijkstra, EWD500, “After many a sobering experience”.
    https://www.cs.utexas.edu/~EWD/transcriptions/EWD05xx/EWD500.html
36. Edsger W. Dijkstra, EWD796a, “Smoothsort, an alternative for sorting in situ”, 1981.
    https://www.cs.utexas.edu/~EWD/transcriptions/EWD07xx/EWD796a.html
37. Vojtěch Jarník, “O jistém problému minimálním”, 1930; Robert C. Prim, “Shortest Connection Networks and Some Generalizations”, Bell System Technical Journal, 1957. Historical priority noted because Dijkstra independently published an equivalent minimum-spanning-tree method in 1959.