RFC-011: ジェネリクスシステム設計 - ゼロコスト抽象とマクロ代替

概要

本文書はYaoXiang言語のジェネリクスシステム設計を定義する。強力なジェネリクス能力によってゼロコスト抽象を実現し、コンパイル時最適化によってマクロへの依存を削減し、デッドコード除去機構を提供する。

核心設計：

統一シグネチャ構文：(T: Type, R: Type) -> ... ジェネリクス引数と通常引数の統一
Type自己記述機構：Typeは言語レベルの特別な存在であり、シグネチャ中のType位置は自動的に推論・補完される
型制約：T: Dup + Add 多重制約、関数型制約
関連型：Iterator: (Item: Type) -> Type = { next: () -> Option(Item), has_next: () -> Bool }
コンパイル時ジェネリクス：N: Int ジェネリクス値引数、コンパイル時定数インスタンス化
条件型：If: (C: Bool, T: Type, E: Type) -> Type 型レベル計算、型族

価値：

ゼロコスト抽象：コンパイル時単相化、実行時オーバーヘッドなし
デッドコード除去：インスタンス化グラフ解析 + LLVM最適化
マクロ代替：ジェネリクスがマクロ使用シーンの90%を代替
型安全性：コンパイル時検査、IDEフレンドリー
明示は暗黙に勝る：Typeの自己記述、コンパイラによる自動推論

参考ドキュメント

本文書の設計は以下のドキュメントに基づく：

ドキュメント	関係	説明
RFC-010: 統一型構文	構文基盤	ジェネリクス構文と統一`name: type = value`モデルの統合
RFC-010: 統一型構文	呼び出し構文	第6節：ジェネリクス呼び出し構文——統一`()`適用、`[]`完全削除
RFC-009: 所有権モデル	型システム	Moveセマンティクスとジェネリクスの自然な結合
RFC-024: spawnベースの並行実行時セマンティクス	実行モデル	DAG解析とジェネリクス型検査
RFC-008: 実行時モデル	コンパイラアーキテクチャ	ジェネリクス単相化とコンパイル時最適化戦略
型宇宙思想	理論的核心	型宇宙階層モデルと値依存型設計
RFC-027: コンパイル時述語と統一静的検証	停止性検査	自動測度合成とコンパイル時評価の安全保証

型宇宙思想と値依存型

YaoXiangのジェネリクスシステムは型宇宙思想の上に築かれている。このメンタルモデルでは言語のすべての概念を階層構造として統一し、核心的な革新は値依存型をType2層の一級市民に昇格させたことにある。

値依存型とは何か？

値依存型は、一つまたは複数の値（他の型のみではなく）に依存する型である。これらの値はコンパイル時に評価され、コンパイル段階で型安全保証を提供できる。

yaoxiang

# 传统泛型：类型参数
List: (T: Type) -> Type

# 值依赖类型：值参数
Array: (T: Type, N: Int) -> Type  # 数组类型依赖于长度值 N
Matrix: (T: Type, Rows: Int, Cols: Int) -> Type  # 矩阵类型依赖于行数和列数

コンテナ型命名階層

言語層には3つのコンテナ概念があり、長さ情報の帰属がそれら根本的な違いである：

型	長さ	セマンティクス	底层
`Array(T, N)`	型	固定長配列、Nは型に含まれる	コアプリミティブ（スタック/インライン優先）
`Vec(T)`	実行時値	実行時長さの原始バッファ、拡張可能	コアプリミティブ（ヒープ上の連続バッファ）
`List(T)`	実行時値	標準ライブラリ型	ライブラリ：`{ data: Vec(T), length: Int }`

三者の分業原則：

Array(T, N)は長さを型に入れる唯一の形——長さはコンパイル時定数であるため、境界失敗のコンパイル時拒否が可能（a[5] がa: Array(Int, 3)の場合、直接コンパイル時エラー、後述「コンパイル時次元検証」参照）。
Vec(T) は実行時長さの最小限な地基——「割り当て可能、長さ取得可能、読み書き可能、拡張可能」の4つの機能のみを提供。容量戦略、拡張係数、縮小可否は一切行わない。他のコンテナを構築する原料である。
List(T)はライブラリ型、プリミティブではない——YaoXiang自体でstd.listに定義され（{ data: Vec(T), length: Int }）、ユーザー定義ジェネリクスレコードと同等の扱いを受ける。拡張可能セマンティクスの全戦略（いつ拡張するか、どの程度拡張するか、共有可能か）はすべてライブラリにあり、コンパイラは関与しない。

Vec(T)の構築形式（二層：先是型引数、次に構築引数）：

yaoxiang

# 空构造——长度 0，元素事后追加
v = Vec(Int)()

# 元素构造——长度由元素个数确定
w = Vec(Int)(1, 2, 3)          # 长度 3

# 槽位分配——分配 n 个零值槽位
buf = Vec(Int)(len=64)         # 长度 64，元素全为零值

槽位割り当てはフィールド名形式（len=）で位置形式ではない：位置形式の単一整数は「単一要素ベクトル」と曖昧（Vec(Int)(64) では「長さ64」と「要素64を含む」を区別できない）。これはジェネリクス構築の統一ルールと一致する：フィールド名形式の実引数は名前でバインドされ、位置推論の影響を受けない。
これはList拡張に必要な唯一プリミティブである——Listは必要に応じて新しいスロットを割り当て、要素を移動させる：
yaoxiang
new_data = Vec(T)(len=self.data.length * 2)
いつ拡張するか、どの程度拡張するか、縮小するかどうかはすべてListが決める。Vecは容量戦略を行わない。

下から上へ、パフォーマンスは減少し、柔軟性は増加する：Array > Vec > List。

命名の根拠：Vec/vectorは主流言語（Rust/C++）では実行時長さの拡張可能シーケンスを指す；Arrayは固定長を指す。

値依存型の核心的優位性

従来ジェネリクスと比較して、YaoXiangの値依存型には以下の核心的優位性がある：

特性	従来ジェネリクス (C++/Rust)	YaoXiang値依存型
型が依存する値	型引数のみに依存	任意の値（関数呼び出し結果を含む）に依存可能
コンパイル時評価	C++テンプレート手動特殊化、Rust不可	自動コンパイル時評価、停止性保証
型レベル計算	テンプレートメタプログラミング（複雑/危険）	統一された型レベル計算エンジン
型安全性	C++なし、Rust制限あり	完全な型安全性、コンパイル時検査
次元検証	実行時検査または手動特殊化	コンパイル時次元検証、実行時オーバーヘッドなし

型宇宙階層と値依存型

型宇宙思想は言語概念を意味的役割によって異なる階層に分割し、値依存型はType2層に位置する：

階層	役割	例
Type-1	値	`42`, `factorial(5)`, 関数自体
Type0	メタ型キーワード	`Type`
Type1	具体型	`Int`, `String`, `Array(Int, 3)`
Type2	関数/型コンストラクタ/値依存型	`add: (Int, Int) -> Int`, `Array: (T: Type, N: Int) -> Type`, `Matrix: (T: Type, Rows: Int, Cols: Int) -> Type`

重要な設計：Type2層の関数、型コンストラクタ、値依存型は統一構文で、すべて(params) -> resultの形式である：

通常関数：(Int, Int) -> Int → 戻り値は値
型コンストラクタ：(T: Type) -> Type → 戻り値は型
値依存型：(T: Type, N: Int) -> Type → 戻り値は型であり、値引数Nに依存する

Curry-Howard同型対応：この統一は偶然ではない。Curry-Howard同型対応は「型は命題、プログラムは証明」であることを指摘する——関数型 A → Bは論理的含意「AならばB」に対応し、ジェネリクス(T: Type) -> Typeは全称量化「すべての型Tに対して」に対応し、値依存型 (n: Int) -> Type は「各整数nに対して型が存在する」に対応する。YaoXiangは関数、型コンストラクタ、値依存型をType2層に統一することで、本質的に「証明」と「計算」を同一の概念——構成的証明として統合する。これはまさに、言語設計におけるCurry-Howard同型対応の直接的な具現化である：一つの形式（(params) -> result）が論理的命題と計算プロセスの両方を担う。

コンパイル時決定性保証

YaoXiangの型宇宙思想は以下を要求する：Type階層のすべてはコンパイル時に決定される。

yaoxiang

# 编译期维度验证示例
Matrix: (T: Type, Rows: Int, Cols: Int) -> Type = {
    data: Array(Array(T, Cols), Rows),
    # 编译期检查：维度必须为正
    _assert: Assert(Rows > 0),
    _assert: Assert(Cols > 0),
}

# 创建 3x3 单位矩阵 - 编译期完成
identity: (T: Add + Zero + One, N: Int) -> ((size: N) -> Matrix(T, N, N)) = {
    matrix = Matrix(T, N, N)()
    # ...
}

# 编译期计算：factorial(3) = 6，数组大小在编译期确定
arr: Array(Int, factorial(3)) = Array(Int, 6)()

コンパイラは自動的に：

