Keyboard shortcuts

Press ← or → to navigate between chapters

Press S or / to search in the book

Press ? to show this help

Press Esc to hide this help

背景トピック

このセクションでは、このガイドに登場する一般的なコンパイラ用語をいくつか取り上げます。Rust 固有の文脈をいくつか示しつつ、一般的な定義を説明することを試みます。

制御フローグラフとは何ですか？

制御フローグラフ（CFG）は、コンパイラ分野で一般的に使われる用語です。フローチャートを使ったことがあるなら、制御フローグラフの概念はかなり馴染みのあるものに感じられるでしょう。これは、根底にある制御フローを明確に示すプログラムの表現です。

制御フローグラフは、エッジで接続された一連の基本ブロックとして構成されます。基本ブロックの重要な考え方は、それが「一緒に」実行される文の集合であるということです。つまり、ある基本ブロックへ分岐すると、最初の文から開始し、その後に残りすべてを実行します。ブロックの末尾でのみ、複数の場所へ分岐する可能性があります（MIR では、その最後の文をターミネータと呼びます）。

bb0: {
    statement0;
    statement1;
    statement2;
    ...
    terminator;
}

Rust で普段使っている多くの式は、複数の基本ブロックにコンパイルされます。たとえば、if 文を考えてみましょう。

a = 1;
if some_variable {
    b = 1;
} else {
    c = 1;
}
d = 1;

これは MIR では 4 つの基本ブロックにコンパイルされます。テキスト形式では、次のようになります。

BB0: {
    a = 1;
    if some_variable {
        goto BB1;
    } else {
        goto BB2;
    }
}

BB1: {
    b = 1;
    goto BB3;
}

BB2: {
    c = 1;
    goto BB3;
}

BB3: {
    d = 1;
    ...
}

グラフィカルな形式では、次のようになります。

                BB0
       +--------------------+
       | a = 1;             |
       +--------------------+
             /       \
  if some_variable   else
           /           \
     BB1  /             \  BB2
    +-----------+   +-----------+
    | b = 1;    |   | c = 1;    |
    +-----------+   +-----------+
            \          /
             \        /
              \ BB3  /
            +----------+
            | d = 1;   |
            | ...      |
            +----------+

制御フローグラフを使う場合、ループは単にグラフ内のサイクルとして現れ、break キーワードはそのサイクルから出る経路へ変換されます。

データフロー解析とは何ですか？

Anders Møller と Michael I. Schwartzbach による Static Program Analysis は、非常に優れたリソースです！

データフロー解析 は、多くのコンパイラで一般的な静的解析の一種です。これは特定の解析ではなく、一般的な手法を表します。

基本的な考え方は、制御フローグラフ（CFG） をたどりながら、ある値が何であり得るかを追跡できるというものです。走査の終わりには、何らかの主張が真であること、または必ずしも真ではないことを示せるかもしれません（例：「この変数は初期化されていなければならない」）。MIR はすでに CFG であるため、rustc は MIR に対してデータフロー解析を行う傾向があります。

たとえば、次のスニペットで、x が使用される前に初期化されていることを確認したいとします。

fn foo() {
    let mut x;

    if some_cond {
        x = 1;
    }

    dbg!(x);
}

このコードの CFG は次のようになるかもしれません。

 +------+
 | Init | (A)
 +------+
    |   \
    |   if some_cond
  else    \ +-------+
    |      \| x = 1 | (B)
    |       +-------+
    |      /
 +---------+
 | dbg!(x) | (C)
 +---------+

データフロー解析は次のように行えます。まず、x が初期化されていることを把握しているかどうかを示すフラグ init から開始します。CFG をたどるにつれて、このフラグを更新します。最後に、その値を確認できます。

まずブロック (A) では、変数 x は宣言されていますが初期化されていないため、init = false です。ブロック (B) では、値を初期化するため、x が初期化されていることが分かります。したがって、(B) の終わりでは init = true です。

ブロック (C) は、状況が興味深くなる場所です。some_cond が true かどうかに対応して、(A) からのものと (B) からのものという 2 つの入力エッジがあることに注目してください。しかし、それは分かりません！some_cond が常に true である場合もあり得るため、その場合 x は実際には常に初期化されています。また、some_cond が何らかのランダムなもの（たとえば時刻）に依存している場合もあり得るため、x は初期化されていないかもしれません。一般に、静的にはそれを知ることはできません（Rice の定理による）。では、ブロック (C) における init の値はどうあるべきでしょうか？

一般に、データフロー解析では、あるブロックに複数の親がある場合（この例の (C) のように）、そのデータフロー値はすべての親（そしてもちろん、(C) で起こること）に対する何らかの関数になります。どの関数を使うかは、実行している解析によって異なります。

この場合、x が使用前に必ず初期化されていなければならないことを確定的に証明できるようにしたいと考えています。これにより、保守的になり、some_cond は時々 false になるかもしれないと仮定せざるを得ません。したがって、私たちの「マージ関数」は「and」です。つまり、(A) かつ (B) で init = true である場合（または x が (C) で初期化される場合）、(C) で init = true になります。しかし、これは当てはまりません。特に、(A) では init = false であり、x は (C) で初期化されません。したがって、(C) では init = false です。つまり、「x は使用前に初期化されていない可能性がある」というエラーを報告できます。

