Valen のメモリ安全：新しい借用チェッカー

自分が何を指しているかを覚えている参照！

この記事は Valen の新しい柔軟な借用チェッカーについての話だ。ようこそ。

私のことはご存じのとおり、私は新しいメモリ安全の仕組みを_愛_していて、それをいろいろ奇妙な形で組み合わせている。

これは私の永遠の探求の一部だ。メモリ安全の聖杯を探している——Rust の借用チェッカーほどの力があり、参照カウントやガベージコレクションほどの手軽さと柔軟さを併せ持つもの。¹²

聖杯を見つけるには、まず三つのメモリ安全の難題を解かねばならないとずっと疑っている。

_より緩い_借用チェッカーは作れるか？³
借用チェッカーに_より複雑なデータ_を読ませられるか？⁴⁵
この二つの仕組みを同時に協調させられるか？

曖昧で得体の知れない話だ、自分でもわかっている！これが何を意味するのか、そして Valen がすでに解を見つけているかもしれないことについては、後で説明する。⁶

この記事が主に焦点を当てるのは最初の部分、Valen のより緩い借用チェッカーだ。

つまりこの記事で扱うのは、それが何であり、何ができ、どう動くのかである。

わかりやすさのため、この記事では構文糖をいくらか自由に解釈している。自動デリファレンス、構造体への直接インデックス（my_vec[0]）、コレクションからの型推論（world.entities[] の entity）は十一月に登場する。これらの構文調整を除けば、借用チェッカーはここで話すすべてに適用される。⁷

ついでに、もっと風変わりな細部にも触れる。たとえば：

Valen の借用チェッカーがなぜこの形になっているのか——Valen のコードから Rust のコードを呼べるようにするためだ。
コンパイラが参照の指す_場所_をどう記憶するのか。
なぜ Valen には借用参照が_一つ_しかなく、他の借用チェッカーには二つあるのか。

それに、この記事は_ばかみたいに長く_、背景説明も多いので、飛ばしてよい箇所ではその都度知らせる。

始めよう！

グループ借用：すれ違いざま、されど大きな可能性

（これは私が語るのが大好きな背景話なので、この節は飛ばしてよい！）

Valen のやり方は「グループ借用」（Group Borrowing）提案の上に成り立っている。設計したのは友人の Nick Smith だ。

核となる考えは、コンパイラが参照の指す先を記憶する（後で説明する）ことで、それに基づいてプログラムがメモリ安全かどうかを検査する、というものだ。

この設計は苦しい船出だった。時間の流れに埋もれかけた。もともとは Mojo のために設計されたのだが、残念ながら、私が全力を尽くしても上層部を説得できなかった。⁸ グループ借用は成功の機会を得ぬまま死んだ。

だが、それが計り知れない可能性を秘めていることはわかっていた。世に出せさえすれば。

そこで私たちは数か月かけて説明を磨き、利点を整理し、昨年一本の記事を書いた⁹。他の言語に採用してほしいという願いを込めて。

実際に採用された！広く伝わったのだ。¹⁰

Google の Carbon はグループ借用へ完全に舵を切った（私たちの記事に謝辞まで載せてくれた、本当にありがたい！）
Ante は Shared Mutability and Stability に見られるように、自言語への取り込みを始めた。
Plecra の排除型は、グループ借用と GhostCell の概念を使って Rust の借用チェッカーを再設計しつつある。¹¹
Zeta はグループ借用と非交差性¹²を組み合わせ、実行時の事実をコンパイル時のメモリ安全に取り込んでいる。
Fang は Cyclic References in Fang に見られるように、自設計への取り込みを進めている。
そして私の Valen は、グループ借用と Vale¹³ の手法を組み合わせ、さらに Rust のコードと相互運用できるようにした。

これらの言語の多くは同じ種類の難題を巡っている。より柔軟な借用チェッカーをどう作るか、だ。

たとえば Valen は、参照カウントや世代付き参照と協調できるだけの柔軟な借用チェッカーを目指している。Carbon は、C++ のコードと協調できるだけの柔軟な借用チェッカーを目指している。

これが難しいのは、借用チェックと他の手法の間に根本的な衝突がずっとあるからだ。こう要約できる：¹⁴

借用チェックには「共有か可変か、どちらか一方」という制約がある。あるオブジェクトへの参照を保持しているなら、他の誰もそのオブジェクトを変更できない。
他の手法は、あるオブジェクトへの参照を保持しつつ、他の誰かがそれを変更できるようにしたい。¹⁵¹⁶

「これでは絶対に解決できないだろう」と思っているはずだ。

そう見える。

だがグループ借用は実際にこの衝突を解決する。「共有か可変か、どちらか一方」を「use-after-free を起こさない」へと緩めるのだ。

晦渋な話で、今のままでは何の意味もない。だがグループ借用がどう動くかを説明し終えれば、わかるはずだ。

まずはグループ借用に何ができるかを見て、それからその仕組みを説明する。

グループ借用に何ができるか

グループ借用は、実行時オーバーヘッドゼロでプログラムにメモリ安全をもたらす。¹⁷

コンパイル時に use-after-free を検出し、しかも以前の案より制約が少ない。

以下はコンパイル時に use-after-free エラーを検出する例だ：

valen

struct Entity {
  hp int;
}
struct World {
  entities Vec<Entity>;
}
func main() int {
  let world = World(Vec<Entity>.new());

  world.entities.push(Entity(42));
  let first_ref = &world.entities[0];

  world.entities = Vec<Entity>.new();

  // Compile error: Used a borrow after invalidated
  return first_ref.hp;
}

この方式は異例なほど柔軟だ。通常のコンパイラは以下のプログラムを扱えないが、この方式なら安全だと見抜ける：¹⁸

valen

func main() int {
  let list = Vec<int>.new();

  // Make two refs to the list
  let ref_a = &list;
  let ref_b = &list;

  // Mutate the list through both refs
  ref_a.push(42);
  ref_b.push(73);

  return 42;
}

