Bend 编译与读回Compilation and Readback全解析从 Lambda 项到 HVM 交互网节点【免费下载链接】BendA massively parallel, high-level programming language项目地址: https://gitcode.com/GitHub_Trending/be/Bend本文围绕 BendGitHub_Trending/be/Bend 仓库中的 compilation-and-readback.md 展开系统讲解 Bend 高阶函数式程序如何被编译为 HVMHigher-order Virtual Machine交互网Interaction NetIC节点以及计算结果如何被读回readback为可读的 Bend 项。你将掌握 7 种 HVM 节点类型与极性的对应关系、λ/应用/复制/叠加等核心项的编码规则、全部编译器 pass 的执行顺序以及如何用-O选项控制每个 pass 的行为。HVM 交互网节点与端口的底层模型HVM 交互网由大量节点node与连接节点的线wire构成。每个节点包含一个main端口编号0和两个auxiliary端口编号1、2。Bend 编译器把高阶 λ 演算程序降级lower成这样的图结构再由 HVM 运行时如 CUDA 后端进行并行归约。按 compilation-and-readback.md 的说明共有 7 种节点节点种类含义Eraser擦除表示被丢弃的值*Constructor构造器CON承载 λ、应用、元组及其消解Duplicator复制器DUP承载复制duplication与叠加superpositionReference引用REF指向顶层函数的引用Number数字NUM用标签label存放数字本身Operation运算OPR用标签存放运算种类Match匹配SWI对数字的switch匹配这一节点集合在源码中的NodeKind枚举里有直接对应src/net/mod.rs 定义了Rot、Era、Opr、Swi、Con(OptionBendLab)、Tup(OptionBendLab)、Dup(BendLab)等种类。同一个节点不同语义CON 与 DUP 的上下文歧义交互网的一个精妙之处在于节点种类相同但通过从哪个端口进入来区分语义。λ 与应用共用 CON 节点一个 λ 项λx x编译为一个 Constructor 节点一个应用((λx x) (λx x))同样编译为 Constructor 节点。两者共享同一个 CON 节点结构0 - 指向 λ 出现的位置 0 - 指向函数 | | λ Lambda Application / \ / \ 1 2 - 指向 λ 体 1 2 - 指向应用出现的位置 | | 指向 λ 变量 指向实参读回时net_to_term通过访问端口判断语义从端口 0 进入 CON则它是 λ或元组从端口 2 进入 CON则它是应用从端口 1 进入则是变量。这一逻辑在 src/fun/net_to_term.rs 的read_con中实现端口 0 分支再根据is_tup启发式区分元组与 λ端口 2 分支读取函数与实参构造Term::App。复制与叠加共用 DUP 节点let {a b} x复制与叠加{a b}superposition都编译为 Duplicator 节点差异同样来自上下文0 - 指向叠加出现的位置 0 - 指向被复制的值 | | # Superposition # Duplication / \ / \ 1 2 - 指向第二个值 1 2 - 指向第二个绑定 | | 指向第一个值 指向第一个绑定读回时read_fansrc/fun/net_to_term.rs处理 DUP/TUP 节点从端口 0 进入表示叠加/元组值从端口 1 或 2 进入表示发现了一个复制将节点暂存入scope以便后续作为let展开Split与insert_split负责把分裂插入到变量使用的最低公共祖先处。Bend 核心项到 HVM 节点的完整映射compilation-and-readback.md 给出了 Bend 核心项的直接编译规则这里结合 src/fun/term_to_net.rs 的encode_term逐条展开Bend 核心项HVM 节点极性polarizationApplication应用CON--LambdaλCON-Duplication复制let {a b} xDUP-Superposition叠加{a b}DUP--Pairs元组CON--Pair elimination元组解构CON-Erasure values如λx *ERAErased variables如λ* xERANumbers数字NUM恒为Switches数字匹配MAT-- 端口 1 上连接一个 CON--分别指向0分支与 1分支—Numeric operations数值运算OPR-- 一个存放运算种类的 NUM按 HVM2 论文约定—References to top-level functions顶层函数引用REF从源码看encode_term对每个分支的处理与表格一一对应Term::Lam→ 新建 CON 节点端口 1 编码模式、端口 2 编码函数体src/fun/term_to_net.rsTerm::App→ 新建 CON 节点端口 0 编码函数、端口 1 编码实参并把出现位置接到端口 2src/fun/term_to_net.rsTerm::Swt→ 一次性分配一个Swi节点其端口 1 上挂一个 CONfst/snd 分别编码 0 分支与 succ 分支与两个子节点src/fun/term_to_net.rsTerm::Oper→ 构造 OPR 节点并用一个带运算标签的 NUM 挂在端口 1 上表示操作种类当只部分应用一个参数时编译器还会做翻转flip处理如SUB↔FP_SUB、DIV↔FP_DIV、LT↔GT见flip_symsrc/fun/term_to_net.rsTerm::Ref→ 直接生成Tree::Ref端口为Term::Era/ 无绑定名的变量模式 →Tree::EraTerm::Let、Term::Fan含元组→ 通过lets栈与make_node_list生成 DUP/TUP 节点链。此外term_to_net.rs 的term_to_hvm在编码完成后还会做一次恶性环vicious cycle检测若created_nodes与网络中实际统计到的节点数不一致则报错拒绝生成该网络——这是编码阶段保证结果可归约的防御性检查。match表达式并不直接编译而是根据adt-encoding选项先翻译为上述核心构造。以type Maybe (Some val) | None为例见 pattern-matching.mdadt-num-scott默认Maybe/Some λval λx (x 0 val)Maybe/None λx (x 1)UnwrapOrZero变成对数字 tag 的switchadt-scottMaybe/Some λval λMaybe/Some λMaybe/None (Maybe/Some val)匹配变成纯 λ 应用(x λx.val x.val 0)。读回Readback从网络还原为 Bend 项运行结果拿到的是归约后的交互网需要net_to_term将其还原为可显示的 Bend 项。完整流程见 src/lib.rs 的readback_hvm_net用hvm_to_net把 HVM 文本格式的网络解析为内部INet调用 src/fun/net_to_term.rs 的net_to_term遍历网络按节点种类与入口端口还原术语对succ分支可能出现的生成函数执行expand_generated根据adt-encoding重新加糖resugar_strings、resugar_lists把编码后的字符串/列表还原为字符串字面量与[a, b, c]语法。读回过程中的几个关键机制CON 节点语义判定read_con依据端口号 is_tup启发式端口 1 是否为闭合树区分 λ/应用/元组/元组解构叠加与复制的配对解析非线性读回linear false时dup_paths记录 DUP 标签对应的栈用于把叠加值与复制变量正确配对read_fan数值运算还原read_opr从 OPR 节点的 NUM 标签中读取运算符号与数值类型U24/I24/F24还原出Term::Oper遇到非法的数字匹配、非法运算、读到根节点或循环网络时会记录ReadbackErrorInvalidNumericMatch、InvalidNumericOp、ReachedRoot、Cyclic并给出中文可读的警告src/fun/net_to_term.rsη 归约decay_or_get_ports在 CON/TUP/DUP 满足特定连接形态端口 1、2 连接到同类节点的 1、2 端口时直接读取对端端口 0等价于对λa let (a,b) a; (a,b)这类解构后又重构的网络做读回级 η 归约无作用域变量恢复collect_unscopedapply_unscoped把游离变量转换为Link/Chn形式处理全局 λ 等无作用域绑定。Bend 编译器 Pass 全清单compilation-and-readback.md 列出了完整的 pass 序列以下按文档顺序整理并标注对应源码Pass作用源码位置encode_adt为构造器生成函数按编码选项encode_adts.rsdesugar_open把 open 项转换为 match 项desugar_open.rsencode_builtins把内建类型的语法糖list、string 等转换为函数调用builtins.rsdesugar_match_def把等式风格的模式匹配函数转换为 match/switch 树desugar_match_defs.rsfix_match_terms规范化所有 match 与 switch 项fix_match_terms.rslift_local_defs把局部def提升为顶层函数lift_local_defs.rsdesugar_bend把bend项转换为顶层函数desugar_bend.rsdesugar_fold把fold项转换为顶层函数desugar_fold.rsdesugar_with_blocks把with与-ask转换为 monadic bind 与 wrapdesugar_with_blocks.rsmake_var_names_unique为每个函数中的每个变量生成唯一名unique_names.rsdesugar_use通过替换消解use别名语法级复制desugar_use.rslinearize_matches按linearize-matches选项线性化 match/switch 中的变量linearize_matches.rslinearize_match_with线性化with子句中的变量若尚未被上一步处理linearize_matches.rstype_check_book运行类型检查仅推断/检查不进行 elaborationcheck/type_check.rsencode_matches按adt-encoding把 match 项变换为 λ 演算形式encode_match_terms.rslinearize_vars线性化变量出现多用则复制、无用则擦除、仅出现一次的let直接内联linearize_vars.rsfloat_combinators按源码中描述的尺寸启发式把组合子提升为顶层函数float_combinators.rsprune按prune选项删除未使用函数definition_pruning.rsmerge_definitions合并完全相同的顶层函数definition_merge.rsexpand_main解引用展开main使其包含真实计算而非懒引用expand_main.rsbook_to_hvm降级到 HVM即本文前半部分介绍的编码过程term_to_net.rseta在 inet 层做 η 归约但不归约两端为ERA/NUM的节点逻辑等价但用户观感异常eta_reduce.rscheck_cycles启发式检查可能引发 HVM 循环的互递归函数调用环mutual_recursion.rsinline_hvm_book内联那些编译为 nullary 节点REF/NUM/ERA的 REFinline.rsprune_hvm_book在 inet 层 η 归约后的额外剪枝层prune.rscheck_net_sizes确保生成的每个定义不会过大而无法在 CUDA 运行时上运行check_net_size.rsadd_recursive_priority在 inet 层为部分二元递归调用打标记便于 GPU 运行时合理分配工作add_recursive_priority.rs这些 Pass 在源码中的真实执行顺序上述 pass 并非文档中的简单罗列其真实执行流程体现在 src/lib.rs 的desugar_book与 src/lib.rs 的compile_bookdesugar_book依次执行check_shared_names→set_entrypoint→encode_adts→fix_match_defs→apply_args→desugar_open→encode_builtins→resolve_refs→desugar_match_defs→fix_match_terms→lift_local_defs→desugar_bend→desugar_fold→desugar_with_blocks→check_unbound_vars→ 变量唯一化与desugar_use→ 按选项执行linearize_matches含Alt变体→linearize_match_with→ 类型检查 →encode_matches→ 再次检查未绑定变量 → 唯一化与desugar_use→linearize_vars→ 按选项float_combinators→ 未绑定引用检查 →prune→merge_definitions→expand_main随后compile_book调用book_to_hvm生成 HVM 网络再按选项依次执行etaη 归约、check_cycles、再次eta、inline_hvm_book、prune_hvm_book、check_net_sizes与add_recursive_priority。可以看到desugar_book与compile_book之间有清晰的职责划分前者完成项级term-level转换与优化后者完成网络级inet-level优化。其中多个 pass 之间还穿插着健全性检查sanity check例如check_unbound_vars与check_unbound_refs保证每个阶段产出的项都保持良好约束。用 -O 选项控制编译 Pass编译 pass 的行为由命令行选项控制详见 compiler-options.md。下表整理了全部选项及其默认值选项默认值作用-Oall关闭启用全部编译器 pass-Ono-all关闭禁用全部编译器 pass-Oeta/-Ono-eta关闭eta 默认开启见下方说明对已定义函数做 η 归约-Oprune/-Ono-prune关闭定义剪枝删除未使用定义-Olinearize-matches/-Olinearize-matches-alt/-Ono-linearize-matches启用match 线性化-Ofloat-combinators/-Ono-float-combinators启用浮出组合子-Omerge/-Ono-merge关闭定义合并-Oinline/-Ono-inline关闭内联 nullary 项-Ocheck-net-size/-Ono-check-net-size关闭编译时默认开启见下方说明网络尺寸检查CUDA 限制 64 节点-Oadt-scott/-Oadt-num-scottadt-num-scottADT 编码方式-Otype-check/-Ono-type-checktype-check类型检查注意表中默认值一列对应 compiler-options.md 的表格而CompileOpts::default()的实现src/lib.rs实际默认开启了eta、linearize_matches、float_combinators、check_net_size与type_check。同时-Ono-all不会关闭type_check见set_no_allsrc/lib.rs且严格模式禁用float_combinators/linearize_matches可能引发无限展开编译器会打印相应警告check_for_strict。几个与编译结果直接相关的选项行为η 归约id_id λx (id x)在-Oeta下变成id_id id在-Ono-eta下保持λz (id z)定义剪枝-Oprune移除Id2 Id这类未被使用的定义定义合并id λx x与also_id λx x在-Omerge下合并为id_$_also_idHVM 输出由两个id/also_id变为单个a内联-Oinline把foo 2内联进mainHVM 输出中 id ~ (foo a)变为 id ~ (2 a)网络尺寸检查-Ocheck-net-size要求每个函数编译后至多 64 个 HVM 节点CUDA 运行时内存限制radix_sort这类展开函数在开启时会报Definition is too large for hvm非*-cu后端可关闭ADT 编码-Oadt-scott为每个构造器生成一个 λ-Oadt-num-scott用数字 tag 指示构造器Option/Some/tag 0、Option/None/tag 1。注意IO 仅在-Oadt-num-scott下可用类型检查默认开启def main() - Bool: return 3会报Expected function type Bool but found u24-Ono-type-check下则正常编译并返回3。实战验证编译 → 运行 → 读回的完整链路将以上概念串起来一条完整的执行链路是bend run 路径 [表达式形式的参数]...以 cli-arguments.md 中的程序为例def main(x, y): return {x - y, y - x}bend run path 5 3→ 输出{2 -2}只传一个参数bend run path 5→ 输出λa {(- a 5) (- a 5)}缺参时结果为部分应用读回为 λ传三个参数5 3 1→ 仍输出{2 -2}多出的参数因交互规则被自然忽略。运行机制见 src/lib.rs 的run_hvm编译器把hvm_book以 pretty 形式写入.out.hvm以子进程方式调用 HVM 二进制执行再从输出中按Result:标记HVM_OUTPUT_END_MARKER截取结果网络parse_hvm_output最终交给读回模块还原为 Bend 项。这就是编译 → 归约 → 读回三个阶段的闭环。仓库测试中tests/golden_tests.rs 覆盖了desugar_file查看各 desugar pass 输出、compile_file查看book_to_hvm后的 HVM 输出、readback_hvm网络读回等场景快照存放在 tests/snapshots 下是观察每个 pass 实际产物最直接的素材例如cli__compile_no_opts.bend.snap、cli__compile_pre_reduce.bend.snap展示了不同优化开关下的 HVM 输出差异。小结Bend 的编译与读回是一套项 → 图 → 项的完整闭环项级 pass 先把各类语法糖消解为 λ 演算核心项book_to_hvm再按统一的 CON/DUP/ERA/NUM/OPR/SWI/REF 编码规则把核心项映射为 HVM 交互网运行时归约完成后读回模块依据入口端口与节点种类还原出可读的 Bend 项。理解这 7 种节点与极性映射以及 20 余个 pass 的执行顺序是调试编译输出、调优-O选项、甚至为 Bend 贡献新优化 pass 的基础。【免费下载链接】BendA massively parallel, high-level programming language项目地址: https://gitcode.com/GitHub_Trending/be/Bend创作声明：本文部分内容由AI辅助生成（AIGC），仅供参考