トニー・ホアー：クイックソートの発明者、「null は私の 10 億ドルの間違い」

1. 身近な「ソート / 並行処理」を逆算する

Python の sort()、Java の Collections.sort()、ほぼ全プログラミング言語のソートは、内部で クイックソート (の改良版) を使っている。1959 年にこれを発明した トニー・ホアー は、現代並行処理の理論 CSP の祖でもある。

2. 100 文字でわかる

3. 500 文字でわかる

1934 年スリランカ生まれ、英国オックスフォード大学卒。1959 年、ロシア語翻訳マシン用のソートアルゴリズムを 1 ヶ月で考案 — それがクイックソート (Quicksort)。平均 O(n log n)、実装簡潔で、現代の標準ソートに。1965 年、Algol 60 言語に「null 参照」を導入 — これが後に「The Billion Dollar Mistake (10 億ドルの間違い)」と本人が公言する後悔の元に。1978 年、CSP (Communicating Sequential Processes) を提唱 — 「並行プロセスがメッセージを送り合う」 モデル、現代の Go の goroutine・Rust の async・Erlang のアクター等の理論基盤。1980 年チューリング賞。Hoare 論理 (プログラム正当性証明)、Hoare の四角形 など多くの名を冠する概念。Microsoft Research や Oxford で現在も研究、91 歳の現役。

4. もっと詳しく

クイックソート (1959)

ロシア語翻訳マシンの研究中、ソートが必要に。彼は 1 ヶ月でクイックソートを考案。「ピボット (中央値) を選び、それより小さいグループと大きいグループに分割、再帰的にソート」というシンプルだが効率的なアルゴリズム。平均 O(n log n)、最悪 O(n²)、実装は数十行で済む。

「null は 10 億ドルの間違い」(1965)

1965 年、Algol W に「null 参照」を導入。「実装が簡単だから入れた」 が、後にこれが原因で世界中のプログラマが NullPointerException で苦しむことに。2009 年の講演で「これは私の 10 億ドルの間違いだった」と公式謝罪、現代言語 (Rust の Option / Kotlin の null safety) はこの教訓を取り入れている。

CSP (1978)

1978 年、Communicating Sequential Processes (CSP) を発表。並行プロセスが「メッセージで通信する」 モデル、共有メモリではなくチャネルで同期。Occam 言語 (1980s)、Go の goroutine・channel (2009)、Rust の async 等の現代並行モデルの理論基盤。

Hoare 論理

プログラムの「正当性 (correctness)」を数学的に証明する論理体系を確立。{P} S {Q} (前提 P、プログラム S 実行後に Q が成立) という記法は、現代の形式手法・契約プログラミングの基本。

5. 現代への影響

• クイックソート / Timsort: 全言語の標準ソート
• Go の goroutine + channel: CSP の直接実装
• Rust の async / await: CSP インスパイア
• Erlang / Elixir のアクター: CSP の派生
• プログラム証明 (Coq / Isabelle): Hoare 論理の応用

6. もっと知りたい人へ

• Wikipedia (日本語): トニー・ホーア
• 講演「Null References: The Billion Dollar Mistake」(2009): 公式謝罪講演
• 書籍「Communicating Sequential Processes」: CSP 原典

7. 次の話

EP.62 では ジョン・マッカーシー を扱います。LISP を作り、「人工知能 (AI)」という言葉を発明した CS の創設者の 1 人。