型位置での関数呼び出しを検出
関数に対してコンパイル時停止性検査を実行（後述の停止性検査メカニズム参照）
コンパイル時に評価
結果を生成された型に埋め込む

値依存型の応用シナリオ

コンパイル時次元検証

yaoxiang

# 矩阵乘法：编译期验证维度匹配
multiply: (T: Add + Multiply + Zero,
           Rows: Int, Cols: Int, M: Int) -> ((
    a: Matrix(T, Rows, Cols),
    b: Matrix(T, Cols, M)
) -> Matrix(T, Rows, M)) = {
    # 编译期检查：a.Cols == b.Rows，否则编译错误
    result = Matrix(T, Rows, M)()
    # ...
}

# 错误在编译期捕获：
# multiply(matrix_2x3, matrix_4x2)  # 编译错误：2 != 4

型安全な配列サイズ

yaoxiang

# 数组大小是编译期常量
Array: (T: Type, N: Int) -> Type = {
    data: Array(T, N),
    length: N,
}

# N 是编译期常量，可以用于类型级计算
first_three: Array(Int, 3) = Array(Int, 3)(1, 2, 3)
# first_three.length == 3（编译期已知）

境界失敗のコンパイル時カバレッジ目標

実装状況説明：コンテナ型は特殊化解除済み——Array(T, N)はconstジェネリクスコンストラクタであり、リテラルコンテキスト落点、in メンバーシップ述語は実装済み。Array(T, N) リテラル落点のNと要素型はコンパイル時検証で強制済み（E1002）、Nは信頼済み——本節の目的メカニズムは「注釈N == 実行時長」の上に構築可能。現在の[] インデックス範囲外（E6003）とDictキー欠落（E6008）は実行時エラートランジション状態；本節値依存型はこれらの境界失敗をコンパイル時に押し下げる目標メカニズムである：
constインデックス：a[5]（5はコンパイル時定数）はa: Array(Int, 3)の場合、直接コンパイル時拒否；
値インデックス：a[i]は前置条件i < len(a)を要求し、値依存型契約証明による；
in述語はホーア論理前置条件の基底：n in 1..10、x in some_setはすべてコンパイル時証明可能な命題。
精錬型の完全な設計は実装時に別途本節を補足する。

条件型

yaoxiang

# 类型级If
If: (C: Bool, T: Type, E: Type) -> Type = match C {
    True => T,
    False => E,
}

# 类型族
AsString: (T: Type) -> Type = match T {
    Int => String,
    Float => String,
    Bool => String,
    _ => String,
}

ジェネリクス関数

yaoxiang

# map: 泛型函数，类型参数 T, R 在编译期确定
map: (T: Type, R: Type) -> (
    (list: List(T), f: (x: T) -> R) -> List(R)
) = (list, f) => {
    result = List(R)()
    for x in list {
        result.push(f(x))
    }
    return result
}

# 使用时完全透明，类型自动推导
numbers = List(Int)()   # 值构造两层形式（见 §9.1）；元素用 push 填充
numbers.push(1)
numbers.push(2)
numbers.push(3)
doubled = map(numbers, (x) => x * 2)  # 推导为 map[Int, Int]

他言語との比較

特性	C++テンプレート	Rustジェネリクス	Haskell GADT	YaoXiang
型引数	✅	✅	✅	✅
値依存型	❌	❌	✅	✅
コンパイル時評価	テンプレートインスタンス化	❌	✅	✅
停止性保証	❌	❌	❌（危険）	✅（自動測度探索 + 明示測度、RFC-027）
型安全性	❌（マクロ展開）	✅	✅	✅
統一構文	❌	❌	❌	✅
コンパイル時次元検証	手動特殊化	実行時検査	型族	コンパイル時自動検証
半自動停止性注釈（decreases/invariant）	❌	❌	❌	❌（注釈構文なし；明示測度は型位置に記述）

停止性検査メカニズム（RFC-027と統合）

値依存型のコンパイル時評価は停止性を保証しなければならない。さもないと型システムが無限ループに陥る。停止性検査はRFC-027のコンパイル時証明パイプラインによって全自動優先で完了する——コンパイラがまず自動的に測度を探索し、証明可能な再帰/ループは通過する；探索できず、かつ明示的に測度が与えられていない場合はコンパイルエラーを報告する（RFC-027 §6.9は型位置の明示測度のフォールバックを提供）。注釈構文への余地を与えない：RFC-022の //! decreases、/*! invariant !*/はRFC-022の廃止に伴い廃止済み、規約とは型注釈そのものである。

トリガー判定基準（RFC-027 §7）：停止性義務は精錬型によってトリガーされる——型が精錬されると検証モードに入る。精錬されていない通常型は検証モードに入らず、停止性義務を生成しない。

再帰関数の停止性検査

コンパイラは精錬シグネチャを持つ再帰関数について、再帰呼び出しの引数が各再帰パスで厳密に減少していることを検査する（RFC-027 §6.7）。規約コメントは一切不要：

yaoxiang

# 带精化签名的递归：无 //! requires/ensures/decreases，编译器自动探索递减
factorial: (n: NonNegative(n)) -> Int = {
    if n <= 1 { return 1 }
    return n * factorial(n - 1)  # 编译器探索：n-1 < n → 递减 → 终止
}

シナリオ	振る舞い
コンパイラが減少を探索可能（例：`n-1`）	通過
探索できないが型位置に測度が与えられている（§6.9）	SMT判定、成立すれば通過
探索できず、かつ明示測度なし / 測度がSMTで反証された	コンパイルエラー
シグネチャに精錬なし（検証モードに入らない）	停止性義務を生成しない

ループの停止性検査

ループは: Invariant(...)や: decreases(...)注釈を必要としない。変数上の精錬型注釈（例：UpTo(n)）は同時にループ不変式と測度境界を提供し、コンパイラは優先順位に従って4つの測度探索戦略を試し、1つ見つかれば停止する（RFC-027 §6.1–6.5）：

線形ランク関数の自動合成——型注釈から変数の境界を抽出し、線形結合を列挙、SMTでm ≥ 0かつ全パスでm' < mを検証
述語違反カウント（実験的）——目標型定義（例：Sorted）からviolation_countを抽出し、隣接交換/移動をカバー
有界増減モード——v += const → 測度upper - v（戦略1の縮退、最速パス）
乗法スケール測度テンプレート——v *= const（const > 1）→ 測度ceil(log_const(upper / v))

yaoxiang

sum: (arr: Array(Int, n)) -> Int = {
    mut i: UpTo(arr.len) = 0   # 类型标注给出上界 arr.len 与下界 0 → 进验证模式
    while i < arr.len {
        # 编译器自动探索：度量 arr.len - i，每次迭代严格递减 1 → 终止得证
        s += arr[i]; i += 1
    }
    return s
}

探索できない場合、ループに名前をバインドし、型位置に測度を与えられる（RFC-027 §6.9）：

yaoxiang

loop: (n: Int) -> Int = {
    mut i = 0
    acc: Terminates(n - i) = while i < n { i = i + 1 }
    return acc
}

停止性検査のワークフロー

┌─────────────────────────────────────────────────────────────┐
│  型検査フェーズ                                                │
│  精錬型の位置に遭遇（引数精錬、戻り値精錬、変数精錬）      │
└─────────────────────────┬───────────────────────────────────┘
                          ▼
┌─────────────────────────────────────────────────────────────┐
│  1. 停止性検査（RFC-027証明パイプライン、全自動優先）                 │
│     - 再帰関数：各再帰パスで引数が厳密に減少していることを検査             │
│     - ループ：4つの測度探索戦略（線形ランク/違反カウント/有界モード/      │
│       乗法スケール）、SMTで減少を検証                                │
│     - 探索できず → プログラマが型位置に測度を与え可能（Terminates）   │
│     - 測度なし / 測度がSMTで反証 → コンパイルエラー（ハード境界）          │
└─────────────────────────┬───────────────────────────────────┘
                          ▼
┌─────────────────────────────────────────────────────────────┐
│  2. コンパイル時評価（組み込みインタプリタで実行）                           │
│     - 純関数：直接評価                                       │
│     - 副作用：コンパイルエラー（型位置は副作用なしでなければならない）                │
└─────────────────────────┬───────────────────────────────────┘
                          ▼
┌─────────────────────────────────────────────────────────────┐
│  3. 結果の型への埋め込み                                            │
│     - Array(Int, factorial(5)) → Array(Int, 120)             │
│     - Matrix(Float, 3, 3) → 具体型                        │
└─────────────────────────────────────────────────────────────┘

優位性

安全性：コンパイル時評価が必ず停止することを保証し、型システムの無限ループを回避
統一性：停止性検査と正当性検証（VC生成）は同じコンパイル時証明パイプライン（RFC-027）を共有、独立した規約構文なし
全自動優先：コンパイラは型注釈から自動的に測度を探索し、証明できれば通過；探索できない場合は型位置に測度（Terminates）を与えられ、これもSMTで判定される——プログラマの手書きdecreases構文に依存しない

動機

なぜ強力なジェネリクスシステムが必要か？

現在の主流言語のジェネリクスには限界がある：

