0 引言

函数式语言的发展历史最早可以追溯到Church & Rosser提出的λ演算。1950年代早期，McCarthy研究并开发了第一个函数式语言LISP，至今仍被使用^[1]。近年来，随着软件系统的复杂化，函数式语言凭借支持高阶函数、具有较好的并行性等优点被广泛研究和应用。例如Twitter目前使用Scala语言^[2]，WhatsApp使用了Erlang^[3]等。此外，在分布式计算、机器学习、大数据处理等研究与商业应用的热点领域中也大量使用了函数式语言^[4-6]。例如，目前流行的开源集群计算框架Apache Spark就是使用Scala实现的^[7]。

随着使用函数式语言构建的软件系统越来越多地被用于处理海量数据，如何构建函数式语言编译器、生成具有更好的运行效率的目标代码，成为了一个关键的问题。函数式语言的编译过程主要包括词法分析、语法分析、CPS(Continuation-Passing Style)变换、高阶代码消除、分配、目标代码生成和代码优化等几个阶段。在性能影响方面，大部分编译阶段技术都较为成熟，但高阶代码消除阶段对于目标代码效率的影响并未得到重视。高阶代码消除是编译函数式语言的必要阶段，作用是将高阶的代码翻译为一阶的代码，使其能够在现有的计算机体系结构中运行。闭包变换(closure conversion)和函数消除(defunctionalization)是两种主要的高阶代码消除方式，很多函数式语言的实现采用了这两种方式之一^[8-10]。尽管现有研究对两种方法进行了理论上的探索和研究，但如何从这两种方法的目标代码的执行效率方面进行研究和比较仍然是一个难题。关于这两种变换方式给目标带来的效率影响，目前尚没有相关结论。

本文的主要目标是研究高阶代码消除方法对函数式语言运行效率的影响。现有研究面临的主要挑战是：现有编译系统的实现只采取单独一种高阶代码消除方法，而不同的编译系统的源语言特征、目标平台和其他编译过程都具有较大区别，因而针对不同的高阶代码消除方法对运行效率的影响，通过比较现有编译系统难以得到有说服力的结论。

为了解决这一困难，本文提出并实现了一种针对高阶代码消除方法对目标代码性能的影响进行比较的编译框架。该框架同时实现了闭包变换和函数消除两种方式，并通过采用同等表达能力的中间表示和语义保持的变换过程实现了菱形的架构，避免了其他转换过程的影响，从而解决了不同编译器的高阶代码消除方法间难以进行比较的问题，为得到准确的比较结果提供了可能。本文首先定义了一种具有代表性的函数式语言——FUN语言；并以FUN语言作为系统的源语言实现了一个基于上述框架的完整编译系统。通过该系统，本文对一组有代表性的源程序进行了实验，实验结果表明，与闭包变换相比，使用函数消除方式所得的目标代码量更少，最多可减少33.76%的目标代码量；并且运行效率更高，最多可提高69.51%。

本文的主要工作包括：

1) 提出并设计了一个能够有效地比较闭包变换和函数消除两种方法的高阶代码消除性能比较框架，并给出了该框架的实现。

2) 进行了系统的实验，并对实验结果进行了分析。实验结果表明，高阶代码消除方法的选择对于目标代码的规模和运行效率具有显著的影响，在减少代码量和时间效率上，函数消除优于闭包变换。

1 背景与问题分析

函数式语言支持高阶函数意味着函数可以像其他普通数据一样定义，可以是匿名的、可作为参数传递、或者作为函数的返回值。例如在下面的例子中：

fun outer x=

  let fun inner y=x+y

  in inner

  end

函数outer内定义了函数inner，并把inner作为其返回值。而函数inner中使用了函数outer的参数x，而x并未在inner中定义——即x是函数inner的自由变量。函数outer返回时，其栈帧已经失效，然而其返回值inner函数仍可能需要被调用，即需要访问x的值。此外，每次调用outer函数的参数x不同，那么所返回的inner函数也具有不同的行为，即函数的具体行为依赖于函数定义处的环境(environment)。目前的计算机体系结构不能直接支持这种抽象。

因而，要支持这种高阶函数，函数式语言的编译器需要将高阶的程序代码转换为一阶的程序代码，使程序中不存在自由变量。高阶代码消除的作用就是完成这一转换，而闭包变换和函数消除是两种常用的高阶代码消除方法。

1.1 闭包变换

闭包变换使用闭包(closure)表示一等的函数(first-class function)。一个闭包由函数代码(函数指针)和函数内自由变量的值的集合两部分组成^[11]。闭包是最常用的一等函数的表示方式^[12]，例如在F#语言就使用了闭包的概念表示函数^[13]。

闭包变换是常用的高阶代码转换方法^[14]。例如Morrisett等^[15]在从System F到有类型汇编语言的编译过程中使用了保持类型的闭包变换；Perconti等^[16]在编译器程序验证工作中也使用了闭包变换。

闭包变换过程使程序中的函数均成为闭合的，即内层的函数中不存在对外层的函数中的变量的引用。要做到这一点，需要为函数增加一个额外的参数作为环境，并且使用函数代码和相应环境组成的闭包来表示一个函数。

