去函数化 | Codeboy's Blog

形式陈述

变换的对象是有限的函数代码族

去函数化把程序中作为值传递的函数改成普通数据，把间接函数应用改成对这些数据的分派。本页先固定一个闭合、纯粹、从左到右按值执行的程序；所有可能出现的函数抽象位置在编译时已知，没有动态加载代码、反射生成函数、可变单元或外部回调。整数按数学整数理解，观察是最终整数与正常结束；下面的具体函数族总能结束。

假设某一函数类型的抽象位置为 $L_1,\ldots,L_r$ 。对每个 $L_i=\lambda x.e_i$ ，列出其自由变量 $y_{i1},\ldots,y_{ik_i}$ ，创建一个构造子 $C_i$ ，字段保存这些变量在函数创建时的值。这使用闭包的词法捕获规则，并以代数数据类型表达有限种标签和每种标签的字段。[1, §§1.1–1.3]

变换包含三个相互配合的动作：函数抽象换成 $C_i(\bar y_i)$ ；函数值参数、返回值及数据字段改存标签值；应用 $f\,v$ 换成 $\operatorname{apply}(f,v)$ 。分派器对 $C_i(\bar y_i)$ 进入转换后的 $e_i$ ，把 x 绑定到 v，把捕获变量读作对应字段。函数与实参的原始求值顺序不能在分派时改变。

本页可以完整执行的函数族

只考虑整数到整数函数，源端有三个构造操作：

text

add(c)       = lambda x. x + c
mul(c)       = lambda x. x * c
compose(f,g) = lambda x. f(g(x))
twice(f,x)   = f(f(x))

目标数据及分派器为

text

Fun = Add(c) | Mul(c) | Compose(f,g)
apply(Add(c), x)       = x + c
apply(Mul(c), x)       = x * c
apply(Compose(f,g), x) = apply(f, apply(g,x))
twiceD(f,x)           = apply(f, apply(f,x))

Compose 的两个字段也是 Fun 值。这里的数据由有限次构造形成有限树；虽然只有三个标签，树可以任意深，整数负载也可以任意多。没有把所有可能函数值预先枚举出来，枚举的是产生函数的代码形状。

直觉

把“怎么调用”集中到一个分派器

给别人一个函数，相当于交给它一份代码和代码需要的材料。闭包实现常直接保存代码地址；去函数化则保存“这是第几种代码”的标签，把所有调用规则集中到 apply。接收者不再调用未知的宿主函数，只需检查数据形状。

这一点也解释了为什么只删除 lambda 不够。若产生函数的位置换成 Add(c)，调用处却仍把它当函数调用，程序就无法执行。相反，只把调用换成 apply 而漏掉捕获字段，分派器虽然知道要加法，却不知道该加哪个 c。产生者、存储位置与消费者必须一起变换。

例子与边界

同一函数传两次，得到 33

令 $f=\operatorname{compose}(\operatorname{mul}(3),\operatorname{add}(2))$ ，其目标表示是 Compose(Mul(3),Add(2))。第一次调用从 x=1 开始，内层 Add 得 3，再由 Mul 得 9；第二次从 9 开始，先得 11，再得 33。因此 twice(f,1) 与 twiceD(f,1) 都为 33。

若把分派器写成 apply(g,apply(f,x))，第一次会先乘 3 再加 2 得 5，第二次得 17。调换两字段的执行顺序不是无害的布局差别。这个反例无需状态就能检测错误。

捕获时间也可单独检查：在外层 c=2 时创建 add(c)，后来进入另一个 c=100 的作用域，应用该函数于 1 应得 3。标签值必须已经是 Add(2)，不能只保存字符串 c 并在调用时查询当前环境。后者会错误得到 101。

有限标签不限制实例数

对输入列表 $[1,2,3,\ldots,n]$ ，逐项创建 add(c) 会得到 n 个不同的 Add 负载，仍只用一个 Add 标签。嵌套 Compose 还可以构成不同形状的复合函数。有限标签集合不意味着有限个运行时状态，更不保证内存有一个与输入无关的上界。