Group borrowing は、borrow checker には普通手に負えないようなパターンを数多く受け付ける。たとえば：

複数のローカル変数が同じオブジェクトを指し、そのどれを通しても書き込める（上の例）。
一方の引数があるオブジェクトを指し、もう一方の引数がそのオブジェクト_内部_のどこかを指し、後者を通してだけ書き込む（次の節で見る）。
複数の関数引数が同じオブジェクトを指し、そのどれを通しても書き込める。¹⁹
スコープを抜けるときにオブジェクトを変更する「ロールバック」構造体を作る。ScopeGuard パターンのようなものだ。²⁰²¹
複数の構造体が同じサブシステムへの可変参照を保持する。²²
ほかにもある。以下でさらに説明する。²³

どれも C++ でおなじみのパターンだが、これをコンパイル時に、しかもメモリ安全に実現できている言語はまだない。

余談

（面白半分の脱線）

もっと面白い例

（あるいは、仕組みの説明へ飛ぶ）

たとえば次の step 関数は、World への参照と、その中のどれか一つの entity への参照を受け取る。

肝は world の entities[] にある mut 付きの entity で、これについては後で説明する。

valen

struct World {
  entities Vec<Entity>;
}
func step(world &World, entity in world.entities[] mut) {
  entity.advance();
  let collision = world.get_collision_for_entity(entity);
  entity.resolve(collision);
}

注目すべき点：

in は「そのうちのどれか一つへの参照」を意味する。
world.entities[] は「world の entities の要素」を意味する。
そこに付いた mut は「変更してよい」を意味する。²⁴²⁵

合わせるとこうなる：entity は world の entities のどれか一つの要素への参照で、しかも変更できる。

これがこの手法の核となる考え方だ：コンパイラは参照がどこを指すか分かっている²⁶。ユーザーが in でその指し先を指定しているからだ。

次にこれが他の言語ではどうなるかを見れば、どれだけ優れているか分かる。（あるいは仕組みの説明へ飛んでもいい！）

まず C++ での等価なコード：

c++

struct World {
  vector<Entity> entities;
};
void step(const World& world, Entity& entity) {
  entity.advance();
  auto collision = world.getCollisionForEntity(entity);
  entity.resolve(collision);
}

もちろん上のコードはメモリ安全を自分で慎重に保つ必要がある。C++ はコンパイル時にメモリ安全を検査しないからだ。

次に Rust での等価なコード。ここでは_確かに_自動的なメモリ安全が得られる：²⁷

struct World {
  entities: Vec<Entity>,
}
fn step(world: &mut World, entity_id: usize) {
  let entity_mut = &mut world.entities[entity_id]; // bounds check, possible panic
  entity_mut.advance();
  let entity_read = &world.entities[entity_id]; // bounds check, possible panic
  let collision = world.get_collision_for_entity(entity_read);
  let entity_mut = &mut world.entities[entity_id]; // bounds check, possible panic
  entity_mut.resolve(collision);
}

Rust は普通は快適だが、ある状況では（この例のように）C++ ほど速くも簡単でもない。同じ階層の別の場所で &mut が必要になるたびに、この参照を取り直さなければならないからだ。

もう一つの選択肢は、プログラムを（いわば）より「フラット」に作り直すことだが、それにもそれなりのトレードオフがある。²⁸

もっと凝ったことをしたいなら、GhostCell を使ってデータに brand を付け、GhostToken でアクセスできる：

struct World<'brand> {
  entities: Vec<GhostCell<'brand, Entity>>,
}
fn step<'brand>(
  world: &World<'brand>,
  entity: &GhostCell<'brand, Entity>,
  token: &mut GhostToken<'brand>,
) {
  entity.borrow_mut(token).advance();
  let collision = world.get_collision_for_entity(entity, token);
  entity.borrow_mut(token).resolve(collision);
}

ここでのジレンマが見えるだろう。

C++ の例は簡単だが²⁹、メモリ安全ではない。
素の Rust はメモリ安全だが、少し遅く、少し複雑だ。³⁰
GhostCell を足すと速度は C++ と同じになるが、やはり少し複雑だ。

Valen のやり方なら、速く、安全で、簡単なものが手に入る：

valen

struct World {
  entities Vec<Entity>;
}
func step(world &World, entity in world.entities[] mut) {
  entity.advance();
  let collision = world.get_collision_for_entity(entity);
  entity.resolve(collision);
}

なかなか見事な単純化だ！

さて、ようやく_どのように動くのか_を説明できる。

これは Rust の唯一参照（&mut）とは違う。同じ entity を指す別の参照が存在してよい。

この関数は world 全体を変更できず、その中の entity だけを変更できる（これは実は巨大な能力で、オプティマイザがこの関数_と_その呼び出し側をよりよく最適化できるようになる。ただしこれについては後で詳しく説明する）。

より正確には、コンパイラは自分のポインタがおおよそどこを指すかしか知らない。world.entities[] の entity は、entities 配列のあるオブジェクトが属するグループのどこかを指している。

Rust では、entity_mut.advance() を呼ぶには &mut Entity が必要で、それを捨ててから、それを含む &World を取り戻して get_collision_for_entity に渡さなければならない。その後、resolve を呼ぶときには &mut Entity をもう一度取り直すことになる。

具体的には、こうした方が borrow checker を扱いやすくなる（ゲームがたまたま ECS 的な走査をするなら速くもなる）が、単一所有がもたらす RAII の利点の一部を失う。

たとえば、異種の木を複数の配列に平坦化すると、ノードは親ノードと一緒に自動削除されなくなる。

また、並列コレクションにあまり細かく分割しすぎると、「ID を追いかける」ことによるキャッシュミスで性能が落ちることもある。

結局のところ、私は特定のアーキテクチャへと押しやるメモリ安全の手法には慎重だ。それが最善とは限らないからだ。

group borrowing でさえ、ある程度はこの問題を抱えている。だから参照カウントや世代付き参照を融合させるのが楽しみだ。

