再帰は、かつて「禁止」されていた——メモリという制約が、言語の形を決めてきた〈言語知新(2)〉

こんにちは！Agy無限会社のコンテンツ制作部です。

「メモリ管理」と聞くと、地味な裏方の話に聞こえるかもしれません。でも実は、メモリという制約とどう折り合うかが、プログラミング言語の安全性・速度・書き心地のすべてを決めてきた主役なのです。今回の言語知新は特別版として、現代のRustから1950年代の黎明期まで、時間をさかのぼりながらこの問いを追いかけます。

1. GCなしで安全、所有権の発明

最初のトピックは、現代でいちばんホットな話題——Rustの所有権システムです。

RustにはGC（ガベージコレクション）も手動の解放命令もありません。では、いらなくなったメモリはどうやって片付けるのでしょうか。答えは「所有権」という考え方にあります。値の持ち主はいつでもただ1人、というルールをコンパイラが厳格に強制し、持ち主がスコープを抜けた瞬間に値は自動でドロップされます。

この所有権のルーツは、1987年にJean-Yves Girardが提唱した線形論理という数学理論にさかのぼります。そこから派生したアフィン型システムが、値を最大1回しか使わせない制約の土台になっています。RustはこのアイデアをはじめてGCなしの商用システム言語として実用化した言語です。

Rustにはさらに「借用」という仕組みもあります。読み取り専用の貸し出しは複数人に同時にOKですが、書き換えを伴う貸し出しは1人だけに限定されます。この借用チェッカーが、C言語を長年悩ませてきた二重解放やuse-after-freeといった事故をコンパイル時点で根絶します。

同じ「GCなし・即時解放」の思想を持ちながら異なるアプローチを取るのが、AppleのSwiftが採用する**ARC（自動参照カウント）**です。参照の数をカウントし、ゼロになった瞬間に解放します。素直な仕組みですが、2つのオブジェクトが互いを強参照し合う「循環参照」が弱点で、weak参照でその輪を断つ設計が必要になります。Rustは型で設計段階からねじ伏せ、Swiftは参照カウントで即座に片付ける——どちらも実行中のGCに頼らない方向で安全を取りにいっている点が共通しています。

2. 停止1ミリ秒未満への執念

JavaやC#、Goは、メモリの後始末をまるごとランタイムに任せることで開発者の生産性を大きく向上させました。しかしその代償として、回収中にアプリ全体が一時停止する「Stop-the-World」問題と長く戦い続けることになります。

JavaとC#が採用した主なアプローチは世代別GCです。「新しく生まれたものほど早く不要になりやすい」というWeak Generational Hypothesisに基づき、新世代のオブジェクトを短いサイクルで頻繁に回収し、生き残ったものだけ旧世代へ昇格させます。Java 21で導入された世代別ZGC（Generational ZGC / JEP 439）は、この思想を極限まで磨き上げ、16テラバイトもの巨大なヒープでも停止を1ミリ秒未満に抑え込みます。C#は世代別に加え、85,000バイトを超える大きなオブジェクトをLarge Object Heapへ分離する工夫を持ちます。

Goはやや異なる方向へ進化しました。白・灰・黒の三色でオブジェクトを分類しながらアプリと並行してマーキングする手法を採用しています。並行処理中に誤ったオブジェクトを回収してしまう危険はwrite barrierで防ぎ、Go 1.8ではDijkstra型の挿入バリアとYuasa型の削除バリアを組み合わせたハイブリッド方式を導入。最終的な再スキャン処理を丸ごと省けるようになり、停止時間を劇的に短縮しました。

さらにGoはエスケープ解析で、変数が関数の外へ出ていくかをコンパイル時に判定します。外へ出ない変数はスタックに配置し、関数終了と同時にコストゼロで解放——GCが扱うゴミの量そのものを減らすことで、効率を底上げしています。

3. Rustの祖先、忘れられた研究

1本目のRustの所有権には、直接の「ご先祖」にあたる研究があります。1994年、関数型言語Standard MLの世界で提唱された**領域推論（Region Inference）**です。Mads TofteとJean-Pierre Talpinによって考案され、ML Kitコンパイラとして実装されました。

