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  # 矩阵类型依赖于行数和列数

容器类型命名分层

语言层有三个容器概念，长度信息的归属是它们的根本区别：

类型	长度	语义	底层
`Array(T, N)`	类型	定长数组，N 在类型中	核心原语（栈/内联优先）
`Vec(T)`	运行时值	运行时长度的原始缓冲，可增长	核心原语（堆上连续缓冲）
`List(T)`	运行时值	标准库类型	库：`{ data: Vec(T), length: Int }`

三者的分工原则：

Array(T, N) 是唯一把长度放进类型的形式——长度是编译期常量，故可做边界失败的编译期拒绝（a[5] 当 a: Array(Int, 3) 直接编译期报错，见下文「编译期维度验证」）。
Vec(T) 是运行时长度的最小地基——只提供「能分配、能取长、能读写、能扩容」四件事，容量策略、增长因子、是否收缩一律不做。它是构建其他容器的原料。
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 membership 谓词均已落地。 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)）同时提供循环不变式与度量边界，编译器按优先级尝试四种度量探索策略，找到一个即停止（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 证明管道，全自动优先）                 │
│     - 递归函数：检查参数在每条递归路径上严格递减             │
│     - 循环：四种度量探索策略（线性秩/违反计数/有界模式/      │
│       乘法缩放），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	泛型 + Trait	Trait系统复杂，学习曲线陡峭
C++	模板	模板特化复杂，编译错误信息差
YaoXiang	值依赖类型	类型可依赖值，编译期维度验证，终止保证

核心矛盾

性能 vs 灵活性：运行时灵活性 vs 编译期优化
复杂 vs 简洁：强大的类型系统 vs 易用性
宏 vs 泛型：宏代码生成 vs 泛型类型安全
值依赖 vs 类型安全：传统泛型无法在编译期验证维度

值依赖类型的核心优势

YaoXiang 的值依赖类型是相对于传统泛型的核心优势：

优势	说明
类型依赖值	`Array: (T: Type, N: Int) -> Type` 让类型依赖于具体的值
编译期求值	类型位置的函数调用在编译期求值，结果直接嵌入类型
维度验证	`Matrix(Float, 3, 3)` 在编译期验证矩阵维度
类型级计算	`If`, `Match` 等条件类型支持类型级计算
终止保证	编译期终止检查（自动度量合成）确保编译期求值必然终止

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) 接口实例化（三类型参数，结果类型 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 内置 marker trait：Dup 与 Clone

三类复制语义：

类型	含义	触发方式	适用场景
原语值复制	赋值时自动值复制，两个值完全独立	赋值/传参自动	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	✅	内部引用计数，复制句柄共享底层 buffer
`&mut T`（可变令牌）	❌	线性独占，不能复制
struct	派生	所有字段 Dup → struct Dup
enum	派生	所有 variant 的所有字段 Dup → enum Dup
tuple	派生	所有元素 Dup → tuple Dup
Fn（闭包）	❌	捕获环境可能非 Dup
`*T`（裸指针）	❌	unsafe，不参与所有权系统

Int/Float/Bool/Char 不是 Dup——它们是值类型，赋值时编译器自动值复制（两个值完全独立）。这不是"浅拷贝"，是编译器对原语的内置处理，不需要也不应该通过 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 不作为用户可见 trait。跨任务安全保障由 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 是运行时值参数，因为二者未出现在任何类型位置。

判定规则（两步）：

形态粗筛：参数标注为非 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 两个内建类型名承载：

Never（⊥） — 三条不可协商的内核性质：

零构造子：无任何字面量或表达式能产生 Never 类型的值。这是元级性质，必须内建。
爆炸原理：Never <: T 对任意类型 T 成立。一个 Never 值可被当作任何类型使用——这正是 assert(false) 之后代码仍通过类型检查的原因（虽然永不执行到）。
发散标记：f: (...) -> Never 表示 f 保证不返回。编译器据此做 dead code 分析。

Never 是内建类型名，不是关键字，parser 无感。不开放空和类型字面量语法。

Void（⊤，即 Unit） — 恰好一个居留者（默认 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 类型对应一个有两个可能值的命题（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公式

这意味着什么？

✅ 泛型特化 → 函数重载自然解决
✅ 性能优化 → 内联自动完成
✅ 代码复用 → 一个函数名，多种实现
✅ 零成本抽象 → 编译期多态，零运行时开销
✅ 无需新关键字 → 完美符合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 内置 marker trait：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 内置 marker trait：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

生命周期与归宿