そう、「C++」と「簡単」を同じ文に入れるのがどれだけ皮肉かは分かっている！

ここには微妙な点がある。GhostCell を使わなくても、たいていは Rust のコードを組み替えて group borrowing と同じ速度にできる。

Valen の借用チェッカーはどう動くか

要約： この仕組みは5つの機構から成る。

すべてのオブジェクトは単一所有権に従い、1つのパスで記述される。
すべての参照は、自分が指すオブジェクトのパスを覚えている。³¹
オブジェクトを破棄すると、そのパスを指すものはすべて使えなくなる。
関数シグネチャはどのパスを変更するかを記述する。
関数を呼び出すと、その変更対象パスの中を指すものはすべて使えなくなる。

このままでは抽象的すぎるので、以下で1つずつ掘り下げていく。

単一所有権

要約： Valen の借用チェッカーは、C++ や Rust と同じく単一所有権の上に成り立っている。すべての値は、それを含むオブジェクト、配列、スタックフレーム、あるいはグローバル変数のいずれかが「所有」する。³²

C++ や Rust の仕組みをすでに知っているなら、ここは飛ばして構わない。

知らない人（あるいはざっと読み返したい人）のために、単一所有権とは何かを説明する。

単一所有権では、データのひとかたまりごとに「所有者」が1つある。たとえば……

次のような C++ プログラムがあるとする。

c++

#include <vector>
struct Engine { int fuel; };
struct Ship { unique_ptr<Engine> engine; };
void foo(vector<Ship>* ships) { ... }
void main() {
    vector<Ship> ships;
    ...
    foo(&ships);
}

……あるいはこの Valen プログラム。

valen

struct Engine { fuel int; };
struct Ship { engine Box<Engine>; }
func foo(ships &Vec<Ship>) { ... }
func main() {
    ships = Vec<Ship>.new();
    ...
    foo(&ships);
}

……このとき、こう言える。³³

main のスタックフレームが vector ships を「所有」している。
vector ships が各 Ship を所有している。
各 Ship が自分の Engine を所有している（unique_ptr 経由）。
各 Engine が自分の int fuel を所有している。
foo はこの vector を所有していない。裸のポインタを持っているだけだ。
所有者を持たない唯一のものが main である。

C++ や Rust を書いたことがあるなら、この考え方には馴染みがあるはずだ。

C を書いたことがある人も、同じように考えているかもしれない。ただし C は単一所有権を明示的に追跡しない。あるオブジェクトを malloc() の呼び出しから free() の呼び出しまでの旅路として追いかけると、ポインタが通過する変数やフィールドはどれも「所有ポインタ」を扱っている、と言えなくもない。まるで探偵が証拠の「管理の連鎖」を追うようなものだ。言い換えれば、ある時点でそのオブジェクトに誰が「責任を持つか」ということである。³⁴

Java や C# のプログラマーも、単一所有権の考え方で考えることがある。ある時点でそのオブジェクトの "dispose" / "cleanup" / "destroy" / "unregister" などのメソッドを呼ぶ必要があるなら、そのオブジェクトを new からその（概念的には破壊的な）メソッド呼び出しまでの旅路として追いかけることができる。そして、ポインタが通過する変数やフィールドが、その「所有参照」を扱っている、と言えなくもない。

ここまで説明してきた単一所有権は、多くの言語の土台になっている。

普通の（制約のない）ポインタと参照を足すと、C++ になる。
世代参照とリージョン借用を足すと、Vale になる。
排他性チェック付き参照を足すと、Rust になる。
グループ借用とその他いくつかの機構を足すと、Valen になる。

単一所有権があれば、すべてのオブジェクトを1本の「パス」で記述できる。次にそれを説明する。

「すべての参照が、指すオブジェクトのパスを覚えている」と、世代参照の「すべての参照が、指すオブジェクトの ID（『世代』）を覚えている」の間には、面白い共鳴を感じる。いわばグループ借用はコンパイル時の世代参照だ。ただ、詳しい話は次の記事に取っておく。

この制約は、後で参照カウントを使って緩める。

main のスタックフレームが foo のスタックフレームを所有している、と言ってもいい。逆でも成り立つ（async はそう動いている）。

より正確には、解放する責任、あるいは最終的に解放を保証する誰かにそれを引き渡す責任である。

パス

すべてのオブジェクトは1本のパスで記述できる。

次の例で考えてみる。

valen

struct Entity { hp int; }
struct World {
  diameter int;
  entities Vec<Entity>;
}
func main() int {
  let x = 42;
  let world = World(73, Vec<Entity>.new());

  ...
}

このプログラムに現れるパスは次のとおり。

x
world
world.diameter
world.entities
world.entities[]
world.entities[].hp

パスは必ず次のいずれかで始まる。

ローカル変数（world など）。
関数の引数。
関数の「グループ引数」（後述）。

その後に続くのは、たとえば次のようなものだ。

.diameter — 特定のメンバーを指す（上記のとおり）。
[] — コレクションの_要素_を指す（上記のとおり）。
.SomeType — union の特定のバリアントを指す。³⁵
このほか数種類の形式があり、後で説明する。³⁶

データは1つにつき所有者が1つしかない（単一所有権だから）。したがって、オブジェクト1つにつきパスも1本だけである。³⁷

で、パスは何の役に立つのか。

参照である。

コンパイラは各参照がどのパスを指しているかを把握しており、それがメモリ安全性の維持に役立つ。

たとえば、WarpEngine か ImpulseEngine のどちらかを持つ union/enum Engine があるなら、パスは my_engine.WarpEngine のようになる。

たとえば関連グループや、マルチタイプグループのサブタイプなど。これらはまた後で詳しく。

厳密には常に成り立つわけではない。関連グループなどを使えば、オブジェクトに複数のパスから到達できる。ただ、それはまた別の話である。

どの参照も、自分がどのパスを指しているかを知っている

たとえばこのプログラムでは：

