課題1: ライフタイムの形式的理解

マンダトリー要件（80点）

問題1: ライフタイムの数学的定義（15点）

1.1 基本概念（5点）

以下の質問に答えなさい：

  • ライフタイムを集合論的に定義しなさい。（2点）
  • プログラムポイント（Program Point）とは何か説明しなさい。（1点）
  • 'a: 'b の意味を集合の包含関係で説明しなさい。（2点）

    • 1.2 半順序集合（5点）

    ライフタイムが半順序集合を形成することを証明しなさい。以下の3つの性質を示すこと：

  • 反射律（Reflexivity）
  • 反対称律（Antisymmetry）
  • 推移律（Transitivity）

    • 各性質について、数式とRustの例を示しなさい。

    1.3 制約解析（5点）

    以下のコードについて、ライフタイム制約を書き出し、解を求めなさい：

    fn example() {
    let x = 5;        // L1
    let y = 10;       // L2
    let r = &x;       // L3
    let s = r;        // L4
    println!("{}", s); // L5
}

  • 各変数のライフタイムを定義しなさい。（2点）
  • 制約を列挙しなさい。（2点）
  • 最小不動点を求めなさい。（1点）

---

問題2: Tofte-Talpin領域推論（20点）

2.1 型付け規則（10点）

以下の型付け規則をRustのコードで具体化しなさい：

REF規則: 

Γ ⊢ e : τ    ρ fresh
─────────────────────
Γ ⊢ ref e : ref^ρ τ

  • この規則の意味を日本語で説明しなさい。（3点）
  • Rustで対応するコード例を示しなさい。（3点）
  • 領域（region）とライフタイムの対応を説明しなさい。（4点）

2.2 DEREF規則（10点）

以下の型付け規則を分析しなさい：

DEREF規則: 

