跳转至

OP 0005: 类型系统、泛型、ADT 与模式匹配

摘要

为 Oort 引入模块级渐进类型:动态模块保持现有解释执行;静态模块获得类型检查、 泛型、ADT、模式匹配与 Result/Option 错误处理。首批只做双向类型检查与局部推导, 不做 HKT,不做全程序 HM。

动机

  • 当前类型标注被解析但完全忽略,容易让用户误以为有检查。
  • 现代语言的经验(Rust/Swift/TypeScript)表明:ADT + 模式匹配比传统继承更适合 数据建模;Result/Option 比异常更适合显式错误处理。
  • C++ 的教训:std::vector<bool> 说明“为优化引入语义特例”代价极高;类型 萃取/偏特化说明开放的编译期类型计算会失控。Oort 应从一开始就限定类型级编程的边界。

设计

1. 渐进类型边界

  • 以模块为单位选择动态/静态(与 OP 0001 的方言一致)。
  • 静态模块内所有函数签名与变量必须有类型;动态边界处用 any / 运行时检查。
  • 边界 trampoline:动态调用静态、静态调用动态时插入装箱/检查代码。
  • 类型错误带 blame(错误归责到具体边界),不把错误推给调用者。

2. 检查算法

  • 基础:双向类型检查(check(expr, expected) / infer(expr))。
  • 局部推断:val x = 42 推断为 Int;函数返回类型可由函数体推断。
  • 泛型:显式类型参数 [T],调用处做统一(unification);可选的全程序 HM 作为后续扩展。
  • 不做高阶类型(F[_]):实现成本高、对多数用户价值低;若需要,单独立案。

函数返回类型推断已实现(2026-11-22)。 顶层 def、do lambda 与类方法 可省略返回标注,从各 return 类型与尾表达式类型合并推断;lambda 还可由期望 函数类型下推返回类型。递归函数/方法仍需显式返回标注——推断无法穿过递归 调用确定类型,对齐 Kotlin/Scala(两者都强制递归函数显式返回类型)。类方法按 调用依赖拓扑序推断(第一切片 def+lambda,第二切片类方法)。已实现算法与跨语言 对比见 design 14。

3. 泛型实现策略

  • 内部单态化(monomorphization):适合静态模块与 LLVM 后端;
  • 边界处类型擦除:动态与静态互操作时使用;
  • 混合策略,具体边界见 设计笔记 03。

3.1 类型参数语法与变型(已接受)

决策(2026-11-18):采用声明处 in/out 变型,语法为 [out T: Bound] / [in T: Bound]。实现与类型检查器一起落地;在此之前, 类型参数仍会在语义分析阶段被显式拒绝。

Oort 已经使用中括号 [T](与 Python/Go/Scala 一致)。采用关键字式变型标注:

