LSR 011 - 代数数据类型

基本信息

  • LSR 编号 011

  • 标题 代数数据类型

  • 作者 Ziyang-Bai

  • 状态 草案

  • 类型 标准规范

  • 创建日期 08-09-2026

  • 归属项目 编译器、标准库、CAS

摘要

代数数据类型由一组构造器组成。每个值保存一个构造器标签和该构造器的字段。构造后不可变。

语法

type Option<T> =
    Some(T)
  | None

type Result<T, E> =
    Ok(T)
  | Err(E)

type Tree<T> =
    Empty
  | Node(Tree<T>, T, Tree<T>)

  • type 右侧列出该类型的全部构造器

  • 构造器名称在声明模块内可见

  • 构造器可使用限定名访问，例如 Option.None

  • 同一模块内构造器名称不得重复

  • 外部模块不得给已有 ADT 追加构造器

构造器

type Ordering =
    Less
  | Equal
  | Greater

type ExprNode =
    Number(frac)
  | Symbol(text)
  | Add(ExprNode, ExprNode)

  • 零字段构造器表示枚举分支

  • 构造器字段只使用位置字段

  • 字段顺序参与构造、匹配、相等和哈希

  • 构造器不支持命名字段

  • 字段类型必须能解析，递归引用除外

构造表达式

let ok = Ok(1)
let expr = Add(Symbol("x"), Number(1/2))
let none Option<int> = None

  • 实参数量必须等于字段数量

  • 实参类型必须能赋给对应字段类型

  • 无法推导泛型实参时报类型错误

  • 构造器调用不执行隐式副作用

泛型

type List<T> =
    Nil
  | Cons(T, List<T>)

  • 类型参数在定义体内按普通类型名解析

  • 构造器使用时必须确定全部类型参数

  • where 约束不属于本条语法

类型身份与静态语义

ADT 是名义类型。类型身份由声明及其所属模块决定，而不是由构造器名称或字段形状决定。

type UserId = UserId(int)
type OrderId = OrderId(int)

UserId 与 OrderId 即使布局相同也不是同一类型，二者不得隐式互转。

  • Option<int> 与 Option<text> 是不同的静态类型

  • 带字段构造器在类型检查阶段具有从字段类型到所属 ADT 的构造函数类型

  • 零字段泛型构造器必须由期望类型或显式类型实参确定所属实例

  • 构造器的名称解析、类型实参推导和穷尽性检查全部在编译阶段完成

  • 完整静态类型信息不要求作为 ADT 值的一部分保留到运行时

泛型实现

本规范定义泛型 ADT 的静态语义，不规定唯一的代码生成策略。实现可以采用运行时擦除、编译期特化，或二者结合。

  • 擦除后的共享实现、特化后的实现必须具有相同的可观察语言语义

  • 实现可以为确定布局的值类型或性能热点生成特化版本

  • 是否特化不得改变构造器可见性、模式匹配结果、相等性或错误行为

  • 核心语言不要求运行时值携带泛型实参的完整类型描述

  • 需要反射、动态类型查询或跨语言调用时，相关元数据由独立规范定义

因此，Option<int> 与 Option<text> 在编译阶段保持不同；实现可以在运行时共享同一份代码和对象布局，也可以分别特化。

递归

type Tree<T> =
    Empty
  | Node(Tree<T>, T, Tree<T>)

  • ADT 可以直接或间接递归引用自身

  • 编译器必须拒绝非法循环类型别名

  • 递归 ADT 的运行时表示不得要求无限大小对象

运行时抽象

ADT 值在语言语义上由所属 ADT、当前构造器和按声明顺序排列的字段组成。实现必须能够区分同一 ADT 的不同构造器，并按当前构造器访问正确的字段。

概念上可写成：

ADTValue = (constructor-tag, fields...)

这只是抽象模型，不规定对象的物理布局。实现可以使用标签加值载荷、标签加指针、内联值、装箱值、指针标签或其他等价表示。

  • 构造器标签只需在所属 ADT 内唯一；其数值编码不属于可观察语言语义

  • ADT 值构造后不可变，构造器标签在值的生命周期内不得改变

  • 实现只需保留执行模式匹配、字段访问、内存管理和动态派发所必需的运行时信息

  • 完整的源码类型、类型别名和泛型推导结果不要求编码进通用 Obj

  • 递归 ADT 必须在某一层使用有限表示，例如引用、指针、句柄或等价的间接形式

模块与二进制边界

分别编译的模块必须就公开 ADT 的调用约定和数据表示达成一致，但该要求不意味着把完整静态类型系统编码进每个运行时值。

  • 模块接口必须记录检查公开构造器和字段所需的静态类型信息

  • 二进制接口必须记录或约定调用约定、布局、对齐、标签编码及所需的析构或追踪操作

  • 编译器不得仅凭源码中构造器的显示顺序假定跨版本 ABI 永久稳定

  • 改变公开 ADT 的构造器集合、字段顺序或字段类型可以构成 ABI 不兼容变更

  • 稳定 ABI、反射、序列化编号和外部函数接口的具体格式由独立 LSR 定义

标准构造

type Option<T> =
    Some(T)
  | None

type Result<T, E> =
    Ok(T)
  | Err(E)

type Binding<K, V> =
    Binding(K, V)

Option、Result 和 Binding 属于标准库基础 ADT。

Binding 表示一对绑定值。接受 Binding 的函数决定该绑定的用途；构造 Binding 不触发替换、求值或模式分支。

Binding 表达式

let b = x => 4
let c = "name" => 1
let d = a => b => c

  • lhs => rhs 的类型为 Binding<A, B>，其中 A 为 lhs 类型，B 为 rhs 类型

  • => 右结合，a => b => c 等价于 a => (b => c)

  • => 的优先级由 LSR-014 定义 [4]

  • match 分支中的 pattern => expr 使用 match 语法 [1]

sym x
let binding = x => 4
let value = substitute(equation, binding)

substitute 接收 Binding<Expr, Expr> 时的语义由 Expr 规范定义 [5]。

模式匹配

match value {
    Some(x) => x
    None => 0
}

match expr {
    Add(lhs, rhs) => lhs + rhs
    Number(n) => n
    _ => 0
}

  • 封闭 ADT 的 match 必须穷尽

  • 非穷尽匹配是编译错误，除非存在 _ 分支

  • 不可达分支应产生诊断

  • 构造器模式的字段数量必须匹配构造器定义

  • 构造器模式按位置字段绑定变量

相等与哈希

  • 构造器不同，== 为 false

  • 构造器相同且全部字段相等，== 为 true

  • 所有字段可比较时，ADT 支持 ==

  • 所有字段可哈希时，ADT 可作为哈希键

  • ADT 不自动获得排序关系

  • 可相等 ADT 值可作为集合元素 [3]

null 与可空类型

type Box =
    Box(text?)

  • null 只能出现在显式可空字段中

  • Option<T> 与 T? 不自动互转

  • 构造器不得把缺失字段隐式填成 null

See Also

参见

引用