想象你是快递分拣中心新上任的主管。传送带上，包裹从来不是一种：信封薄而软，纸箱方方正正，圆筒一碰就滚。更麻烦的是，有的包裹里还套着更小的包裹。你的信息系统却只会说一句话：“所有包裹都是纸箱。”于是分拣错误、爆仓、投诉接连不断。这几乎是所有编译器团队都会撞上的墙：类型系统太粗糙，表达不了“一个东西要么是 A、要么是 B、要么是 C”。TVM 在 RELAY IR 中引入代数数据类型（ADT），正是为了打破这堵墙——它让类型系统能描述“多种形状”的数据，并提供一套叫模式匹配的“分拣规则表”，安全高效地把每种形状的处理流程独立出来。本文就用这套分拣中心的视角，把 ADT 的定义、语法、匹配、编译、类型检查到实际应用完整讲一遍。

岗位关联

读懂 ADT，你就拿到了理解 RELAY 类型系统的钥匙：动态形状、循环展开、图匹配优化这些 TVM 核心能力，都建立在“能安全描述和分支处理异构结构”之上。对 AI 从业者而言，这是从“用编译器”迈向“改编译器”的必经一站。

目录
  1. 可视化演示
  2. ADT基本概念
  3. RELAY定义语法
  4. 和类型与积类型
  5. 模式匹配机制
  6. 编译处理流程
  7. ADT类型检查
  8. 循环递归表达
  9. TVM实际应用
  10. AI 应用场景
  11. Python 演示
  12. 常见误区
  13. 面试题

可视化演示

展示RELAY IR中代数数据类型的和类型积类型构造、模式匹配分派及递归类型展开，交互切换查看ADT核心机制。

本节配有交互动效（进入视口后自动加载，约 3KB）。

类型构造：和类型与积类型 和类型取值空间为各构造器基数之和 积类型取值空间为各字段基数之积 |Sum|=|A|+|B| ADT通过构造器组合类型空间

ADT基本概念

你走进快递分拣中心，传送带上一片混乱：信封、纸箱、圆筒三种形状的包裹混在一起。老分拣系统只认识“纸箱”这一种类型，遇到信封就罢工。ADT（代数数据类型）就是为这种情况设计的：它允许类型系统说清楚“我可能是信封、也可能是纸箱、还可能是圆筒”。在 TVM 的 RELAY IR 中，ADT 是表达这类异构结构的基础设施。

ADT 由两种基础拼图构成。积类型（product type）像一张表格：所有字段同时存在，比如纸箱的面单必须有收件人、地址、重量三栏，缺一不可，这是“与”的关系。和类型（sum type）像一张候选清单：一次只能选一个，包裹要么是信封、要么是纸箱、要么是圆筒，这是“或”的关系。每个候选叫一个变体，而“把材料打包成一个变体值”的动作由构造器（constructor）完成。

每个构造器生产的值都会携带一个整数标签，标识自己是第几个变体，类似面单上的类型编号。不同构造器可以携带不同的字段集合：信封带一个地址字段，纸箱带重量字段，圆筒带直径字段。这样，一个 ADT 值 = 标签 + 对应的字段，在运行时既能区分“我是谁”，又能安全读取“我有什么”。

回到分拣中心：积类型是那张必须全部填写的面单，和类型是“今天只来一种包裹”的约束。代数数据类型这个名字听着吓人，实际上就是把“与”和“或”组合起来，让编译器也能像分拣主管一样，清楚地知道传送带上可能出现的每一种情况。

∣A⊕B∣=∣A∣+∣B∣,∣A×B∣=∣A∣×∣B∣\displaystyle |A \oplus B| = |A| + |B|, \quad |A \times B| = |A| \times |B|
值的总数满足“加法”与“乘法”的算术规律，这正是“代数”二字的来源。
  1. 和类型 A ⊕ B⊕ 表示不相交并集，取值要么来自 A、要么来自 B，代表“或”的关系。
    A⊕B={⟨0,a⟩∣a∈A}∪{⟨1,b⟩∣b∈B}A \oplus B = \{ \langle 0, a \rangle \mid a \in A \} \cup \{ \langle 1, b \rangle \mid b \in B \}
  2. 取值个数相加A 有 |A| 种值、B 有 |B| 种值，和类型总共 |A| + |B| 种，对应三种包裹并集的规模。
    ∣A⊕B∣=∣A∣+∣B∣|A \oplus B| = |A| + |B|
  3. 积类型 A × B× 的取值是成对组合 (a, b)，代表“与”的关系，对应面单上多个字段同时存在。
    A×B={(a,b)∣a∈A,b∈B}A \times B = \{ (a, b) \mid a \in A, b \in B \}
  4. 取值个数相乘每个 a 都能配任意 b，总数是 |A| × |B|，所以叫积类型。
    ∣A×B∣=∣A∣×∣B∣|A \times B| = |A| \times |B|

