HN 日本語サマリー

← 一覧へ戻る
プログラミング

Borrow Checking Zero-Cost Cyclic Mutability

Borrow Checking Zero-Cost Cyclic Mutability (antelang.org)

35 pointsby jfecher2 コメント

要約

Ante言語は、Rustに似た所有権と借用セマンティクスを持つ低レベル関数型言語ですが、借用チェッカーをより柔軟にし、Rustの「エイリアスかミューテートかのどちらか」という制約を緩和しています。この新しい設計は、プレース（places）と不安定なプレース（unstable places）という概念を導入し、サイクリックミュータビリティや複雑なデータフローを静的に安全に扱えるようにします。

全文翻訳

ゼロコストの循環的ミュータビリティの借用チェック

Anteは、Rustに似た所有権セマンティクスと借用に基づいた低レベルな関数型言語です[1]。しかし、Rustとは異なり、Anteの主要な目標は、借用チェッカーをより寛容にすること、特に、参照をエイリアス化するかミューテートするか、その両方を同時に行うことはできないというRustのルールを緩和することです。

// Rustでは:
let mut my_tuple = (1, 2);
let first_elem = &my_tuple.0;

// error[E0506]: cannot assign to `my_tuple` because it is borrowed
my_tuple = (3, 4);
println!("{first_elem}");

私は、ダングリングポインタにつながるコードを排除しつつ、上記のコードのような記述を、型システム内で完全に静的に許可したいと考えました。

しかし、それは古い話です。このサイトの最初のブログ記事で既に触れました。その記事は今となってはかなり時代遅れです。それから数年が経ち、Anteのアプローチは大幅に変更され、より柔軟にするための多くの機能が追加されました。そして今、グループ借用の多くの要素と私自身のアイデアを融合させることで、さらに根本的に安全な全体像を生み出すために、再び変更されました。この記事では、新しい設計について説明し、それが循環的なミュータビリティや複雑なデータフローを安全にサポートするのに十分な表現力を持つ、より柔軟な種類の安全な共有ミュータビリティをどのように実現するかを示します。

多くのRust開発者は共有ミュータビリティそのものの価値に懐疑的であるため、ここでより寛容であることがなぜ有用なのかを改めて説明する価値があります。より寛容であるということは、以下のことを意味します：

  • 借用チェッカーのエラーが減少します。エラーが少ないことは、新規ユーザーの学習曲線が容易になり、経験豊富なユーザーのイテレーション時間が短縮されます。
  • より多くのデザインパターンが許可されます。オブザーバーパターンは、共有ミュータビリティなしでは動作させるのが困難です。循環型データ構造もより直接的に表現できます。
  • 既存のデザインパターンにおける回避策が減少します。特に、ベクターへのインデックスの強制が少なくなります。これは有用なパターンですが、言語がユーザーにこのアプローチを強制すべきだとは思いません。
  • 共有ミュータビリティをサポートする他の言語との相互運用性が向上します。

最後の点は、見かけ以上に重要です。Anteは、ある程度オプトインで所有権を使用できるように設計されており、デフォルトではC#のような感覚で使えることを目指しています。これは野心的な目標ですが、共有ミュータビリティを許可することは、この目標達成に大いに役立ちます。

余談：Anteの以前のルールは何が悪かったのか？

ほとんどの読者はAnteの古い借用チェックのルールに馴染みがないと思いますが、興味のある方のために変更の動機をいくつか説明します。もしあなたがそうでないなら、このセクションはスキップして構いません。

私はほとんどの読者ではありません

元の記事では、Anteのrefとmut参照が&Cell<T>のアナログであると述べられており、その点は基本的に変わりありません。それ以降に行われた拡張のほとんどは、これを何らかの形で拡張するものでした。特に、「ローカルユニークネス」を導入し、共有ミュータブル参照がuniq参照（Rustの&mut Tと考えてください）が期待される場所で使用されるためには、ローカルにユニークであるだけでよいようにしました。これは、コンパイラが、mut Stringと同時に使用される任意の変数が、それをミュータブルにエイリアスしていないことを示すだけでよいことを意味しました。これは最終的に、aがbのどこにも現れない場合に実装されるDistinct a bトレイトの形を取りました。例えば、mut Stringがuniq Stringとして扱われると同時にVec I32を使用する場合、コンパイラはバックグラウンドでDistinct String (Vec I32)制約をチェックします。StringはVec I32内に現れることはないため、コードは許可され、Stringはローカルにユニークとみなされます。これは、uniq String参照がまだ有効である間、使用される各変数に対して繰り返されました。

