去功能化：每个人都这样做，没有人谈论它（2019）

在我作为研究人员的生活之外，我为专业软件工程师提供高级培训。我在教学中强调的一件事是在表面实例上学习深层概念的重要性。例如，我教程序员排除重构目录的噪音，并了解最熟悉的重构是如何遵循一些原始代数定律的，例如恒等式 X 2*A = XA * XA，它很容易从高中代数，对应于用两个函数替换一个接受布尔参数的函数。当我第一次开始教专业人士时，我所知道的所有重构都源于编程语言的单步归约，以及求和、乘积和指数（函数）的代数定律。去年，当我构建能够根据语言语义自动生成编程工具的系统时，我了解了去功能化，这是一种将高阶函数替换为等效的一阶函数的转换。 Olivier Danvy 教授曾用它来展示表达编程语言语义的许多范式之间的对应关系。我很快意识到这种转换作为一种重构技术的普遍性，隐式地用于从使递归函数迭代到使单机程序分布式的任务中。然而，它在重构文献中完全闻所未闻——并且不符合我以前的思维框架。在这篇文章中，我想给出一个总结，展示该技术及其用途，以及学习如何识别去功能化和重新功能化的实例可以帮助程序员更轻松地理解设计选择中的权衡。作为一种诞生于编译器研究并受形式语义滋养的技术，去功能化是 PL 研究的见解如何转化为实际编程建议的一个主要例子。考虑基本的过滤器函数，它输入一个列表并输出满足某些条件的子列表。每个函数式编程学生都学习如何编写类似以下代码的内容。 filter :: ( Int -> Bool) -> [ Int] -> [ Int] filter f [] = [] filter f (x :xs) = if fx then x : filter f xs else filter f xs... filter isOdd [ 1, 2, 3, 4, 5] filter isPrime [ 1, 2, 3, 4, 5] filter ( \x -> x < y) [ 1, 2, 3, 4, 5] 这是一个更高的-order 函数，接受条件作为调用者传递的函数进行检查。代码与传入的函数完全无关，其中可能有无数个。然而你在日常生活中遇到的过滤器并不是这样工作的。当您在网上购物时，您可以单击复选框以将搜索限制为衬衫、裤子和靴子，但您不能提供任意的过滤条件。一般来说，在当今的分布式应用程序世界中，高阶编程具有挑战性。具有高阶函数参数的远程过程调用需要序列化这些函数，这并不容易安全或有效地进行。作为替代方案，程序员可以设计一种数据类型来表示所有感兴趣的过滤器函数。设计这种类型很像设计一种编程语言：程序员需要决定过滤原语是什么以及如何组合它们。这是一个可能的答案：

数据过滤器 = IsOdd | IsPrime |小于整数 |和过滤器过滤器应用::过滤器 -> Int -> Bool apply IsOdd x = isOdd x apply IsPrime x = isPrime x apply (LessThan y) x = x < y apply ( And fg) x = apply fx && apply gx filter :: Filter -> [ Int] -> [ Int] filter f [] = [] filter f (x :xs) = if apply fx then x : filter f xs else filter f xs... filter IsOdd [ 1, 2, 3 , 4, 5] filter IsPrime [ 1, 2, 3, 4, 5] filter ( LessThan y) [ 1, 2, 3, 4, 5] 版本2更长，但它的优点是可以选择过滤器在一台机器上并在另一台机器上使用。这似乎是另一个问题，它使许多机器的编程本质上比为一台机器编程更困难。但是，实际上，这种过滤器语言的设计思想是不必要的。上面的代码可以从Version 1自动派生出来，上面的改动是去功能化的一个例子，把一个高阶函数变成了一个一阶函数。在本节中，我们会将之前更改的临时工作替换为通用的自动化转换。这个例子中的大部分工作是在 Filter 数据类型中提出案例并给出它们的实现。这些可以从代码中自动确定，但不是我们上面给出的定义过滤器函数的代码。相反，去功能化的洞察力是找到高阶函数的所有实际用途。过滤器函数的每次不同使用都会在过滤器数据类型中产生一个新案例。前两个 IsOdd 和 IsPrime 很简单；它们来自以下用途：LessThan 情况更有趣一点，因为它需要一个 Int 参数。尽管它有无数个实例化，但这并不意味着原始代码有无数个不同的用途。相反，它来自引用外部信息的单一用途，例如： 在上面的代码中，y 是一个自由变量，由外部上下文定义。在 LessThan 情况下，这将成为 Int 参数。然后 f 和 g 也必须去功能化。但是，由于它们与整个过滤器具有相同的类型，因此它们本身成为过滤器，给出递归情况（和过滤器过滤器）。

创建一个数据类型，每个可能的函数都有一个变量，每个变量都有字段来存储相应函数引用的自由变量。将过滤条件的调用替换为应用函数，该函数确定数据结构表示的过滤条件并执行它。在版本 1 上运行此过程，并使用一组合适的过滤器功能，生成版本 2 中的代码。过滤器的“编程语言”已经以完整的形式出现，无需设计工作。在选择去功能化的形式时，我们正在进行权衡。原始版本，称为直接或重新功能化形式，是开放的，这意味着很容易添加一种新的过滤器：只需使用不同的 lambda 调用它。相比之下，对于去功能化的形式，添加新的过滤条件需要修改过滤器所依赖的数据结构。然而，与函数不同的是，去功能化形式的数据结构可以被序列化，具有所有的好处：打印、比较、保存和网络传输。在下一节中，我们将在野外观察许多不知情的去功能化使用。从表面上看，这些应用程序彼此之间没有相似之处，尽管其中许多会产生某种状态机。然而，每个应用程序都提供了两种备选方案之间的设计选择，这提供了开放性和可序列化性之间的权衡。去功能化和再功能化在编程中有很多应用。在这里，我们展示了去功能化如何解释程序员经常做的几个表面上无关的更改，并阐明所做的权衡。其中大多数将去功能化与更流行的转换，CPS（“继续传递风格”）转换相结合。在 CPS 中，每个函数都被赋予一个额外的参数，一个称为“延续”的函数，并将使用返回值调用此函数，而不是正常返回该值。去功能化与 CPS 转换的融合允许将动作分成多个部分，并在不同的时间或在不同的机器上执行。将递归函数（例如将树打印为迭代函数）更改为迭代函数可能很棘手，需要嵌套循环和显式堆栈。这些堆栈正是去功能化的延续，堆栈性质的出现是因为延续可能会引用其他延续。