valen

struct Entity { hp int; }
struct World {
  entities Vec<Entity>;
}
func main() int {
  let world = World(Vec<Entity>.new());

  world.entities.push(Entity(42));

  let entity_ref = &world.entities[0];

  ...
}

entity_ref の型は &Entity in world.entities[] です。

つまり、world の entities の要素への参照です。

先ほど見た例では：

valen

struct World {
  entities Vec<Entity>;
}
func step(world &World, entity in world.entities[] mut) {
  entity.advance();
  let collision = world.get_collision_for_entity(entity);
  entity.resolve(collision);
}

world.entities[] の中の entity が、world の entities の要素を指す entity パラメータを指定しているのがわかります。

Rust を知っているなら：パスはライフタイムとはあまり似ていません。別物として捉えたほうが理解しやすいでしょう。³⁸

次は、なぜこんなことをするのかを見ていきます。パスでどうメモリ安全性を保証するのかを。

実際には、ライフタイムは非常に粗い粒度の位置として扱えますが、どちらかといえば命令のスパンのようなものです。

パスによるメモリ安全性の保証³⁹

コンパイラはパスを使って解放後使用（use-after-free）を検出します。 すでに破棄されたデータを指す参照をデリファレンスしている、という状況を見つけ出すのです。

そのために次の2つのルールを使います：

あるオブジェクトを変更するとき、そのオブジェクトの_内部_を指す参照をすべて「無効」とマークする。
「無効」とマークされた参照を使おうとすると、コンパイラがエラーを出す。

この main 関数を見てください。

valen

struct Entity { hp int; }
struct World {
  entities Vec<Entity>;
}
func main() int {
  let world = World(Vec<Entity>.new());

  world.entities.push(Entity(42));
  let first_ref = &world.entities[0];

  world.entities = Vec<Entity>.new();

  // Compile error: Used a borrow after invalidated
  return first_ref.hp;
}

このコードでは2つのことが起きています：

world.entities = ... の箇所で、コンパイラはその内部を指す参照（world.entities[]）をすべて無効にします。first_ref が無効になりました。
return first_ref.hp の箇所で、コンパイラは first_ref を使っているのを見て、エラーを出します。

私の言い方に注目してください：

あるオブジェクトを変更するとき、そのオブジェクトの_内部_を指す参照をすべて「無効」とマークする。

あるオブジェクト_そのもの_を指す参照は無効にしません。そのオブジェクトの_内部_を指す参照を無効にするのです。

この main 関数を見てください。

valen

struct Ship { fuel int; }
func main() int {
  let vec = Vec<Ship>.new();
  vec.push(Ship(42));

  let vec_ref = &vec;
  let elem_ref = &vec[0];

  // Mutate `vec`.
  // Don't invalidate `vec_ref`.
  // Invalidate `elem_ref`.
  vec.push(Ship(73));

  // Can still use `vec_ref`.
  vec_ref.push(Ship(81));

  // Can't use `elem_ref`,
  // Compile error: Used a borrow after invalidated
  return elem_ref.fuel;
}

push を呼び出すと、その vec が変更されます。

これにより、vec の_内部_を指す参照がすべて無効になります。

つまり elem_ref が無効になります（vec_ref はまだ有効です）。

ですから vec_ref はまだ使えますが、elem_ref は使えません。

ここまで、ある参照が可変かどうかは一切述べていないことに注意してください。

そして Valen には借用参照が1種類しかありません。

C++ や Rust 出身の人なら戸惑うかもしれません。どちらも複数の参照の種類があるからです（C++ には const と非 const、Rust には & と &mut）。

Valen では、あるものの可変性はその型には属しません。 外側の関数が決めます。

Valen は関数パラメータに mut を付けますが、あれは単なる糖衣構文です。mut はパラメータの型には属しません。⁴⁰

イースターエッグのコメントを見つけましたね！

レックレス軍曹は馬で、アメリカ海兵隊で上級曹長まで昇進しました。

レックレス上級曹長は何でも食べました：スクランブルエッグ、ビール、コカ・コーラ、そして噂ではポーカーチップまで。

彼女は高い栄誉を受け、「戦時と平時の動物」勇敢章を授与されました。

このイースターエッグを見つけた人は、HN、lobste.rs、reddit のコメントに「morning sun」（彼女の韓国語の名前）とそっと書けば、あなた自身のメダルがもらえます！

（最初に見つけた q2dominic、timpi4ever、joonazan に乾杯！）

mut は関数シグネチャの一部です。一部の言語が async をパラメータではなく関数に付けるのと少し似ています。

関数シグネチャが無効化の情報を伝える

では、コンパイラは push が vec を変更したとどうやって知るのでしょうか？

push はシグネチャでそれを示さなければなりません。使うのは mut キーワードです。

これが push のシグネチャです：

valen

func push<T>(self &Vec<T> mut) { ... }

……これは次のものの糖衣構文です：

valen

func push<T>(self &Vec<T>) mut(self) { ... }

mut(self) は self の型に属するのではなく、どちらかといえば_関数_に属することに注意してください。

ですから main が vec.push(...) を呼び出すとき、main は vec を self として渡しています。

コンパイラは mut(self) を見て、self が実際には vec だと把握し、vec が変更されたとわかります。

こうして、vec の_内部_を指す参照を無効にすべきだと知るのです。

もう1つ例を挙げます：

valen

func step(world &World, entity in world.entities[] mut) {
  entity.advance();
  let collision = world.get_collision_for_entity(entity);
  entity.resolve(collision);
}

変更しているのは world 全体ではなく、world.entities[] の中の何かだけです。

これは良いことです。呼び出し側が持つ entities への参照を無効にせずに済むからです。

たとえば、次の step_and_read は、上記の entity を無効に_しない_ step 関数を呼んでいます。

valen

func step_and_read(world &World, entity in world.entities[] mut) {
  // Only modifies an entity's contents.
  step(world, entity);

  // ...so can still use `entity`!
  entity.read_book();
}