本質的に&Cell<T>から&mut Tへのこのような変換を許可することは、柔軟性にとっては非常に良かったのですが、いくつかの大きな欠点がありました：

  • Stringのような一般的な型は、他の型内に現れることが多いため、ローカルユニーク参照に変換される際に、あまり一般的でない型と比較して使用が困難になりました。
  • Distinct a bは、プライベートフィールドを含むbのすべてのフィールドを再帰的に調べます。これは、ライブラリ内の公開構造体にプライベートフィールドを追加すると、以前は有効だったローカルユニーク変換が無効になる可能性があるため、破壊的な変更となりました。
  • mutとlocal uniq間の変換は頻繁に発生し、コンパイラが自動的に行っていたにもかかわらず、混乱を招きました。
  • refとmut（共有ミュータビリティを許可）およびimmとuniq（許可しない）の4つの参照タイプに依存していました。

すべてが悪かったわけではありません。特に、Rcの値の一部を（参照カウントをインクリメントして）クローンする必要があるという注意点がありましたが、安全な循環的ミュータビリティをエンコードするのに十分な強力さがありました。

しかし、上記の理由から、設計を変更する必要があることは明らかでした。この記事の残りの部分は、私が最終的にたどり着いた新しい設計について説明しており、これはこれらの問題すべてを解決しつつ、安全な循環的ミュータビリティ[2]とスレッドセーフティのような良い部分を維持しています。

コアとなる問題

なぜ、以下のような共有ミュータビリティの一部は安全なのでしょうか？

my_safe_fn (pair: String, String) = 
    name = ref pair.first
    pair.first := "Foo"
    println name  // OK!

一方で、以下のようなものは安全ではないのでしょうか？

my_unsafe_fn (vec: mut Vec t) = 
    elem = vec.get 1
    vec.clear ()
    println elem  // ダングリング参照！

違いは、私が「シェイプ安定性（shape stability）」と呼ぶものにあります。型のシェイプが安定している場合、以前有効だった参照を無効にするようなミューテーションを行う方法はありません。メモリ内の参照を視覚化すると役立ちます。pairとnameがメモリ上でどのように見えるかを見てみましょう：

ミューテーション前：

      name
       |
       V
pair: ((first_ptr, first_len, ..), (second_ptr, second_len, ..))


ミューテーション後：

      name
       |
       V
pair: ((first_ptr, first_len, ..), (second_ptr, second_len, ..))

各Stringは、ptr, len, metadataのアンボックス化されたタプルであり、外側のペアの各コンポーネントもアンボックス化されています。このレイアウトでは、nameを無効にするようにpairをミューテートする方法はありません！

一方、vecとelemを見ると、明確な違いがあります：

ミューテーション前：

vec: (data_ptr, length, capacity)
          |
          V
          [0, 1, 2, 3]
              ^
              |
             elem


ミューテーション後：

vec: (data_ptr, length, capacity)
          |
          V
          []
              ^
              |
             elem

elemは明らかにダングリングしています！問題は、vecをミューテートするとdata_ptrがミューテートされる可能性があり、再割り当て時に別の場所を指す可能性があることです。そのシェイプが変更され、elemは置き去りにされました。

参照タイプが、安定したものを指しているのか不安定なものを指しているのかを記憶できれば、ユニークネスを廃止して、より正確な制限で、より少ない有効なプログラムを拒否できるようになるでしょう。

プレイス（Places）対ライフタイム（Lifetimes）

パズルの最初のコア部分は、ライフタイムの代わりに「プレイス」を使用することです。

ライフタイムは、変数または参照が有効なコードの抽象領域を表す任意のシンボルですが、プレイスは、参照が借用できるものの正確なセットです：

foo (x: I32) (y: I32): Unit = 
    r1: ref 'x I32 = ref x
    r2: ref 'y I32 = ref y

    r3: ref '(x, y) I32 = 
        if true then ref x else ref y