言語	ジェネリクス能力	問題
Java	境界型	コンパイル時単相化、ジェネリクス特殊化なし
C#	ジェネリクス制約	実行時型検査、パフォーマンスオーバーヘッドあり
Rust	ジェネリクス + トレイト	トレイトシステムが複雑、学習曲線が急峻
C++	テンプレート	テンプレート特殊化が複雑、コンパイルエラーメッセージが悪い
YaoXiang	値依存型	型が値に依存可能、コンパイル時次元検証、停止性保証

核心的矛盾

パフォーマンス vs 柔軟性：実行時柔軟性 vs コンパイル時最適化
複雑 vs 簡潔：強力な型システム vs 使いやすさ
マクロ vs ジェネリクス：マクロコード生成 vs ジェネリクス型安全性
値依存 vs 型安全性：従来ジェネリクスはコンパイル時に次元を検証できない

値依存型の核心的優位性

YaoXiangの値依存型は従来ジェネリクスに対する核心的優位性である：

優位性	説明
型が値に依存	`Array: (T: Type, N: Int) -> Type` により型が具体的な値に依存可能
コンパイル時評価	型位置の関数呼び出しはコンパイル時に評価され、結果が直接型に埋め込まれる
次元検証	`Matrix(Float, 3, 3)` はコンパイル時に行列次元を検証
型レベル計算	`If`、`Match`などの条件型が型レベル計算をサポート
停止性保証	コンパイル時停止性検査（RFC-027自動測度合成）によりコンパイル時評価の停止を保証

yaoxiang

# C++/Rust 无法做到的编译期验证
matrix: Matrix(Float, factorial(3), factorial(2)) = ...
# 编译期计算：factorial(3) = 6, factorial(2) = 2
# 类型为 Matrix(Float, 6, 2)

# 维度不匹配在编译期捕获
identity: Matrix(Float, 3, 3) = ...
# multiply(matrix_2x3, identity_3x3)  # 编译错误：2 != 3

ジェネリクスシステムの価値

yaoxiang

# 示例：统一API设计
# 不同容器类型的map操作

# 传统方案：每个类型单独实现
map_int_array: (array: Vec(Int), f: Fn(Int) -> Int) -> Vec(Int) = ...
map_string_array: (array: Vec(String), f: Fn(String) -> String) -> Vec(String) = ...
map_int_list: (list: List(Int), f: Fn(Int) -> Int) -> List(Int) = ...
map_string_list: (list: List(String), f: Fn(String) -> String) -> List(String) = ...

# 泛型方案：一个泛型函数覆盖所有类型
map: (T: Type, R: Type)(container: Container(T), f: Fn(T) -> R) -> Container(R) = {
    for item in container {
        result.push(f(item))
    }
    result
}

設計目標

核心目標

ゼロコスト抽象 - ジェネリクス呼び出しは具体型呼び出しと等価
デッドコード除去 - コンパイル時解析、使用されるジェネリクスのみインスタンス化
マクロ代替 - ジェネリクスがマクロ使用シーンの90%を代替
型安全性 - コンパイル時検査、実行時型オーバーヘッドなし
IDEフレンドリー - スマートヒント、明確なエラーメッセージ
値依存型 - 型が値に依存可能、コンパイル時次元検証をサポート
コンパイル時評価の安全性 - コンパイル時停止性検査（RFC-027自動測度合成）によりコンパイル時評価の停止を保証

設計原則

コンパイル時決定：ジェネリクス引数はコンパイル時に決定
単相化優先：具体コードを生成、仮想関数呼び出しを回避
制約駆動：型制約がインスタンス化を指導
プラットフォーム最適化：特化はプラットフォーム固有最適化をサポート
型宇宙統一：関数/型コンストラクタ/値依存型をType2層に統一
停止性保証：型位置の関数呼び出しは停止を証明しなければならない

提案

1. 基本ジェネリクス

1.1 ジェネリクス型引数

重要なルール：ジェネリクス型定義は明示的に: Typeを注釈しなければならない。さもないとHMによって関数として推論される。
書き方意味
List: (T: Type) -> Type = {...} ✅ 型コンストラクタ
List = {...} ❌ HMが関数として推論、型ではない

書き方	意味
`List: (T: Type) -> Type = {...}`	✅ 型コンストラクタ
`List = {...}`	❌ HMが関数として推論、型ではない

yaoxiang

# 泛型类型定义（必须有 : Type）
Option: (T: Type) -> Type = {
    some: (T) -> Self,
    none: () -> Self
}

Result: (T: Type, E: Type) -> Type = {
    ok: (T) -> Self,
    err: (E) -> Self
}

List: (T: Type) -> Type = {
    data: Vec(T),
    length: Int,
    push: (self: List(T), item: T) -> Void,   # self 只是约定名，不是关键字
    get: (self: List(T), index: Int) -> Option(T),
}

# 泛型函数（无 : Type，HM 推断为函数）
map: (T: Type, R: Type) -> ((opt: Option(T), f: Fn(T) -> R) -> Option(R)) = {
    return match opt {
        some => Option.some(f(some)),
        none => Option.none(),
    }
}

# 泛型约束（直接表达式，单行可省略 return）
clone: (T: Clone)(value: T) -> T = value.clone()

# 多类型参数
combine: (T: Type, U: Type) -> ((a: T, b: U) -> (T, U)) = (a, b)

ジェネリクス関数呼び出し構文

1.1 統一シグネチャ構文

yaoxiang

# 泛型函数使用统一的 (T: Type, R: Type) 签名语法
map: (T: Type, R: Type) -> ((list: List(T), f: (x: T) -> R) -> List(R)) = ...

# 多类型参数
combine: (T: Type, U: Type) -> ((a: T, b: U) -> (T, U)) = (a, b)

1.2 Type自己記述機構

Typeは言語レベルの特別な存在であり、コンパイラはシグネチャ中のType位置を自然に認識し、実引数型から自動的に推論・補完する。

yaoxiang

# 编译器自动推断泛型参数
numbers: List(Int) = List(Int)()
#         ^^^^^^^^   ^^^^^^^^
#         类型声明   构造调用：Int 填充 T，() 值构造

# 函数调用推断
numbers: List(Int) = List(Int)()
f: (x: Int) -> String = (x) => x.to_string()
strings: List(String) = map(numbers, f)
# 编译器推断：T=Int, R=String

1.3 単相化

yaoxiang

# 源代码
map: (T: Type, R: Type) -> ((list: List(T), f: (x: T) -> R) -> List(R)) = {
    result: List(R) = List(R)()
    for x in list {
        result.push(f(x))
    }
    return result
}

# 使用点
int_list: List(Int) = List(Int)()
doubled: List(Int) = map(int_list, (x: Int) => x * 2)  # 实例化 map[Int, Int]

string_list: List(String) = List(String)()
uppercased: List(String) = map(string_list, (s: String) => s.to_uppercase())  # 实例化 map[String, String]

# 编译后（等价代码）
map_Int_Int: (list: List(Int), f: (Int) -> Int) -> List(Int) = {
    result: List(Int) = List(Int)()
    for x in list {
        result.push(f(x))
    }
    return result
}

map_String_String: (list: List(String), f: (String) -> String) -> List(String) = {
    result: List(String) = List(String)
    for s in list {
        result.push(f(s))
    }
    return result
}

1.4 明示的な補完（推論失敗時）

yaoxiang

# 可推断时省略 Type 参数
numbers: List(Int) = List(Int)()
strings: List(String) = map(numbers, (x: Int) => x.to_string())

# 无法推断时必须显式填充
# map(numbers, (x) => x)  # ❌ Error: Cannot infer R

### 2. 型制約システム

#### 2.1 単一制約