相反，如果系统后来收到一个来自未知插件的新函数代码，当前三个标签就未必能表达它。可以重新做全程序分析、允许可扩展分派，或在接口保留普通闭包；不能未经说明把“所有抽象位置已知”的条件去掉。[1, §§1.2–1.3]

与闭包转换、CPS 的分界

闭包转换把环境显式化后，仍可采用“代码指针加环境”的统一调用接口。本文目标则以一个已知构造子族和穷尽分派表达函数值。两者都保存捕获信息，差别在代码身份与调用的表示：前者读代码指针，后者按构造子分派。

CPS把剩余计算变成函数；对其中有限种续延函数去函数化，就得到显式控制帧。这可以解释抽象机的来源，却不是本文变换只适用于续延的理由。上面的 Add/Mul/Compose 是普通整数函数，也能使用相同方法。

推论与应用

为什么标签执行与源函数一致

定义解释 $\llbracket\cdot\rrbracket$ ：Add(c) 对应 $x\mapsto x+c$ ，Mul(c) 对应 $x\mapsto cx$ ，Compose(f,g) 对应 $x\mapsto\llbracket f\rrbracket(\llbracket g\rrbracket(x))$ 。对有限函数树结构归纳，得到

\operatorname{apply}(F,x)=\llbracket F\rrbracket(x).

叶子由分派规则直接成立；组合节点先用 g 的归纳假设得到同一中间整数，再用 f 的假设得到同一结果。连续用两次这条等式，即证明 twiceD 保持输出。把这个证明推广到整门高阶语言，需要定义环境与函数值的对应并对求值推导归纳；本文下载实现的输入是这个封闭函数族；任意高阶源程序还需要上述一般转换及环境关系。

若一棵函数树展开后有 F 个节点，apply 每个节点访问一次，需 $O(F)$ 次分派与整数运算，递归控制深度不超过树高。已有子函数可以作为不可变指针共享，所以创建 Compose 只需两个引用；若把共享图按树展开计 F，同一共享子图在不同调用位置仍可能再次执行，不能按“不同对象数”低估计算。

对一般转换，已给定每个抽象位置的捕获集合与绑定身份后，发出代码和捕获字段的工作可按源节点数 N 与总字段数 K 计 $O(N+K)$ 。自由变量分析本身应另计，标签分派还假设能用固定标签直接选择分支；串行逐项比较 r 个标签会有不同成本。不同函数类型通常需要不同标签族与 apply 接口，本页未用一个无类型容器冒充类型保持证明。

迁移任务把 f 改成 Compose(Add(2),Mul(3))，应得到 twiceD(f,1)=17；再让输入 n 决定重复组合次数，检查标签种类不增加、数据深度会增长。若目标宿主没有尾调用优化，去函数化后的递归 apply 仍会用宿主栈；trampoline解决的是另一个控制转移接口。终点任务把两项测试分开验收。

参考资料

[1] Olivier Danvy、Lasse R. Nielsen，Defunctionalization at Work，BRICS RS-01-23，June 2001，§§1.1–1.3，正文 pp.4–7：有限抽象位置、动态创建任意多个闭包与全程序转换；§3 讨论续延去函数化。会议版发表于 PPDP 2001，pp.162–174。本文采用独立 Add/Mul/Compose 例。

[2] John C. Reynolds，Definitional Interpreters for Higher-Order Programming Languages，ACM Annual Conference，1972，pp.717–740。历史来源；具体构造与条件以上述作者报告的可读版本为核对依据。

形式陈述 ​

变换的对象是有限的函数代码族 ​

本页可以完整执行的函数族 ​

把“怎么调用”集中到一个分派器 ​

同一函数传两次，得到 33 ​

有限标签不限制实例数 ​

与闭包转换、CPS 的分界 ​

为什么标签执行与源函数一致 ​

反向链接