经过 CPS+去功能化的递归函数往往类似于状态机。 Danvy 教授还使用逆变换，使用巧妙的递归方案将一些经典的状态机算法转换为以前未知的无状态版本。想象一个银行网站，它包含关闭账户和转移资产的代码：amount = account1.withdrawAll(amount); account2.add（金额）。想象一下，如果帐户 1 和 2 的数据可能在不同的服务器上管理。然后将代码更改为从第一个帐户中退出，然后向第二个服务器发送消息，通知它从第二个帐户中退出。这个消息正是去功能化的延续。一个相关的用途是在基于延续的 Web 框架中。例如，在热门网站 Hacker News 上，注销的用户可以发表评论，进入登录页面，登录，然后重定向到发布评论的原始页面。为了实现这一点，程序员只需要编写诸如“如果未登录，则转到登录屏幕，然后发表评论”之类的顺序代码；服务器将保存登录后发生的一切，作为登录完成后调用的延续。然而，因为这个延续不能被序列化并发送到另一台机器，这个决定将网站限制在单个服务器上运行，如果服务器在用户登录之前重新启动将无法工作。为了解决这个问题，黑客新闻团队重写了用于存储有关登录后在登录页面本身上执行的操作的数据的网站。这些数据以及网站上其他地方的类似事件可以被视为去功能化的延续。了解网站两个版本之间的对应关系有助于我们了解如何获得两者的好处。虽然原始 Hacker News 代码背后的名人程序员 Paul Graham 吹嘘他的 Web 框架的简单和优雅，但代码的简单性很可能因需要为每个不同的捕获延续手动定义数据结构而受到损害。这表明对去功能化的语言级支持可用于保持显式延续的美感，同时获得多台机器的可扩展性。一些系统，例如 MFlow 和 j macro-rpc 框架，试图通过以不同的方式通过网络发送延续来规避这个问题：通过发送有关执行过去的信息，以便另一台机器可以重播一个函数调用以到达第一台机器停止的地方。这可以看作是我的 ICFP 2018 论文中关于温度计延续的应用。当程序从文件或网络中读取时，它通常会暂停以等待数据。为避免吞吐量损失，程序员转向非阻塞 I/O，即程序表示希望读取数据，但稍后接收数据。提供非阻塞 I/O 的一种方法是在数据可用时向程序发送通知，如 Linux 的 SIGIO。相应的通知处理程序可以从原始阻塞 I/O 程序中通过去功能化读取函数内部继续的“分隔”部分来派生。

“普通”多态性，就像在 Java 的泛型中一样，允许在具有任意类型数据的容器上编写函数，例如：在 List<X> 上为任何类型 X 编写函数。但是在任何容器上编写函数，例如单个函数适用于列表和树，必须能够将 List<X> 和 Tree<X> 抽象为 F<X>，其中 F 表示任意类型的函数。包括 Haskell 在内的一些语言允许对类型函数进行抽象的类型变量（二阶多态），但大多数具有多态性的语言都不允许。但是有一个技巧可以将这种高阶多态性转化为 Java 或 OCaml 可以处理的东西：将 List<Int> 和 Tree<Int> 之类的类型转化为 App<List, Int> 或 App<Tree, Int>，演示由 HighJ 库提供。事实证明，这只是类型级别的去功能化。去功能化由 John Reynolds 在他 1972 年的论文“高阶编程语言的定义解释器”中引入，作为将高阶语言（如 ML）编译成一阶语言（如 C）的一种方式。尽管今天通常避开支持其他技术比如闭包转换，。今天，它仍然在诸如 MLTon 之类的全程序优化编译器和 PAKCS 中使用，后者将功能逻辑编程语言 Curry 编译为“一阶”逻辑编程语言 Prolog。 Olivier Danvy 和他的合作者通过他们在指定编程语言语义的不同方式的相互推导性方面的工作，在编程语言社区中推广了去功能化。一个重要的见解是他们对评估上下文的解释，即在归约语义中使用的“有漏洞的程序”，将它们解释为小步和大步语义的去功能化延续。去功能化是一种通用的技术，简单而晦涩，在编译器、理论 PL、各级软件工程，甚至可能在语言设计中都有应用。通过向我们展示有多少对程序等效的确切方式——以及有多少修改程序的技术是等效的，它表明更深入地理解一个主题意味着发现更多的东西是相同的。有关此处所有示例的更多详细信息，请参阅原始演讲的丰富记录。生物：吉米·科佩尔（Jimmy Koppel）是一名五年级博士。麻省理工学院计算机辅助编程小组的学生，研究重点是元元编程。他还经营着一家企业培训高级软件工程师，此前曾获得过“20 Under 20” Thiel Fellowship 创业奖。免责声明：这些帖子是由个人贡献者撰写的，目的是为了社区的利益，在 SIGPLAN 博客上分享他们的想法。本博客中所代表的任何观点或意见都是个人的，仅属于博客作者，不代表 ACM SIGPLAN 或其上级组织 ACM 的观点或意见。