```yaoxiang
# 基本trait定义（接口类型）
Clone: Type = {
    clone: (Self) -> Self,
}

Display: Type = {
    fmt: (Self, Formatter) -> Result,
}

Debug: Type = {
    fmt: (Self, Formatter) -> Result,
}

# 使用约束：在签名中直接声明类型约束
clone: (T: Clone) -> (value: T) -> T = value.clone()

debug_print: (T: Debug)(value: T) -> Void = {
    formatter = Formatter.new()
    value.fmt(formatter)
    print(formatter.to_string())
}

2.2 多重制約

yaoxiang

# 多重约束语法
combine: (T: Clone + Add)(a: T, b: T) -> T = {
    a.clone() + b
}

# 泛型容器的排序
sort: (T: Clone + PartialOrd)(list: List(T)) -> List(T) = {
    # 实现排序算法
    result: List(T) = list.clone()
    quicksort(&mut result)
    return result
}

# 函数类型约束
map: (T: Type, R: FnMut(T))(array: Vec(T), f: R) -> Vec(R) = {
    result: Vec(R) = Vec()
    for item in array {
        result.push(f(item))
    }
    return result
}

# 使用
doubled: Vec(Int) = map(Vec(1, 2, 3), (x: Int) => x * 2)  # 编译器推断

制約名の出典（2026-09-22注）：Add / Subtract / Multiply / Divide / Modulo などの演算子制約はRFC-011b: 演算子オーバーロードとインターフェース駆動演算子で定義・実装される—— T: Add ≜ Add(T, T, T)インターフェースインスタンス化が登録済み（3つの型引数、結果型Oは明示）。Zero / One / PartialOrd / Fn / FnMut は現在定義出典がなく、宙に浮いた制約名であり、後続のRFCで個別に実装される予定；それまでは、これらの名前を含む例は紙面上の概念図である。

2.3 関数型制約

yaoxiang

# 高阶函数约束
call_twice: (T: Type, F: Fn() -> T)(f: F) -> (T, T) = (f(), f())

call_with_arg: (T: Type, U: Type, F: Fn(T) -> U)(arg: T, f: F) -> U = f(arg)

compose: (A: Type, B: Type, C: Type, F: Fn(A) -> B, G: Fn(B) -> C)(a: A, f: F, g: G) -> C = g(f(a))

# 使用示例
result: Int = call_with_arg(42, (x: Int) => x * 2)  # result = 84
composed: String = compose(
    "hello",
    (s: String) => s.to_uppercase(),
    (s: String) => s + " WORLD"
)  # composed = "HELLO WORLD"

2.4 組み込みマーカートレイト：DupとClone

3種類のコピーセマンティクス：

型	意味	トリガー方法	適用シーン
プリミティブ値コピー	代入時に自動値コピー、2つの値は完全に独立	代入/引数渡し自動	Int, Float, Bool, Char
Dup	シャローコピー：ハンドル/トークンをコピー、基盤データは共有	代入/引数渡し自動	`&T`トークン、`ref T`、String/Bytes
Clone	ディープコピー：完全独立した複製を作成	`value.clone()`	Cloneを実装する任意の型

Dupのセマンティクス：Dupを実装する型は、代入/引数渡し時に所有権を移転しない——コンパイラがハンドル/トークンをコピーし、複数の保持者が同じ基盤データを指す。これはRFC-009所有権モデルにおけるMoveデフォルトセマンティクスの補完関係にある。

DupとCloneは直交する概念：

Dup = ハンドルをコピー、データを共有（変更は相互に影響）
Clone = データをコピー、コピーは独立（変更は相互に影響しない）

ルール：

1. プリミティブ値型（Int, Float, Bool, Char） — コンパイラ組み込み値コピー、Dupではない
2. Dup  — 参照/トークン型と内部参照カウント型にのみ適用
3. Clone — 明示的ディープコピー、任意の型が実装可能
4. デフォルトMove — 他の型はデフォルトMoveセマンティクスを維持

どの型がDupか：

型	Dup	理由
`&T`（借用トークン）	✅	ゼロサイズトークン、トークンコピー = 複数のビューが同じデータを指す
`ref T`	✅	Rc/Arcコピー = 参照カウント+1、ヒープデータを共有
String, Bytes	✅	内部参照カウント、ハンドルをコピーして基盤バッファを共有
`&mut T`（可変トークン）	❌	線形排他、コピー不可
struct	派生	全フィールドDup → struct Dup
enum	派生	全バリアントの全フィールドDup → enum Dup
tuple	派生	全要素Dup → tuple Dup
Fn（クロージャ）	❌	キャプチャ環境がDupでない可能性あり
`*T`（生ポインタ）	❌	unsafe、所有権システムに参加しない

Int/Float/Bool/CharはDupではない——これらは値型であり、代入時にコンパイラが自動的に値コピーする（2つの値は完全に独立）。これは「シャローコピー」ではなく、プリミティブに対するコンパイラ組み込み処理であり、Dup型属性を通じて表現する必要はないし、すべきでもない。

yaoxiang

# 原语值类型：编译器自动值复制（不是 Dup）
x: Int = 42
y = x          # 值复制，x 和 y 完全独立
print(x)       # ✅

# Dup：浅拷贝，复制句柄共享数据
view: &Point = &point
view2 = view    # ✅ Dup：复制令牌，两者指向同一个 point
print(view.x)   # ✅

# Clone：显式深拷贝，创建独立副本
backup = big_struct.clone()  # 显式调用

# 泛型约束
dup_use: (T: Dup) -> T = x         # T: Dup → 可以浅拷贝
clone_use: (T: Clone) -> T = x.clone()  # T: Clone → 可以深拷贝

注意：Send/Syncはユーザー可視トレイトではない。タスク横断安全保証はref キーワードとコンパイラ全自動処理によって行われる——refは自動的にRcまたはArcを選択し、ユーザーはSend/Syncを理解する必要がない。

3. 関連型

3.1 関連型定義

yaoxiang

# Iterator trait（使用 (Item: Type) -> Type 语法）
Iterator: (Item: Type) -> Type = {
    next: (Self) -> Option(Item),
    has_next: (Self) -> Bool,
    collect: (T: Type)(Self) -> List(T),
}

# 使用
collect_all: (T: Type, I: Iterator(T))(iter: I) -> List(T) = {
    result: List(T) = List(T)
    while iter.has_next() {
        if let Some(item) = iter.next() {
            result.push(item)
        }
    }
    return result
}

# Vec的Iterator实现
# 使用方法语法糖：Vec.Item, Vec.next, Vec.has_next
# 迭代位置由包装记录携带（Vec 本身是原始缓冲，无 index 字段）
VecIter: (T: Type) -> Type = {
    data: &Vec(T),
    index: Int,
}

VecIter.has_next: (T: Type)(self: &VecIter(T)) -> Bool = {
    return self.index < self.data.length
}

VecIter.next: (T: Type)(self: &mut VecIter(T)) -> Option(T) = {
    if self.index < self.data.length {
        item = self.data[self.index]
        self.index = self.index + 1
        return Option.some(item)
    } else {
        return Option.none()
    }
}

VecIter.Item: (T: Type)(arr: &VecIter(T)) -> T = {
    return arr.data[arr.index]
}

3.2 ジェネリクス関連型（GAT）

yaoxiang

# 更复杂的关联类型
Producer: (Item: Type) -> Type = {
    Item: T,
    produce: (Self) -> Option(Item),
}

# 关联类型可以是泛型的
Container: (Item: Type) -> Type = {
    Item: T,
    IteratorType: Iterator(Item),  # 关联类型也是泛型的
    iter: (Self) -> IteratorType,
}

# 使用
process_container: (T: Type, C: Container(T))(container: C) -> List(T) = {
    container.iter().collect()
}

4. コンパイル時ジェネリクス

4.1 コンパイル時値引数

核心設計：ジェネリクスシグネチャ中のTypeは型引数をマークする；具体型（Int/Bool/Float

など）で注釈された引数リストはコンパイル時値引数の候補であり、コンパイル時値引数になるかどうかは値が型位置で参照されているか（値依存）による。constキーワードは不要。

判定基準は型位置で参照されているかであり、「具体型で注釈されているか」ではない：add: (a: Int, b: Int) -> Int = a + b においてa/bは実行時値引数である。両者が型位置に現れないため。

判定ルール（2ステップ）：

形態粗選別：引数が非Typeの具体型（例：Int）で注釈されている → 候補に挙げる。
用途精選別：候補名が型位置（型本体フィールド型、内側Fn引数型、Assert

述語、Array(T, N)などの型コンストラクタ実引数位置）に現れる → コンパイル時値引数として確認；そうでない場合は実行時値引数と見なす。

書き方	判定	理由
`add: (a: Int, b: Int) -> Int = a + b`	a/b 実行時値引数	値位置にのみ出現、型構築に参加しない
`Array: (T: Type, N: Int) -> Type = { data: Array(T, N) }`	N コンパイル時値引数	N が`Array(T, N)`の型コンストラクタ実引数位置に現れる
`factorial: (N: Int) -> (k: N) -> Int`	N コンパイル時値引数	N が内側引数`k`の型として機能
`Foo: (T: Type, N: Int) -> Type = { x: T }`	N 落空（下記参照）	N が型本体で参照されていない、実行時値引数に退化

値依存の本質：コンパイル時値引数＝値依存型——値が型を構築するために使用される場合にのみ、コンパイル時の決定が必要。形態（: Int）は候補資格を決定し、用途（型位置に出現）がコンパイル時値引数かどうかを決定する。これは§「コンパイル時決定性保証」における「型位置の関数呼び出しはコンパイル時に評価される」と同じ根本的判定基準である。

yaoxiang

# ════════════════════════════════════════════════════════
# 编译期值参数：N 在类型位置（Measure 长度槽）被引用
# ════════════════════════════════════════════════════════
Measure: (T: Type, N: Int) -> Type = {
    data: Array(T, N),  # N 出现在类型构造实参位 → 编译期值参数
    length: N,
}

# 使用方式：factorial(5) 在类型位置求值（编译期），结果 120 嵌入类型
m: Measure(Int, factorial(5))  # Measure(Int, 120)

# ════════════════════════════════════════════════════════
# 值依赖：N 作为内层参数 k 的类型
# ════════════════════════════════════════════════════════
# N 是编译期值参数（出现在 (k: N) 的类型位）；
# k 是运行时值参数，其类型为字面量类型 N（单值类型）。
factorial: (N: Int) -> (k: N) -> Int = {
    return match k {
        0 => 1,
        _ => k * factorial(k - 1)
    }
}

落空候補の処理：具体型で注釈されているが型位置で参照されていない候補（上の表のFooの Nなど）は実行時値引数（関数レベルパス）に退化する。型コンストラクタパスの落空候補は実行時スロットを占有できず（型コンストラクタはコンパイル時に評価される）、宣言側で直接エラー[E1094]を報告する：「Nはコンパイル時値引数として宣言されているが、型本体で参照されていない」——以前は静かに破棄されており、インスタンス化arityの不一致を引き起こしていた。

4.2 コンパイル時計算

yaoxiang

# ════════════════════════════════════════════════════════
# 编译期计算示例
# ════════════════════════════════════════════════════════

# 编译器在编译期计算字面量类型的函数调用
SIZE: Int = factorial(5)  # 编译期为 120

# 矩阵类型使用
Matrix: (T: Type, Rows: Int, Cols: Int) -> Type = {
    data: Array(Array(T, Cols), Rows),
}

# 编译期维度验证
identity_matrix: (T: Add + Zero + One, N: Int)(size: N) -> Matrix(T, N, N) = {
    matrix: Matrix(T, N, N) = Matrix(T, N, N)()
    for i in 0..size {
        for j in 0..size {
            if i == j {
                matrix.data[i][j] = One::one()
            } else {
                matrix.data[i][j] = Zero::zero()
            }
        }
    }
    matrix
}

# 使用：编译期计算，生成 Matrix(Float, 3, 3)
identity_3x3: Matrix(Float, 3, 3) = identity_matrix(Float, 3)(3)

NeverとVoid：型システムの⊥と⊤

YaoXiangの型システムは、Curry-Howard同型対応において⊥（偽/空型）と⊤（真/Unit）の両方を備え、Neverと Voidの2つの組み込み型名で担う：

Never（⊥） — 交渉不可能な3つの内核的性質：

ゼロコンストラクタ：Never型の値を生成するリテラルや式は一切ない。これはメタレベル性質であり、組み込みでなければならない。
爆発原理：Never <: Tは任意の型Tに対して成立する。Never値は任意の型として使用できる——これが assert(false)の後のコードが型検査を通る理由である（決してそこに到達しないが）。
発散マーカー：f: (...) -> Neverはfが戻らないことを保証する。コンパイラはこれに基づいてdead code解析を行う。

Neverは組み込み型名であり、キーワードではないためパーサは感知しない。空和型リテラル構文は開放しない。

Void（⊤、すなわちUnit） — ちょうど1つの居住者（デフォルトvoid値）を持ち、真命題「恒真」の担い手である。Void はゼロフィールド積型の単位元であり、Neverはゼロバリアント和型の単位元である——両者は双対である。x: Void = <デフォルト> は合法、x: Never = ...は右辺に書けるものがない。

4.3 コンパイル時検証（標準ライブラリ実装）

yaoxiang

# ════════════════════════════════════════════════════════
# 标准库实现：利用条件类型
# ════════════════════════════════════════════════════════

# 标准库定义
# IsTrue：值宇宙到类型宇宙的桥——Bool 真值映射为类型
IsTrue: (b: Bool) -> Type = match b {
    true => Void,      # ⊤，有值，程序继续
    false => Never,    # ⊥，无值，发散
}

# Assert：编译期精化类型原语——对 Bool 命题的类型级表述
Assert: (cond: Bool) -> Type = IsTrue(cond)
#
# cond 为 true  → Assert(true)  = Void    （恒真，擦除）
# cond 为 false → Assert(false) = Never   （恒假，编译错误/发散）
# cond 判不了   → 由证明管道按 dispatch 模式决定：
#                  CompileTime → Unknown，要求 prove
#                  Runtime     → 插入 check，注入 Γ 假设

# 使用方式1：在类型定义中作为约束
Bounded: (T: Type, N: Int) -> Type = {
    data: Array(T, N),
    # 编译期检查：N 必须大于 0（Assert 在类型位置）
    length: Assert(N > 0),
}

# 使用方式2：在表达式中使用
IntArray: (N: Int) -> Type = Array(Int, N)
# 验证：IntArray(10) 的大小等于 sizeof(Int) * 10
Assert(size_of(IntArray(10)) == sizeof(Int) * 10)

4.4 コンパイル時ジェネリクス特化

yaoxiang

# 小数组优化：使用函数重载实现编译期泛型特化

# 通用实现
sum: (T: Type, N: Int) -> ((arr: Array(T, N)) -> T) = {
    result = Zero::zero()
    for item in arr.data {
        result = result + item
    }
    return result
}

# N=1 特化
sum: (T: Type) -> ((arr: Array(T, 1)) -> T) = arr.data[0]

# N=2 特化
sum: (T: Type) -> ((arr: Array(T, 2)) -> T) = arr.data[0] + arr.data[1]

# 小数组循环展开（N <= 4）
sum: (T: Type, N: Int) -> ((arr: Array(T, N)) -> T) = {
    # 编译器优化：展开循环
    return arr.data[0] + arr.data[1] + arr.data[2] + arr.data[3]
}

5. 条件型

Curry-Howard同型対応：条件型をCurry-Howardの視点で見ると、論理におけるcase分析である。Bool 型は2つの可能な値（True/False）を持つ命題に対応し、If はその命題の真偽に応じて異なる結果を選択する——これはまさに論理におけるcase分解である。match C { True => T, False => E } は実際には「命題CがTrueの場合の結論はT、CがFalseの場合の結論はE」を表現している。

5.1 If条件型

yaoxiang

# 类型级If
If: (C: Bool, T: Type, E: Type) -> Type = match C {
    True => T,
    False => E,
}

# 示例：编译期分支
NonEmpty: (T: Type) -> Type = If(T != Void, T, Never)

Optional: (T: Type) -> Type = If(T != Void, T, Void)

# 编译期验证（统一到 §4.3 的 Assert 定义）
# Assert: (cond: Bool) -> Type = IsTrue(cond)

# 使用
# 类型计算：If(True, Int, String) => Int
# 类型计算：If(False, Int, String) => String

5.2 型族

Curry-Howard同型対応：型族は「命題即型」の最も直接的な体現である。Add: (A: Type, B: Type) -> Type は「型レベルで加法関数を書いた」のではなく、自然数加算に関する命題を構成している。(Zero, B) => B は「命題Add(Zero, B)はBと等価である」と言い、(Succ(A'), B) => Succ(Add(A', B))は「Add(A', B)が成立するなら、Add(Succ(A'), B)も成立する」と言う。これはPeano公理における加法定義そのものである。型検査器がこのmatch式の通過を検証することは、この定義の論理的一貫性を検証することと等価である。

yaoxiang

# 编译期类型转换
AsString: (T: Type) -> Type = match T {
    Int => String,
    Float => String,
    Bool => String,
    _ => String,  # 默认
}

# 类型级计算
Length: (T: Type) -> Type = match T.length {
    0 => Zero,
    1 => Succ(Zero),
    2 => Succ(Succ(Zero)),
    _ => TooLong,
}

# 类型级加法（Curry-Howard：case analysis + 递归调用，需要终止性检查才是完整归纳）
Add: (A: Type, B: Type) -> Type = match (A, B) {
    (Zero, B) => B,
    (Succ(A'), B) => Succ(Add(A', B)),
}

# 示例：编译期计算 2 + 3
Two: Type = Succ(Succ(Zero))
Three: Type = Succ(Succ(Succ(Zero)))
Five: Type = Add[Two, Three]  # Succ(Succ(Succ(Succ(Succ(Zero)))))

6. 関数オーバーロード特化

6.1 基本特化

yaoxiang

# 基本特化：使用函数重载（编译器自动选择）
sum: (arr: Vec(Int)) -> Int = {
    # 编译为更高效的代码
    return native_sum_int(arr.data, arr.length)
}

sum: (arr: Vec(Float)) -> Float = {
    # 使用SIMD指令
    return simd_sum_float(arr.data, arr.length)
}

# 通用实现
sum: (T: Type) -> ((arr: Vec(T)) -> T) = {
    result = Zero::zero()
    for item in arr {
        result = result + item
    }
    return result
}

6.2 条件特化

yaoxiang

# 完全符合RFC-010语法的特化方式：函数重载

# 具体类型特化
sum: (arr: Vec(Int)) -> Int = {
    return native_sum_int(arr.data, arr.length)
}

sum: (arr: Vec(Float)) -> Float = {
    return simd_sum_float(arr.data, arr.length)
}

# 泛型实现（编译器自动选择最优）
sum: (T: Type) -> ((arr: Vec(T)) -> T) = {
    result = Zero::zero()
    for item in arr {
        result = result + item
    }
    return result
}

# 使用时完全透明
int_arr = Vec(Int)(1, 2, 3)
float_arr = Vec(Float)(1.0, 2.0, 3.0)

# 编译器自动选择最优特化
sum(int_arr)     # 选择 sum: (Vec(Int)) -> Int
sum(float_arr)    # 选择 sum: (Vec(Float)) -> Float

6.3 関数オーバーロードとインラインの完璧な結合

重要な特性：関数オーバーロードとインライン最適化は自然に結合し、ゼロコスト抽象を実現する。

yaoxiang

# ======== 源代码 ========
sum: (arr: Vec(Int)) -> Int = {
    return native_sum_int(arr.data, arr.length)
}

sum: (arr: Vec(Float)) -> Float = {
    return simd_sum_float(arr.data, arr.length)
}

sum: (T: Type) -> ((arr: Vec(T)) -> T) = {
    result = Zero::zero()
    for item in arr {
        result = result + item
    }
    return result
}

# 使用
int_arr = Vec(Int)(1, 2, 3, 4, 5)
result = sum(int_arr)

# ======== 编译后（等价代码）=======
# 编译器自动选择最优特化，然后内联
result = native_sum_int(int_arr.data, int_arr.length)

# 完全等价于手写优化代码，无函数调用开销！

核心的優位性：

コンパイラのスマート選択

yaoxiang

sum(int_arr)      # 自动选择 sum: (Vec(Int)) -> Int
sum(float_arr)    # 自动选择 sum: (Vec(Float)) -> Float
sum(custom_arr)  # 自动选择 sum: (T: Type) -> ((arr: Vec(T)) -> T)

インライン最適化
- 小さな関数は呼び出し点に自動インライン化
- 関数呼び出しオーバーヘッドゼロ
- 手書き最適化コードと完全に等価
型安全性
- コンパイル時型検査
- 実行時オーバーヘッドゼロ
- 仮想関数テーブル不要

RFC-010との完璧な適合

yaoxiang

# 完全使用统一语法
name: type = value
# 无需impl、where等新关键字

実際の応用例：

yaoxiang

# 性能敏感的数值计算
fibonacci: (n: Int) -> Int = {
    if n <= 1 { return n }
    return fibonacci(n - 1) + fibonacci(n - 2)
}

fibonacci: (n: Float) -> Float = {
    # 使用Binet公式
    phi = (1.0 + 5.0.sqrt()) / 2.0
    return (phi.pow(n) - (-phi).pow(-n)) / 5.0.sqrt()
}

# 编译器自动选择并内联
fibonacci(10)      # 选择 Int 版本，完全内联
fibonacci(10.5)    # 选择 Float 版本，使用Binet公式

これは何を意味するか？

✅ ジェネリクス特化 → 関数オーバーロードで自然に解決
✅ パフォーマンス最適化 → インラインが自動完了
✅ コード再利用 → 1つの関数名で複数の実装
✅ ゼロコスト抽象 → コンパイル時多態、実行時オーバーヘッドゼロ
✅ 新キーワード不要 → RFC-010統一構文に完璧に適合


### 7. デッドコード除去メカニズム

#### 7.1 インスタンス化グラフ解析

```rust
// 编译器内部：构建泛型实例化依赖图
struct InstantiationGraph {
    // 节点：泛型实例化
    nodes: HashMap<InstanceKey, InstanceNode>,

