高阶代码消除性能比较框架的设计与实现

赵迪　华保健　朱洪军

摘要：

函数式语言编译中，闭包变换和函数消除是广泛采用的高阶代码消除方法。为了提高函数式语言的运行效率，针对函数式语言编译阶段的高阶代码消除过程对目标代码效率的影响，設计并实现了一种函数式语言编译框架。该框架采用了菱形的架构，平行地使用了闭包变换与函数消除两种高阶代码消除方法。设计了一种具有代表性的函数式语言——FUN语言，并以FUN语言为基础，给出了比较框架的一个完整实现。通过该系统，对闭包变换与函数消除的效率影响进行对比实验，选取具有典型特征的测试例，分别从生成代码的规模和运行效率方面对闭包变换与函数消除两种方法的结果进行比较。实验结果表明，与闭包变换相比，使用函数消除方式所得的目标代码量更少，最多可减少33.76%的目标代码量；并且运行效率更高，最多可提高69.51%。

关键词：

编译框架；函数式语言；高阶代码；闭包变换；函数消除

中图分类号：

TP311.5

文献标志码：A

Abstract：

In functional programming language compilation， closure conversion and defunctionalization are two widely used higherorder code eliminating methods. To improve the operational efficiency of functional programming languages， focusing on the higherorder code eliminating phase， a compiler frame to compare the performance of code generated by closure conversion and defunctionalization was proposed. Both closure conversion and defunctionalization were used in parallel in the comparing frame with a diamond structure. A functional programming language named FUN and a compiling system for FUN based on the comparing frame was proposed. Experiment is conducted on the system to compare the two methods. The outputs were compared in performance and quantity of code.Comparison experiments of closure conversion and defunctionalization were conducted on the proposed system by using typical use cases， and the experimental results were compared in code quantity and operation efficiency. The result suggests that compared with closure conversion， defunctionalization can produce shorter and faster target code； the amount of code can be decreased by up to 33.76% and performance can be improved by up to 69.51%.

英文关键词Key words：

compiler frame； functional programming language； higherorder code； closure conversion； defunctionalization

0引言

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

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

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

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

本文的主要工作包括：

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

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

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

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

1.1闭包变换

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

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

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

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

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

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

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

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

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

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

1.2函数消除

函数消除使用一阶的类型来表示一等的函数[12]。函数消除由Reynolds在20世纪70年代早期提出[17]并被广泛应用，例如Cejtin等在MLton编译器中使用了函数消除作为对程序的全局变换，生成具有简单类型的中间表示[8]；文献[12]中，Danvy和Nielsen对函数消除在程序的CPS表示上的应用和正确性影响

等进行了讨论；Fourtounis和Papaspyrou等[18]介绍了函数消除方法的一种变体，可以对模块化的程序进行分开编译。

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

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

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

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

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

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

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

分析形成携带语法信息的符号流。符号流经过语法分析生成程序的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.3GHz，Windows 7操作系统。内存为2GB。对目标代码统一使用GCC（版本4.8.1）编译生成目标程序。

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

5结语

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

本文工作为比较不同的高阶代码消除方法提供了技术基础，为提高函数式语言的运行效率提供了参考。

参考文献：

[1]

HUDAK P. Conception， evolution， and application of functional programming languages [J]. ACM Computing Surveys， 1989， 21（3）： 359-411.

[2]

VENNERS B. Twitter on Scala [EB/OL]. [20160108]. http：//www.artima.com/scalazine/articles/twitter_on_scala.html.

[3]

OCONNELL A. Inside Erlang， the rare programming language behind WhatsApps success [EB/OL]. [20160108]. http：//www.fastcompany.com/3026758/insideerlangtherareprogramminglanguagebehindwhatsappssuccess.

[4]

MENG X， BRADLEY J， YAVUZ B， et al. MLlib： machine learning in Apache Spark [J]. arXiv preprint arXiv：1505.06807， 2015.

MENG X， BRADLEY J， YAVUZ B， et al. MLlib： machine learning in Apache Spark [EB/OL]. [20151208]. http：//www.jmlr.org/papers/volume17/15237/15237.pdf.

[5]

KRILL P. Microsoft to big data programmers： try F# [EB/OL]. [20151122]. http：//www.infoworld.com/article/2613049/developmenttools/article.html.

[6]

TRELFORD P. Learning with F# [C]// CUFP 07： Proceedings of the 4th ACM SIGPLAN Workshop on Commercial Users of Functional Programming. New York： ACM， 2007： Article No. 7.

[7]

ZAHARIA M， CHOWDHURY M， FRANKLIN M J， et al. Spark： cluster computing with working sets [C]// Proceedings of the 2nd USENIX Conference on Hot Topics in Cloud Computing. Berkeley， CA： USENIX Association， 2010： 10.

[8]

CEJTIN H， JAGANNATHAN S， WEEKS S. Flowdirected closure conversion for typed languages [C]// ESOP 00： Proceedings of the 9th European Symposium on Programming Languages and Systems. London： Springer， 2000： 56-71.

[9]

EISENBERG R A， STOLAREK J. Promoting functions to type families in Haskell [C]// Haskell 14： Proceedings of the 2014 ACM SIGPLAN Symposium on Haskell. New York： ACM， 2014： 95-106.

[10]

KUAN G， MACQUEEN D. Engineering higherorder modules in SML/NJ [C]// Proceedings of the 21st International Conference on Implementation and Application of Functional Languages. Berlin： Springer， 2009： 218-235.

[11]

LANDIN P J. The mechanical evaluation of expressions [J]. Computer Journal， 1964， 6（4）： 308-320.

[12]

DANVY O， NIELSEN L R. Defunctionalization at work [C]// Proceedings of the 3rd ACM SIGPLAN international Conference on Principles and Practice of Declarative Programming. New York： ACM， 2001： 162-174.

[13]

HANSEN M R， RISCHEL H. Functional Programming Using F# [M]. Cambridge： Cambridge University Press， 2013.

[14]

APPEL A W， JIM T. Continuationpassing， closurepassing style [C]// Proceedings of the 16th ACM SIGPLANSIGACT Symposium on Principles of Programming Languages. New York： ACM， 1989： 293-302.

[15]

MORRISETT G， WALKER D， CRARY K， et al. From system F to typed assembly language [J]. ACM Transactions on Programming Languages and Systems， 1999， 21（3）： 527-568.

[16]

PERCONTI J T， AHMED A. Verifying an open compiler using multilanguage semantics [M]// SHAO Z. Programming Languages and Systems， LNCS 8410. Berlin： Springer， 2014： 128-148.

[17]

REYNOLDS J C. Definitional interpreters for higherorder programming languages [J]. HigherOrder and Symbolic Computation， 1998， 11（4）： 363-397.

[18]

FOURTOUNIS G， PAPASPYROU N S. Supporting separate compilation in a defunctionalizing compiler [C]// Proceedings of the 2nd Symposium on Languages， Applications and Technologies. Dagstuhl： Schloss DagstuhlLeibnizZentrum fuer Informatik， 2013， 29： 39-49.

FOURTOUNIS G， PAPASPYROU N S. Supporting separate compilation in a defunctionalizing compiler [EB/OL]. [20151205]. http：//www.softlab.ntua.gr/～gfour/files/slate2013.pdf.

[19]

BELL J M， BELLEGARDE F， HOOK J. Typedriven defunctionalization [C]// Proceedings of the 2nd ACM SIGPLAN International Conference on Functional Programming. New York： ACM， 1997： 25-37.

[20]

APPEL A W. Compiling with Continuations [M]. New York： Cambridge University Press， 1992： 1-64.