課題1: 所有権理論の理解

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

問題1: 型システムの分類（15点）

以下の文が正しければ○、誤りであれば×で答え、×の場合は正しい説明を記述しなさい。

  • Rustは線形型（Linear Types）を採用している。
  • アフィン型では、値を使用せずに破棄することができる。
  • 線形論理では、リソースを何度でも使用できる。
  • Curry-Howard対応により、型はプログラムに対応する。
  • Rustの所有権システムは実行時にメモリ安全性をチェックする。

    • 各3点、計15点

    ---

    問題2: メモリ安全性の保証（20点）

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

    2.1 空間的安全性（Spatial Safety）（7点）

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

    fn dangle() -> &i32 {
    let x = 5;
    &x
}

  • このコードがコンパイルエラーになる理由を説明しなさい。（3点）
  • エラーメッセージで指摘される問題は何か？（2点）
  • 修正方法を2通り示しなさい。（2点）

    • 2.2 時間的安全性（Temporal Safety）（7点）

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

    let s = String::from("hello");
let r = &s;
drop(s);
println!("{}", r);

  • このコードがコンパイルエラーになる理由を形式的に説明しなさい。（4点）
  • Rustの型システムがどのようにこのエラーを防いでいるか説明しなさい。（3点）

    • 2.3 スレッド安全性（Thread Safety）（6点）

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

    let mut data = vec![1, 2, 3];
let r1 = &data;
let r2 = &mut data;

  • このコードがコンパイルエラーになる理由を「Aliasing XOR Mutability」の観点から説明しなさい。（3点）
  • なぜこの規則が重要なのか、具体例を挙げて説明しなさい。（3点）

    • ---

    問題3: RAIIとMove Semantics（25点）

    3.1 RAIIの理解（10点）

  • RAIIとは何か、簡潔に説明しなさい。（3点）
  • C++のRAIIとRustの所有権システムの違いを説明しなさい。（4点）
  • 以下のコードを完成させて、RAIIの例を示しなさい：

    • struct File {
    handle: FileHandle,
}

impl Drop for File {
    fn drop(&mut self) {
        // ここを実装しなさい
    }
}

    （3点）

    3.2 Move Semanticsの理論（15点）

  • 値カテゴリの説明（5点）
- lvalue（左辺値）とは何か説明しなさい。 - rvalue（右辺値）とは何か説明しなさい。 - 具体例を挙げなさい。

  • ムーブの理論（5点）

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

   let s1 = String::from("hello");
   let s2 = s1;

- s1の型は何か？ - ムーブ後のs1の型は何か？ - なぜs1は使えなくなるのか、型理論の観点から説明しなさい。

  • Bottom Type（⊥）の説明（5点）
- Bottom Typeとは何か説明しなさい。 - Rustでのムーブとの関係を説明しなさい。

---

問題4: 借用規則の形式化（20点）

4.1 参照の種類（10点）

以下の表を埋めなさい：

参照の種類 型 読み取り 書き込み 複数存在 Aliasing Mutability
不変参照 ? ? ? ? ? ?
可変参照 ? ? ? ? ? ?

各1点、計12点（表が10点分）

4.2 形式化（10点）

「Aliasing XOR Mutability」の規則を論理式で表現しなさい：

∀ x: T,
  (?) ∨ (?)

  • 論理式を完成させなさい。（5点）
  • この論理式の意味を日本語で説明しなさい。（5点）

    • ---

    ボーナス課題（20点）

    ボーナス1: 歴史的コンテキストの調査（10点）

    以下の言語/システムについて調査し、レポートを作成しなさい：

  • Cyclone（2006）
- どのような言語か？ - Rustとの違いは？ - なぜ普及しなかったか？

  • ATS（2008）
- どのような言語か？ - Rustとの違いは？ - どのような分野で使われているか？

  • Rustの成功要因
- CycloneやATSとの違いは？ - なぜRustは産業界で採用されたか？ - エルゴノミクスの重要性

提出形式：

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

    • ---

    ボーナス2: 形式的証明の実装（10点）

    以下のプログラムについて、Subject ReductionとProgressの性質を証明しなさい：

    fn process(s: String) -> String {
    let s2 = s.to_uppercase();
    s2
}

  • Subject Reduction（主辞簡約）の証明（5点）
