类型系统设计¶
整理自项目早期的设计讨论(原始记录未纳入仓库)。
1. 类型系统哲学:渐进类型¶
Oort 是一门动态优先(dynamic-first)的渐进类型语言。类型系统的核心目标不是"让所有代码静态类型化",而是让开发者能够按需、按模块地将关键代码从动态迁移到静态,同时保持互操作性。
1.1 核心原则¶
- 动态优先:所有代码默认按动态类型执行,类型注解是可选的增强
- 模块级迁移:以模块(源文件)为单位切换类型检查严格度,而非表达式级
- 健全边界:静态模块内部保证 Type Soundness;跨模块边界插入运行时检查
- 可归责性(Blameability):类型错误发生时,系统能明确指出责任方
1.2 Type Soundness 的定位¶
Type Soundness 由两个定理组成:
- 进展性(Progress):良类型的表达式要么是值,要么可以继续执行——不会"卡住"
- 保持性(Preservation):表达式执行一步后,结果仍保持原来的类型
在渐进类型语言中,完全的 Soundness 在动态部分是被有意放宽的。Oort 的目标不是完美 Soundness,而是可归责性:
| 区域 | Soundness | 说明 |
|---|---|---|
| 纯静态模块内部 | ✅ 健全 | 编译时保证类型安全 |
| 纯动态模块内部 | ❌ 不保证 | 类型错误运行时抛出 |
| 跨模块边界 | ✅ 可归责 | 运行时检查 + Blame Tracking |
1.3 Any / Dynamic 与 Object / Type 的关系¶
这三者是正交概念,不是简单的父子关系:
Object:类型层次的顶点(Top Type),所有具体对象的公共超类。∀T. T <: ObjectNothing/⊥:底层类型(Bottom Type),表示永不返回。∀T. Nothing <: TDynamic:类型系统的逃逸机制,独立于子类型格。∀T. T <: Dynamic且Dynamic <: T(后者需运行时检查)Type:元类型(类型的类型),属于元编程维度,与Dynamic正交
统一规则:unify(T, Dynamic) = Dynamic(Dynamic "吞噬"静态类型)。边界检查的本质是将 Dynamic → T 的统一延迟到运行时验证。
1.4 模块级类型开关¶
每个源文件顶部可通过标志控制类型检查模式:
| 模式 | 行为 | 泛型处理 |
|---|---|---|
| 未开启(默认) | 动态类型,类型错误运行时抛出 | 泛型退化为 Any |
@strict-types |
静态检查,允许 any 注解逃逸 |
泛型实例化 + 单态化 |
迁移路径:加标志 → 将报错处暂标 any → 逐步替换为具体类型 → 性能自动随单态化覆盖率提升。
2. 泛型实现策略¶
2.1 泛型底层实现方式对比¶
| 方式 | 代表语言 | 渐进友好度 | 性能 | 代码体积 |
|---|---|---|---|---|
| 类型擦除 | Java, TypeScript | ⭐⭐⭐⭐⭐ | 低 | 小 |
| 单态化 | C++, Rust | ⭐ | 极高 | 大(膨胀) |
| 字典传递 | Haskell, Swift | ⭐⭐⭐ | 中 | 小 |
| 混合模式 | Oort(选定方案) | ⭐⭐⭐⭐ | 高 | 中 |
核心洞察:渐进类型的本质是"运行时保留动态能力"。单态化在编译期将类型固化为特定机器码,与动态能力的"未知性"本质冲突。类型擦除承认"运行时类型信息不重要",与动态哲学一致。
2.2 Oort 的混合泛型架构¶
决策:静态模块内单态化 + 动态模块内擦除 + 边界适配桩¶
┌─────────────────┐ 边界桩 ┌─────────────────┐
│ 静态模块 │ ◄────────────► │ 动态模块 │
│ │ (自动装箱/ │ │
│ 单态化快码 │ 拆箱+检查) │ 擦除+Tagged值 │
│ sort_int() │ │ sort(list) │
│ sort_float() │ │ → 统一按 Any │
└─────────────────┘ └─────────────────┘
静态模块内部:单态化¶
- 编译器对确定的类型执行激进单态化
fn sort<T>(list: List<T>)被调用为sort<Int>时,生成sort_int机器码- 消除虚表查找、消除装箱、CPU 流水线友好
动态模块内部:类型擦除 + 标签值¶
- 所有值都是 Tagged Value(参见
01-runtime-value-representation.md) - 泛型仅作为元数据存在,运行时统一按
Any处理 - 保持动态语言的灵活性和 REPL 体验
模块边界:动态适配桩(Adapter Thunks)¶
编译器自动生成边界桩代码:
- 导出(Static → Dynamic):生成
sort_dynamic包装器,接收 Tagged Value → 检查标签 → 解包 → 调用sort_int→ 打包返回值 - 导入(Dynamic → Static):视为返回
Any,插入运行时类型断言
2.3 泛型特化回退¶
编译器为泛型函数自动生成两个版本:
sort_monomorphic<T>:静态调用路径,高性能sort_erased:动态调用路径,内部使用比较回调(Comparator Callback)或运行时类型检查
用户只需写一个函数定义,编译器自动处理。当动态模块传入 List<any> 时,自动走擦除版本。
2.4 自动装箱/拆箱¶
迁移过程中用户无需手动处理 int 到 Integer 的转换:
- 边界桩代码负责从 Tagged Value 中提取原生值(如
i32) - 提取失败时抛出运行时错误(而非编译错误),保证渐进性
- 静态模块内部不跨边界的值绝不装箱(逃逸分析保证)
2.5 类型内部表示与泛型实例化¶
本节是跨语言调研与 Oort 的取舍记录,不改变当前已实现行为。具体的 typed IR 类型表与线格式见 design 15 与 spec 14。
泛型实现经常把三个层次混在一起:编译期类型表示、实例化的运行时 表示、值/布局/ABI。它们解决的问题不同,必须分开讨论。
2.5.1 编译期类型表示¶
| 方案 | 代表 | 优点 | 缺点 |
|---|---|---|---|
| 名义类型 | Java、C#、Rust、Swift、Kotlin | 身份稳定、跨模块/ABI 容易、递归类型自然 | 需要符号表;结构相同不自动兼容 |
| 结构类型 | TypeScript、Go interface、部分 ML | 组合灵活、无需预声明 | 身份/规范化复杂,跨模块 ABI 更难 |
| 混合 | Scala、Dart、Haskell | 兼顾 | 规则与实现更复杂 |
主流编译器通常把类型规范化成类型图/树 + 驻留表(interning),而不是 源码字符串:
- 相同类型只存一份,比较退化为 ID/指针比较(rustc
TyCtxt/TyKind、 SwiftType、GHCType、MLIRType); - 递归类型用名义引用(
Nominal(symbol, args))或Box/ID 避免无限展开; - 泛型参数用
TypeParam(index)/de Bruijn;推断变量用 union-find/levels; - 泛型签名用
Forall(params, body)表示 scheme,实例化 = 替换 + 规范化; - 方差(声明处或使用处)、类型别名是否展开、递归类型的相等规则都需要在 表示层显式建模。
结论:无论泛型采用哪种实例化方案,编译器内部都需要一个规范化的类型 表示与驻留/去重,否则相等判断、替换和缓存都会退化。
2.5.2 实例化与运行时表示¶
| 方案 | 代表 | 换来的 | 付出的 |
|---|---|---|---|
| 类型擦除 | Java、TypeScript、Kotlin/JVM、Scala/JVM、OCaml | 代码小、编译快、二进制兼容好、动态友好 | 无运行时类型参数、基本类型装箱、无法特化布局 |
| 单态化/模板 | C++、Rust、D、Swift(特化)、C#(值类型) | 无装箱、内联/去虚化、性能最好 | 代码膨胀、编译慢、分离编译难 |
| 具体化(Reified) | C#/.NET、Dart、Swift(metadata) | 运行时类型信息、反射、值类型泛型 | metadata/ABI 复杂、启动与内存成本 |
| 字典/见证 | Haskell type class、Swift witness、Rust dyn Trait、Go 泛型 |
一份代码、灵活、分离编译友好 | 间接调用、布局不特化 |
| 混合 | C#、Swift、Go(GCshape + 字典) | 在体积/性能间折中 | 实现与规则更复杂 |
- 擦除:泛型参数只存在于编译期。Java 的
Signature属性、Kotlin metadata、ScalaClassTag能在反射层部分恢复信息,但不能用于new T、instanceof T或基本类型特化。 - 单态化:每个具体实参生成专用代码/布局。C++ 模板通常要求头文件可见; Rust 依赖 metadata 做跨 crate 单态化;嵌套泛型可能组合爆炸。
- 具体化:运行时保留类型实参/描述符。C# 引用类型实例共享代码、值类型 特化;Dart 用 reified 类型 + tree shaking。
- 字典/见证:把类型对应的操作集合作为隐藏参数传递。Haskell 字典、 Swift witness table、Rust trait object、Go 的 shape/dictionary 都属于 这一类;代码小,但每次操作有间接成本。
2.5.3 值、布局与 ABI¶
| 问题 | 擦除/字典 | 单态化/具体化 |
|---|---|---|
| 是否装箱 | 通常装箱或统一表示 | 可按具体类型拆箱 |
| 布局 | 只能统一布局 | List<Int> 与 List<String> 可有不同布局 |
| 调用 | 间接(虚表/字典) | 直接调用 |
| 符号/名称 | 描述符/metadata token | 需要 mangling 包含类型实参 |
| 分离编译 | Java class / C# metadata 较友好 | C++ 头文件/模板实例化较难 |
| 运行时反射 | C#/Dart 有 Type 对象;Java 受限 | Rust/C++/TS 基本没有 |
2.5.4 对 Oort 的取舍¶
Oort 是模块级渐进类型:oort-core 静态、oort-object 动态。§2.2 已选择
静态侧单态化 + 动态侧擦除 + 边界桩;本节的表示结论是:
- 编译期:类型表使用规范化后的类型对象 + 驻留 ID。标量/容器结构相等,
类/ADT/接口名义相等(稳定
symbol_id)。泛型阶段再引入TypeParam/Forall/App(Nominal, args);实例化 = 替换 + 规范化。 - typed IR:S2/S3 只存具体容器类型(
List[Int]等);泛型单态化 在 typed HIR → typed 字节码之间完成,类型表最终不含类型变量,Rust VM 无需运行时类型参数。 - 运行时:静态实例使用具体布局/未装箱值;动态方言保持 tagged/boxed;
跨方言边界用 box/unbox + 守卫。当前没有
is/cast/反射,暂不引入 reified 描述符;将来需要时再在类型表中增加 runtime descriptor。 - 代码膨胀兜底:若泛型实例组合过多,可引入字典/共享 shape 作为 fallback (类似 Go),而不是一开始就放弃单态化。
- 开放问题:多态递归、跨模块 ABI/mangling、特化策略(
@inline/final)、 运行时类型测试的边界语义,留到泛型实现阶段裁决。
跨方言边界与 FFI(object→core、值映射/守卫/blame、C profile)的落地设计见 design 17。
3. 类型检查器架构¶
3.1 类型系统组成¶
当前支持的类型:
| 类别 | 类型 | 说明 |
|---|---|---|
| 原子类型 | NullType, Bool, Int, String |
不可再分的基础类型 |
| 复合类型 | List[T] |
参数化的容器类型 |
| 函数类型 | Function[[P1, P2, ...], R] |
允许泛型函数 |
| 类类型 | Type[P1, P2, ...] |
允许泛型类 |
| 渐进类型 | Dynamic |
类型黑洞,与任何类型可统一 |
3.2 Phase 1:显式泛型实例化(无类型推断)¶
核心机制:类型替换(Substitution)
泛型实体在环境中存储为 (type_params, func_type) 对,如 identity 存储为 (["T"], (T) -> T)。调用时从调用点获取显式类型实参,通过 substitute() 递归替换类型变量(处理嵌套泛型如 List[List[T]])。
设计要点:
- 普通标识符 → Type 子类;泛型实体 → GenericFunction / GenericClass
- 空列表需要显式类型注解(无推断时无法确定元素类型)
- 结构相等性判定:递归比较复合类型
3.3 Phase 2:Hindley-Milner 类型推断¶
在 Phase 1 稳固后,增量添加 HM 推断。核心组件:
| 组件 | 作用 | 难点 |
|---|---|---|
| 类型变量生成 | 为每个子表达式分配唯一 T1, T2, ... |
全局唯一计数器 |
| 约束生成 | 根据 AST 生成等式约束 | 处理 let 多态需泛化 |
| 合一算法(Unification) | 求解约束系统 | Occurs Check 防循环 |
| 泛化(Generalization) | let x = e in b 中将自由类型变量泛化为 ∀T |
作用域管理 |
合一算法(unify(t1, t2, subst) -> Substitution):先对两个类型应用当前替换,然后:
- 相同 → 返回当前替换
- TypeVar → occurs check 通过后扩展替换(防止 T = List[T] 无限类型)
- 复合类型 → 递归合一各子部分
- 不兼容 → 抛出 UnificationError
Let-Polymorphism:仅在 let 绑定时泛化自由类型变量,避免过度泛化。
实现建议:并查集优化合一性能;延迟泛化;记录约束来源以生成友好错误信息。
3.4 渐进类型扩展¶
在类型检查器中引入 DynamicType(单例),关键行为:
- Dynamic 参与的任何运算结果仍为 Dynamic
- Dynamic → Static 边界:记录需插入运行时检查的位置
- Static → Dynamic:无需检查(Liskov 替换,安全)
4. 方法重载¶
4.1 设计决策:联合类型 + 模式匹配¶
不采用传统的签名重载(Overloading),而是采用联合类型 + 模式匹配。
理由:
| 传统重载 | 联合类型 + 模式匹配 |
|---|---|
f(x: Int) -> Int / f(x: String) -> String |
f(x: Int \| String) -> Int \| String |
| 多个实现体,编译期选择 | 单一实现体,内部 match 分支 |
| 动态侧无法选择实现 | 动态侧自然执行运行时匹配 |
| 边界契约复杂(需合并多个签名) | 边界契约简单(单一函数) |
核心哲学:重载不应是"同一个名字的不同函数",而应是"同一个函数对不同数据形状的显式处理"。
4.2 静态侧与动态侧行为¶
- 静态侧:模式匹配编译为高效跳转表(Jump Table),编译期完成类型检查
- 动态侧:重载信息擦除,退化为普通函数 + 运行时类型分支
4.3 边界契约¶
当静态函数导出到动态环境时,计算所有匹配分支签名的最弱公共超类型(Least Upper Bound)作为契约:
- 例:
f(Int) -> Int和f(String) -> String→ 动态侧契约为f(Any) -> Any - 包装器内部保留检查:传入
Int时确保返回Int
4.4 Blame Tracking¶
重载调用失败时的归责规则:
| 场景 | 归责 |
|---|---|
| 动态传参不匹配任何分支 | 调用者(Dynamic Caller) |
| 动态传参匹配多个分支(歧义) | 设计者(重载定义不清晰) |
| 静态函数内部匹配分支返回错误类型 | 被调用者(Static Callee) |
错误信息应包含调用栈和期望的类型签名,标记为"边界类型违规"。
4.5 避免 TypeScript 的陷阱¶
TypeScript 的重载在运行时完全擦除,导致以下问题:
// TS: 运行时无法验证重载正确性
function fn(a: number): number;
function fn(a: string): string;
function fn(a: any): any { return a; } // 实现体可能返回错误类型
Oort 的对策:强制实现体内部通过 match 显式处理类型分支,编译器在边界生成契约检查,确保返回值与输入类型对应。
5. 边界机制¶
5.1 边界检查规则¶
| 方向 | 是否需检查 | 原因 |
|---|---|---|
| Static → Dynamic | 否 | 静态值必满足动态期望 |
| Dynamic → Static | 是 | 动态值可能破坏静态保证 |
| Dynamic ↔ Dynamic | 否 | 全动态世界无保证 |
5.2 边界桩代码生成¶
编译器在 AST 中插入运行时类型检查节点:x: Int = dynamic_expr 变为 x: Int = checked(dynamic_expr, Int)。代码生成时:检查类型标签 → 匹配则直接赋值(快路径) → 不匹配则抛出 TypeError + Blame 信息。
5.3 性能优化策略¶
- 批量验证:多个边界检查合并为一次验证,减少分支预测失败
- 多态内联缓存(PIC):边界处使用 PIC,类型稳定时直接跳转单态化代码
- JIT 特化:热点边界通过 Profiling 特化为无检查版本
- 受控逃逸分析:确保不跨边界的值绝不装箱
5.4 健全模式 vs 性能模式¶
默认采用可配置的健全模式:开发模式下严格边界检查(安全优先),生产模式可通过 @unsafe_skip_check 注解显式跳过检查(性能优先,开发者担保类型正确性)。
6. 实现阶段¶
6.1 三阶段泛型实现¶
| 阶段 | 目标 | 策略 | 产出 |
|---|---|---|---|
| Phase 1 | 互操作优先 | 类型擦除 | 所有模块统一 IR,静态检查仅编译期报错 |
| Phase 2 | 性能优化 | 模块级单态化 | @strict-types 模块内部单态化,边界自动生成桩 |
| Phase 3 | 极致性能 | PGO(Profile-Guided Optimization) | JIT 将热点边界桩去虚拟化,内联单态化代码 |
6.2 类型检查器演进¶
| 阶段 | 能力 | 关键实现 |
|---|---|---|
| Phase 1 | 显式泛型实例化 | 类型替换 + 环境管理 |
| Phase 2 | HM 类型推断 | 约束生成 + 合一算法 + Let-Polymorphism |
| Phase 3 | 渐进类型集成 | DynamicType + 边界检查记录 + Blame Tracking |
6.3 VM 支持需求¶
- 统一对象头:静态/动态对象共享兼容头部,包含类型指针或标签
- 多态内联缓存(PIC):模块间调用边界处的类型快速分发
- 类型元数据反射:静态模块保留部分类型元数据(即使单态化),供动态模块运行时查询
- ABI 兼容性约定:模块间调用通过 Tagged Value 传递,模块内部使用原生寄存器
6.4 参考语言对比¶
| 语言 | 渐进策略 | 泛型 | 借鉴点 |
|---|---|---|---|
| Racket / Typed Racket | 模块级边界 + Contract | 参数化多态 | 健全边界设计、Blame Theorem |
| TypeScript | 编译时擦除 | 擦除 | 迁移平滑性、开发者体验 |
| Dart | AOT + JIT 混合 | Reified + AOT 特化 | 模块级混合编译 |
| Luau (Lua) | VM 擦除 + 编译器优化 | 擦除 | 动态性保持 |
| Swift | @objc 桥接 |
字典传递 + 特化 | 静态语言中的动态桥接 |
7. 附录:解析器组合子(教育参考)¶
本节为函数式编程技术的学习参考,不直接用于 Oort 实现(Oort 使用 ANTLR4)。
解析器组合子通过组合小型解析器函数 (string, pos) → Optional[(result, new_pos)] 构建复杂语法解析器。核心组合子:seq(序列)、choice(选择)、many(重复)、map(转换)。递归定义需 lazy 包装解决前向引用。
与类型系统的关系:在 Haskell 等静态类型语言中,类型签名 Parser a = String -> Maybe (a, String) 能在编译期保证组合正确性,阻止非法组合(如将字符串解析器与数字处理器错误连接)。这体现了类型系统对程序正确性的价值——正是 Oort 渐进类型系统希望在静态模块中获得的收益。