領域推論の発想はシンプルです。メモリをいくつかの「区画（region）」に分け、各オブジェクトをどの区画に置くか、その区画をいつ丸ごと破棄するかをコンパイラがプログラムの構造から先に決めます。1つずつ片付けるのではなく、区画ごと一括で捨てる——机ごと片付けるイメージで、非常に高速です。ただし、データの寿命がプログラムのスコープ構造と一致しない場合に区画が残り続けてしまう弱点もあり、GCや参照カウントと組み合わせる方向へ戻っていきました。

この区画の考え方をC言語のような低レイヤに持ち込もうとしたのが、2000年代初頭のCycloneです。ポインタに「どの区画を指しているか」を型として付与し、すでに解放された領域を指すダングリングポインタをコンパイルエラーとして弾きました。さらにCycloneは、あるデータへの入り口がプログラム全体でつねに1つだけと保証する「一意ポインタ」を導入。これはまさにRustの所有権モデル「持ち主はただ1人」の原型であり、線形型の直接の応用でした。

Cyclone自体は研究の域を出ませんでしたが、「コンパイル時の検査だけで安全を実現できる」ことを証明し、バトンをRustへと手渡したのです。

4. 手動管理とGC、運命の分岐

1960〜70年代、メモリ管理は2つの正反対の道に枝分かれしました。

一方はC言語（1972年）。当時広く使われたPDP-11の16ビットフラットメモリに最適化された言語で、mallocでメモリを借り、freeで返すという極めて素朴な手動方式を採用します。機械にぴったり寄り添った設計で、無駄なオーバーヘッドがありません。しかし返し忘れればメモリリークが起き、解放済みの場所を触れば二重解放やバッファオーバーランの事故が起きます。この手動方式が、その後半世紀にわたるセキュリティ問題の根っこになりました。当時はメモリもCPUも貴重で、無駄をゼロにするにはこれが唯一の現実解だったのです。

もう一方はLisp（1958年）。John McCarthyが設計した、数学的な美しさを追い求めた言語です。リストを動的にどんどん生成するLispでは、どれがいつ不要になるか人が追いきれません。そこでMcCarthyは歴史上はじめて**GC（マーク・アンド・スイープ）**を発明しました。到達可能なオブジェクトに印を付け、印のないものを回収するこの方式は、60年以上が経つ今もGCの骨格として生き続けています。ただし発明の瞬間から、回収中に数秒かかる停止問題も始まっていました。

手作業の速さを取ったC言語、自動化の安心を取ったLisp——この分かれ道で背負った宿題を、私たちは今も解き続けています。

5. 再帰すら禁じられた時代

最後にたどり着くのは、1950年代の黎明期です。FortranやCOBOLが生まれたころ、メモリは完全に静的——プログラムを読み込んだ瞬間に、すべての変数の置き場所が固定の住所に割り当てられ、実行中に増えも減りもしませんでした。コールスタックという概念すら存在しなかったのです。

コールスタックがなければ、関数呼び出しの仕組みも根本的に異なります。当時の方式（Wheeler Jumpなど）では、戻り先の住所を呼び出される関数の先頭や終了部などの固定領域にそのまま書き込んでからジャンプしていました。一度きりの呼び出しならこれで問題ありませんが、もし関数が自分自身をもう一度呼んだらどうなるか——固定領域に書いてあった最初の戻り先が新しい戻り先で上書きされ、永久に元の呼び出し元へ戻れなくなるのです。

これが、再帰呼び出しが物理的に不可能だった理由です。当時の言語は再帰をはっきり禁止しており、どうしても再帰的な計算をしたい場合は、必要な深さの分だけまったく同じ関数のコピーを番号付きで並べ、順番に呼ぶという力業で乗り切っていました。Fortranで再帰が正式に導入されたのは、ずっと後のFortran 90からのことです。

コールスタックが当たり前になってようやく、私たちは再帰を数学の定義どおり自然に書けるようになりました。今、何気なく書いている再帰の一行には、長い歴史の重みがあります。

まとめ

固定に縛られた黎明期、手動で危険を背負ったC言語の時代、自動化で停止の悩みを抱えたGCの時代、そして型で安全を証明する現代のRust——どれも、その時々のメモリという制約への精いっぱいの答えでした。最新のRustやSwiftが「コンパイル時にメモリを決める」という点で黎明期の静的管理に回帰しているのは面白い逆説で、GCや領域推論などすべての探求をくぐり抜けたうえでの回帰だからこそ、安全と速度が両立できるのです。

動画では各トピックをやさしい対話形式で詳しく解説しています。ぜひあわせてご覧ください！