RELAY定义语法

分拣中心要接纳新形状的包裹，第一步不是改造机器，而是更新“包裹类型登记表”：给新类型起名、列出它的每种包装方式、每种包装需要哪些材料。RELAY 中用 data 关键字做同样的登记：

这段声明告诉编译器：存在一个名为 List 的泛型数据类型，它有两种构造方式。Nil 是零参构造器，代表“空列表”，类似一个不需要任何材料就能完成的空包裹；Cons 是两参构造器，接收一个 T 类型元素和另一个 List<T>，类似把一件物品装进一个更小的同型包裹里。冒号左边是构造器名字，右边是函数签名，读作：用这些参数，你能得到这个类型的值。

data 语法与函数定义 def 是并列的顶层语法形式，因此 ADT 可以出现在 RELAY 程序的任意作用域中。RELAY 的解析器对 data 声明提供专门支持，解析后将 ADT 定义注册进全局类型环境，后续表达式才能引用这些构造器。泛型参数 <T> 让一个 ADT 定义能复用于不同类型，例如 List<Tensor> 与 List<Shape>。

登记表填好，分拣系统就知道了三种包裹的存在。data 一词，用贴近数据而非算法的语气告诉编译器：“这几种形状，你以后都会见到，请提前做好准备。”这就为后续的匹配与分拣打好了基础。

data  List(T)=Nil∣Cons(T,  List(T))\displaystyle \text{data}\; \text{List}(T) = \text{Nil} \mid \text{Cons}(T,\; \text{List}(T))
竖线 | 是“或”，把数据类型的全部变体一一列出，就像登记表上列出每种包装方式。
  1. data 关键字向编译器登记一个新类型的开始，声明后面跟着类型名字。
    data  List(T)\text{data}\; \text{List}(T)
  2. 类型参数 (T)List 是泛型类型，T 可被任意具体类型替换，让一个定义服务多种元素。
    List(T)=Nil∣Cons(T,  List(T))\text{List}(T) = \text{Nil} \mid \text{Cons}(T,\; \text{List}(T))
  3. 竖线 | 分隔变体读出“或”的味道，Nil 与 Cons 是两种互斥的构造方式。
    Nil∣Cons(T,  List(T))\text{Nil} \mid \text{Cons}(T,\; \text{List}(T))
  4. 构造器签名每个构造器声明自己的参数类型，Nil 无参数，Cons 含头部与尾部两参。
    Nil:()→List(T),Cons:(T,List(T))→List(T)\text{Nil} : () \to \text{List}(T), \quad \text{Cons} : (T, \text{List}(T)) \to \text{List}(T)
text4 行
data List<T> {  Nil : () -> List<T>  Cons : (T, List<T>) -> List<T>}

和类型与积类型

面单黏在包裹上，内容物装在里面——两者合在一起，才构成一个可识别的快件。ADT 的内部编码也是同样的思路：每个值 = 标签 + 字段负载，这种形式叫带标签联合（tagged union）。

积类型贡献了“多字段同时存在”的能力。RELAY 的构造器参数在底层被组织成一个元组，例如 Cons(1, tail) 的两个参数就构成一个积：任何时候你都同时拥有头部和尾部。和类型贡献了“多选一”的能力：整个 List 若非 Nil 即 Cons，永远不可能既是 Nil 又是 Cons。

带标签联合的编码方式是：先用一个整数记录当前是哪个变体，再把该变体的字段作为另一个数组存储。消费方拿到值后，先读标签判断变体，再按变体解释字段。RELAY 还提供了 Option 之类的内建和类型，用于表达“可能有值也可能没有”的场景，例如安全地从映射中查键。

