Roc 类型系统解析带注解的标签联合如何泛化扩展变量并在更宽联合中复用【免费下载链接】rocA fast, friendly, functional language.项目地址: https://gitcode.com/GitHub_Trending/ro/roc导读本文围绕 Roc 编译器快照测试generalize_annotated_value_tag_widening深入讲解Hindley-Milner 泛化generalization如何作用于带注解、非扩展non-expansive的标签联合值一个被注解为[Red, Green, ..]的开放标签联合值其尾部扩展变量会被泛化为多态变量从而能够被安全地赋给更宽的标签联合[Red, Green, Blue, ..]。读完本文你将掌握 Roc 中开放标签联合open tag union与扩展变量extension variable的语义、注解如何充当泛化的准入凭证opt-in以及如何通过快照测试从词法、解析、规范化到类型推断的完整编译管线中验证这一行为。一、从一个快照测试说起仓库 test/snapshots/generalize_annotated_value_tag_widening.md 是一个典型的编译器快照测试snapshot test。这类测试的定位在 test/snapshots/README.md 中有明确说明Snapshot tests that validate compiler behavior by capturing the output of each compilation stage for specific Roc code examples.即通过捕获特定 Roc 代码在编译各阶段词法分析、解析、规范化、类型检查等的输出来校验编译器行为帮助在编译器行为发生意外变化时检测回归。该快照的 META 区给出了测试的语义定位descriptionAn annotated, non-expansive value generalizes its extension variable, so it is usable at a wider tag union (tier-2 generalization) typefile关键词有三个annotated带注解、non-expansive非扩展/不膨胀、generalizes its extension variable泛化其扩展变量最终效果是usable at a wider tag union可用于更宽的标签联合这属于所谓tier-2 generalization第二级泛化。测试的完整源码快照的 SOURCE 段内容如下app [main!] { pf: platform ../basic-cli/main.roc } f : [Red, Green, ..] f Red g : [Red, Green, Blue, ..] g f main! |_| {}这段代码构成一个完整的 Roc 应用头部声明main!为对外暴露的入口并使用basic-cli平台../basic-cli/main.roc。核心逻辑只有两个顶层绑定f被注解为开放标签联合[Red, Green, ..]实际值是单个标签Redg被注解为更宽的开放标签联合[Red, Green, Blue, ..]直接复用f。main! |_| {}是应用入口接收一个参数并返回空记录保证程序可编译运行。EXPECTED 与 PROBLEMS 的含义快照的# EXPECTED和# PROBLEMS均为NIL表示编译全程不产生任何诊断报告reports。根据 test/snapshots/README.md普通快照typefile的 PROBLEMS 区存放的是每个reporting.Report的规范 S-表达式序列化NIL意味着编译无任何错误或警告。这一结果本身就是断言把带注解的开放标签联合值赋给更宽的联合类型是合法的、类型安全的行为。二、背景知识Roc 的开放标签联合与扩展变量2.1 结构类型与标签联合Roc 的类型系统以结构类型structural types为主——类型由形状决定形状相同即为同一类型无需预先声明。在 docs/langref/types.md 的 Structural Types 一节中列出了三类结构类型记录records、标签联合tag unions与元组tuples{ name : Str, age : U64 } # 记录 [Ok(a), Err(e)] # 标签联合 (Str, U64) # 元组2.2 开放联合与扩展变量记录和标签联合既可以是**封闭closed的恰好包含列出的字段/标签也可以是开放open**的——以扩展变量结尾表示还可能有更多{ name : Str, .. } # 任何至少包含 name : Str 的记录 { name : Str, ..r } # 同上并把剩余部分命名为 r [Red, Green, ..] # 该联合或任何更宽的联合 [Red, Green, ..u] # 同上并把剩余部分命名为 u关键语义引自 docs/langref/types.mdAn anonymous extension (..) is a fresh variable each time; a named one (..r) lets you refer to the same rest in more than one place.匿名扩展变量..每次出现都是一个全新的变量代表可能存在的其他标签具名扩展变量..u可以在多处引用同一个剩余部分从而表达两个类型共享相同的尾部。类型注解f : [Red, Green, ..]表达的正是这种开放性f的类型是包含Red、Green且还可能包含其他标签的联合。因此[Red, Green, ..]是[Red, Green, Blue, ..]的一个子类型——凡是能接受后者中Red/Green的上下文也一定能接受前者。2.3 为什么需要泛化仅靠开放联合的子类型关系还不足以解释测试中的赋值。关键在于f的扩展变量..是本地的、新鲜的变量把它赋值给g时编译器需要让f的扩展变量能够与g中额外出现的Blue兼容。这正是 Hindley-Milner 泛化要解决的问题在完成 let 绑定的类型推断后将类型中未受约束的变量转化为可多态实例化的变量详见 src/types/generalize.zig 顶部注释In Hindley-Milner type systems, we use ranks to track the scope level where type variables are introduced. When we finish inferring a let-binding, we attempt to generalize its type - converting concrete type variables into polymorphic ones that can be instantiated differently at each use site.三、TYPES 段泛化前后的类型形态快照的# TYPES段记录了类型检查最终推断出的类型inferred-types(inferred-types (defs (patt (type [Green, Red, ..])) (patt (type [Blue, Green, Red, ..])) (patt (type _arg - {}))) (expressions (expr (type [Green, Red, ..])) (expr (type [Blue, Green, Red, ..])) (expr (type _arg - {}))))三个定义的类型分别是定义推断类型说明f[Green, Red, ..]开放标签联合尾部为匿名扩展变量g[Blue, Green, Red, ..]更宽的开放标签联合main!_arg - {}接收任意参数的函数返回空记录注意两点标签顺序被规范化Red, Green→Green, RedRed, Green, Blue→Blue, Green, Red。这说明标签联合在类型表示中是无序集合快照输出按某种规范序排列f与g的类型都保留了尾部扩展变量..而不是被展开成具体类型。g的类型正是在f的类型基础上追加了Blue得到的更宽联合。类型检查器接受g f本质上是接受如下统一unificationf的扩展变量rigid var#others与g类型中除Red, Green之外的部分合一而g中多出的Blue恰好落入该扩展变量的取值范围内。这只有在f的扩展变量已经被泛化generalized为多态变量后才能成立——否则两个定义各自持有独立的刚性变量赋值必然失败。3.1 CANONICALIZE 段规范化的证据快照的# CANONICALIZE段展示了源码被规范化canonicalize之后的中间表示CIR。其中f的注解被规范化为(annotation (ty-tag-union (ty-tag-name (name Red)) (ty-tag-name (name Green)) (ty-rigid-var (name #others))))这里出现了关键信息扩展变量在规范化 IR 中被表示为ty-rigid-var (name #others)——一个名为#others的刚性类型变量rigid type variable。g的注解同样被规范化为包含Red、Green、Blue三个ty-tag-name外加同一个#others刚性变量的联合。Roc 编译器内部用rigid与flex两类变量刻画类型约束刚性变量一旦被绑定就不再改变其定义可参见 src/check/snapshot.zig 中的SnapshotContent联合类型flex/rigid/alias/structure/recursive/err。泛化的本质见 src/types/generalize.zigGeneralization is per-variable, not per-type.A type can be partially generalized where some variables are quantified while others remain as shared unification variables that escaped from outer scopes.也就是说泛化是逐变量进行的。f的类型[Red, Green, #others]中Red、Green是确定性的标签真正被泛化的是#others这个扩展变量——它被提升为多态变量允许在不同使用点被实例化为不同的其余部分。这正是快照描述中所说generalizes its extension variable的底层机制。四、tier-2 泛化注解是泛化的准入凭证4.1 注解即 opt-in快照描述中出现的tier-2 generalization是这批泛化快照测试共用的术语。与之配套的系列测试见 test/snapshots 目录下的generalize_annotated_value_*系列generalize_annotated_value_multi_type.md注解值可在两种具体类型间实例化generalize_annotated_value_block_local.md块级非顶层注解值同样构成真正的 schemegeneralize_annotated_value_expansive.mdRHS 为函数调用expansive的注解值仍可被泛化——注解本身就是 opt-in膨胀性不阻碍泛化generalize_annotated_value_unannotated_not_generalized.md未注解的值不会被泛化tier-2 门槛在同一值上使用两种具体类型会报类型不匹配generalize_annotated_value_record_function_field.md类型内嵌函数的注解值可泛化generalize_annotated_value_nested_expansive.md嵌套膨胀场景generalize_annotated_value_constrained.md携带 where 约束的顶层注解值不允许作为多态值。4.2 对照实验没有注解会怎样为了理解注解的关键作用对照同目录下的 generalize_annotated_value_unannotated_not_generalized.md。它的源码是app [main!] { pf: platform ../basic-cli/main.roc } bare [] nums : List(U64) nums bare strs : List(Str) strs bare main! |_| {}这里的bare []没有类型注解。虽然[]是非扩展non-expansive的右值但因为没有注解编译器不会对它做泛化于是bare的类型被第一次使用点固定为List(U64)第二次使用时strs bare产生TYPE MISMATCH错误——期望List(Str)实际是List(U64)。快照的 PROBLEMS 段给出了完整的规范诊断结构severity、region、headline、类型对照等TYPES 段中bare的两个使用点类型分别为List(U64)与List(Str)且第二个使用点被标记为e-runtime-error。把两个测试放在一起规则就非常清晰值是否带注解是否泛化能否用于多个具体类型带注解annotated是tier-2 generalization能未注解unannotated否不能第二次使用报类型不匹配也就是说在当前的 Roc 编译器中类型注解是让顶层/let 值获得多态泛化的显式 opt-in。这也是 value restriction值限制在 Roc 中的具体体现——src/types/generalize.zig 中把顶层定义不被泛化的情形描述为 value restrictionRank 1 (outermost):Top-level definitions not being generalized (value restriction)4.3 expansive 对照实验膨胀 RHS 不阻碍带注解值另一个值得对照的是 generalize_annotated_value_expansive.md。传统 Hindley-Milner 的值限制value restriction通常会阻止语法上会分配/产生新东西的表达式如函数调用被泛化而该测试证明在 Roc 中identity : a - a identity |x| x made : List(a) made identity([]) # 函数调用expansive RHS nums : List(U64) nums made strs : List(Str) strs mademade的右值是函数调用identity([])expansive但因为带有注解List(a)它依然被泛化随后在List(U64)和List(Str)两个具体类型下分别实例化全程无诊断报告(defs (patt (type a - a)) (patt (type List(a))) (patt (type List(U64))) (patt (type List(Str))) (patt (type _arg - {})))这印证了快照描述中的论断注解是泛化的 opt-inexpansiveness 不阻碍泛化。回到本文主题f Red是非扩展右值语法上就是一个标签字面量自然同样适用 tier-2 泛化。五、编译管线各阶段如何验证这一行为快照测试的价值在于它不仅断言能编译还逐阶段钉死了中间产物任何阶段的输出漂移都会立即暴露回归。下面沿着generalize_annotated_value_tag_widening.md的快照结构走一遍完整编译管线。5.1 TOKENS词法分析KwApp,OpenSquare,LowerIdent,CloseSquare,OpenCurly,LowerIdent,OpColon,KwPlatform,StringStart,StringPart,StringEnd,CloseCurly, LowerIdent,OpColon,OpenSquare,UpperIdent,Comma,UpperIdent,Comma,DoubleDot,CloseSquare, LowerIdent,OpAssign,UpperIdent, LowerIdent,OpColon,OpenSquare,UpperIdent,Comma,UpperIdent,Comma,UpperIdent,Comma,DoubleDot,CloseSquare, LowerIdent,OpAssign,LowerIdent, LowerIdent,OpAssign,OpBar,Underscore,OpBar,OpenCurly,CloseCurly, EndOfFile,逐行对应源码的六个逻辑单元app [main!] { pf: platform ... }头f : [Red, Green, ..]——OpColon后是OpenSquare 两个UpperIdentDoubleDotCloseSquareDoubleDot即扩展变量..的词法形态f Red——OpAssign后接一个UpperIdentg : [Red, Green, Blue, ..]——DoubleDot再次出现g f——OpAssign后接LowerIdent引用小写标识符fmain! |_| {}与EndOfFile。注意f Red中Red是UpperIdent大写标识符在 Roc 词法层就是标签字面量而g f中f是LowerIdent小写标识符指代变量。这种大小写区分的词法设计是标签联合语法能够无需引号书写的原因之一。5.2 PARSE语法树解析产物是 S-表达式形式的 AST(file (app (provides (exposed-lower-ident (text main!))) (record-field (name pf) (e-string (e-string-part (raw ../basic-cli/main.roc)))) (packages (record-field (name pf) (e-string (e-string-part (raw ../basic-cli/main.roc)))))) (statements (s-type-anno (name f) (ty-tag-union (tags (ty (name Red)) (ty (name Green))) ..)) (s-decl (p-ident (raw f)) (e-tag (raw Red))) (s-type-anno (name g) (ty-tag-union (tags (ty (name Red)) (ty (name Green)) (ty (name Blue))) ..)) (s-decl (p-ident (raw g)) (e-ident (raw f))) (s-decl (p-ident (raw main!)) (e-lambda (args (p-underscore)) (e-record)))))值得注意的解析细节f的类型注解被解析为(ty-tag-union (tags (ty (name Red)) (ty (name Green))) ..)——..作为ty-tag-union的直接子节点出现说明扩展变量在语法层面就隶属于联合类型本身f Red的 RHS 是(e-tag (raw Red))即标签构造表达式g f的 RHS 是(e-ident (raw f))即对已定义变量的引用main! |_| {}是(e-lambda (args (p-underscore)) (e-record))匿名参数_ 空记录体。5.3 CANONICALIZE规范化 IR# CANONICALIZE段展示 CIR 形态前一节已详述核心是注解中的ty-rigid-var (name #others)以及g的声明体是对局部变量f的查找e-lookup-local(d-let (p-assign (ident g)) (e-lookup-local (p-assign (ident f))) (annotation (ty-tag-union (ty-tag-name (name Red)) (ty-tag-name (name Green)) (ty-tag-name (name Blue)) (ty-rigid-var (name #others)))))main!的体在 CIR 中是e-empty_record。值得注意的是 CIR 中f和g的扩展变量同名#others——这是因为它们都是匿名..规范化时各自生成内部名称快照显示为同一个占位名。5.4 TYPES类型检查结果如第三节所述最终f : [Green, Red, ..]、g : [Blue, Green, Red, ..]类型检查器在此过程中完成了一次关键的统一把f的泛化扩展变量实例化为与g类型兼容的其余部分。这一阶段的实现基础是 src/check/unify.zig 中的统一逻辑其中对rigid变量的处理可见unifyRigid等函数而泛化本身由 src/types/generalize.zig 的Generalizer.generalize()完成——它按 rank 调整变量、把可泛化变量提升为多态 scheme。整个过程没有产生任何报告快照PROBLEMS为NIL。六、实践在命令行运行该快照如果你在本地构建了 Roc 编译器源码可以用快照工具直接复现该测试详见 test/snapshots/README.md 的 Usage 一节# 生成全部快照 zig build run-snapshot-tool # 仅运行/更新指定快照 zig build run-snapshot-tool -- test/snapshots/generalize_annotated_value_tag_widening.md # 若编译器行为有意变更可用 --update-expected 刷新期望输出 zig build run-snapshot-tool -- test/snapshots/generalize_annotated_value_tag_widening.md --update-expected快照文件中的# FORMATTED段显示NO CHANGE说明该源码已经符合 Roc 格式化规范无需重排。你也可以把 SOURCE 段的代码另存为.roc文件直接用编译器入口命令验证roc build main.roc由于EXPECTED/PROBLEMS均为NIL正常构建应当不产生任何类型诊断并成功产出可执行文件。要观察未注解不泛化的对照行为将f/g的注解删去再编译即可复现generalize_annotated_value_unannotated_not_generalized.md中的 Type Mismatch 报告。七、小结一套规则两种场景回到本文开头的源码整个测试验证的是一条精确的类型规则链语法层[Red, Green, ..]是开放标签联合..是扩展变量表示还可能更多docs/langref/types.md规范化层扩展变量成为ty-rigid-var #others联合类型自带一个可变的尾部快照 CANONICALIZE 段泛化层因为f带有类型注解且 RHS 非扩展其类型被泛化为多态 scheme——特别是扩展变量被泛化tier-2 generalization使用层g f时f的方案被实例化到包含Blue的上下文与g的注解[Red, Green, Blue, ..]成功统一验证层快照的 TOKENS / PARSE / CANONICALIZE / TYPES 各段逐阶段钉死中间产物PROBLEMS 为NIL断言全程零诊断。这一测试是 Roc 编译器注解即泛化 opt-in策略的组成部分。与之配套的generalize_annotated_value_*系列快照multi_type、block_local、expansive、unannotated_not_generalized、record_function_field、nested_expansive、constrained 等共同定义了当前 Roc 类型检查器的泛化边界。想要深入底层实现可以继续阅读 src/types/generalize.zigrank 与逐变量泛化、src/check/unify.zigrigid/flex 统一、src/check/snapshot.zig类型快照表示以及 docs/langref/types.md开放/封闭类型与扩展变量的语言规范。【免费下载链接】rocA fast, friendly, functional language.项目地址: https://gitcode.com/GitHub_Trending/ro/roc创作声明：本文部分内容由AI辅助生成（AIGC），仅供参考