Γ ⊢ e : ref^ρ τ
────────────────
Γ ⊢ !e : τ

  • この規則をRustの構文で表現しなさい。（4点）
  • 参照の読み取りと領域の関係を説明しなさい。（3点）
  • なぜ領域注釈が必要か説明しなさい。（3点）

    • ---

    問題3: Variance（変性）（25点）

    3.1 Covariant（10点）

    以下の質問に答えなさい：

  • &'a T がcovariantである定義を書きなさい。（3点）
  • なぜ安全なのか、時間軸の図を使って説明しなさい。（4点）
  • 以下のコードが正しい理由を説明しなさい：

    • fn extend<'long, 'short>(x: &'long i32) -> &'short i32
where
    'long: 'short,
{
    x
}

    （3点）

    3.2 Invariant（10点）

    以下の質問に答えなさい：

  • なぜ &'a mut T はinvariantでなければならないか説明しなさい。（4点）
  • もし &'a mut T がcovariantだったらどうなるか、反例を示しなさい：

    • fn evil<'a>(short: &'a mut &'static str) {
    let local = String::from("local");
    *short = &local;  // もしcovariantなら...
}

    この関数がなぜ危険か、ステップバイステップで説明しなさい。（6点）

    3.3 Contravariant（5点）

    以下のコードについて説明しなさい：

    fn contravariant() {
    let f: fn(&'static str) = |s| println!("{}", s);
    let g: fn(&str) = f;

    let local = String::from("local");
    g(&local);
}

  • なぜこのコードは正しいか説明しなさい。（3点）
  • 関数引数のライフタイムが反変である理由を説明しなさい。（2点）

    • ---

    問題4: Higher-Ranked Trait Bounds（20点）

    4.1 基本概念（8点）

  • HRTBsとは何か、全称量化の観点から説明しなさい。（3点）
  • for<'a> の形式的意味を論理式で表現しなさい。（3点）
  • Early-bound と Late-bound の違いを説明しなさい。（2点）

4.2 実装問題（12点）

以下の関数を完成させなさい：

// 問題A: クロージャを返す関数（6点）
fn returns_closure() -> ??? {
    Box::new(|x: &str| x)
}

// 問題B: apply関数の実装（6点）
fn apply<F>(f: F, x: &i32) -> &i32
where
    F: ???,  // ここを埋めなさい
{
    f(x)
}

各問題について：

  • 正しい型注釈を書きなさい。（各3点）
  • なぜその型が必要か説明しなさい。（各3点）

---

ボーナス課題（20点）

ボーナス1: Variance表の完成（8点）

以下の表を完成させ、各型のvarianceとその理由を説明しなさい：

型 Variance 理由
`&'a T` ? ?
`&'a mut T` ? ?
`*const T` ? ?
`*mut T` ? ?
`fn(&'a T)` ? ?
`fn() -> &'a T` ? ?
`Box` ? ?
`Cell` ? ?

各行について：

  • Variance（共変/反変/不変）を答えなさい。（各0.5点）
  • 理由を簡潔に説明しなさい。（各0.5点）

    • ---

    ボーナス2: Tofte-Talpin論文の調査（7点）

    以下の課題を実施し、レポートを作成しなさい：

  • 論文の要約（3点）
- Tofte-Talpin (1997) の論文を読み、主要なアイデアを要約しなさい - 領域推論アルゴリズムの概要を説明しなさい

  • Rustへの影響（2点）
- Tofte-Talpin理論がどのようにRustに採用されたか説明しなさい - Rustでの改良点を挙げなさい

  • 他言語との比較（2点）
- MLKit（Tofte-Talpinの実装）との違い - Cycloneとの違い

提出形式：

  • Markdown形式のレポート（1500文字以上）
  • 参照文献を明記すること

参考文献：

  • Tofte, Mads, and Jean-Pierre Talpin. "Region-based memory management." Information and Computation 132.2 (1997): 109-176.

---

ボーナス3: ライフタイム制約ソルバーの実装（5点）

ライフタイム制約を解くシンプルなソルバーを実装しなさい：

use std::collections::{HashMap, HashSet};

#[derive(Debug, Clone, Copy, PartialEq, Eq, Hash)]
struct Lifetime(u32);

#[derive(Debug, Clone)]
struct Constraint {
    // 'a: 'b を表す（'a outlives 'b）
    outlives: Lifetime,
    outlived: Lifetime,
}

struct LifetimeConstraintSolver {
    constraints: Vec<Constraint>,
}

impl LifetimeConstraintSolver {
    fn new() -> Self {
        // ここを実装
    }

    fn add_constraint(&mut self, outlives: Lifetime, outlived: Lifetime) {
        // ここを実装
    }

    fn solve(&self) -> Result<HashMap<Lifetime, HashSet<Lifetime>>, String> {
        // ここを実装
        // 推移律を適用して、各ライフタイムがoutliveする
        // ライフタイムの集合を返す
    }

    fn check_consistency(&self) -> Result<(), String> {
        // ここを実装
        // 循環依存をチェック
    }
}

// テストケース
#[cfg(test)]
mod tests {
    use super::*;

    #[test]
    fn test_simple_constraint() {
        let mut solver = LifetimeConstraintSolver::new();
        let a = Lifetime(1);
        let b = Lifetime(2);

        solver.add_constraint(a, b);  // 'a: 'b

        let result = solver.solve().unwrap();
        assert!(result[&a].contains(&b));
    }

    #[test]
    fn test_transitive() {
        let mut solver = LifetimeConstraintSolver::new();
        let a = Lifetime(1);
        let b = Lifetime(2);
        let c = Lifetime(3);

        solver.add_constraint(a, b);  // 'a: 'b
        solver.add_constraint(b, c);  // 'b: 'c

        let result = solver.solve().unwrap();
        // 推移律により 'a: 'c も成立
        assert!(result[&a].contains(&c));
    }

    #[test]
    fn test_cycle_detection() {
        let mut solver = LifetimeConstraintSolver::new();
        let a = Lifetime(1);
        let b = Lifetime(2);

        solver.add_constraint(a, b);  // 'a: 'b
        solver.add_constraint(b, a);  // 'b: 'a

        // 循環依存はエラー（'a = 'b の場合を除く）
        assert!(solver.check_consistency().is_ok());  // 'a = 'b
    }
}

要件：

  • 制約を追加できること（2点）
  • 推移律を適用して解を求められること（2点）
  • テストが全て通ること（1点）

    • ---

    評価基準

    マンダトリー部分（80点）

    項目 配点 評価ポイント
    問題1：数学的定義 15点 集合論的理解、制約解析の正確性
    問題2：Tofte-Talpin 20点 型付け規則の理解と応用
    問題3：Variance 25点 3種類のvarianceの理解と証明
    問題4：HRTBs 20点 全称量化の理解と実装

    ボーナス部分（20点）

    項目 配点 評価ポイント
    ボーナス1：Variance表 8点 網羅的な理解
    ボーナス2：論文調査 7点 理論的背景の深い理解
    ボーナス3：ソルバー実装 5点 アルゴリズムの実装能力

    注: ボーナスは最大20点まで加算されます。

    ---

    提出方法

    ファイル構成

    rust-lifetime-mastery-01/
├── answers.md              # マンダトリー問題の回答
├── bonus1-variance-table.md   # ボーナス1の表
├── bonus2-tofte-talpin.md     # ボーナス2のレポート
└── bonus3-solver/
    ├── src/
    │   └── lib.rs          # ソルバーの実装
    └── Cargo.toml

    提出期限

  • マンダトリー：第1章学習後、1週間以内
  • ボーナス：第4章修了時まで

---

ヒント

問題1のヒント

数学的定義：

  • ライフタイムは時間区間の集合
  • プログラムポイントはコード中の位置
  • 包含関係は部分集合関係

半順序集合：

  • 反射律: 'a ⊇ 'a
  • 反対称律: 'a ⊇ 'b ∧ 'b ⊇ 'a ⇒ 'a = 'b
  • 推移律: 'a ⊇ 'b ∧ 'b ⊇ 'c ⇒ 'a ⊇ 'c

制約解析： 

変数のライフタイム:
'x = [L1, end)
'r = [L3, end)

制約:
'r ⊆ 'x
's = 'r

問題2のヒント

REF規則： 

let x = 5;        // e: i32
let r = &x;       // ref^'a x: &'a i32

DEREF規則： 

let x = 5;
let r = &x;       // r: &'a i32
let y = *r;       // y: i32

問題3のヒント

Covariant： 

長いライフタイム → 短いライフタイムは安全
&'long i32 <: &'short i32 ('long: 'short のとき)

Invariant： 

&'a mut T がcovariantだと、
短いライフタイムを長いライフタイムに拡張できてしまう
→ ダングリングポインタ

Contravariant： 

関数が長いライフタイムを要求 → 短いもので呼び出しても安全
fn(&'long T) <: fn(&'short T) ('long: 'short のとき)

問題4のヒント

HRTBs： 

// 通常のライフタイムパラメータ
fn foo<'a, F>(f: F)
where
    F: Fn(&'a i32),  // 'a は固定

// HRTBs
fn bar<F>(f: F)
where
    F: for<'a> Fn(&'a i32),  // 任意の 'a

型注釈： 

Box<dyn for<'a> Fn(&'a str) -> &'a str>