    // 边：使用关系
    edges: HashMap<InstanceKey, Vec<InstanceKey>>,
}

struct InstanceKey {
    generic: FunctionId,  // 泛型函数ID
    type_args: Vec<TypeId>,  // 类型参数
    const_args: Vec<ConstId>,  // Const参数
}

// 算法：可达性分析
fn eliminate_dead_instantiations(graph: &InstantiationGraph) {
    let mut reachable = HashSet::new();

    // 从入口点开始（main、导出函数等）
    let entry_points = find_entry_points();
    for entry in entry_points {
        dfs_visit(entry, &graph, &mut reachable);
    }

    // 未访问的实例化就是死代码
    for node in &graph.nodes {
        if !reachable.contains(node.key) {
            eliminate(node);
        }
    }
}

7.2 使用点解析

yaoxiang

# 源代码分析
map: (T: Type, R: Type)(list: List(T), f: Fn(T) -> R) -> List(R) = ...

# 使用点1：实例化 map(Int, Int)
int_list = List(Int)()
int_list.push(1)
int_list.push(2)
int_list.push(3)
doubled = map(int_list, (x) => x * 2)  # 需要 map[Int, Int]

# 使用点2：实例化 map(String, String)
string_list = List(String)()
string_list.push("a")
string_list.push("b")
string_list.push("c")
uppercased = map(string_list, (s) => s.to_uppercase())  # 需要 map[String, String]

