类型化 ADT 设计(S4)¶
状态:设计草案 + S4a/S4b 原型(2026-11-23)。单态与泛型 ADT(含 prelude
Option)已进入 typed HIR / kind=1 v6 / Python typed VM / Rust typed VM;S4b 原型在运行时擦除类型参数,复杂模式仍留后续。不改变语言表面。关联:design 15 的 S4 扩展;design 03 的泛型表示;design 14 的 ADT 检查;spec 14 的 typed 字节码格式;design 16 的值相等语义。
1. 目标与范围¶
1.1 目标¶
让以下 oort-core 程序在 typed 路径上运行,并与 -t vm 输出一致:
#lang oort-core
enum Shape {
Circle(radius: Int),
Rect(width: Int, height: Int),
Empty,
}
def area(shape: Shape) -> Int {
match shape {
Circle(r) => r * r * 3,
Rect(w, h) => w * h,
Empty => 0,
}
}
print(area(Circle(2)))
print(area(Rect(3, 4)) == 12)
具体要求:
- 名义 ADT 类型、构造器、载荷;
match与构造器/通配/变量/嵌套模式;- ADT 结构相等与打印;
- 递归 ADT(如
Tree); - 与 Python typed VM、Rust typed VM 的差分;
.obc序列化 round-trip。
1.2 非目标¶
- 不实现类、接口、typed 闭包、函数值跨 ADT;
- 不在 S4 做跨模块 ADT(module import 仍被 typed 子集拒绝);
- 不改变
match的穷尽性规则; - 不做决策树/跳转表优化(先线性匹配,后优化);
- 不承诺内存布局 ABI;初始载荷是 boxed 值的数组;
- 不引入 GC(见 §7)。
2. 现状与约束¶
2.1 oort-core 已有语义¶
enum E[T]是名义泛型 ADT;支持声明处变型、内建Option/Result;- 构造器可带载荷;模式支持构造器、字面量、Tuple、或模式、守卫;
- 检查器已做穷尽性检查;ADT 使用结构相等;
- 运行时
OortADT保存type、variant(构造器名)与values; - 擦除式 HIR 用
BuildEnum建立类型/构造器,用Match的 arm 函数执行匹配。
2.2 typed 路径现状¶
- S4a 之前
IrTypeLike = IrType | ContainerType,没有名义类型; - S4a 之前
lower_typed_module拒绝EnumDef/Match; - S4a 之前 kind=1 类型表是每 proto 的后序表(v4,tag 1–11);
- kind=1 没有全局存储;函数通过
DEF_FUN/LOAD_G绑定; - Python typed VM 是 boxed baseline,Rust typed VM 使用未装箱标量 +
Rc容器; - typed 路径仍单模块,prelude 的 synthetic enum 被跳过。
这些约束决定了 S4 的主要设计点不是“再加一个值类型”,而是:
- 名义类型如何进入类型表;
- 构造器如何在不引入全局存储的前提下表示;
Match如何绕过现有 arm 函数而保持模式语义;- 泛型实例如何在不同 proto 间保持同一身份。
3. 先行研究¶
| 系统 | ADT 表示 | 匹配实现 | 对 Oort 的启示 |
|---|---|---|---|
| Rust enum | 单态化后的判别式 + union;可做 niche 优化 | 编译为 switch/决策树 | 静态身份 + 单态化布局是长期目标 |
| Swift enum | 名义 enum,载荷内联,indirect 处理递归 |
编译为分支/跳转 | 递归与载荷布局必须显式设计 |
| OCaml variant | 统一 block:tag + 字段;多态不单态化 | 子句匹配/决策树 | 统一 tagged payload 是最简单的起点 |
| Haskell ADT | lifted constructors,info table;统一堆对象 | 模式匹配编译 | 不必第一步就为每个 ADT 生成专用布局 |
| Java sealed interface | 引用对象,名义类型,无载荷内联 | instanceof/switch |
名义身份与运行时类型检查可以分离 |
C++ std::variant |
库级 tagged union | visit |
判别式 + payload 足以表达语义 |
提炼:S4 先采用“名义声明 + 统一 tagged payload”的保守布局,与
OCaml/std::variant 接近;单态化、niche、决策树留到 S4c 性能阶段。类型身份
必须来自声明的 (origin, name),不能只把构造器名当字符串比较。
4. 类型模型¶
4.1 名义 ADT 类型¶
typed 路径新增:
@dataclass(frozen=True)
class AdtType:
origin: str # 模块 origin,prelude 为 <core-prelude>
name: str # enum 名
args: tuple[IrTypeLike, ...] = ()
IrTypeLike = IrType | ContainerType | AdtType。
- 相等性:
origin+name+args结构相等; - 类型表去重键相同;
- 单态 enum 是
args=()的特例; - 构造器载荷类型从检查器的
ConstructorInfo读取,typed lowering 不重新推断。
4.2 模块级声明表¶
ADT 是模块级声明,构造器 ID 必须跨 proto 稳定,因此不能继续只放在每 proto 类型表里。kind=1 v6 增加模块头:
u32 adt_decl_count
adt_decl[adt_decl_count]:
string origin
string name
u16 ctor_count
ctor[ctor_count]:
string name
u8 arity
adt_decl_id是模块内稳定索引;- 构造器 ID 可以是
(decl_id, ctor_index),加载时展开; - 载荷的具体类型不在模块头重复:
AdtType的类型参数与检查器元数据已经足够; - 名字/arity 只用于运行时构造、打印和边界守卫;不用于重新类型检查。
4.3 类型表 tag¶
S4a(单态)在每 proto 类型表新增:
S4b 支持类型参数:
类型表 tag 12 写入 u16 adt_decl_id, u16 arg_count, u16 arg_type_id[];运行时
ADT 值保存具体实例类型(decl + args),用于守卫与相等。格式版本提升为 v6。
5. 构造器与值¶
5.1 构造器调用的 lowering¶
现有擦除路径通过 BuildEnum 把构造器绑定为全局值,再用 Call 调用。typed
路径没有全局存储,且构造器不是普通用户函数。typed lowerer 识别“目标为构造器
的直接调用”,生成:
- 载荷按声明顺序连续搬入窗口,和
NEW_LIST/NEW_DICT的窗口约定一致; - 载荷个数由模块声明表的
arity决定,因此不需要额外的 count 操作数; - 空载荷构造器直接
NEW_ADT A=0, B=ctor, C=dst; - 构造器作为一等函数值仍显式拒绝(typed 路径本来就不支持函数值)。
这避免为构造器新增全局表,也不改变擦除路径。
5.2 运行时值¶
初始布局采用统一 tagged payload:
- Python typed VM 复用
OortADT,保持打印和相等语义; - Rust 使用
Rc<TypedAdt>; - 载荷元素是
TypedValue,暂不单态化内联; - 空载荷构造器仍分配一个小的 ADT 值,不等同于
Unit; - ADT 值不可变;递归 ADT 的有限树不会形成环。
S4c 再评估按声明/实例生成专用 Rust enum、内联标量载荷或 niche 优化。
6. 匹配¶
6.1 不让 typed 路径复用 arm 函数¶
共享 HIR 的 Match 把每个 arm 降低为带绑定的函数,再由 VM 调用。这适合擦除
路径,但 typed 路径没有 typed 闭包/函数值,且 arm 参数类型需要从 scrutinee
反推。S4 建议 typed lowerer 单独降低 match:
- 校验 scrutinee 的静态类型是 ADT(或后续 Tuple/字面量);
- 按声明顺序生成构造器测试和字段提取;
- 绑定通过
MOVE写入 arm 的局部槽; - 守卫在绑定后求值;
- 无匹配时报告运行时“non-exhaustive match”错误。
新增 typed 指令:
ADT_TAG 返回变体索引;ADT_FIELD 越界/错误变体必须显式报错。构造器模式
编译成:
ADT_TAG tag, value
JMP_IF_NE tag, CtorIndex, next_arm
ADT_FIELD field0, value, 0
...绑定...
...arm body...
JMP end
S4a 支持:
- 通配
_、变量绑定; - 构造器模式(可嵌套);
- 空载荷/带载荷构造器;
- arm 守卫(布尔表达式)。
S4b 继续支持:
- 字面量/Tuple/或模式与嵌套组合;
- 泛型 ADT 的载荷;
- 更复杂的绑定类型。
match 的穷尽性仍由 core 检查器负责;typed 路径只消费检查结果,不重新检查。
6.2 后续优化¶
S4c 可把线性测试改成决策树(Maranget 风格)或跳转表;初始版本先保证语义和 差分,不把性能写进门禁。
7. 相等、打印与 GC¶
- 相等:名义
(origin, name, args)+ 变体 + 载荷递归typed_equal; 与动态values_equal对齐; - 打印:
Ctor或Ctor(v0, v1),空载荷不打印括号,和OortADT.__str__一致; - GC:S4 的 ADT 值不可变,递归 ADT 是由已求值构造器组成的有限树;
Rc/RefCell足够,不引入 tracing GC。若后续允许 ADT 持有可变 List/类实例 或 typed 闭包,必须与 Rust VM v2/design 01 一起重新评估环回收。
8. 序列化与兼容性¶
- kind=1 版本提升为 v6;
- 文件头增加模块级 ADT 声明表,再写 functions/main;
- 每 proto 类型表新增 tag 12;
- 新 opcode:
NEW_ADT、ADT_TAG、ADT_FIELD、EQ_ADT、NE_ADT; - 旧读者遇到 v6/未知 opcode/tag 必须显式拒绝;
- 不改变 kind=0 格式;
- 单模块 S4a 不涉及跨模块 origin;v6 预留
origin字段,跨模块 ADT 在 B2/ 后续扩展中启用。
9. 里程碑¶
| 阶段 | 范围 | 退出条件 |
|---|---|---|
| S4a 单态 ADT | 模块声明表;构造器;同构/递归单态 enum;NEW_ADT/ADT_TAG/ADT_FIELD;构造器/通配/变量/守卫匹配;相等/打印 |
示例与差分通过;round-trip;Rust 一致 |
| S4b 泛型 ADT | Option/Result、泛型载荷、reified 实例类型参数 |
已完成(原型);复杂模式留后续 |
| S4c 优化 | 决策树/跳转表、单态布局、标量载荷内联;基准 | 不改变语义;typed benchmark 有收益 |
S4a 的实现顺序:
- 类型模型 + 模块声明表 + v6 序列化;
- typed HIR 识别
EnumDef/构造器调用/match; - Python typed VM 的构造/匹配/相等/打印;
- Rust typed VM 同步;
-t tvmvs-t vm、Rust 差分、round-trip、示例。
10. 风险与开放问题¶
- 构造器识别:检查器是否保留构造器调用与普通函数的明确区别?typed lowerer 不能靠名字猜测。
- match arm 函数 vs 内联 lowering:本文倾向前者不用、typed 专用 lowering; 需要确认共享 HIR 的 arm 元数据不会丢失绑定顺序。
- 泛型实例身份:S4b 是否采用模块级 instance 表/单态化,还是运行时携带
类型参数;这会影响
.obc和相等性。 - 递归声明:
Tree的载荷引用自身,类型表/声明表必须允许非类型表的 自我引用,不能沿用容器类型的“后序无环”规则。 - 跨模块 origin:
m.Type的运行时身份与导出/导入;S4a 先限定单模块。 - prelude:
Option/Result的 synthetic enum 如何进入模块声明表, 以及是否在 S4a 就支持。 - GC:当前 ADT 不可变无环;一旦 ADT 可持有可变的 List/类实例,环可能出现。
- ABI/性能:统一 payload 是语义优先方案;S4c 的专用布局需要重新评估
.obc是否携带布局元数据。
11. S4a 实现状态(2026-11-23)¶
已实现:
AdtType(origin, name)进入IrTypeLike;S4a 使用固定 origin"<typed-module>"(跨模块身份留 B2);- 模块级
AdtDecl/AdtConstructor表;kind=1 v6 文件头写入 origin/ name/构造器名/arity; - typed HIR 新增
BuildAdt/AdtTag/AdtField;EnumDef不再写入 main, 构造器直接调用/空载荷引用会转成BuildAdt; - typed
match专用 lowering:构造器/通配/变量/嵌套构造器模式 + 守卫; 字面量/Tuple/或模式仍显式拒绝; - opcode 75–79:
NEW_ADT/ADT_TAG/ADT_FIELD/EQ_ADT/NE_ADT; - Python typed VM 复用
OortADT/OortType;Rust 使用TypedValue::Adt+TypedAdt;相等、打印、递归 ADT 与主结果转换已对齐; - 验收:
examples/08_core/08_18_typed_adts.ort、typed 单测、OBC round-trip、 Rust differentialtyped_adts。
已知限制:
- 只支持单态 enum;
Option/Result等泛型构造器仍拒绝; AdtField的校验按字段索引放宽(同一索引在不同构造器可有不同类型);- 序列化不保存构造器 payload 类型,只保存 arity;读取后的
.obc用于执行, 不用于重新类型检查; - 无跨模块 ADT、无类/接口/typed 闭包、无 GC 变更。
11.1 S4b 实现状态(2026-11-23)¶
已实现:
AdtType.args进入静态 typed 类型;用户泛型 enum 与 preludeOption可用;- 泛型构造器类型实参由检查器的期望类型/实参推断,typed lowerer 读取检查结果;
match的 payload 类型通过substitute从实例类型参数得到;- prelude
Option/Result的 synthetic enum 进入模块 ADT 声明表; - Rust/Python typed VM 使用相同的构造器/标签/payload 执行路径;
- 验收:
examples/08_core/08_19_typed_generic_adts.ort、typed 单测、 differentialtyped_generic_adts。
S4b 原型的限制:
- 运行时 ADT 值现在携带
AdtType实例身份(decl + args),守卫/相等可区分Option[Int]与Option[String]; - v6 类型表 tag 12 保存参数列表;反汇编/round-trip 保留实例参数;
- prelude 的 Option/Result 声明会出现在每个 typed 模块的声明表中;
AdtField对泛型字段仍做宽松校验(字段 payload 模板不写入声明表);- 跨模块 ADT、边界转换、完整复杂模式仍留后续。
12. 推荐决策¶
- 先 S4a 单态 ADT,把名义身份、构造、匹配、相等、打印和 v6 格式跑通;
- 类型身份用
(origin, name, args),不要用构造器名字符串; - 值布局先用统一 tagged payload,不提前做 Rust enum 单态化;
- match 用 typed 专用 lowering +
ADT_TAG/ADT_FIELD,不复用 arm 函数; - S4b 再引入泛型实例表 + Option/Result prelude;
- S4 不引入 GC,但记录“ADT 持有可变对象/闭包后需重新评估”。