当三种包裹在传送带上混行时，分拣机不需要拆开包裹就知道该走哪条道——它只需扫面单的标签。这就是带标签联合的精髓：把“我是谁”的决定权交给显式标签，而不是靠猜。

encode(v)=⟨tag(v),  fields(v)⟩\displaystyle \text{encode}(v) = \big\langle \text{tag}(v),\; \text{fields}(v) \big\rangle
每一个 ADT 值都被编码成“标签 + 字段”的二元组，标签决定如何解释字段。
  1. tag(v)取出 v 的构造器索引，一个从 0 开始的整数，标识它是第几个变体。
    tag(v)∈{0,1,…,n−1}\text{tag}(v) \in \{0, 1, \ldots, n-1\}
  2. fields(v)取出 v 携带的字段列表，里面按构造器签名的顺序存放参数。
    fields(v)=(f1,f2,…,fk)\text{fields}(v) = (f_1, f_2, \ldots, f_k)
  3. 角括号 ⟨·⟩把标签与字段打包成一个整体，共同构成值的运行时表示。
    ⟨tag(v),  fields(v)⟩\big\langle \text{tag}(v),\; \text{fields}(v) \big\rangle
  4. 编码全貌消费者先看标签、再按需取字段，整个编码过程保证“知道是谁”与“拿到什么”不分离。
    encode(v)=⟨tag(v),  fields(v)⟩\text{encode}(v) = \big\langle \text{tag}(v),\; \text{fields}(v) \big\rangle

模式匹配机制

有了面单标签，分拣机怎么处理每个包裹呢？靠的是一张“分拣规则表”：每条规则写着“如果标签是信封，就走扫描通道；如果标签是纸箱，就走称重通道……”。RELAY 中的 match 表达式就是这张规则表。

match 接受一个要检查的值，以及若干分支。每个分支由两部分组成：左边的模式（pattern）和右边的表达式。模式刻画出一种可能的形状，比如 Nil 或 Cons(h, t)。当被匹配的值与某个模式吻合时，分支表达式就会被执行。

模式中出现的名字不是新建变量，而是从被匹配值的字段中“解构”出来的绑定。比如在 Cons(h, t) 模式中，h 会绑定到列表头部、t 绑定到尾部，这些绑定只在对应分支体内可见。RELAY 的类型检查器还会做穷尽性检查：如果某些构造器没有对应分支，编译会直接报错，防止运行时出现“不知道该怎么办”的包裹。

分拣规则表写全了，任何形状的包裹都有处理通道，没有例外。穷尽性检查让编译器成为你的质检员：漏写一个变体，它当场指出，而不用等包裹卡在传送带上才发现。

match  x  with  Nil⇒e0∣Cons(h,t)⇒e1\displaystyle \text{match}\; x\; \text{with}\; \text{Nil} \Rightarrow e_0 \mid \text{Cons}(h, t) \Rightarrow e_1
一个 match 表达式 = 一条将被散的值 + 一组“模式 → 动作”的分支，分支之间用竖线连接。
  1. match x对值 x 开启分派，x 必须是某个 ADT 类型的值。
    match  x\text{match}\; x
  2. Nil ⇒ e₀第一个分支的模式是构造器 Nil，命中后执行表达式 e₀。
    Nil⇒e0\text{Nil} \Rightarrow e_0
  3. 竖线连接分支分支按顺序逐个测试，每个分支对应一个变体。
    e0∣Cons(h,t)⇒e1e_0 \mid \text{Cons}(h, t) \Rightarrow e_1
  4. Cons(h,t) ⇒ e₁模式里绑定 h、t，对应字段由模式解构赋值，分支体中使用这两个名字。
    Cons(h,t)⇒e1\text{Cons}(h, t) \Rightarrow e_1

编译处理流程

登记表、面单、规则表都是给管理层看的；传送带上的机械臂听不懂这些，它们只认挡板位置和推杆动作。ADT 也一样：RELAY 的构造器和 match 是给编译器前端和高层优化 pass 看的，生成最终代码前，它们会被降级成简单的标签整数和分支跳转。