Valen コンパイラを正しく作り（さらに LLVM にパッチを当てれば）、これ_ひょっとすると_、これまでにない形でオプティマイザを活用できるようになるかもしれません。⁴¹

下でもう少し詳しく触れるが、手短に言うとこうだ。最適化器は、2つの関数が読み取りでしか重ならず、書き込みでは重ならないと分かれば、それらを並べ替えられる。計算をループの外に持ち出すことさえあり得る。

グループ借用のある変種

元々のグループ借用の設計には、ここまで挙げたものの多く（それ以上も！）がすでに含まれている。ここからは、Valen がその上に加えるもの、つまりこれを_輝かせる_ためのものだ。

可変の中の不変

このプログラムを思い出してほしい。受け取るのは不変の世界で、その実体要素だけが例外だ。

valen

struct World {
  entities Vec<Entity>;
}
func step(world &World, entity in world.entities[] mut) {
  entity.advance();
  let collision = world.get_collision_for_entity(entity);
  entity.resolve(collision);
}

2つの引数参照を受け取り、より具体的な方を通して変更できる。それ以外は何も変更できない。

Valen がこの機能を加えたのは、world 全体を可変で渡すという古典的な借用チェックの常套手段を使わずに済むようにするためだ。

これにはいくつか利点がある。

第一に、より強い API を書く助けになるので、プログラムの設計に役立つ。

関数全体を通して、世界のうち想定外の部分を何も変更できないことを強制できる。

チームに手を動かしたがる新人（あるいは vibe code をあなたの顔に投げつけたがるプロダクトマネージャー）がいる場合、これがかなり効きそうだ。

第二に、この機能は Valen のコードをより良く最適化できるようにするのではないかと思っている。

ここでは深く立ち入らないが、⁴² 大まかに言えば、何が変わり得て何が変わらないかについて、より細かい情報を最適化器に与えると、コードを並べ替えて高速化できる箇所を見つけやすくなる。⁴³⁴⁴

一時的な一意性

Valen の目標の一つは、Kotlin が Java を、C++ が C を呼ぶのと同じくらい気軽に、Rust のコードをシームレスに呼び出せるようにすることだ。

もちろんこれは厄介だ。グループ借用と Rust の参照は別物だからだ。

グループ借用では、自分の参照が指すデータを他人が変更できる。
Rust では、各参照は共有（&）か一意（&mut）のどちらかだ。参照を保持している間、その参照が指すものを誰も変更できない。

そこで疑問が湧く。グループ借用の参照を一時的に Rust の参照に変えられるだろうか？

答えは、できる。

仕組みは単純だ。Valen が Rust を呼び出すとき：

ある Valen 参照がその呼び出しの間、そのデータに触れられる唯一の参照なら、Rust の &mut として渡せる。
同じオブジェクトを指し得る Valen 参照が複数あるなら、Rust の & 参照としてしか渡せない。

この話題は Memory Safety Across the Valen/Rust Boundary で少し書いたので読んでほしい。

この一時的な変換は、いずれ より汎用的な機能へと発展するかもしれない。Valen には Rust の Vec のようなもの、つまり各要素が一意参照であるものをサポートしてほしいが、グループ借用ではそれができない。

Valen には「一意グループ」のようなものを持たせられるのではないかと考えている。たとえば関数に unique(world.ships[]) と注釈すれば、その階層のその部分を指す新しい参照の作成を防げる。

ただ、この方向性はもっと検討が必要だ。Valen の最大の強みの一つは借用参照が一種類しかないことだから……二つ目の「一意」参照を導入するのは慎重に考える必要がある。

Mastodon か Bluesky で聞いてくれれば、喜んで説明する！

これをうまく活かすには LLVM にパッチを当てる必要があるかもしれない。LLVM は noalias の観点で考える癖があり、「読み取り専用」の観点では考えない。厄介だが、実現は可能だ！

だからといって Valen が C++ や Rust などより速いとは限らない。同等の高速化は、それらの言語でも追加のリファクタリングや unsafe で実現できると_思う_。ここでの Valen の主な利点は人間工学と柔軟性であり、速度とは限らない。

ワイルドカード子孫パス

これも Valen が Rust のコードを呼び出すのを助ける機能だ。

Golden Spike を動かそうとして、難問にぶつかった。

Valen が参照を返す Rust 関数（たとえば下の -> &Gem）を呼び出すとき、その参照がどこを指すのかをどうやって知るのか？

たとえば：

impl Chest {
  pub fn gem(&self) -> &Gem { &self.gem }
}

Valen はこれに戸惑う。Valen はすべての参照のパスを知りたがるからだ。

Valen の理想の世界では、上のコードをこう見るだろう。

valen

func gem(self &Chest) -> &Gem in self.gem { &self.gem }

だが残念！ Valen は Rust のコードから self.gem の中の in を推論できない。

しかし視野を広げれば、Rust のコードが言いたいのは、返すものが self の**「内部のどこか」**を指すということだ。

ならば、この概念を Valen に加えよう！

Valen は上の Rust 関数を、今ではこう書いたのと等しいものとして解釈する。

valen

func gem(self &Chest) -> &Gem in self.gem... { &self.gem }

in self.gem... は「self.gem の_内部のどこか_を指す」という意味だ。

これはワイルドカード子孫パスと呼ばれていて、明らかにもっと良い名前が必要だ。

詳しくは Memory Safety Across the Valen/Rust Boundary に書いた。

Rust との相互運用だけに留まる話ではないと思う。シグネチャから内部の詳細を消し去り、ライブラリ API をより柔軟で前方互換性の高いものにできる。ただ、ここも注意が必要で、理屈の上では他の機能でも同じことができる。⁴⁵

たとえば、ある型が private なグループを public な名前で再エクスポートできるようにするとか。「関連グループ」とでも呼べるものだ。

これがどう噛み合うか

上で「メモリ安全性の聖杯」の話をした。そして、それを見つけるために解かないといけない3 つの課題にも触れた。