class Producer[out T] { def get: T }
class Consumer[in T] { def put(x: T) }
class Box[T] { def get: T; def set(x: T) }          # 不变型
class Sorted[out T: Comparable] { ... }             # 变型 + 上界
  • out:协变(只生产 T);in:逆变(只消费 T);缺省不变型。
  • 变型在声明处标注(Kotlin/C# 模型),定义时校验使用是否合法,错误信息定位到类型定义, 而不是分散到每个使用点。
  • 上界统一为 T: Bound;复杂约束放到 where 子句。这样 [ ] 内不再出现 </>,彻底消除比较、基类声明、类型限定三者共用尖括号的歧义。
  • 函数类型参数不需要变型标注:函数类型天然对参数逆变、对返回值协变。

其他语言的现状(供比较):

语言 类型参数 变型语法 位置
C++ <T> 无(模板不变型) —
Java <T> ? extends T / ? super T 使用处通配符
C# <T> out T / in T 声明处(接口/委托)
Kotlin <T> out T / in T;使用处 out/in 投影 声明处 + 使用处
TypeScript <T> in T / out T(4.7+,可选) 声明处
F# 'T out / in 声明处(接口/委托)
Scala [T] +T / -T 声明处
OCaml 'a +'a / -'a 声明处(模块签名)
Rust <T> 无注解,编译器推断 —
Swift <T> 无用户注解(推断) —
Haskell 无括号 type role(GHC),非变型标注 —
Dart <T> 泛型默认协变(不健全);covariant 是参数重写修饰符 —

选择理由:

  • 不用 +/-:紧凑但可读性差,容易与算术混淆(Scala/OCaml 的负担)。
  • 不用使用处通配符:? extends 冗长,且把变型决策分散到调用点(Java 的负担)。
  • 不依赖纯推断:Rust/Swift 的推断需要完整的所有权/类型求解器,错误信息难以解释; Oort 的渐进类型阶段不具备这个条件。
  • 关键字而非符号:与 in/out 的直觉一致,也避免再次向 </> 叠加语义。

当前 T < Upper / T > Lower / T: MetaType 三套限定符尚未实现检查,改变成本很低; 迁移在实现类型检查器时进行,MetaType 约束移入 where T :: Meta 或推迟。

4. ADT 与模式匹配

enum Option[T] {
    Some(value: T)
    None
}

match opt {
    Some(v) => v,
    None => 0,
}
  • 标签联合(tagged union),编译期穷尽性检查;
  • 模式:字面量、变量、构造器、元组/列表、通配符、守卫;
  • 编译为决策树,而不是线性 if 链;
  • 与现有 class 并存:ADT 用于数据,类用于行为/动态派发。

第一切片(2026-11-21,OP 0017):已实现单态 enum、构造器、嵌套构造器 模式、_/绑定模式与顶层构造器穷尽性,端到端执行。

泛型 ADT 增量 A/B/C(2026-11-22,OP 0022):已实现 enum E[T]、类型应用 Option[Int]、构造器类型实参推断(期望类型/实参类型, 未绑定报硬错误)、match 载荷代换、自递归泛型载荷、声明处 [out T]/[in T] 变型的极性检查(out 为软关键字),以及内建 Option[out T]/Result[out T, out E] (Some/None/Ok/Err,固定名义 origin,模块级保留名);类型参数在 HIR/字节码前擦除,后端零改动。

完整模式匹配语义切片(2026-11-22,OP 0023): 已实现字面量/元组/或模式、if 守卫与嵌套穷尽性(Maranget witness); match 的 scrutinee 扩展到 Bool/Int/Float/String/Tuple。.obc 升到 version 2 (模式字面量值与 guard 字段,仍读 v1)。决策树编译留作性能切片。

ADT 相等与槽对象(2026-11-22,OP 0024): 已实现 ADT 结构值相等与 key-safe ADT 键,以及静态类实例的身份相等/键; 含函数载荷的 ADT 相等、不可键 ADT 作键显式拒绝。

5. 错误处理

  • 标准库提供 Result[T, E] 与 Option[T],配合模式匹配。
  • 不使用 try/catch 作为主要控制流;异常仅用于不可恢复错误(或完全不引入)。
  • ? 传播语法作为糖,最终降级为 match。

6. 内存管理

  • 动态方言:Tracing GC(简单、可移动)或 ARC(无暂停但循环引用需处理)。 首选简单 Mark-Sweep,后续可替换。
  • 静态方言:所有权/生命周期或区域分配(远期)。
  • 该决定影响闭包表示与 FFI,需在字节码/LLVM 实现前确定。

7. 运算符重载(类型系统的一部分)

  • 不采用 C++ 的全局符号重载与偏特化;采用 trait 风格: Add 等接口按类型实现;
  • 对称运算(a + b 与 b + a)通过自由函数或交换律声明处理,避免 __radd__ 式隐式规则;
  • 运算符声明语法见 OP 0002。

正交性检查

  • 与类:ADT 不参与继承;类不要求 ADT 语义。
  • 与宏:类型检查在宏展开之后、运行之前。
  • 与字节码:类型信息用于优化,但动态模块不依赖它。

替代方案

  1. 全程序 HM:推断强,但错误信息与模块化编译困难,且与类/子类型交互复杂。
  2. 纯动态 + 运行时检查:简单,但无法提供编译期保证。
  3. 类型类 + 开放世界:表达力强,但实例解析复杂度高(Scala/Haskell 的教训)。

实现计划

  1. 拒绝清单先行:在静态方言中,未实现特性仍显式报错。
  2. 双向检查 + 局部推断 + 基础泛型。
  3. ADT + match + 穷尽性检查。
  4. Result/Option 与标准库。
  5. 边界 trampoline 与 blame。
  6. 类型级 comptime(最后,需与宏提案统一)。

已实现的第一步(2026-11-20)

OP 0017 落地了探针:#lang oort-core、 Int/Bool/Unit、标注必填的函数、局部推断、if/return、独立的 CoreTypeChecker。它验证了模块级静态/动态路由,但还不是本提案的完整 实现:expected-type 传播、泛型、ADT/match、Result/Option、静态对象 模型与跨方言 FFI 仍待完成。探针阶段显式拒绝跨方言导入,避免在 trampoline 之前假装有健全边界。

跨模块类型标注已实现(OP 0025 增量 A,2026-11-22):类型导出与值导出 分表;from 导入类同时绑定构造器与类类型;enum 类型名通过 m.E 引用, 不支持 type-only 导入。标注仍在检查后擦除,运行时与字节码不改。

单继承也已实现(OP 0025 增量 B,2026-11-22):基类槽/方法继承、覆盖、 super、名义子类型与分支 LUB、继承槽确定赋值;函数类型参数改为逆变。 静态接口已实现(OP 0026,2026-11-22):方法契约、多接口实现与接口继承, 纯静态擦除。属性访问器仍留后续。

未解决问题

  • var 与 val 的类型可变性(流敏感类型?)。
  • 变型规则已确定为声明处 in/out(见 §3.1);仍需确认是否允许使用处投影, 以及类与 trait 是否采用同一套健全性校验。
  • 动态方言中的类型标注是“文档”还是“运行时断言”?