OP 0022: 泛型 ADT 与内建 Option / Result¶
- 状态:Implemented
- 作者:fyabc
- 创建日期:2026-11-22
- 相关提案:OP 0005(类型系统主线;§3.1 变型、§4 ADT、§5 错误处理)、 OP 0017(薄探针与局部双向检查)、 OP 0004(字节码 VM)
- 相关设计:design 14(已实现算法基线)、 design 03(远期泛型策略)、 spec 11(语言参考)、 spec 12(类型擦除后端)
摘要¶
实现 P6 的泛型 ADT 切片:oort-core 的泛型 tagged union,包含
- 声明
enum Option[T] { Some(value: T), None },类型应用Option[Int]; - 构造器的类型参数只由期望类型或实参类型确定(不引入 HM);
match时按 scrutinee 的实参代换构造器载荷类型;- 声明处变型
[out T]/[in T]的语法与声明处健全性检查; - 内建
Option[out T]与Result[out T, out E],构造器Some/None/Ok/Err。
类型参数在 HIR/字节码之前擦除,共享后端(解释器、VM、.obc)零改动。
上界 T: Bound、泛型类/函数/lambda、? 传播糖、嵌套穷尽性、ADT 相等均不在
本切片。
动机¶
- 类型系统不对称。
List[T]/Dict[K, V]等内建容器已参数化,用户 ADT 却只能单态。任何“包一层”的数据建模都要为每种载荷类型复制一遍 (OptionInt、OptionString…),ADT +match的表达力在容器场景塌陷。 Option/Result是 OP 0005 §5 的核心承诺。没有泛型就无法给它们写出 类型;错误处理只能用异常或哨兵值,违背“显式优于隐式”。- 后端条件已满足。spec 12 已确认 ADT 降低只需“构造器名 + 元数”,类型参数 属于检查层。泛型 ADT 是对“类型擦除后端”论断的第一次真实检验:若后端需要 改动,说明 spec 12 的抽象选错了。
- 与现有类型哲学一致。design 14 §2 论证了 oort-core 没有顶类型、没有
union:
if c { 1 } else { "s" }不能合并成Object,正确表达是enum IntOrStr { I(Int), S(String) }。Option[T]正是这个方向的自然延伸。
设计¶
1. 语法¶
enum Option[out T] {
Some(value: T),
None
}
enum Result[out T, out E] {
Ok(value: T),
Err(error: E)
}
enum MyList[out T] {
Cons(head: T, tail: MyList[T]),
Nil
}
def find(xs: MyList[Int], target: Int) -> Option[Int] {
if target == 0 { Some(0) } else { None }
}
val a: Option[Int] = Some(1)
val b: Option[List[Int]] = Some([]) # 期望类型把 T 定为 List[Int],空字面量可检查
val c = Some("x") # 推断为 Option[String]
val d: Result[Int, String] = Err("boom")
- 类型参数
[T]/[T, E];可选变型前缀out/in(见 §5)。 - 类型应用复用现有下标语法
Name[...],与List[T]等一致,不引入尖括号。 - 构造器仍按位置绑定;字段名只作文档(与单态 enum 一致)。
- 类型参数约定大写,但不强制——Oort 不靠命名规则承载语义。
2. 类型表示:模板与实例¶
泛型声明必须区分“类型构造器”与“应用后的类型”:
TypeParameterType(name) # 声明体内引用参数的刚性变量
AdtTemplate(origin, name, params, constructors) # 声明(类型构造器)
AdtType(template, args) # 应用,如 Option[Int]
ForallType(params, body) # 构造器的多态类型方案
AdtTemplate在解析字段之前注册,因此MyList[T]自递归直接引用模板; 递归位置写成AdtType(template, (TypeParameterType("T"),))。- 模板的构造器载荷只含本模板的
TypeParameterType;嵌套泛型一律以已应用的AdtType表示(Option[B]是AdtType(option, (B,))),因此代换不会发生 变量捕获。 - 名义性 =
template.origin + name;参数逐个结构比较。Option[Int] != Option[String]。 - 单态 enum 统一成
params=()的模板,用户可见语义不变。
3. 构造器是多态值¶
Some 的类型方案是 forall T. (T) -> Option[T];None 是
forall T. Option[T]。类型参数只能由两处信息确定:
check 模式(期望类型是 AdtType 且模板相同):用期望的实参直接绑定参数,
再把实参按代换后的载荷类型检查。这让 design 14 §3 的期望类型传播自然扩展:
val xs: Option[List[Int]] = Some([]) # T = List[Int],[] 有期望
val ys: MyList[Int] = Cons(1, Nil) # Nil 在 MyList[Int] 期望下实例化
infer 模式(无期望的调用):先推断各实参类型,再用最小一阶合一求解模板 参数。求不出的参数是硬错误,不是 Unknown:
val x = None # Cannot infer type argument 'T' of constructor 'None'
val r = Ok(1) # Err 的 E 无法确定,同样报错
这与 Rust 一致:let x = None; 触发 E0282 “type annotations needed”。故意不把
未绑定参数默认为 Unknown——那会把错误推迟到使用点,违背“错误就地归责”。
冲突:同一参数被实参推出互不兼容的类型时报诊断(例如两处约束都对同一
T)。不同参数各自约束(Pair(1, "s"))合法。
一等值:裸泛型构造器只有在期望是函数类型时才可实例化:
零参泛型构造器(None)作为值同理需要期望类型;在 match 模式中不受影响,
因为模式由 scrutinee 的类型驱动。
4. match¶
- scrutinee 必须是
AdtType;按“模板参数 → 实参”代换构造器载荷后检查子模式。 在Option[Int]上Some(v)把v绑定为Int;在Result[Int, String]上Err(e)绑定String。 - 穷尽性仍按模板的构造器名集合;嵌套穷尽性仍是后续切片(现有行为不变)。
- 运行时不感知类型参数:variant 名 + payload(spec 12)。
Some(1)与Some("x")在运行时同构,匹配只看 variant。这正是类型擦除的含义。 - 未来的穷尽性/冗余检查沿用 Maranget 的 usefulness 算法
(
U(P, q):候选模式是否覆盖了此前矩阵未覆盖的值),它天然支持泛型载荷与 嵌套构造器;本切片不实现。
5. 变型(声明处)¶
语法来自 OP 0005 §3.1:[out T] / [in T],缺省不变型。
软关键字。in 已是保留字(for ... in),out 不是。为避免把 out 升为
全局关键字(破坏 val out = 1 这类合法代码),文法用两个独立标签:
typeParameter
: (in_variance=IN | out_variance=identifier)? name=identifier
(qualifier=(COLON | LT | GT) typeExpr=expression)? (ASSIGN defaultValue=expression)?
ANTLR 不允许同一标签混用 token 与 rule(variance=(IN | identifier) 会报
RULE_LABEL != TOKEN_LABEL)。两个标签在 AST builder 中合并为 VarianceKind;
out 仍是普通标识符(val out = 1 合法),非法变型文本报
Expected 'in' or 'out' before type parameter ...。
声明处健全性检查。enum 的载荷是构造器产出的数据,处于协变位置; 极性规则:
| 类型形状 | 参数极性 |
|---|---|
直接出现 T |
协变 |
List[T] / Set[T] / Tuple[...] |
协变(core 集合不可变,spec 11) |
Dict[K, V] |
键、值均协变(同上) |
(P1, ...) -> R |
参数翻转,返回不变 |
F[A1, ...](泛型 ADT) |
按 F 声明的变型逐参复合;不变型不约束 |
out T 只允许出现在协变位置,in T 只允许逆变,不变型不受限:
为什么现在检查一个“不可观察”的性质:本提案落地时静态模型没有顶类型、 继承或接口,任意两个不同实参类型之间没有子类型关系,因此变型关系暂时无法 改变可赋值性。(后续 OP 0025 增量 B 已加入类 单继承,变型在类实参之间可观察。)本切片仍强制声明处检查,因为:
- OP 0005 §3.1 已接受该语法,“解析但静默忽略”违反显式拒绝原则;
- 继承/接口切片到来时需要立刻启用健全性检查,届时再补会把不健全的声明留在 代码库里;
- 检查成本低(只遍历 payload 类型),且为未来 typed IR 的单态化提供合法性前提。
is_assignable 对同模板 AdtType 按变型逐参比较;在子类型出现前,这一规则
退化为相等(Unknown 参与错误恢复时除外)。
跨语言依据:
- Kotlin 在声明处用
out表示“只生产”、in表示“只消费”,并检查成员中 的使用位置(Source<out T>、Comparable<in T>): https://kotlinlang.org/docs/generics.html。 - C# 同样用
out/in,但只允许出现在接口/委托上,类实现保持不变型: https://learn.microsoft.com/en-us/dotnet/CSharp/programming-guide/concepts/covariance-contravariance/creating-variant-generic-interfaces。 - Scala 用
+A/-A,编译器检查协变参数只能出现在返回位置: https://docs.scala-lang.org/tour/variances.html。 - 形式化:Emir、Kennedy、Russo、Yu 把变型标注的健全性做成对成员类型的 极性判定(“variance and generalized constraints for C# generics”); Kennedy & Pierce 进一步研究带变型的名义子类型的可判定性,并指出必须拒绝 不健全的声明:https://www.cs.cmu.edu/~aldrich/FOOL/FOOLWOOD07/program/kennedy-abstract.html。
Oort 取同一极性规则,范围限于 enum 载荷;泛型类出现后再扩展。
6. 上界与默认值:本切片显式拒绝¶
文法已能解析 T: Bound(COLON qualifier)与 T = Default(ASSIGN)。本切片
在检查器中显式拒绝:
Type parameter bounds are not supported in oort-core yet; oort-core has no
traits/interfaces to use as bounds.
Type parameter defaults are not supported in oort-core yet.
依据:Rust 的 T: Trait、Kotlin 的 T : Comparable<T>、C# 的
where T : ... 都依赖类型类/接口约束;oort-core 的继承、接口与 trait 化运算符
仍在 P6 后续。没有约束目标时实现上界只能产生一个没有意义的构造。
类型参数名不得与已知类型名或 in/out 冲突(避免 enum E[Int] 这类遮蔽);
重复参数名报错。
7. 擦除与后端¶
检查器内的“单态化”。OP 0005 §3.3 说“内部单态化 + 边界擦除”。在当前的 类型擦除后端上,单态化只发生在检查器的抽象域:类型参数被实参代换,不生成按 类型特化的代码。真正的代码单态化属于 typed IR/LLVM 阶段;这与 design 03 的 三阶段规划一致。
- HIR:
_lower_enum_def只发射(构造器名, 元数),忽略type_params; 无新指令。 .obc:格式不变(spec 13);逐字节 round-trip 测试不受影响。- 运行时:解释器与 VM 的
EnumDef/BuildEnum不读类型参数;构造器名 + payload 即全部语义。 - 边界擦除:跨方言导入仍显式拒绝;未来 trampoline 落地时,泛型实参不越过 边界,动态侧只看到不透明 ADT 值(tag + payload)。本切片不做 reified 泛型或运行时类型实参。
跨语言对照:
| 语言 | 泛型实现 | 运行时是否保留类型实参 |
|---|---|---|
| Rust | 单态化(编译期为每个实参生成代码) | 是(体现在特化代码中) |
| Java | 类型擦除 | 否 |
| C# / .NET | 具体化(reified) | 是 |
| OCaml | 统一表示 + 类型擦除 | 否('a option 运行时无参数) |
| Oort(本切片) | 检查器代换 + 后端擦除 | 否 |
参考:Rust Book ch10 与 rustc-dev-guide 对单态化的描述
(https://doc.rust-lang.org/book/ch10-01-syntax.html、
https://rustc-dev-guide.rust-lang.org/backend/monomorph.html);Oracle 的
Java 擦除教程(https://docs.oracle.com/javase/tutorial/java/generics/erasure.html);
OCaml Option 模块(https://ocaml.org/manual/5.5/api/Option.html)。
8. 内建 Option / Result¶
目标定义:
enum Option[out T] {
Some(value: T),
None
}
enum Result[out T, out E] {
Ok(value: T),
Err(error: E)
}
构造函数名的选择对齐主流:Rust/OCaml 的 Some/None、Ok/Err(OCaml 用
Error,Swift 用 .success/.failure)。Oort 采用 Some/None 与
Ok/Err,最短且与 OP 0005 §4 的示例一致。
实现方式:预置源码注入。把上面的定义解析成 AST,拼在每个 oort-core
模块正文之前,使 Pass1、检查器、解释器和 VM 共用同一条普通 enum 路径:
- 优点:Option/Result 就是普通的泛型 enum,检查器与两个后端无需任何特判; 预置代码本身可读、可测试。
- 固定名义 origin:注入的 enum 使用
"<core-prelude>"作为名义 origin (EnumDef增加declaration_origin字段)。否则每个模块各有一份Option模板,跨模块返回Option[Int]的函数签名在调用方会出现名义性 分裂。固定 origin 后,任何模块里的Option[Int]在静态类型上相等。 - 保留名:类型
Option/Result,构造器Some/None/Ok/Err。 模块顶层重定义报专用诊断(“……is declared in the core prelude”); 内层作用域可按普通遮蔽规则局部遮蔽(与print一致)。 代价是用户不能声明enum Foo { Some(Int) },这是显式代价,写进规范。 - 导出:预置构造器不进入模块导出;导入方各自持有同一份预置。AST dump 以
synthetic标记注明来源。
替代方案(B 计划):检查器预声明静态模板 + 解释器/VM 各自预安装内建 ADT。 少一层 AST 拼接,但要在两个后端各写一份内建类型初始化,且 Option/Result 无法 用普通 enum 源码表达。保留为 B 计划。
迁移路径:跨模块类型导出(P6“跨模块类类型标注”)落地后,可把预置源码迁到 随包分发的 core stdlib 模块;用户可见的名字与类型不变。
实现(2026-11-22):semantics/core/prelude.py 用 AST 节点构造两段声明;
Compiler._run_input 与 compile_unit_details 在语义分析前对 core 模块调用
inject_core_prelude(-t ast 不注入)。注入节点 synthetic=True,AST dump
跳过;declaration_origin="<core-prelude>" 固定名义 origin。检查器把预置构造器
标为 from_prelude,模块导出过滤它们;用户重定义类型/构造器/顶层名报
... is declared in the core prelude.。运行时每个模块照常执行注入的 enum,
构造器绑定存在于模块环境,但静态导出已过滤,检查后的代码不可达。
9. 诊断¶
| 场景 | 诊断 | 类别 |
|---|---|---|
| 泛型 enum | 不再拒绝(删除 Generic enums are not supported...) |
— |
| 裸泛型类型名 | Type 'Option' requires 1 type argument(s); write Option[...]. |
TypeCheckError |
| 实参个数错误 | Type 'Option' expects 1 type argument(s), got 2. |
TypeCheckError |
| 单态 enum 加实参 | Enum 'Shape' does not take type arguments. |
TypeCheckError |
| 参数无法推断 | Cannot infer type argument 'T' of constructor 'None'; add a type annotation. |
TypeCheckError |
| 参数冲突 | Type parameter 'T' of constructor 'Pair' is inferred as both Int and String. |
TypeCheckError |
| 构造器作值 | A generic constructor cannot be used as a value without an expected function type. |
TypeCheckError |
| 变型误用 | Type parameter 'T' is declared covariant ('out') but appears in a contravariant position in constructor 'B'. |
TypeCheckError |
| 上界 / 默认值 | 见 §6 | UnsupportedSyntax |
| 预置名重定义 | Type 'Option' is declared in the core prelude. / Constructor 'Some' is declared in the core prelude. |
TypeCheckError |
| 泛型类/函数/lambda | 保持现有拒绝(本切片不放开) | UnsupportedSyntax |
边界与限制¶
明确不包含:
- 泛型类、泛型函数、泛型 lambda、泛型方法/扩展(继续显式拒绝);
- 上界、
where子句、类型参数默认值、高阶类型(F[_]); - 一等多态与显式类型应用(无
Some::<Int>式语法);实例化只来自期望类型或 实参; - reified 泛型、运行时类型实参、泛型相等(ADT 相等仍是后续切片);
- 嵌套穷尽性与决策树编译(沿用顶层构造器覆盖);
?传播糖(单独提案;本提案只保证它能降级为match);- 跨模块类型名导入(本提案落地时;预置 origin 是唯一例外)。该限制已由
OP 0025 增量 A 解除:类可
from导入类型, enum 类型名用m.E。
正交性检查¶
- 与类型系统:复用双向检查与局部推断(design 14),只为一个受限场景引入 一阶合一——构造器调用求解,不做 let 泛化、不做全程序 HM。
- 与类/对象:
ClassType不变;泛型类仍拒绝;ForallType的结构为未来泛型 类/函数预留。 - 与函数/闭包:
FunctionType不变;lambda 的期望下推不变。 - 与模块:本提案落地时 enum 类型名不导出;预置 enum 用固定 origin 解决跨
模块类型统一。后续 OP 0025 增量 A 增加独立类型导出(
m.E/from类)。 - 与宏/编译期:无交互。
- 与后端:HIR/字节码/VM/
.obc均无改动,由差分测试验证。 - 是否引入特例:三处,全部显式记录——(1) 预置注入与保留名,(2)
out软 关键字,(3) 构造器多态方案。没有隐式例外。
替代方案¶
- 只做运行时擦除,不做静态泛型(Java 式):实现最省,但 oort-core 的价值 就在编译期检查,放弃检查等于回到动态方言。
- 现在就在后端单态化:没有 typed IR,共享后端是动态值;先做会为不存在的 优化付出复杂度。
- 字典传递 / 类型类:正好为上界铺路,但本切片没有约束目标;留到 trait/ 接口切片。
- 使用处变型(Java 通配符
? extends):OP 0005 §3.1 已拒绝;变型决策应 留在声明处。 - 单态 Option 族 / nullable / union:design 14 §2 已论证 oort-core 没有顶 类型与 union;ADT 是正确表达。
- 显式 import stdlib 模块:被“跨模块类型导出未实现”阻塞;作为 §8 的迁移 路径保留。
向后兼容¶
- 单态 enum 的源码语义不变;内部表示改为零参模板。
oort-core新增保留名Option/Result/Some/None/Ok/Err,以及软关键字out;oort-object完全不受影响。enum E[T]从显式拒绝变为支持,需同步 spec 11 与 conformance 06 的拒绝清单。.obc格式不变,旧字节码可继续读取。- 现有枚举测试应全部通过;涉及
AdtType构造表示的测试可能需要跟进。
实现计划¶
进度(2026-11-22):增量 A(泛型 ADT)、B(声明处变型)与 C (内建
Option/Result)均已实现,由 spec 11/06、design 14、 implementation 09 与测试覆盖。
分三个可独立评审的增量:
增量 A:泛型 enum(无变型、无预置)¶
- 前端:AST/文法已解析类型参数与
X[...],A 阶段无需改动。 semantics/core/types.py:TypeParameterType、ForallType、AdtTemplate、AdtType(template, args);代换、受限合一、describe_type、is_assignable、join_types。checker.py:泛型 enum 声明(先注册模板再解析载荷、自递归);类型应用注解; 构造器方案;check 模式的 Call/Name 期望绑定;infer 模式的合一与诊断;match载荷代换;删除泛型 enum 拒绝。- 测试与示例;VM/eval 差分。
- 文档:spec 11、conformance 06、design 14、implementation 09、OP 0005、 roadmap。
增量 B:变型¶
- 文法软关键字与 AST builder 校验;
TypeParameter.variance。 - 声明处极性检查与诊断;
is_assignable的变型逐参比较。 - 测试:合法协变/逆变、函数位置的误用、嵌套泛型复合极性。
增量 C:预置 Option/Result¶
- 预置源码、AST 注入点(所有 core 编译路径)、
declaration_origin、synthetic标记、导出过滤。 - 保留名诊断;示例与文档(spec 11、spec 08 的 core 部分或新页面)。
- 测试:构造/推断/match/跨模块返回 Option/Result/重定义拒绝。
测试矩阵¶
- 声明:多参数、重复参数、参数遮蔽、自递归
MyList[T]、空 enum、非顶层。 - 注解:
Option[Int]、嵌套Option[List[Int]]、元数错误、裸名、单态 enum 加 实参。 - 构造:
Some(1)推断、期望驱动Some([])、None/Ok(1)未绑定报错、参数 冲突、构造器作值。 - match:
Option[Int]/Result[Int, String]绑定类型、嵌套构造器模式、零参泛型 构造器、穷尽性、跨构造器错误。 - 模块:函数返回
Option[Int]跨模块可用(固定 origin);用户泛型 enum 的类型名 在本提案落地时不可导入(后续由 OP 0025 增量 A 以m.E支持)。 - 变型:
Option[out T]/Result[out T, out E]通过;函数反转极性拒绝;in的 对称用例。 - 后端:同一批 ADT 程序在
-t vm与-t eval下结果一致;.obcround-trip 不变。 - 负面:泛型类/函数/lambda 仍拒绝;上界/默认值报 UnsupportedSyntax。
未解决问题¶
- 预置实现 A/B(§8):AST 注入 vs 检查器 + 双后端预安装。倾向 A,待增量 C 启动前用一个小原型验证注入点覆盖所有编译路径。
- 未绑定类型参数:硬错误 vs
Unknown+ 警告。倾向硬错误(Rust E0282 先例, 错误就地归责);若实际使用中Err("x")过吵,再评估。 - 变型检查时点:本切片启用 vs 推迟到子类型切片。倾向启用(§5 理由), 但若增量 B 阻塞主线,可拆出。
- 显式类型应用(turbofish 等价物):
Some::<Int>或Some<Int>?与现有 文法如何共存?留到泛型函数切片统一设计。 - 一等多态构造器:
map(Some, xs)这类用法需要类型实参下推或高阶类型, 不在本切片。 Result的错误上界(Swift 的Failure: Error):需要 Error trait/ 接口,随类型类一起设计。- 局部遮蔽预置构造器:允许内层作用域遮蔽(与
print一致),但模块顶层 保留。是否需要更严格的全局保留,待实现反馈。