闭包变换的过程可概括为：

1) 计算每个函数定义内的自由变量的集合。

2) 对每个函数定义增加一个额外的参数表示环境。环境具体可看作自由变量的列表，转换后的代码中，函数体中的自由变量均从环境中获得，因此函数中不再有自由变量，函数均成为闭合的。

3) 在函数定义外，转换后的代码需构造具体的环境变量，并将函数代码与具体环境一起组成一个闭包，一个函数即由一个闭包表示。

对于函数调用，转换后的代码先从相应的闭包中取出函数代码和环境，再将环境与原来的参数一起作为参数调用函数代码。

为直观起见，下面以一个代码块为例。对于下面的代码：

fun outer x=

  let fun inner y=x+y

  in inner

  end

val acc=outer 1 2

经过闭包变换后的结果为：

val outer=

  let fun outer_code(env_0, x)=

    let val inner=

      let fun inner_code(env_1, y)=

        let val x=#1 env_1

        in x+y

        end

      in(inner_code, (x, ()))

      end

    in inner

    end

  in(outer_code, ())

  end

val acc=

  let val closure_0=(#1 outer)((#2 outer), 1)

  in(#1 closure_0)((#2 closure_0), 2)

  end

可以看到，转换后的代码中，原来的函数名变为了包含函数代码的闭包变量的名字。而使用函数时从相应闭包的第一元获得函数代码，并作用于环境(闭包的第二元)和参数。

1.2 函数消除

函数消除使用一阶的类型来表示一等的函数^[12]。函数消除由Reynolds在20世纪70年代早期提出^[17]并被广泛应用，例如Cejtin等在MLton编译器中使用了函数消除作为对程序的全局变换，生成具有简单类型的中间表示^[8]；文献[12]对函数消除在程序的CPS表示上的应用和正确性影响等进行了讨论; Fourtounis等^[18]介绍了函数消除方法的一种变体，可以对模块化的程序进行分开编译。

此外，函数消除还有一些良好性质，例如Bell等^[19]证明了函数消除是保持类型的。

函数消除的过程包括以下几个方面：

1) 对每个函数定义，计算其自由变量集合。

2) 转换后的代码增加一个apply函数，其中包括一条case表达式，对apply函数的第一个参数进行分支判断。

3) 对原代码中的函数定义：将自由变量封装进一个环境中；函数名初始化为一个新的类型构造符作用于该环境；函数代码中，使自由变量从环境中初始化；最后，函数代码作为分支语句加入到apply函数的case表达式中，并且该新类型构造符作为其分支条件，自由变量均在分支语句中拆箱。

4) 原代码中的函数调用转换为对apply函数的调用，并且第一个参数为原函数名，第二个参数为原来的参数。

那么对于上节中的例子，函数消除的结果为：

datatype lam=LAM_0

  | LAM_1 of int

fun apply(f, arg)=

  case f

    of LAM_0=>

      let val inner=LAM_1(arg)

      in inner

      end

    | LAM_1 x=>

        x+arg

val outer=LAM_0()

val acc=apply(apply(outer, 1), 2)

2 源语言设计

设计编译系统首先要确定源语言，本文设计了一种轻量级的函数式语言作为编译系统的源语言，在文中称为FUN语言。FUN包含了函数式语言的基本功能、具有丰富的表达能力，从而使研究结果具有代表性和普遍性。

FUN语言支持高阶函数，其核心的语法定义如表 1所示。FUN的计算过程由表达式的求值驱动。

表 1中的符号e表示一个FUN语言表达式。一个表达式可以作为一个FUN语言程序。表达式是递归定义的，包括：

1) 基本表达式，即不具有子结构的表达式。包括变量名(由符号x表示)，空值常量(由()表示)，字符串常量(由“s”表示)，整数常量i以及布尔值常量true和false。因此FUN语言支持空类型、字符串类型、整型和布尔型这些基本数据类型。

2) 表达式fn x=>e定义了一个无名的函数抽象，其参数为x。表达式e₁ e₂表示一个函数作用，其中e₁为函数、e₂表示参数。

3) (e₁, e₂, …, e_n)表示由e₁, e₂, …, e_n构成的n元组。#i e表示对表达式e投影得到第i个分量，其中e应当具有元组类型。

4) ini e表示将构造符ini作用于e。表达式case e of $\xrightarrow[{in{i_j}{x_j} => {e_j}}]{}$表示对e中的构造符进行匹配和分支跳转。

5) 表达式PrimOp ${\vec e}$表示对一组(一个或多个)表达式上的基本操作。符号PrimOp表示操作符，FUN语言内建的操作符包括整数上的加减法、乘法和大小比较，布尔值的与、或、非操作，字符串输出，以及整数到字符串的转换。

6) let val x=e₁ in e₂ end与let fix f x=e₁ in e₂ end以e₂为作用域分别绑定了一个变量名和可递归函数。

7) 表达式if e₁ then e₂ else e₃根据e₁的求值结果进行分支跳转。

举例而言，源语言上的一个实现加法函数的程序代码段如下：

let fun add x=fn y=>x+y