上記では、r1はxのみから借用するため、プレイスは'xです。同様に、r2はyのみから借用するため、プレイスは'yです。r3はxまたはyから借用できるため、そのプレイスは両者の和集合、つまり'(x, y)です。プレイスは、変数zの構造体フィールドbarから借用する参照を表す'z.barのようなパスになることもあります。

プレイスは常に変数を指すとは限りません。ref 2のような一時的な参照に対する参照など、匿名プレイスもありますが、この記事では重要ではありません。

プレイスは、一般的に借用チェックを容易にします！Anteの借用チェックは実際には非常にシンプルです。値が使用されるたびに、それが参照するプレイスが既に移動されている場合はエラーを発行します。実際にはこれよりも少し複雑ですが、それがコアであり、数行のコードで実装できます。

不安定なプレイス（Unstable Places）

プレイスが得られたら、単純なマーカー!で「不安定な」プレイスをモデル化できます。a!のような不安定なプレイスは、プレイスaへの任意のミューテーションによって無効になります。これは、プレイスa!を持つ20個の変数がある場合でも、それらを同時にミューテートできることも意味します。なぜなら、それらをミューテートしても、プレイスがa!!である変数のみが無効になるからです。

これは少し抽象的ですが、実際にはどのように機能するか見てみましょう。まず、安全であるはずなのにコンパイラに拒否されるRustコードから始めます：

fn rejected(v: &mut Vec<String>) {
    // error: cannot borrow `*v` as mutable more than once at a time
    let (first, last) = (v.first_mut().unwrap(), v.last_mut().unwrap());
    *first = "Mutate first".to_string();
    println!("{last}");
}

Rustコンパイラは、firstをミューテートしてもlastを無効にする方法がないにもかかわらず、これを拒否します。理論的には、最初の要素が最後の要素でもある場合でも、このコードは有効であるはずです[3]。

Anteでは、ベクターの要素への参照を「不安定」とマークすることで、これをモデル化できます：

// ミュータブルなベクターを受け取り、ベクター内の最初の要素への
// 不安定な参照を 'v 内で返す `first_mut` メソッドを宣言します
Vec.first_mut (v: mut Vec t): mut 'v! t can Fail = ...
Vec.last_mut  (v: mut Vec t): mut 'v! t can Fail = ...

これで、rejectedの同等のコードを問題なく記述できます：

not_rejected (v: mut Vec String) = 
    first, last = v.first_mut (), v.last_mut ()
    first.* := "Mutate first"
    println last  // OK!

上記では、firstとlastは両方ともmut 'v! Stringの型を持ちます。そのため、firstをミューテートすると、v!!のプレイスを持つものを使用できなくなります[4]が、そのようなものはありません。したがって、両方を使用しても問題ありません。

参照が不安定かどうかは、実際には推論されるため、常にユーザーが手動で選択する必要はありません。タグ付きユニオンやコレクション型の要素への参照は、例として不安定になります。

ループ

ループと分岐は一般的に非常に単純です。それらは、ループの外で宣言された変数がループ内で無効になった場合にエラーが発行されるという、所有権のルールにほぼ従います：

var v = Vec.of [1, 2, 3]
one = v.get 0

for _ in 0 .. 3 do
    println one  // error: one may be invalidated by a later mutation in the for loop
    v.clear ()   // note: one invalidated here

同様に、キャプチャされた環境の一部を無効にするクロージャは、Rustの用語でFnOnceとして扱われ、一度しか呼び出せないようになります。

Anteにはエフェクトハンドラもあります！それらの制御フローはより複雑で、不安定なプレイスの無効化とどのように相互作用するかについてのルールはここに文書化されていますが、変更される可能性があります（少しハッキーだと思います）。（執筆時点では）handleと不安定なプレイスの相互作用はまだ実装されていません。

排他性（Exclusivity）

特定のパラメータがエイリアスしない場合にのみ有効な関数を記述することが可能です：

a_and_b_cant_alias (a: mut Vec String) (b: mut Vec String) = 
    elem = a.first_mut ()
    b.clear ()
    println elem  // OK！しかし、どうやって？