- s: String であることを示す - s.to_uppercase() の型を示す - s2: String であることを示す - 型が保たれることを証明する

  • Progress（進行性）の証明（5点）
- プログラムが値を返すか、さらに簡約できることを示す - panic の可能性を考察する

提出形式：

  • 形式的な証明をMarkdown形式で記述
  • 各ステップを明確に

---

ボーナス3: 所有権システムの限界の実装（10点）

以下のパターンをRustで実装しなさい：

3.1 自己参照構造体（5点）

自己参照構造体をPinを使って実装しなさい：

use std::pin::Pin;

struct SelfRef {
    data: String,
    ptr: *const String,
}

// ここを実装しなさい

要件：

  • new() メソッドを実装
  • get_data() メソッドを実装
  • 安全性を保証すること

3.2 グラフ構造（5点）

親と子が互いに参照し合う構造をRcとRefCellを使って実装しなさい：

use std::rc::Rc;
use std::cell::RefCell;

struct Node {
    value: i32,
    children: Vec<Rc<RefCell<Node>>>,
    parent: Option<???>,
}

// ここを実装しなさい

要件：

  • 親ノードの追加
  • 子ノードの追加
  • メモリリークを防ぐ工夫

    • ---

    評価基準

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

    項目 配点 評価ポイント
    問題1：型システムの分類 15点 正確な○×判定と適切な訂正
    問題2：メモリ安全性の保証 20点 3つの安全性の理解
    問題3：RAIIとMove Semantics 25点 理論的背景の理解
    問題4：借用規則の形式化 20点 形式的な表現能力

    ボーナス部分（20点）

    項目 配点 評価ポイント
    ボーナス1：歴史的調査 10点 調査の深さと正確性
    ボーナス2：形式的証明 10点 証明の厳密性
    ボーナス3：限界の実装 10点 実装の正確性と安全性

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

    ---

    提出方法

    ファイル構成

    rust-ownership-deep-dive-01/
├── answers.md              # マンダトリー問題の回答
├── bonus1-history.md       # ボーナス1のレポート
├── bonus2-proof.md         # ボーナス2の証明
└── bonus3-code/
    ├── self_ref.rs        # 自己参照構造体の実装
    └── graph.rs           # グラフ構造の実装

    提出期限

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

---

ヒント

問題2のヒント

空間的安全性：

  • ダングリングポインタとは？
  • スコープとライフタイムの関係

時間的安全性：

  • Use-after-freeとは？
  • Rustの借用チェッカーの役割

スレッド安全性：

  • データ競合とは？
  • なぜ不変参照と可変参照は同時に存在できないか？

問題3のヒント

RAII：

  • Resource Acquisition Is Initialization
  • スコープベースのリソース管理
  • Drop traitの役割

Move Semantics：

  • lvalue: 名前を持つ、アドレスがある
  • rvalue: 一時的、アドレスがない
  • Bottom Type（⊥）: 到達不可能を表す型

問題4のヒント

形式化：

  • 論理記号: ∀（すべて）、∃（存在する）、∨（または）
  • 集合記号: ∈（属する）
  • 不変参照は複数、可変参照は1つ

ボーナス3のヒント

自己参照構造体：

  • Pinを使ってメモリ上で固定
  • 生ポインタ（*const T）の使用
  • unsafeブロックが必要

グラフ構造：

  • Rc: 参照カウント
  • RefCell: 内部可変性
  • Weak: 循環参照を防ぐ

    • ---

    学習の確認

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

  • [ ] アフィン型システムの理論
  • [ ] 線形論理とRustの関係
  • [ ] メモリ安全性の形式的保証
  • [ ] RAIIとMove Semanticsの理論
  • [ ] 借用規則の形式化
  • [ ] 所有権システムの歴史的コンテキスト
  • [ ] 所有権システムの限界と対策

次の章では、借用チェッカーの内部動作を詳しく学びます。

Previous
解説: 理論的基礎
Next
借用チェッカーの内部