跳转至

类型系统设计

整理自项目早期的设计讨论(原始记录未纳入仓库)。


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 <: Object
  • Nothing / ⊥:底层类型(Bottom Type),表示永不返回。∀T. Nothing <: T
  • Dynamic:类型系统的逃逸机制,独立于子类型格。∀T. T <: Dynamic 且 Dynamic <: T(后者需运行时检查)
  • Type:元类型(类型的类型),属于元编程维度,与 Dynamic 正交
          ⊤ (Object)
         / \
    Static   Dynamic (Any)    ← Dynamic 不在标准子类型格中
         \ /                    而是作为"可渗透边界"存在
          ⊥ (Nothing)

统一规则:unify(T, Dynamic) = Dynamic(Dynamic "吞噬"静态类型)。边界检查的本质是将 Dynamic → T 的统一延迟到运行时验证。

1.4 模块级类型开关

每个源文件顶部可通过标志控制类型检查模式:

# @strict-types    ← 开启静态检查

def add(a: Int, b: Int) -> Int:
    return a + b
模式 行为 泛型处理
未开启(默认) 动态类型,类型错误运行时抛出 泛型退化为 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、 Swift Type、GHC Type、MLIR Type);
  • 递归类型用名义引用(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、Scala ClassTag 能在反射层部分恢复信息,但不能用于 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 已选择 静态侧单态化 + 动态侧擦除 + 边界桩;本节的表示结论是:

  1. 编译期:类型表使用规范化后的类型对象 + 驻留 ID。标量/容器结构相等, 类/ADT/接口名义相等(稳定 symbol_id)。泛型阶段再引入 TypeParam/Forall/App(Nominal, args);实例化 = 替换 + 规范化。
  2. typed IR:S2/S3 只存具体容器类型(List[Int] 等);泛型单态化 在 typed HIR → typed 字节码之间完成,类型表最终不含类型变量,Rust VM 无需运行时类型参数。
  3. 运行时:静态实例使用具体布局/未装箱值;动态方言保持 tagged/boxed; 跨方言边界用 box/unbox + 守卫。当前没有 is/cast/反射,暂不引入 reified 描述符;将来需要时再在类型表中增加 runtime descriptor。
  4. 代码膨胀兜底:若泛型实例组合过多,可引入字典/共享 shape 作为 fallback (类似 Go),而不是一开始就放弃单态化。
  5. 开放问题:多态递归、跨模块 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 渐进类型系统希望在静态模块中获得的收益。