このような場合、コンパイラは依然として何らかの排他性ルールを必要とします。この場合、パラメータがミューテートされると、コンパイラは呼び出し元がユニークな値を渡すことを保証する必要があります：

bad_caller (c: mut Vec String) = 
    // error: 'a cannot alias 'b in this use of a_and_b_cant_alias, but 'c was used for both
    a_and_b_cant_alias c c

これをチェックするために、ミューテーションが発生するたびに、コンパイラはMutate 'pエフェクトを発行し、関数にミューテートされる可能性のあるプレイスをタグ付けします。呼び出しサイトでは、ミューテートされる可能性のある各プレイスは、インスタンス化された他のプレイスから区別される必要があります[5]。mut自体は依然として任意のエイリアスを許可することに注意してください。コンパイラがMutate 'pを発行して実際にミューテーションが発生した場合にのみ、コンパイラは呼び出しサイトで、ジェネリックがまだスコープ内にある間に'pにならないことをチェックします。

使用（Use）対言及（Mention）

Mutate 'pは、「使用」と「言及」の区別の一例です。ミュータビリティを単に言及するコードは、いかなるユニーク性制約も受けません。これは、プレイスがパスになる可能性があるため、mut Context全体を関数に渡すことができますが、Mutate 'ctx.fieldしかできません。このシナリオは、コンテキスト値のフィールドをミュータブルにイテレートする際によく発生します：

type Entity = name: String, health: I32
type Context = entities: Vec Entity, events: Vec String, score: U32

Context.on_death (ctx: mut Context) (entity: ref Entity): Unit
    can Mutate 'ctx.events
= 
    ctx.score += 10
    ctx.events.push "${entity.name} died"

iterate_example (ctx: mut Context) = 
    for entity in ctx.entities do
        entity.health -= 1
        if entity.health <= 0 then
            ctx.on_death entity  // OK!

Rustでは上記のコードは拒否されますが、Anteには実際にはいくつかの選択肢があります。上記のようにContext.on_deathでMutate 'ctx.eventsを公開することで、そのフィールドのみがミューテートされることを保証できます（整数のミューテーションは参照を無効にすることは決してないので、ctx.scoreには同様の注釈は必要ありません）。あるいは、on_deathに、entityがそもそもctx内に格納される可能性があることを伝えることもできます：

Context.on_death (ctx: mut Context) (entity: ref 'ctx.entities! Entity): Unit
    can Mutate 'ctx
= 
    ctx.score += 10
    ctx.events.push "${entity.name} died"

上記では、'ctx全体がミューテートされる可能性があると述べています。この特定の例では、これは望ましくありません。なぜなら、entityが不安定な参照であるため、on_deathの呼び出しが終わった後も有効ではなくなるからです。しかし、他のコードパターンでは、'ctx全体をミューテートする必要がある場合や、それを不透明にする[6]必要がある場合があり、まさにそれが望ましいでしょう。

複雑なデータフロー

少し立ち止まって、借用チェックをライフタイムではなく「プレイス」と「ミューテーション」の観点から再構築することがいかに強力であるかを示したいと思います。ライフタイムはコードの領域に結びついているため、Rustは複雑なデータフローに苦労することがあります：

fn get_default<'r, K: Hash + Eq + Copy, V: Default>(
    map: &'r mut HashMap<K, V>,
    key: K,
) -> &'r mut V {
    match map.get_mut(&key) {
    //    --- 最初のミュータブルな借用がここで発生します
        Some(value) => value,
        None => {
            map.insert(key, V::default());
            //  ^~~~~~ error[E0499]: cannot borrow `*map` as mutable more than once at a time
            map.get_mut(&key).unwrap()
        }
    }
}

Rustの現在のモデルでは、上記のコードを動作させるには、ライフタイムをコード領域よりもプレイス（エイリアスセット）に近いものとしてモデル化する次世代借用チェッカーであるPoloniusが必要です。Anteでは、これは単に機能します：