もっと_緩い_借用チェッカーは作れるか？
借用チェッカーに_もっと複雑なデータ_を読ませられるか？
この 2 つのシステムを同時に協調させられるか？

Valen の借用チェッカーは 1 つ目の鍵だ。任意のオブジェクトに対して複数の参照を持てて、そのどれを通しても読み書きできる。

2 つ目と 3 つ目は別の記事で扱う（この記事はもう長すぎる！）が、その核心だけさっと予告させてほしい。

半ページで説明しようと慌てて書いた草稿がこれだ。理解しようとする人はいないはず。さっさと先へ飛ばそう！

上の例を思い出してほしい。

valen

struct World {
  entities Vec<Entity>;
}
func step(world &World, entity in world.entities[] mut) {
  ...
}

ユーザーがパスを指定しないとき、参照カウントクラスを使う方を選べるようにしたい。こんなふうに。

valen

class World {
  entities Vec<Entity>;
}
func step(world World, entity Entity) mut {
  ...
}

ユーザーが自由にこう簡略化できるようになったら最高だ。⁴⁶

もちろん、参照カウントと借用を混ぜるのは困難で有名だ。⁴⁷

答えは 2023 年にやったある思考実験から来ている。僕はそれを Arrrlang と呼んだ。名前は冗談だが、前提は面白い。ヒープを N 個のグローバル配列として表す。N はプログラム中の型の数だ。⁴⁸

そこで思った。グループ借用は_配列を理解する_。そして参照カウントは、互いに参照し合う N 個の配列と見なせる。

この 2 つを重ねると、鍵となる洞察が見えてくる。参照カウント型を、まるで配列の集まりであるかのように借用チェッカーに記述すれば、それらを指す借用参照をメモリ安全に持てるかもしれない。

もちろん、コンパイラが参照カウントオブジェクトを_実際に_配列へコンパイルする必要はない。ただ、グループ借用の言い回しを使って、そのように借用チェッカーへ記述することは_できる_。

そうすれば多くの問題が一気に消えるし、グループ借用にまだ足りない部品が何なのかもはっきり分かる。

Vale の region に似た「複数型グループ」。普通のグループ借用は、1 つのグループに 1 つの型しか許さない。⁴⁹⁵⁰
「実行時」グループ。実行時グループへの参照は無効化されない。

言ったとおり、今はまだどれも筋が通らない。続きの記事を待っていてほしい！

参照カウントはずっと制約が少ない（たとえば参照は一時的でなくてよく、借用チェックはそうではない）。つまり、もっと多くのパターンを解き放てる（オブザーバ、侵入型リンクリストなど）。また、あるオブジェクトにアクセスしている間、誰もそれを解放できないという意味でもあり、これはたいてい良いことだ。

だがそれは見方次第でもある。参照カウントは循環でときどき問題を起こすし、線形型とはあまり相性がよくない。ほとんどの場合、僕は参照カウントが好きだ。もっと複雑な部分や速度が要る部分では、借用が好きだ。

言語としては両方をサポートするのが一番だと思う。

難しい理由は、Rc にどうしてあの RefCell が付いてくるのか、その理由とまったく同じだ。

かつては「ゼロオーバーヘッド」言語の例だったが、実際には ID の追跡と境界チェックというオーバーヘッドがある。

これは enum にも役立つ！

面白いことに、Iris は内部でヒープをまさにこのように表現していて、Iris は Rust の一部が安全であることの形式検証に使われたことがある。

今回はここまで

読んでくれてありがとう！

次の数本の記事では、参照カウントと世代参照をどう融合させるか、そして Valen のグループ借用チェッカーがどう実装されているかを、もう少し詳しく説明する。

これは氷山の一角にすぎない。続きをいち早く読みたければ、僕の RSS feed を購読するか、r/valen をフォローするか、Valen discord に参加してほしい。Bluesky と Mastodon で僕をフォローするのも歓迎だ！

Cheers，

Evan Ovadia

付録：型安定性の例外

この部分はまだ Valen には実装されていない。乞うご期待！

グループ借用はもっと賢くなれる。my_vec.push(42) と書いたとき、たとえ push が mut(self) と宣言していても、my_vec.size を指すポインタは無効化されない。

理屈は単純だ。誰がどう my_vec を変更しようと（それが Vec なら）、my_vec.size にあるものは常にそこにあり続ける。Vec の size を整数以外の何かに変えることは誰にもできない。言い換えれば、それは「型安定」なのだ。

もう少し一般化しよう。グループ借用は、型安定なデータを指すものを決して無効化しない。

型安定な中身（プリミティブ型、struct、固定長配列）を指すポインタも、その中身の内部にある型安定なものを指すポインタも無効化しない。無効化するのは、型不安定なもの（enum の中身、ポインタの指す先）の内部を指すポインタだけだ。

たとえば次のプログラムでは、誰が Level の中身をどう変更しようと、その Terrain への参照が無効になることはない。

valen

struct Level {
  terrain Terrain;
  entities HashMap<EntityId, Entity>;
  location_to_entity HashMap<Location, EntityId>;
}
func add_entity(level &Level mut, entity Entity) {
  level.location_to_entity.insert(entity.loc, entity.id);
  level.entities.insert(entity.id, entity);
}
func main() {
  let level = ...;
  let terrain_ref = &level.terrain;

  // Doesn't invalidate terrain_ref!
  level.add_entity(Entity(1, Loc(4, 5), 42));

  print(terrain_ref.tiles.len());
}

俺の立場はこうだ。誰かに時間を割いて読んでもらいたいなら、自分で時間を割いて手を動かして書け。

読んでくれてありがとう =)

この記事で全部説明する。このまま読み進めてほしい。

つまり「より複雑なデータを読む」とは、任意の形をしたデータグラフを指す不変借用参照をどうやって作るか、という話だ。