ボーナス3のヒント

ソルバーのアルゴリズム：

  • 制約をグラフで表現
  • 推移閉包を計算（Warshall-Floyd）
  • 循環依存をチェック

    • fn solve(&self) -> Result<HashMap<Lifetime, HashSet<Lifetime>>, String> {
    // 1. 初期化
    let mut outlives_map = HashMap::new();

    // 2. 直接的な制約を追加
    for constraint in &self.constraints {
        outlives_map
            .entry(constraint.outlives)
            .or_insert_with(HashSet::new)
            .insert(constraint.outlived);
    }

    // 3. 推移律を適用（不動点まで）
    loop {
        let mut changed = false;
        // outlives_map を更新
        // ...
        if !changed { break; }
    }

    Ok(outlives_map)
}

    ---

    学習の確認

    この課題を通じて、以下を理解できたか確認してください：

  • [ ] ライフタイムの数学的定義
  • [ ] 半順序集合としての性質
  • [ ] Tofte-Talpin領域推論理論
  • [ ] 型付け規則（REF、DEREF）
  • [ ] Covariantの定義と安全性
  • [ ] Invariantの必要性と危険性
  • [ ] Contravariantの意味
  • [ ] HRTBsの全称量化
  • [ ] Early-bound vs Late-bound
  • [ ] ライフタイム制約の解法

次の章では、複数のライフタイムパラメータと省略規則を学びます。

Previous
解説: 形式的理解
Next
複雑なライフタイム