get_default
    (map: mut 'r HashMap k v)
    (key: k)
    {Hash k} {Eq k} {Copy k} {Default v}
: mut 'r! v can Mutate 'r, Panic = 
    match try do map.get_mut key
    | Some value -> value
    | None ->
        map.insert key (default ())
        map.get_mut key ~> panic_on_fail

Anteの借用チェッカーは既にプレイスに基づいているため、参照を特定のコード領域に結びつけようとしません。代わりに、map.get_mutからの戻り値の参照がNoneブランチで使用されないため、検証する必要はありません。これは直感的に理解できるはずです。参照が使用されないのであれば、それがダングリングしているかどうかは関係ありません。

別の例を見てみましょう：

struct Thing;

impl Thing {
    fn maybe_next(&mut self) -> Option<&mut Self> { None }
}

fn main() {
    let mut temp = &mut Thing;

    loop {
        match temp.maybe_next() {
        //    ^^^^ error: `*temp` was mutably borrowed here in the previous iteration
        //         of the loop first borrow used here, in later iteration of loop
            Some(v) => { temp = v; }
            None => { }
        }
    }
}

上記では、Rustはtemp = v;（ループの外で定義された変数への代入）のため、maybe_nextの借用がループ自体よりも長く続く可能性があると考えています。

type Thing = x: Unit

Thing.maybe_next (_: mut Thing): Maybe (mut Thing) = None

main () = 
    var temp = mut Thing ()

    while true do
        match temp.maybe_next ()  // OK!
        | Some v -> temp := v
        | None -> ()

一方、同等のAnteコードは、tempが匿名プレイス'pを取得し、maybe_nextが同じ'pを返し、ミューテーションは'pへの任意の「不安定な」参照のみを無効にするため、問題ありません。

不安定なプレイスを使用して、RustのRc<T>（参照カウントポインタ）のような共有ポインタを安全にミューテートできます。

最初の認識は、分析がプレイスに基づいているため、Rcは共有要素を表すプレイスを必要とすることです：Rc 'p t。これはBoxのような他のポインタタイプには必要ありませんが、Rcの場合、この追加パラメータ'pは、同じ値の異なるクローンを同じ内部値にリンクするために必要です。

Rcの内部へのミュータブル参照を取得することをモデル化する際には、以前のプレイスの和集合を利用する必要があります：

Rc.get (rc: mut 'outer (Rc 'inner t)): mut '(outer!, inner) t = ...

この型は、Rcへのミュータブル参照がある場合、内部要素へのミュータブル参照を取得できることを示しています。この返された参照は2つのプレイスを持ちます：outer!（共有ポインタ境界を通過しているため不安定であり、Rc値自体が置き換えられる可能性がある）、およびinner（このRcのすべてのクローンが指す共有値）です。

例を試してみましょう：

mutate_rc_bad (rc1: mut Rc 'p (Vec String)) (rc2: mut Rc 'p (Vec String)) = 
    // string_ref: mut '(rc1!!, p!) String
    string_ref = rc1.get () |> Vec.first_mut

    // 'p をミューテートするため、不安定な 'p! を持つ string_ref は無効になります
    // note: string_ref may be invalidated by this mutation
    rc2.get () |> Vec.clear

    // error: string_ref may have been invalidated by an earlier mutation
    println string_ref

素晴らしい！実行時チェックなしでRc値を介して安全にミューテートでき、何か unsafe なことをしようとするとコンパイラがバックアップしてくれます。これは循環参照さえも表現するのに十分でしょうか？

循環的ミュータビリティのためには…他に何も必要ありません！Rcを使用してサイクルを形成し始めることができます[7]。

type List 'p t = 
   | Nil
   | Cons t (Rc 'p (List 'p t))

main () = 
    var f = Rc.of (Cons false (Rc.of Nil))  // false -> []
    var t = Rc.of (Cons true f)             // true -> false -> []
    if f is Cons _ tail then
        // tail のプレイスは '(f!!, a!) なので、f または共有プレイス 'a の任意のミューテーションによって無効になります。
        // 後者の 'a の無効化は、他の共有ノードをミューテートした場合に使用できなくならないようにするために重要です。
        tail := t

    emit_list t
        |> take 5
        |> iter println  // true, false, true, false, true

// ここでの `do` は無関係です。ジェネレータ関数として使用されるシンクを返します。
emit_list (l: ref List t) = do
    if l is Cons elem tail then
        emit elem
        emit_list tail