（Rust の構造体は他の Rust 構造体への参照を保持できるが、それは一時的なものに限られる。だから Rust のゲームでは ECS がこれほど人気なのだ。俺が今でも Rust を Fortran 側に分類している理由でもある。）

Valen には group borrowing があるが、Vale にあるのは region borrowing だ。
Valen には通常の世代参照があるが、Vale にあるのは確率的世代参照だ。
Valen には（Vale にはない）Rust 相互運用、Rc、comptime がある。
Valen には（Vale にはある）完全リプレイ、FFI を恐れない機能はない。

どちらも線形型を採用している。

構文はほぼ同じままだが、Valen は構文上「簡略化された Rust」に寄るかもしれない。

制約付き参照と Vale の現在のハイブリッド方式の間には、俺が「ハイブリッド世代メモリ」と呼ぶ方式があった。スコープ内で世代参照を「つなぎ止める」と、その参照は生き続けられる。俺は諦めるまでに 32 バージョンも作った。

オプティマイザに渡せる情報が増えるので、実行時に速くなる。
Cell、RefCell、Mutex なしで参照カウントを実装できる。
同じ理由で generational references も使える。

たとえば、異種の木を複数の配列に平坦化すると、親ノードを削除しても子ノードは自動で削除されない。

また、並列コレクションをあまり細かく分割しすぎると、「ID 追跡」的なキャッシュミスで速度が落ちることがある。

結局のところ、特定のアーキテクチャへと誘導するメモリ安全策には慎重でありたい。それが最善とは限らないからだ。

グループ借用もある程度は同じ効果を生む。だからこそ参照カウントや世代参照を組み込みたいと思う。

Sergeant Recklessは馬で、アメリカ海兵隊で上級曹長まで昇進した。

Sergeant Reckless はスクランブルエッグ、ビール、コカ・コーラ、そしてどうやらポーカーチップまで何でも食べた。

彼女は多くの栄誉を受け、「戦時と平時の動物」勇敢章を授与された。

このイースターエッグを見つけたなら、HN、lobste.rs、redditのコメントにこっそり「morning sun」（彼女の韓国語名）と書けば、あなたにも報酬がもらえる！

（q2dominic、timpi4ever、joonazan さん、最初に見つけたお三方、おめでとうございます！）

だが、それは見方による。参照カウントはときどき循環で問題を起こすし、線形型とはあまり相性が良くない。ほとんどのものには参照カウントが好きだ。より複雑な部分や速度が必要な部分には借用が好きだ。

言語が両方をサポートするのは良いことだと思う。