降级的第一步，是把每个构造器调用编码为二元组（标签，字段数组）；第二步，是把 match 表达式编译成对标签的连续比较，类似级联的 if-else，或者按标签索引的跳转表；第三步，是把模式中的绑定变量替换为对字段数组的投影访问。经过这三步，复杂的模式匹配就变成了普通的运行时分支。

因为标签是连续整数，RELAY 可以选用 switch 跳转表把匹配优化到 O(1)。字段投影只需根据构造器签名给出的偏移量访问数组元素，几乎零开销。此外，如果一个 ADT 类型只使用过一部分构造器，死代码消除还能删掉永不触发的分支，让生成的代码更紧凑。

面单被翻译成了机械臂能懂的挡板指令，三种包裹最终各就各位。ADT 的抽象在编译过程中被安全地“拆解”了，而这个过程中，模式匹配的安全性一次都没有打折。

process(x)={ei[y⃗i↦proji(x)]if tag(x)=i\displaystyle \text{process}(x) = \begin{cases} e_i[\vec{y}_i \mapsto \text{proj}_i(x)] & \text{if } \text{tag}(x) = i \end{cases}
匹配被编译成“比较标签 → 投影字段 → 替换绑定”的分情形处理，与 if-else 或 switch 一一对应。
  1. process(x)表示 x 经过模式匹配后的整体行为，是编译产物的抽象描述。
    process(x)\text{process}(x)
  2. tag(x) = i读取 x 的构造标签，若等于第 i 个变体的编号则进入该情形。
    tag(x)=i\text{tag}(x) = i
  3. proj_i(x)投影操作，按第 i 个构造器的签名从字段数组中取出对应位置的值。
    proji(x)\text{proj}_i(x)
  4. 替换绑定变量把模式中绑定的变量 \vec{y} 替换成投影结果，原模式表达式变成纯数据访问。
    ei[y⃗i↦proji(x)]e_i[\vec{y}_i \mapsto \text{proj}_i(x)]

ADT类型检查

任何包裹要登上传送带，先得过质检关：面单上写着信封，内容物就必须是信封该有的样子。ADT 的类型检查规则做的就是这件事——保证构造器用对的参数造出对的值。

类型检查器对每个构造器给出一条规则：如果你有一个类型为 τᵢ 的值 v，那么用第 i 个构造器 Cᵢ 包装 v，得到的就是目标 ADT 类型 D 的值。这条规则保证了从任何构造器出来的值，在类型上都统一为 D，消费者可以放心地匹配。

对 match 表达式的检查，RELAY 要求每个分支产生相同的返回类型，否则合并类型会不一致；同时要求模式覆盖所有构造器，即穷尽性检查。对于泛型 ADT，类型检查器会在实例化时把类型参数替换为具体类型，例如 List<Tensor> 中的 T 被替换成 Tensor，并在替换后验证构造器参数类型仍然匹配。

质检员点头放行后，包裹才允许上流水线。类型规则让“面单与内容一致”不再是口头承诺，而是编译期就被强制执行的铁律——这正是 ADT 比无标签 union 安全的核心原因。

Γ⊢v:τiΓ⊢Ci(v):D\dfrac{\Gamma \vdash v : \tau_i}{\Gamma \vdash C_i(v) : D}
横线上方是前提：环境能推出 v 的类型；横线下方是结论：构造器调用得到目标类型 D。
  1. Γ ⊢ vτᵢ：Γ 是类型环境，⊢ 表示“可推出”，整个前提断言 v 拥有类型 τᵢ。
    Γ⊢v:τi\Gamma \vdash v : \tau_i
  2. 横线（推导规则）表示“前提成立则结论成立”，是自然演绎中的一条推理规则。
    前提结论\dfrac{\text{前提}}{\text{结论}}
  3. Cᵢ(v)D：第 i 个构造器包装 v 后，产物类型是 ADT 类型 D，与具体参数类型无关。
    Γ⊢Ci(v):D\Gamma \vdash C_i(v) : D
  4. 每个构造器一条规则所有变体的构造器都指向同一个目标类型 D，消费者无需关心具体来源。
    C1(τ1):D,  C2(τ2):D,  …,  Cn(τn):DC_1(\tau_1): D,\; C_2(\tau_2): D,\; \ldots,\; C_n(\tau_n): D

循环递归表达

最棘手的包裹是套娃：纸箱里还有纸箱，一层套一层，深不见底。以前的分拣机看到这种包裹直接死机，因为它只会处理“一层”的结构。ADT 的递归类型就是为这样的套娃而生的。

在 List 的定义中，Cons 的第二个参数的类型正是 List 本身——定义中出现了自己，这就是递归类型。有了它，任意长度的序列都能表达：最少是 Nil，多一个元素就把 Cons 再套一层。树的表达同理：树要么是一片叶子，要么是一个节点带着几棵子树。

递归类型给了 RELAY 表达循环和深度结构的能力。RNN 的时间步序列可以建模为一个 ADT 列表，网络体作为 Cons 的字段，编译器通过模式匹配对每个时间步应用网络体，生成展开的循环代码。对于固定步数，编译期就能完全展开；对于动态步数，则降级为带运行时的循环执行。

分拣机学会递归后，套娃包裹不再是噩梦：拆开一层，里面露出更小的一层，按同一套规则继续处理，直到遇见最里层的“空包裹”。这种“自己处理自己”的优雅简洁，让 RELAY 第一次真正意义上支持了循环与递归网络结构。

[1,2,3]=Cons(1,  Cons(2,  Cons(3,  Nil)))\displaystyle [1, 2, 3] = \text{Cons}(1,\; \text{Cons}(2,\; \text{Cons}(3,\; \text{Nil})))
单个元素逐层嵌套在 Cons 中，最内层是一个 Nil——递归类型用这个模式表达任意长度的序列。
  1. Nil递归的终止记号。分拣机的“空包裹”，表示序列在这里结束。
    Nil\text{Nil}
  2. 最内层 Cons(3, Nil)只有一个元素的列表，尾部指向空列表。
    Cons(3,  Nil)\text{Cons}(3,\; \text{Nil})
  3. 逐层向外嵌套每次在外层再套一个 Cons，元素 2 与元素 3 所在的小列表相连。
    Cons(2,  Cons(3,  Nil))\text{Cons}(2,\; \text{Cons}(3,\; \text{Nil}))
  4. 完整链表元素 1 套在最外层，得到长度为 3 的列表，整个过程可无限重复。
    Cons(1,  Cons(2,  Cons(3,  Nil)))\text{Cons}(1,\; \text{Cons}(2,\; \text{Cons}(3,\; \text{Nil})))

TVM实际应用

分拣中心终于完成了全面升级：能处理异形包裹、能应对套娃、能根据路况动态调整通道。这套能力放到 TVM 里，就是 RELAY 引入 ADT 后解锁的一连串实际应用。

最直接的应用是动态形状。深度模型推理时 batch size 常常在请求间变化，静态形状编译器只能针对固定形状优化。借助 ADT，形状可以定义为静态维度与动态维度的和类型，编译产物同时覆盖所有情况，让单个内核服务不同 batch 的请求。

ADT 还用于 RELAY 的计算图优化：许多 pass 本身就是“图模式匹配”——在图上查找特定结构并替换，而 ADT 的模式匹配为这种遍历提供了统一且安全的机制。此外，像 Shape::Static(n) 这样的构造器在 pass 中可以作为编译期可证明的信息源，让图优化在合法时开启动态形状相关的简化，在不可能时安全地跳过。

从异形包裹到套娃再到动态路由，ADT 让 RELAY 这台“分拣机”拥有了完整的表达能力：类型安全地描述“可能是什么”，并高效地处理“每一种可能”。这正是现代机器学习编译器处理复杂、动态网络结构时的必备基础。

Shape=Static(n)∣Dynamic(s)\displaystyle \text{Shape} = \text{Static}(n) \mid \text{Dynamic}(s)
一个形状维度要么是编译期已知的静态大小，要么是运行时才可知的动态符号，二者构成和类型。
  1. Static(n)静态形状，n 是编译期确定的整数，可触发常量折叠与内存规划。
    Static(n)\text{Static}(n)
  2. Dynamic(s)动态形状，s 是符号变量，运行时才绑定具体数值。
    Dynamic(s)\text{Dynamic}(s)
  3. 符号 s用符号表示未知维度，例如请求到达前的 batch size。
    s∈Symbolss \in \text{Symbols}
  4. 联合类型维度要么静态、要么动态，编译器按标签分发到两种优化路径。
    Shape=Static(n)∣Dynamic(s)\text{Shape} = \text{Static}(n) \mid \text{Dynamic}(s)

AI 应用场景

动态形状推理服务编译

阶段：模型编译与部署优化

解决的问题：传统 TVM 对静态形状编译，推理服务请求的 batch size 一旦变化，旧内核失效需要重新编译，造成延迟尖峰。利用 ADT 的 Shape = Static(n) | Dynamic(s)，编译产物可以覆盖多档 batch，运行时按标签分发，既保留静态优化又兼顾动态变化。

具体案例：某在线推荐系统在高峰与低谷期 batch 从 1 到 64 波动。使用 RELAY 动态形状路径后，单个内核适配所有 batch，吞吐提升约 30%，启动时编译次数降到接近零。

RNN 循环网络编译

阶段：图优化与代码生成

解决的问题：循环网络的时间步在图中展开会得到超长计算图；不用 ADT 时，手动展开或宏生成都很脆弱。用递归 List 类型表达时间步序列，以模式匹配逐时间步应用网络体，编译器即可生成循环或有限展开。

具体案例：语音识别 LSTM 推理中，时间步长随音频长度动态变化。ADT 列表让编译器生成按时间步循环的内核，内存占用稳定，首次编译时间明显缩短。

图融合优化 Pass

阶段：编译优化（算子融合）

解决的问题：手写遍历计算图判断节点类型容易出错、难以维护。ADT 模式匹配把“识别结构”与“提取字段绑定”统一起来，还附带穷尽性检查，新增算子类型时编译器会提醒补全 pass 分支。

具体案例：TVM Pass 用 match 优雅描述 Conv+BN+ReLU 融合模式，模式中绑定的变量直接用于生成融合算子，融合规则像分拣规则表一样清晰可查。

Python 演示

python71 行
"""RELAY ADT 的 Python 类比:构造器、标签与模式匹配"""  class TagValue:    """ADT 底层表示:tag 标签 + fields 字段"""     def __init__(self, tag, fields):        self.tag = tag        self.fields = fields  def make_constructor(tag):    """构造器工厂:把参数打包成带标签的值"""     def constructor(*fields):        return TagValue(tag, fields)    return constructor  # 类型定义:List = Nil | Cons(T, List)  (模拟 RELAY data 声明)Nil = make_constructor(0)Cons = make_constructor(1)  def match(value, arms):    """模式匹配:按 tag 分发到对应分支"""    for tag, fn in arms:        if value.tag == tag:            return fn(*value.fields)    raise ValueError("non-exhaustive match: 缺少构造器分支")  def length(lst):    """递归计算链表长度,对应 RELAY 的 match 写法"""    return match(lst, [        (0, lambda: 0),        (1, lambda head, tail: 1 + length(tail)),    ])  def to_list(lst):    """把 ADT 链表转换成 Python 列表"""    return match(lst, [        (0, lambda: []),        (1, lambda head, tail: [head] + to_list(tail)),    ])  # 类型定义:Shape = Static(n) | Dynamic(s)  (模拟动态形状)Static = make_constructor(0)Dynamic = make_constructor(1)  def shape_desc(shape):    """对 Shape 值做模式匹配"""    return match(shape, [        (0, lambda n: "static size %d" % n),        (1, lambda s: "dynamic symbol %s" % s),    ])  def main():    lst = Cons(1, Cons(2, Cons(3, Nil())))    print("length =", length(lst))    print("to_list =", to_list(lst))    print(shape_desc(Static(32)))    print(shape_desc(Dynamic("batch")))  if __name__ == "__main__":    main()
目的：用纯 Python 模拟 RELAY 的 ADT 构造器、标签分发式模式匹配与递归列表处理，直观展示编译器内部降级后的核心机制。
  1. class TagValue对应 ADT 值的运行时表示：一个标签加一串字段。
  2. def make_constructor(tag)构造器工厂，把任意参数打包成带标签的值。
  3. Nil = make_constructor(0)零参构造器，标签为 0，无需参数即可构造。
  4. Cons = make_constructor(1)两参构造器，标签为 1，参数被冻结在 fields 中。
  5. def match(value, arms)对应编译后的标签分发逻辑，逐个比较 tag。
  6. if value.tag == tag现场版“扫描面单”，命中后调用对应分支函数。
  7. raise ValueError(...)模拟穷尽性检查失败：漏了某个构造器分支。
  8. lambda head, tail: 1 + length(tail)模式绑定：从 fields 解构出头和尾并递归。
  9. (0, lambda: [])Nil 分支直接返回空列表，是递归的终止条件。
  10. shape_desc(shape)对动态形状类型的值做模式匹配，语义与 RELAY 的 Shape ADT 一致。

常见误区

误区“ADT 不就是自定义数据类型吗？跟结构体差不多，无非是把几个字段打包在一起，没什么特别的。”

正解结构体只是积类型，表达“同时拥有字段 A 和 B”；ADT 还包含和类型，表达“要么是 A 要么是 B”。这个“或”的能力，才是表达可选值、动态形状和递归结构的根基。RELAY 里的 List 若不是 Nil 就必然是 Cons，结构体永远表达不了这种二选一。

为何常见：大多数程序员最早接触的自定义类型是 struct/class，容易把“自定义类型”简单等同于“积类型”，忽略了和类型这个关键维度。

误区“match 不就是个好看的 if-else 吗？写得花哨一点而已，功能上跟手写分支没区别。”

正解模式匹配的独特价值在编译期：穷尽性检查保证所有变体被覆盖，模式绑定自动从字段中解构变量，编译器还能将匹配优化为跳转表。这些是手写 if-else 无法自动获得的正确性保证，不是语法层面的甜味剂。

为何常见：从最终生成的指令看，确实都是分支跳转，于是容易忽略编译期间的类型级保证才是模式匹配的灵魂。

误区“ADT 是 Haskell 这类函数式语言才玩的东西，工业编译器用不上，学了也没用。”

正解TVM 的 RELAY IR 正是用 ADT 表达动态形状、循环与递归网络，这是工业级机器学习编译器的核心需求。Rust 的 enum、C++17 的 std::variant 本质上也是 ADT，离工程一点也不远。

为何常见：AI 从业者大多接触 Python/C++，对函数式构造感到疏远，误以为 ADT 与工程实践无关。

误区“C 里的 union 不就是和类型吗？都占一块内存，都可以存不同类型，名字也像。”

正解C union 是无标签联合，运行时不知道当前存的是哪个变体，读错字段就是未定义行为。ADT 的和类型是带标签联合，每个值都携带构造器标签，运行时可以安全区分并读取对应字段。

为何常见：union 与 sum type 的英文名相近（union / disjoint union），内存布局也相似，初学者极易混淆。

误区“每次构造都要打标签，每次匹配都要查标签，肯定比直接操作 struct 慢，编译器不会选它。”

正解标签只是一个小整数，匹配编译成整数比较或跳转表，现代硬件还有分支预测加持，实际开销几乎可忽略。相比它带来的表达力和编译期安全，这点成本是编译器非常乐意支付的。

为何常见：直觉上“额外的信息 = 额外的开销”，但没有考虑到编译期的优化能力和硬件层面的加速机制。

面试题

Q1. 代数数据类型中的“和类型”（sum type）相当于集合运算中的哪种操作？

单选题 · easy

  • A.交集运算
  • B.并集运算← 正确答案
  • C.补集运算
  • D.笛卡尔乘积

答案：B。和类型的取值来自 A 或 B，集合规模相加，与并集运算同构。交集和笛卡尔乘积对应积类型，补集则与类型构造无关。分拣中心的三种包裹就是“并”出来的一个集合。

Q2. 在 RELAY 中定义代数数据类型使用的关键字是？

单选题 · easy

  • A.struct 关键字
  • B.class 关键字
  • C.data 关键字← 正确答案
  • D.enum 关键字

答案：C。RELAY 用 data 声明 ADT，与 def 并列。struct/class 是面向对象语言的概念，enum 虽类似但不等于完整的 ADT。就像分拣中心的登记表，标题写的就是 data。

Q3. 下列哪个类型是典型的和类型（sum type）？

单选题 · mid

  • A.包含两个字段的元组
  • B.固定长度的数组
  • C.Tensor 张量类型
  • D.Option 可空类型← 正确答案

答案：D。Option 要么是 Some 要么是 None，是典型的“多选一”和类型。元组和定长数组是积类型，Tensor 是 RELAY 的内建类型。如同“包裹要么有内容，要么空着”。

Q4. 模式匹配的穷尽性检查主要保证什么？

单选题 · mid

  • A.所有构造器分支都被覆盖← 正确答案
  • B.匹配速度达到最优
  • C.表达式没有副作用
  • D.代码行数最短化

答案：A。穷尽性检查在编译期核对模式分支是否覆盖全部构造器，漏分支直接报错，防止运行时出现未定义行为。它不关注速度、副作用或代码行数。分拣规则表必须写全，漏掉哪种包裹形状都会被当场打回。

Q5. 带标签联合（tagged union）的编码形式是？

单选题 · mid

  • A.仅存储数据字段
  • B.标签与数据分离保存
  • C.标签与数据绑定成对← 正确答案
  • D.标签替换数据类型

答案：C。带标签联合把 tag 和 fields 打包成二元组，消费方先读标签、再根据标签解释字段。标签与数据绑定成对，才能安全区分不同变体。面单和内容物是一体的，扫面单才知道怎么处理包裹。

Q6. 构造器类型规则“如果 v : τᵢ，那么 Cᵢ(v) 的类型是什么”的结论是？

单选题 · hard

  • A.v 保持其原有类型不变
  • B.构造器调用得到目标类型 D← 正确答案
  • C.构造器调用返回空类型
  • D.构造器调用类型不确定

答案：B。规则的前提是 v 的类型为 τᵢ，结论是 Cᵢ(v) 的类型为目标 ADT 类型 D。所有构造器产出的值都统一为 D，消费者才能放心匹配。每种包装方式造出来的都是“同一类包裹”。

Q7. 递归类型 List = Nil | Cons(T, List) 无法直接表达哪种结构？

单选题 · hard

  • A.任意长度的链表
  • B.嵌套的树形数据
  • C.定长的静态数组← 正确答案
  • D.循环网络结构展开

答案：C。递归 List 能表达任意长度链表、嵌套树形和循环网络的时间步展开，但定长静态数组本质是“同时拥有 N 个槽位”的积类型，用张量或元组表达更合适。套娃能套任意多层，却放不进一个固定格子的收纳盒。

Q8. ADT 相比普通结构体的优势有哪些？

多选题 · mid

  • A.表达多种可选变体← 正确答案
  • B.模式匹配安全解构← 正确答案
  • C.穷尽性编译期检查← 正确答案
  • D.自动生成计算图

答案：ABC。ADT 能表达“多选一”的变体、通过模式匹配安全解构字段、并在编译期做穷尽性检查。自动生成计算图是 TVM 框架整体的能力，不是 ADT 本身的职责。结构体只会说“同时有这些字段”，ADT 还能说“要么这种、要么那种”。

Q9. 关于模式匹配的编译降级过程，下列说法正确的有？

多选题 · hard

  • A.按标签整数比较分发← 正确答案
  • B.绑定变量投影字段← 正确答案
  • C.分支数量必须为偶数
  • D.可采用跳转表加速← 正确答案

答案：ABD。匹配被编译成对标签整数的比较分发，模式绑定的变量用字段投影替换，标签连续时可以优化为跳转表。分支数量没有奇偶限制，只要覆盖全部构造器即可。分拣机的机械臂不关心有几条滑道，只关心每条都有对应的挡板动作。

Q10. TVM 的 RELAY 引入 ADT 的目的包括？

多选题 · easy

  • A.表达动态数据形状← 正确答案
  • B.表达循环递归结构← 正确答案
  • C.替代硬件指令集
  • D.提升编译期安全← 正确答案

答案：ABD。RELAY 用 ADT 表达动态形状（如 Shape = Static | Dynamic）、循环递归结构（如 List 表达时间步）并提升编译期安全（穷尽性检查与类型规则）。ADT 是编译器的类型系统能力，与硬件指令集无关。分拣中心升级信息系统，不等于重新发明传送带电机。