# 未使用：map[Float, Float] 等
# 这些泛型实例不会被生成

# 编译后只包含被使用的实例
map_Int_Int: (list: List(Int), f: Fn(Int) -> Int) -> List(Int) = ...
map_String_String: (list: List(String), f: Fn(String) -> String) -> List(String) = ...

7.3 コンパイル時ジェネリクスDCE

yaoxiang

# 编译期分析：编译期泛型使用情况
Array: (T: Type, N: Int) -> Type = {
    data: Array(T, N),
}

# 实际使用情况
arr_10_int = Array(Int, 10)(data=[1, 2, 3, 4, 5, 6, 7, 8, 9, 10])  # 两层：类型参数 + 构造参数
arr_100_int = Array(Int, 100)()   # 空构造，数据事后赋值

# 编译后只生成被使用的Size
Array_Int_10: (Array(Int, 10)) = ...
Array_Int_100: (Array(Int, 100)) = ...

# 未使用的Size不会生成
# Array(Int, 50) 不会生成

7.4 モジュール間DCE

yaoxiang

# 模块A
# A.yx
pub map: (T: Type, R: Type)(list: List(T), f: Fn(T) -> R) -> List(R) = ...

# 模块B
# B.yx
use A.{map}
int_list = List(Int)()
int_list.push(1)
int_list.push(2)
int_list.push(3)
doubled = map(int_list, (x) => x * 2)  # 实例化 map(Int, Int)

# 模块C
# C.yx
use A.{map}
string_list = List(String)()
string_list.push("a")
string_list.push("b")
string_list.push("c")
uppercased = map(string_list, (s) => s.to_uppercase())  # 实例化 map(String, String)

# 编译分析：
# - 模块B使用 map[Int, Int]
# - 模块C使用 map[String, String]
# - 编译后二进制只包含这两个实例

7.5 LLVMレベルDCE

rust

// 编译流水线
fn optimize_ir(ir: &mut IR) {
    // 1. 单态化（YaoXiang编译器）
    ir.monomorphize();

    // 2. 内联优化
    ir.inline_small_functions();

    // 3. 常量传播
    ir.constant_propagation();

    // 4. 生成LLVM IR
    let llvm_ir = ir.to_llvm();

    // 5. LLVM优化pass
    llvm_ir.add_pass(Passes::DEAD_CODE_ELIMINATION);
    llvm_ir.add_pass(Passes::INLINE_FUNCTION);
    llvm_ir.add_pass(Passes::GLOBAL_DCE);
    llvm_ir.add_pass(Passes::MERGE_FUNC);

    // 6. 运行优化
    llvm_ir.run_optimization_passes();
}

8. マクロ代替戦略

8.1 コード生成代替

yaoxiang

# ❌ 宏方案：代码生成
macro_rules! impl_debug {
    ($($t:ty),*) => {
        $(impl Debug for $t {
            fn fmt(&self, f: &mut Formatter) -> Result {
                write!(f, "{:?}", self)
            }
        })*
    };
}

# ✅ 泛型方案：自动派生
# 使用函数重载方式自动派生
debug_fmt: (T: fields...) -> ((self: Point(T)) -> String) = {
    return "Point { x: " + self.x.to_string() + ", y: " + self.y.to_string() + " }"
}

# 使用
p = Point { x: 1, y: 2 }
p.debug_fmt(&formatter)  # 自动生成调用

8.2 DSL代替

yaoxiang

# ❌ 宏方案：HTML DSL
html! {
    <div class="container">
        <h1> { title } </h1>
        <ul>
            { for item in items {
                <li> { item } </li>
            }}
        </ul>
    </div>
}

# ✅ 泛型方案：类型安全构建器
Element: Type = {
    tag: String,
    attrs: HashMap(String, String),
    children: List(Element),
    text: Option(String),
}

create_element: (tag: String) -> Element = {
    return Element(tag, HashMap::new(), List::new(), None)
}

with_class: [E: Element](elem: E, class: String) -> E = {
    elem.attrs.insert("class", class)
    return elem
}

with_text: [E: Element](elem: E, text: String) -> E = {
    return E { text: Some(text), ..elem }
}

# 构建DOM
container = create_element("div")
    |> with_class("container")
    |> with_children(List::new())

title_elem = create_element("h1") |> with_text(title)
items_li = items.map((item) =>
    create_element("li") |> with_text(item)
)
root = container |> with_children(List::new() + [title_elem, ul_elem])

8.3 型レベルプログラミング代替

yaoxiang

# ❌ 宏方案：类型级计算
macro_rules! add_types {
    ($a:ty, $b:ty) => {
        ($a, $b)
    };
}