データフロー解析については、間違いなくさらに多くのことを述べられます。このトピックについては、多くの理論を含む膨大な研究文献があります。ここでは順方向解析についてのみ議論しましたが、逆方向データフロー解析も有用です。たとえば、ブロック (A) から開始して順方向へ進む代わりに、x の使用箇所から開始し、その初期化を見つけるために逆方向へ進むこともできたでしょう。

「全称量化」とは何ですか？「存在量化」はどうでしょうか？

数学では、述語は_全称量化_または_存在量化_されることがあります。

  • 全称 量化:
    • 述語は、すべての可能な入力について真である場合に成立します。
    • 伝統的な表記: ∀x: P(x)。「すべての x について、P(x) が成り立つ」と読みます。
  • 存在 量化:
    • 述語は、真となる入力がいずれか存在する場合に成立します。つまり、単一の入力が存在すればよいということです。
    • 伝統的な表記: ∃x: P(x)。「P(x) が成り立つような x が存在する」と読みます。

Rust では、これらは型チェックやトレイト解決で登場します。たとえば、

fn foo<T>()

この関数は、すべての型 T について関数が well-typed であると主張しています: ∀ T: well_typed(foo)。

別の例です。

fn foo<'a>(_: &'a usize)

この関数は、任意のライフタイム 'a（呼び出し元によって決定される）について、well-typed であると主張しています: ∀ 'a: well_typed(foo)。

別の例です。

fn foo<F>()
where for<'a> F: Fn(&'a u8)

この関数は、すべてのライフタイム 'a について F: Fn(&'a u8) であるような、すべての型 F について well-typed であると主張しています: ∀ F: ∀ 'a: (F: Fn(&'a u8)) => well_typed(foo)。

もう 1 つ例を挙げます。

fn foo(_: dyn Debug)

この関数は、関数が well-typed であるような、Debug を実装する何らかの型 T が存在すると主張しています: ∃ T: (T: Debug) and well_typed(foo)。

de Bruijn インデックスとは何ですか？

De Bruijn インデックスは、どの変数がどのバインダーで束縛されているかを、整数のみを使って表現する方法です。もともとはラムダ計算の評価で使うために考案されました（詳細はこの Wikipedia の記事を参照してください）。rustc では、de Bruijn インデックスをジェネリック型を表現するために使用しています。

以下は、de Bruijn インデックスをクロージャにどのように使えるかを示す基本的な例です（ただし、rustc では実際にはこうしていません！）:

|x| {
    f(x) // `x` の de Bruijn インデックスは 1。`x` は 1 レベル上で束縛されているため

    |y| {
        g(x, y) // `x` のインデックスは 2。2 レベル上で束縛されているため
                // `y` のインデックスは 1。1 レベル上で束縛されているため
    }
}

共変性と反変性とは？

Rust Nomicon のサブタイピングの章を参照してください。

型チェッカーが分散をどのように扱うかの詳細については、このガイドの variance の章を参照してください。

「自由リージョン」または「自由変数」とは何ですか？「束縛リージョン」はどうですか？

自由と束縛の概念を、プログラム変数の観点から説明しましょう。これは私たちにとって最も馴染みのあるものだからです。

  • クロージャを作成する次の式を考えてください: |a, b| a + b。 ここで、a + b の中の a と b は、クロージャが呼び出されたときに渡される引数を参照しています。そこにある a と b はクロージャに束縛されており、クロージャシグネチャ |a, b| は名前 a と b のバインダーである、と言います（その内部で a や b を参照すると、それが導入する変数を参照するためです）。
  • 次の式を考えてください: a + b。この式では、a と b は式の外側で定義されたローカル変数を参照しています。これらの変数は式の中に自由に現れる、つまり自由であり、束縛されていない（結び付けられていない）と言います。

これで説明は終わりです。ある変数が何らかの式/文/その他の中で「自由に現れる」とは、その式/文/その他の外側で定義されたものを参照している場合です。同じことを別の言い方にすると、式の「自由変数」を参照できるということです。これは単に、「自由に現れる」変数の集合です。

では、これはリージョンとどのような関係があるのでしょうか？ 同様の概念を型やリージョンにも適用できます。たとえば、型 &'a u32 では、'a は自由に現れます。しかし、型 for<'a> fn(&'a u32) ではそうではありません。

コンパイラに関する参考資料

公式 Discord の mem、scottmcm、Levi の推薦に感謝します。また、さらにいくつかの推薦を含んでいた Graydon Hoare による twitter スレッドへのリンクを投稿してくれた tinaun にも感謝します！

その他の出典: https://gcc.gnu.org/wiki/ListOfCompilerBooks

他にも提案がある場合は、issue または PR をぜひ開いてください。

書籍

コース

Wiki

その他の論文とブログ記事