この探究からは面白い実験がたくさん生まれた。対象は制約付き参照、線形型、参照カウント、そしてその他いろいろだ。 ↩
この記事は 0% が AI によって書かれている。詳しい考えはこちら。 ↩
あるいはもっと正確に言うなら、「同じオブジェクトに対して複数の_読み書き_借用参照を持てる借用チェッカーは作れるのか？」 ↩
詳しくは後述するが、ここで言う「より複雑なデータ」とは完全なデータグラフのことだ。オブジェクトが他のオブジェクトを自由に参照でき、C++ や Java などで見られるような形を指す。Rust や Fortran のように、もの同士が普通は互いを参照できない言語とは違う。 ↩
手短に言えば、この問題に答えるのが Vale の世代参照とリージョン借用を組み合わせた方式だ。不変リージョン借用によって、コンパイラは既存のデータ全体を一時的に凍結された「リージョン」として追跡し、その中を指す借用参照を保持できる。 ↩
今のところほのめかすことしかできないが、Valen はすでにこの問題を解決しているかもしれない。Valeのアイデア、2023 年のある思考実験、Nick Smith の Group Borrowing、それにいくつかの調整を組み合わせて、それらが調和して共存できるようにしたのだ。 ↩
具体的には、今のコンパイラでは手動でデリファレンスする必要があり、構造体ではなく配列の添字に直接アクセスする。たとえば my_vec.data[0] と書く。world.entities[] の中の entity &Entity のように、すべての引数に型を書く必要もある。 ↩
他人の言語の上で作業するとはそういうことだ！ ↩
今読んでいるこの記事のほうが group borrowing の説明としてはるかに優れているが、古い記事なら Group Borrowing: Zero-Cost Memory Safety with Fewer Restrictions がある。 ↩
これらの言語のやり方がそれぞれどう動き、どう比較されるかについて、近いうちに記事を書く。楽しみにしていてほしい！ ↩
一級の権限によってライフタイムと型チェッカーを統合し、拒否するコードを減らしている。一見の価値は間違いなくある！ ↩
Zeta の借用チェッカーは、二つの参照が同じデータの_別々の部分_を指している（つまり「互いに素」である）ことを証明できる。たとえば i != j と分かっていれば、両方の添字が実行時の値であっても list.get_mut(i) と list.get_mut(j) が互いに素であると証明できる。詳しくはこちら！ ↩
Valen と Vale の主な違い： ↩
俺はこの衝突をよく「言語キラー」と呼ぶ。多くの実験的言語の多くのバージョンを壊してきたからだ。Vale の初期の方式もその一つだった。 ↩
C++ がこれを必要とするのは、普段そう使っているからだ。unique_ptr がオブジェクトを保持し、多数の非一時的な生ポインタがそれを指す。参照カウントやガベージコレクションにも同じ需要がある。どちらの場合も厄介なのは、借用参照を保持している間に他人がオブジェクトを変更する可能性があることだ。 ↩
この目標には異論もあるだろう。参照の参照先は足元で差し替えられるべきではないが、ID／添字の参照先は差し替えられてもよい（Rust のように）と考える者もいる。制約が強すぎると考える者もいる。俺はユーザー自身が選ぶべきだと思う。 ↩
とはいえ、ゼロの実行時オーバーヘッドでメモリ安全を実現できる言語があるかどうかは議論の余地がある。Chasing the Myth of Zero-Overhead Memory Safetyを参照。これはグループ借用にも同じく当てはまる。 ↩
通常、借用チェッカーはオブジェクトを変更できる参照が2つある場合の扱いを知らないため、コンパイルエラーを出す。グループ借用はこの多重読み書き参照を禁止せずに済むだけの柔軟性を持つ。use-after-free をより正確に防ぐ方法を知っているからだ。 ↩
例はこのページの「fn attack」のサンプルを参照。これは借用チェッカーにとって通常は難物だ。ただ、GhostCellが助けになることもある！ ↩
通常の借用チェッカーでは扱えない。ユーザーが読み書き参照を2つ欲しがっているからだ（shared-xor-mutable に反する）。片方は直接使い、もう片方は ScopeGuard オブジェクトの中に生きている。 ↩
これはユーザー定義の defer 文の土台にもなる！ ↩
手元に例がないので想像してほしい。複数の File オブジェクトがそれぞれ同じ FileSystem オブジェクトへの参照を持ちたいとする。借用チェックでは通常これを扱えない（同一オブジェクトへの読み書き参照が多すぎる）が、group borrowing なら問題ないはずだ。 ↩
詳しくは後述するが、group borrowing を出発点にすると次のことができる： ↩
Rust の独占参照（&mut）とは違う。同じ実体を指す他の参照が同時に存在できる。 ↩
この関数は世界全体を変更できない。変更できるのはその中の実体だけだ（これは実は巨大な能力で、オプティマイザがこの関数_および_その呼び出し元をより良く最適化できることを意味する。詳しくは後で説明する）。 ↩
より正確に言えば、自分がどこを指しているかを_おおよそ_把握している。world.entities[] 内の実体は、entities 配列の中のあの_一群_のオブジェクトのどこかを指している。 ↩
Rust では entity_mut.advance() を呼ぶのに &mut Entity が必要で、それを捨ててから外側の &World を取り戻し、get_collision_for_entity に渡さなければならない。その後 resolve を呼ぶときには、また &mut Entity を取得し直す必要がある。 ↩
具体的には、借用チェッカーとの格闘が楽になる（ゲームがたまたま ECS 的な走査をするなら速くもなる）。ただし単一所有権がもたらす RAII の利点の一部は失われる。 ↩
そう、「C++」と「簡単」を同じ文に入れるのがどれほど皮肉かは分かっている！ ↩
ここには微妙な点がある。GhostCell を使わなくても、Rust コードの構造を調整すればグループ借用並みの速度に達することはたいてい可能だ。 ↩
「すべての参照が自分が指すオブジェクトのパスを覚えている」ことと、世代参照の「すべての参照が自分が指すオブジェクトの ID（『世代』）を覚えている」ことの間に、奇妙な対応関係を感じる。グループ借用はコンパイル時の世代参照と_言えなくもない_。ただ、それは次の記事で！ ↩
この制限は後で参照カウントを使って緩める。 ↩
main のスタックフレームが foo のスタックフレームを所有していると言ってもいい。逆でも成り立つ（async はそう動く）。 ↩
より正確には、それを解放する責任、あるいは最終的に解放されることを保証できる誰かに引き渡す責任だ。 ↩
たとえば WarpEngine または ImpulseEngine を含む union/enum Engine があるなら、パスは my_engine.WarpEngine になりうる。 ↩
たとえば関連グループや、複数型グループのサブタイプなど。これも後で詳しく！ ↩
これは_厳密には_成り立たない。関連グループのようなものを使えば、オブジェクトは実際には複数のパスから到達できる。それはまた別の話。 ↩
実際には、ライフタイムは非常に粗い位置として使えるが、ライフタイムはむしろ命令列のスパンに近い。 ↩
イースターエッグのコメントを見つけたね！ ↩
mut は関数シグネチャの一部だ。一部の言語が async を引数ではなく関数に書くのと似ている。 ↩
これについては下でもう少し詳しく触れるが、要は、最適化器が「2つの関数は読み取りで重なり、書き込みでは重ならない」と分かれば、順序を入れ替えたり、計算をループの外に持ち出したりできるということだ。 ↩
Mastodon か Bluesky で聞いてくれれば、喜んで説明する！ ↩
これを実現するには、LLVM にパッチを当てて、この情報をもっと活用できるようにする必要があるかもしれない。LLVM は「読み取り専用」よりも noalias で考える傾向がある。厄介だが、不可能ではない！ ↩
だからといって Valen が C++ や Rust より速いとは限らない。それらの言語でも、追加のリファクタリングや unsafe を使って同等の高速化は できる と思っている。Valen の強みはどちらかといえば人間工学と柔軟性にあり、速度とは限らない。 ↩
例えば、ある型を公開名で公開しつつ、プライベートなグループを再エクスポートすることができる。いわば「関連グループ」のようなものだ。 ↩
参照カウントの制約はずっと少ない（例えば借用チェックと違い、参照は一時的でなくてもよい）。つまり、より多くのパターン（オブザーバ、侵入型リンクリストなど）を解き放てる。また、オブジェクトにアクセスしている間は誰もそれを解放できないという意味でもあり、これはたいてい良いことだ。 ↩
これが難しい理由は、Rc に RefCell がある理由とまったく同じだ。 ↩
これは「ゼロコスト」言語の例だが、実際には ID の追跡と境界チェックという形でコストがかかる。 ↩
これは enum にも役立つはずだ！ ↩
面白いことに、Iris はヒープを内部でこのように表現しており、Rust の一部が安全であることを形式的に検証するのに使われた。 ↩

グループ借用：すれ違いざま、されど大きな可能性

グループ借用に何ができるか

もっと面白い例

Valen の借用チェッカーはどう動くか

単一所有権

パス

どの参照も、自分がどのパスを指しているかを知っている

パスによるメモリ安全性の保証39

関数シグネチャが無効化の情報を伝える

グループ借用のある変種

可変の中の不変

一時的な一意性

ワイルドカード子孫パス

これがどう噛み合うか

今回はここまで

付録：型安定性の例外

Footnotes

パスによるメモリ安全性の保証³⁹