# ✅ 泛型方案：条件类型
Add: (A: Type, B: Type) -> Type = match (A, B) {
    (Int, Int) => Int,
    (Float, Float) => Float,
    (Int, Float) => Float,
    (Float, Int) => Float,
    _ => TypeError,
}

# 编译期验证
AssertAddable: (A: Type, B: Type) -> Type = If(Add(A, B) != TypeError, (A, B), compile_error("Cannot add"))

# 使用
result_type = Add[Int, Float]  # 推导为 Float

RFC-011bとの関係（2026-09-22注）：本節のリフティング型族Add(A, B)は RFC-011b演算子インターフェース登録テーブルの型レベル視点に他ならない——核登録 Add(Int, Float, Float)と本表の(Int, Float) => Float は同じルールであり、ユーザーのインターフェースインスタンス化は毎回このテーブルへの行追加である。§5.2のPeano型レベルAdd は純粋に型レベルの計算（同名で別物）であり、値レベルの演算子インターフェースと互いに干渉しない——演算子クエリは登録テーブルを実装し、名前解析を経由しない。

9. 例

9.1 完全なジェネリクスコンテナ例

yaoxiang

# ======== 1. 定义泛型容器 ========
# 使用 (T: Type) -> Type 语法
Result: (T: Type, E: Type) -> Type = {
    ok: (T) -> Self,
    err: (E) -> Self,
}

Option: (T: Type) -> Type = {
    some: (T) -> Self,
    none: () -> Self,
}

List: (T: Type) -> Type = {
    data: Vec(T),
    length: Int,

    # 泛型方法（T 由外层 List(T) 自动带入作用域）
    push: (self: List(T), item: T) -> Void,
    pop: (self: List(T)) -> Option(T),
    map: (R: Type) -> ((self: List(T), f: (T) -> R) -> List(R)),
    filter: (self: List(T), predicate: (T) -> Bool) -> List(T),
    fold: (U: Type) -> ((self: List(T), initial: U, f: (U, T) -> U) -> U),
}

# ======== 2. 实现泛型方法 ========
# 函数定义在 List 命名空间下（List. 前缀 = 命名空间归属）
# 要让 list.push(item) 这种 . 调用语法生效，需要显式绑定：List.push = push[0]
# self 只是约定参数名，编译器不看名字看类型

List.push: (T: Type) -> ((self: List(T), item: T) -> Void) = {
    if self.length >= self.data.length {
        # 扩容
        new_data = Vec(T)(len=self.data.length * 2)
        for i in 0..self.length {
            new_data[i] = self.data[i]
        }
        self.data = new_data
    }
    self.data[self.length] = item
    self.length = self.length + 1
}

List.pop: (T: Type) -> ((self: List(T)) -> Option(T)) = {
    if self.length > 0 {
        self.length = self.length - 1
        return Option.some(self.data[self.length])
    } else {
        return Option.none()
    }
}

List.map: (T: Type, R: Type) -> ((self: List(T), f: (T) -> R) -> List(R)) = {
    result = List(R)()
    for i in 0..self.length {
        result.push(f(self.data[i]))
    }
    return result
}

List.filter: (T: Type) -> ((self: List(T), predicate: (T) -> Bool) -> List(T)) = {
    result = List(T)()
    for i in 0..self.length {
        if predicate(self.data[i]) {
            result.push(self.data[i])
        }
    }
    return result
}

List.fold: (T: Type, U: Type) -> ((self: List(T), initial: U, f: (U, T) -> U) -> U) = {
    result = initial
    for i in 0..self.length {
        result = f(result, self.data[i])
    }
    return result
}

# ======== 3. 类型约束使用 ========
# 实现 Clone for List
List.clone: (T: Clone) -> ((self: List(T)) -> List(T)) = {
    result = List(T)()
    for i in 0..self.length {
        result.push(self.data[i].clone())
    }
    return result
}

# ======== 4. 使用示例 ========
# 创建泛型List
numbers = List(Int)()
numbers.push(1)
numbers.push(2)
numbers.push(3)

# 使用泛型方法
doubled = numbers.map((x) => x * 2)
evens = numbers.filter((x) => x % 2 == 0)

# 使用fold计算
sum = numbers.fold(0, (acc, x) => acc + x)  # sum = 6

# 泛型组合
sum_of_evens = numbers
    .filter((x) => x % 2 == 0)
    .map((x) => x * 2)
    .fold(0, (acc, x) => acc + x)  # sum_of_evens = 8

9.2 ジェネリクスアルゴリズム例

yaoxiang

# ======== 1. 泛型排序算法 ========
Comparator: (T: Type) -> Type = {
    compare: (T, T) -> Int,  # -1 if a < b, 0 if a == b, 1 if a > b
}

# 泛型quicksort
quicksort: (T: Clone) -> ((array: Vec(T), cmp: Comparator(T)) -> Vec(T)) = {
    if array.length <= 1 {
        return array.clone()
    }

    pivot = array[array.length / 2]
    left = Vec(T)()
    right = Vec(T)()

    for i in 0..array.length {
        if i == array.length / 2 {
            continue
        }
        item = array[i]
        comparison = cmp.compare(item, pivot)
        if comparison < 0 {
            left.push(item)
        } else {
            right.push(item)
        }
    }

    sorted_left = quicksort(left, cmp)
    sorted_right = quicksort(right, cmp)

    result = sorted_left.clone()
    result.push(pivot)
    result.extend(sorted_right)
    return result
}

# ======== 2. IntComparator实现 ========
# 使用函数重载实现
compare: (a: Int, b: Int) -> Int = {
    if a < b {
        return -1
    } else if a > b {
        return 1
    } else {
        return 0
    }
}

# ======== 3. 使用示例 ========
# 排序Int数组
numbers = Vec(Int)(3, 1, 4, 1, 5, 9, 2, 6)
sorted = quicksort(numbers, Comparator(Int)())

# 排序String数组（需要StringComparator）
strings = Vec(String)("hello", "world", "foo", "bar")
sorted_strings = quicksort(strings, Comparator(String)())

9.3 コンパイル時ジェネリクス例

yaoxiang

# ======== 1. 编译期矩阵类型 ========
Matrix: (T: Type, Rows: Int, Cols: Int) -> Type = {
    data: Array(Array(T, Cols), Rows),

    # 编译期维度验证：利用 Assert 标准库类型
    _assert: Assert(Rows > 0),  # Rows > 0，否则编译错误
    _assert: Assert(Cols > 0),  # Cols > 0，否则编译错误

    # 矩阵运算
    multiply: (M: Int) -> ((self: Matrix(T, Rows, Cols), other: Matrix(T, Cols, M)) -> Matrix(T, Rows, M)) = {
        result = Matrix(T, Rows, M)()
        for i in 0..Rows {
            for j in 0..M {
                sum = Zero::zero()
                for k in 0..Cols {
                    sum = sum + self.data[i][k] * other.data[k][j]
                }
                result.data[i][j] = sum
            }
        }
        return result
    }
}

# ======== 2. 编译期矩阵创建 ========
identity: (T: Add + Multiply + One, N: Int) -> ((size: N) -> Matrix(T, N, N)) = {
    matrix = Matrix(T, N, N)()
    for i in 0..N {
        for j in 0..N {
            if i == j {
                matrix.data[i][j] = One::one()
            } else {
                matrix.data[i][j] = Zero::zero()
            }
        }
    }
    return matrix
}

# ======== 3. 使用示例 ========
# 创建编译期已知大小的矩阵
# 2x3 矩阵
matrix_2x3 = Matrix(Float, 2, 3)()
matrix_2x3.data[0][0] = 1.0
matrix_2x3.data[0][1] = 2.0
matrix_2x3.data[0][2] = 3.0
matrix_2x3.data[1][0] = 4.0
matrix_2x3.data[1][1] = 5.0
matrix_2x3.data[1][2] = 6.0

# 3x2 矩阵
matrix_3x2 = Matrix(Float, 3, 2)()
matrix_3x2.data[0][0] = 7.0
matrix_3x2.data[0][1] = 8.0
matrix_3x2.data[1][0] = 9.0
matrix_3x2.data[1][1] = 10.0
matrix_3x2.data[2][0] = 11.0
matrix_3x2.data[2][1] = 12.0

# 矩阵乘法：2x3 * 3x2 = 2x2
result = matrix_2x3.multiply(matrix_3x2)

# 编译期验证：result类型为 Matrix(Float, 2, 2)
# 2x2 单位矩阵
identity_3x3 = identity(Float, 3)()

# 维度不匹配：编译错误
# bad_multiply = matrix_2x3.multiply(identity_3x3)  # 编译错误：3x3 != 2x3

トレードオフ

利点

ゼロコスト抽象
- コンパイル時単相化、実行時オーバーヘッドなし
- 仮想関数不要、RTTI不要
デッドコード除去
- コンパイル時解析、使用されるジェネリクスのみインスタンス化
- コード膨張が制御可能
マクロ代替
- 型安全なコード生成
- IDEフレンドリー、明確なエラーメッセージ
コンパイル時計算
- コンパイル時ジェネリクスがコンパイル時計算をサポート
- 次元検証などの機能
- constキーワード不要、純粋な型制約