このパターンは、RustのGhostCellを使用するパターンに非常に似ていますが、より人間工学的（GhostTokenは不要）で組み込みの方法です。これらのチェックは完全に静的であり、実行時チェックはありません。強調しておきます。

必要であれば、shared mut typeシュガーを使用して、物事を少し簡略化することもできます。その場合は、ドキュメントの関連セクションを参照してください。

マルチスレッディングに関する注意

より寛容な共有ミュータビリティにより、Anteはどのようにスレッドセーフティを維持するのでしょうか？

それほど興味深い答えはありません。Anteは単純にRustのSend/Syncトレイトをコピーします。ref/mut参照は両方とも共有ミュータビリティを許可するため、どちらのトレイトも実装しません。

代わりに、Anteは追加の参照種類immとuniqを持ち、これらはRustの&と&mutに対応します。これらの参照はほとんど使用されません。スレッド境界を通過した後、ref/mutに低下して関数を呼び出すことができるマルチスレッドコードで、ほぼ唯一使用されます。

将来、参照の種類はプレイス変数にアタッチされ、任意の参照種類に対してポリモーフィックなコードをより簡単に記述できるようになります。

まとめ

これは多くの内容でした！最後までお付き合いいただいた皆様、ありがとうございます！一度にすべてを理解するのは大変ですが、記事の長さにもかかわらず、コアコンセプトはそれほど複雑ではないと思います。確かにルールはありますが、ほとんどは言語をより柔軟にし、より多くのコードを「そのまま動作」させるためのものです。主なメンタルモデルは、参照が借用できる「プレイス」と、それらが不安定かどうかを追跡することです。

この記事は、Anteの共有ミュータビリティと安定性に関するドキュメントの再述が主ですが、元の共有ミュータビリティの記事のフォローアップとして、また変更の背後にある動機について話すために、記事形式で書きたかったのです。

もしこれらに興味を持ったなら、AnteのDiscordに参加して、言語の最新情報を入手し、質問してください！GitHubページでコンパイラをクローンして、自分で言語を試すこともできます。プロジェクトに興味がある場合、最も役立つ方法は、プロジェクトを広めて可視性を高めることです！もちろん、貢献も歓迎されます（コンパイラは小さく、私は手助けできます）！

  1. 低レベルという言葉は常に議論の余地があります。ここでは、デフォルトでアンボックス型があり、広範なGCがない言語を意味するために使用しています。好みの定義があれば教えてください！ ↩︎
  2. 新しい設計は、循環的ミュータビリティにとって実際にはより効率的です！以前の設計のようにクローンを必要としません。 ↩︎
  3. Rustではサウンドではありません。なぜなら、同じデータへの複数の&mut参照はエイリアスに関する仮定に違反するためですが、ターゲットセマンティクスではサウンドであるはずです！ ↩︎
  4. プレイスの!はネストできます！'foo!は'foo内の不安定なプレイスですが、'foo!!は前の不安定なプレイス内の不安定なプレイスになります。これは、例えばVec (Vec String)のString要素などです。型が複数の不安定性のソースを持っている場合（例：複数のベクターを保持する構造体）、API設計者は個別のフィールドを公開することを選択できます（例：'foo.bar! vs 'foo.baz!）、または親プレイス'foo!に強制してこれを非表示にすることを選択できます。 ↩︎
  5. 既に'pであったプレイスは実際には問題ありません。関数の本体は既にそれらを認識しており、それらのケースをチェックします。これにより、不変コンテナと、同じコンテナ内のミュータブル参照を渡すようなパターンが可能になります。 ↩︎
  6. Anteの将来のバージョンでは、「抽象プレイス」が可能になり、構造体はフィールドとは別に、内部のプレイスのセットを公開できるようになります。ライブラリ著者は、通常のコードで構造体フィールドを非表示にしながら、構造体内の複数のプレイスを互いに区別したい場合にこれを利用できます。欠点は、これらが特定の構造体フィールドに接続されていないため、抽象プレイスへの変換をサウンドに保つのはライブラリ著者の責任となることです。 ↩︎
  7. Rcを使用してサイクルを形成しても、メモリリークが発生します！リークを防ぐには別のコレクションメカニズムが必要ですが、それはサイクルのミュータビリティとは別の問題です。 ↩︎