LSR 011 - 代数数据类型
================================================================================

基本信息
--------------------------------------------------------------------------------

- LSR 编号 011
- 标题 代数数据类型
- 作者 Ziyang-Bai
- 状态 草案
- 类型 标准规范
- 创建日期 08-09-2026
- 归属项目 编译器、标准库、CAS

摘要
--------------------------------------------------------------------------------

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

语法
--------------------------------------------------------------------------------

.. code-block:: text

   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 追加构造器

构造器
--------------------------------------------------------------------------------

.. code-block:: text

   type Ordering =
       Less
     | Equal
     | Greater

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


- 零字段构造器表示枚举分支
- 构造器字段只使用位置字段
- 字段顺序参与构造、匹配、相等和哈希
- 构造器不支持命名字段
- 字段类型必须能解析，递归引用除外

构造表达式
--------------------------------------------------------------------------------

.. code-block:: text

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


- 实参数量必须等于字段数量
- 实参类型必须能赋给对应字段类型
- 无法推导泛型实参时报类型错误
- 构造器调用不执行隐式副作用

泛型
--------------------------------------------------------------------------------

.. code-block:: text

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


- 类型参数在定义体内按普通类型名解析
- 构造器使用时必须确定全部类型参数
- ``where`` 约束不属于本条语法

类型身份与静态语义
--------------------------------------------------------------------------------

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

.. code-block:: text

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


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

- ``Option<int>`` 与 ``Option<text>`` 是不同的静态类型
- 带字段构造器在类型检查阶段具有从字段类型到所属 ADT 的构造函数类型
- 零字段泛型构造器必须由期望类型或显式类型实参确定所属实例
- 构造器的名称解析、类型实参推导和穷尽性检查全部在编译阶段完成
- 完整静态类型信息不要求作为 ADT 值的一部分保留到运行时

泛型实现
--------------------------------------------------------------------------------

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

- 擦除后的共享实现、特化后的实现必须具有相同的可观察语言语义
- 实现可以为确定布局的值类型或性能热点生成特化版本
- 是否特化不得改变构造器可见性、模式匹配结果、相等性或错误行为
- 核心语言不要求运行时值携带泛型实参的完整类型描述
- 需要反射、动态类型查询或跨语言调用时，相关元数据由独立规范定义

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

递归
--------------------------------------------------------------------------------

.. code-block:: text

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


- ADT 可以直接或间接递归引用自身
- 编译器必须拒绝非法循环类型别名
- 递归 ADT 的运行时表示不得要求无限大小对象

运行时抽象
--------------------------------------------------------------------------------

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

概念上可写成：

.. code-block:: text

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


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

- 构造器标签只需在所属 ADT 内唯一；其数值编码不属于可观察语言语义
- ADT 值构造后不可变，构造器标签在值的生命周期内不得改变
- 实现只需保留执行模式匹配、字段访问、内存管理和动态派发所必需的运行时信息
- 完整的源码类型、类型别名和泛型推导结果不要求编码进通用 ``Obj``
- 递归 ADT 必须在某一层使用有限表示，例如引用、指针、句柄或等价的间接形式

模块与二进制边界
--------------------------------------------------------------------------------

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

- 模块接口必须记录检查公开构造器和字段所需的静态类型信息
- 二进制接口必须记录或约定调用约定、布局、对齐、标签编码及所需的析构或追踪操作
- 编译器不得仅凭源码中构造器的显示顺序假定跨版本 ABI 永久稳定
- 改变公开 ADT 的构造器集合、字段顺序或字段类型可以构成 ABI 不兼容变更
- 稳定 ABI、反射、序列化编号和外部函数接口的具体格式由独立 LSR 定义

标准构造
--------------------------------------------------------------------------------

.. code-block:: text

   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 表达式
--------------------------------------------------------------------------------

.. code-block:: text

   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]_

.. code-block:: text

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


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

模式匹配
--------------------------------------------------------------------------------

.. code-block:: text

   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`` 与可空类型
--------------------------------------------------------------------------------

.. code-block:: text

   type Box =
       Box(text?)


- ``null`` 只能出现在显式可空字段中
- ``Option<T>`` 与 ``T?`` 不自动互转
- 构造器不得把缺失字段隐式填成 ``null``

See Also
--------------------------------------------------------------------------------

.. seealso::

   - :doc:`LSR-005 - 模式匹配 <LSR-005>`
   - :doc:`LSR-013 - 集合类型规范 <LSR-013>`
   - :doc:`LSR-014 - 运算符规范 <LSR-014>`
   - :doc:`LSR-016 - Expr 构造与提升规范 <LSR-016>`

引用
--------------------------------------------------------------------------------

.. [1] :doc:`LSR-005 - 模式匹配 <LSR-005>` - ``match`` 分支语法、穷尽检查和构造器模式
.. [3] :doc:`LSR-013 - 集合类型规范 <LSR-013>` - 集合元素可包含可相等 ADT 值
.. [4] :doc:`LSR-014 - 运算符规范 <LSR-014>` - ``=>`` token、优先级和结合性
.. [5] :doc:`LSR-016 - Expr 构造与提升规范 <LSR-016>` - ``Binding<Expr, Expr>`` 的消费边界