欠点

コンパイル時間
- ジェネリクスインスタンス化がコンパイル時間を増加
- 制約解決が遅くなる可能性
メモリ使用量
- コンパイラのメモリ使用量が増加
- キャッシュ機構にメモリが必要
実装の複雑さ
- 制約ソルバーが複雑
- 型レベル計算エンジンが複雑
エラー診断
- ジェネリクスエラーが複雑になる可能性
- 明確なエラーヒントが必要

緩和策

キャッシュ戦略
- インスタンス化結果のキャッシュ
- LRUキャッシュによるメモリ制限
増分コンパイル
- コンパイル結果のキャッシュ
- 増分インスタンス化
エラーヒント
- 明確なエラーメッセージ
- ジェネリクス引数推論のヒント
並列コンパイル
- ジェネリクスの並列インスタンス化
- マルチスレッド制約解決

代替案

案	選択しない理由
基本ジェネリクスのみ	複雑なマクロを代替できない
純粋マクロシステム	型安全性なし、エラーメッセージが悪い
依存制約のみ	柔軟性不足
実行時ジェネリクス	パフォーマンスオーバーヘッドあり

リスク

リスク	影響	緩和策
制約解決の複雑さ	コンパイル時間が長すぎる	増分解決 + キャッシュ
コード膨張	バイナリファイルが大きすぎる	DCE + 閾値制御
実装の複雑さ	開発期間の延長	段階的実装
エラー診断	ユーザーエクスペリエンスが悪い	詳細なエラーメッセージ

オープンな問題

未決議問題

議題	説明	状態
インスタンス化戦略	Eager vs Lazy vs Threshold	議論待ち
キャッシュサイズ	LRUキャッシュ容量設定	議論待ち
エラー診断	ジェネリクスエラーメッセージの詳細度	議論待ち

後続最適化

最適化項目	価値	実装難易度
インスタンス化グラフ解析	高	中
型レベルプログラミングDSL	中	高
ジェネリクスパフォーマンスベンチマーク	中	低

付録

構文BNF

bnf

# 泛型参数使用统一 () 语法，作为函数类型的一部分
# 如 map: (T: Type, R: Type) -> ((list: List(T), f: (T) -> R) -> List(R))

# 类型约束（在泛型参数中）
type_bound ::= identifier
             | identifier '+' identifier ('+' identifier)*

# 参数声明（类型 + 名字）
parameter ::= identifier ':' type

parameters ::= parameter (',' parameter)*

# 函数声明：name: type = expression
# 泛型参数是函数类型中的第一个参数组：(T: Type) -> ((params) -> return)
function ::= identifier ':' type '=' (expression | block)

# 方法声明：Type.method: type = expression
method ::= identifier '.' identifier ':' type '=' (expression | block)

# 类型定义（统一 Binding 语法）
# 泛型类型如 List: (T: Type) -> Type = { ... }
generic_type ::= identifier ':' type '=' type_expression

# 泛型参数中的 Type 由编译器自动从实参类型填充
# 如 map(numbers, f)，T 从 numbers: List(Int) 提取，R 从 f: (Int) -> String 提取

ライフサイクルと帰結

┌─────────────┐
│   草案      │  ← 現在の状態
└──────┬──────┘
       │
       ▼
┌─────────────┐
│  レビュー中     │  ← オープンなコミュニティ議論とフィードバック
└──────┬──────┘
       │
       ├──────────────────┐
       ▼                  ▼
┌─────────────┐    ┌─────────────┐
│  承認済み     │    │  拒否済み     │
└──────┬──────┘    └──────┬──────┘
       │                  │
       ▼                  ▼
┌─────────────┐    ┌─────────────┐
│   accepted/ │    │    rfc/     │
│ (正式設計)  │    │ (元の場所を保持)  │
└─────────────┘    └─────────────┘

RFC-011: ジェネリクスシステム設計 - ゼロコスト抽象とマクロ代替 ​

概要 ​

参考ドキュメント ​

型宇宙思想と値依存型 ​

値依存型とは何か？ ​

コンテナ型命名階層 ​

値依存型の核心的優位性 ​

型宇宙階層と値依存型 ​

コンパイル時決定性保証 ​

値依存型の応用シナリオ ​

コンパイル時次元検証 ​

型安全な配列サイズ ​

境界失敗のコンパイル時カバレッジ目標 ​

条件型 ​

ジェネリクス関数 ​

他言語との比較 ​

停止性検査メカニズム（RFC-027と統合） ​

再帰関数の停止性検査 ​

ループの停止性検査 ​

停止性検査のワークフロー ​

優位性 ​

動機 ​

なぜ強力なジェネリクスシステムが必要か？ ​

核心的矛盾 ​

値依存型の核心的優位性 ​

ジェネリクスシステムの価値 ​

設計目標 ​

核心目標 ​

設計原則 ​

提案 ​

1. 基本ジェネリクス ​

1.1 ジェネリクス型引数 ​

ジェネリクス関数呼び出し構文 ​

1.1 統一シグネチャ構文 ​

1.2 Type自己記述機構 ​

1.3 単相化 ​

1.4 明示的な補完（推論失敗時） ​

2.2 多重制約 ​

2.3 関数型制約 ​

2.4 組み込みマーカートレイト：DupとClone ​

3. 関連型 ​

3.1 関連型定義 ​

3.2 ジェネリクス関連型（GAT） ​

4. コンパイル時ジェネリクス ​

4.1 コンパイル時値引数 ​

4.2 コンパイル時計算 ​

NeverとVoid：型システムの⊥と⊤ ​

4.3 コンパイル時検証（標準ライブラリ実装） ​

4.4 コンパイル時ジェネリクス特化 ​

5. 条件型 ​

5.1 If条件型 ​

5.2 型族 ​

6. 関数オーバーロード特化 ​

6.1 基本特化 ​

6.2 条件特化 ​

6.3 関数オーバーロードとインラインの完璧な結合 ​

7.2 使用点解析 ​

7.3 コンパイル時ジェネリクスDCE ​

7.4 モジュール間DCE ​

7.5 LLVMレベルDCE ​

8. マクロ代替戦略 ​

8.1 コード生成代替 ​

8.2 DSL代替 ​

8.3 型レベルプログラミング代替 ​

9. 例 ​

9.1 完全なジェネリクスコンテナ例 ​

9.2 ジェネリクスアルゴリズム例 ​

9.3 コンパイル時ジェネリクス例 ​

トレードオフ ​

利点 ​

欠点 ​

緩和策 ​

代替案 ​

リスク ​

オープンな問題 ​

未決議問題 ​

後続最適化 ​

付録 ​

構文BNF ​

ライフサイクルと帰結 ​

RFC-011: ジェネリクスシステム設計 - ゼロコスト抽象とマクロ代替

概要

参考ドキュメント

型宇宙思想と値依存型

値依存型とは何か？

コンテナ型命名階層

値依存型の核心的優位性

型宇宙階層と値依存型

コンパイル時決定性保証

値依存型の応用シナリオ

コンパイル時次元検証

型安全な配列サイズ

境界失敗のコンパイル時カバレッジ目標

条件型

ジェネリクス関数

他言語との比較

停止性検査メカニズム（RFC-027と統合）

再帰関数の停止性検査

ループの停止性検査

停止性検査のワークフロー

優位性

動機

なぜ強力なジェネリクスシステムが必要か？

核心的矛盾

値依存型の核心的優位性

ジェネリクスシステムの価値

設計目標

核心目標

設計原則

提案

1. 基本ジェネリクス

1.1 ジェネリクス型引数

ジェネリクス関数呼び出し構文

1.1 統一シグネチャ構文

1.2 Type自己記述機構

1.3 単相化

1.4 明示的な補完（推論失敗時）

2.2 多重制約

2.3 関数型制約

2.4 組み込みマーカートレイト：DupとClone

3. 関連型

3.1 関連型定義

3.2 ジェネリクス関連型（GAT）

4. コンパイル時ジェネリクス

4.1 コンパイル時値引数

4.2 コンパイル時計算

NeverとVoid：型システムの⊥と⊤

4.3 コンパイル時検証（標準ライブラリ実装）

4.4 コンパイル時ジェネリクス特化

5. 条件型

5.1 If条件型

5.2 型族

6. 関数オーバーロード特化

6.1 基本特化

6.2 条件特化

6.3 関数オーバーロードとインラインの完璧な結合

7.2 使用点解析

7.3 コンパイル時ジェネリクスDCE

7.4 モジュール間DCE

7.5 LLVMレベルDCE

8. マクロ代替戦略

8.1 コード生成代替

8.2 DSL代替

8.3 型レベルプログラミング代替

9. 例

9.1 完全なジェネリクスコンテナ例

9.2 ジェネリクスアルゴリズム例

9.3 コンパイル時ジェネリクス例

トレードオフ

利点

欠点

緩和策

代替案

リスク

オープンな問題

未決議問題

後続最適化

付録

構文BNF

ライフサイクルと帰結