in add 10 5

end

则上述程序定义了函数add，其返回值是一个参数为整数的函数，并用add 10所的结果作用于5，程序运行结果应为15。

FUN语言的设计为本文所要研究的问题提供了足够的性质和特征，同时减少了无关的细节。

3 框架设计与实现

图 1给出了比较框架的整体设计，主要包括前端处理、中间表示间的转换、后端处理三个部分。

1) 在前端处理阶段，源语言的源程序文本首先经过语法分析形成携带语法信息的符号流。符号流经过语法分析生成程序的FUN语言中间表示，即源程序在内存中的结构化表示。

2) 在中间表示转换阶段，FUN语言中间表示的程序首先要经过CPS变换形成CPS风格的中间表示。CPS变换的作用是使所有中间计算结果均被明确表示，并且函数不再返回，而是通过延续(Continuation)表示“下一步要做的事情”^[20]。延续由一个函数表示，源语言原有的函数接受一个延续作为额外的参数，并且函数执行结束通过调用延续完成控制转移。对于所有执行流发生转移的表达式，例如函数调用、条件转移等，需要定义新的延续，以表示执行流转移的关系。由于CPS风格的代码中，函数从不返回，因而程序执行不再依靠调用栈。

中间表示转换阶段的下一个步骤是高阶代码消除。为了对比闭包变换与函数消除的效果，采用了菱形的架构，即：同一个程序的CPS中间表示可分别经过闭包变换和函数消除生成closure converted中间表示和defunctionalized中间表示；而这两种中间表示分别经过进一步的变换形成Flat中间表示，对于两种高阶代码消除方法形成了同一种中间表示下的不同结构，从而保持后续处理流程的一致性。

Flat中间表示是本文设计的一种平坦的不含有高阶代码的程序中间表示，既能携带closure converted中间表示和defunctionalized中间表示的信息，又便于之后的变换过程。

3) 后端处理阶段包括分配与代码生成阶段。分配阶段生成Machine中间表示，是本文设计的一种显式地进行内存分配并且与机器语言相似的中间表示，以便于目标代码的生成。代码生成阶段的作用是在Machine中间表示的基础上生成目标代码。最后，目标代码与运行时支持一同构成目标程序。运行时支持包括对FUN语言一些内建操作的支持，以及垃圾回收算法等，运行时支持与分配、代码生成均需要按照一致的内存模型。

比较框架的整体设计通过这种架构，在使用不同的高阶代码消除方法同时共用其他流程，提高了比较结果的可靠性。

这一框架设计的基础上，本文以FUN语言作为源语言、以C语言作为目标语言搭建了一个编译系统，对该框架进行了实现，并提供了相应的运行时支持。

4 实验设计与结果分析

本文在实现的编译系统上进行了实验，并对实验结果进行了分析。实验的目的是通过该系统比较闭包变换与函数消除对目标代码的运行效率的影响。

为了全面地比较闭包变换与函数消除对目标代码运行效率的各方面影响，实验选取了目标代码的代码量和目标程序的运行效率两个方面对闭包变换与函数消除两种方式进行比较。为了得到有代表性的结果，在测试用例上，针对数据结构上的动态和静态操作、递归过程、函数定义和函数调用这几个方面，编写了7个具有代表性的源程序作为测试样本，涵盖了源语言上的所有表达式类型。

实验机器的CPU主频为2.3 GHz，Windows 7操作系统。内存为2 GB。对目标代码统一使用GCC(版本4.8.1)编译生成目标程序。

表 2列出了使用两种方法得到的目标代码量(以行为单位)之间的比较结果。通过表 2的数据可以得出：对于所有测试例，使用函数消除得到的目标代码量较少。特别是，测试例f和g分别在累加函数内定义了大量的有名函数定义和无名函数定义，对这两种情况，使用函数消除得到的目标代码量明显少于使用闭包变换得到的结果，目标代码量分别减少33.76%和14.44%，说明函数消除方法能显著减少函数抽象的目标代码量。

为了比较两种高阶代码消除方法对目标程序运行效率的影响，图 2给出了各组用例编译所得的程序运行时间随动态分配空间大小变化的结果。

从图 2可以看出，除测试例b中的一个数据点之外，使用闭包变换所得目标程序所需运行时间更少。当时间曲线稳定时(即程序动态分配空间充足时)，使用函数消除所得的结果比使用闭包变换效率分别提高28.34%、1.71%、24.62%、32.86%、35.06%、69.51%、35.09%，说明使用函数消除更有利于提高目标代码的运行效率。

表 3列出了对每个测试例函数消除减少的代码量和运行时间的结果。结果显示了函数消除减少对于代码量和运行时间的减少并不成线性关系，说明函数消除减少运行时间的原因除了单纯减少了代码量，还可能有利于后端的优化。

5 结语

本文提出了一种用于比较闭包变换与函数消除两种高阶代码消除方法的编译系统框架，给出了该框架的实现，并通过该系统进行实验分析比较了两种方法对目标程序的效率影响。实验与分析结果表明，使用函数消除得到的目标代码具有更高的运行效率和更少的目标代码量。