趙迪　華保健　朱洪軍

摘要：

函數(shù)式語(yǔ)言編譯中，閉包變換和函數(shù)消除是廣泛采用的高階代碼消除方法。為了提高函數(shù)式語(yǔ)言的運(yùn)行效率，針對(duì)函數(shù)式語(yǔ)言編譯階段的高階代碼消除過(guò)程對(duì)目標(biāo)代碼效率的影響，設(shè)計(jì)并實(shí)現(xiàn)了一種函數(shù)式語(yǔ)言編譯框架。該框架采用了菱形的架構(gòu)，平行地使用了閉包變換與函數(shù)消除兩種高階代碼消除方法。設(shè)計(jì)了一種具有代表性的函數(shù)式語(yǔ)言——FUN語(yǔ)言，并以FUN語(yǔ)言為基礎(chǔ)，給出了比較框架的一個(gè)完整實(shí)現(xiàn)。通過(guò)該系統(tǒng)，對(duì)閉包變換與函數(shù)消除的效率影響進(jìn)行對(duì)比實(shí)驗(yàn)，選取具有典型特征的測(cè)試?yán)?，分別從生成代碼的規(guī)模和運(yùn)行效率方面對(duì)閉包變換與函數(shù)消除兩種方法的結(jié)果進(jìn)行比較。實(shí)驗(yàn)結(jié)果表明，與閉包變換相比，使用函數(shù)消除方式所得的目標(biāo)代碼量更少，最多可減少33.76%的目標(biāo)代碼量；并且運(yùn)行效率更高，最多可提高69.51%。

關(guān)鍵詞：

編譯框架；函數(shù)式語(yǔ)言；高階代碼；閉包變換；函數(shù)消除

中圖分類號(hào)：

TP311.5

文獻(xiàn)標(biāo)志碼：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%.

英文關(guān)鍵詞Key words：

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

0引言

函數(shù)式語(yǔ)言的發(fā)展歷史最早可以追溯到Church & Rosser提出的λ演算。1950年代早期，McCarthy研究并開(kāi)發(fā)了第一個(gè)函數(shù)式語(yǔ)言LISP，至今仍被使用[1]。近年來(lái)，隨著軟件系統(tǒng)的復(fù)雜化，函數(shù)式語(yǔ)言憑借支持高階函數(shù)、具有較好的并行性等優(yōu)點(diǎn)被廣泛研究和應(yīng)用。例如Twitter目前使用Scala語(yǔ)言[2]，WhatsApp使用了Erlang[3]等。此外，在分布式計(jì)算、機(jī)器學(xué)習(xí)、大數(shù)據(jù)處理等研究與商業(yè)應(yīng)用的熱點(diǎn)領(lǐng)域中也大量使用了函數(shù)式語(yǔ)言[4-6]。例如，目前流行的開(kāi)源集群計(jì)算框架Apache Spark就是使用Scala實(shí)現(xiàn)的[7]。

隨著使用函數(shù)式語(yǔ)言構(gòu)建的軟件系統(tǒng)越來(lái)越多地被用于處理海量數(shù)據(jù)，如何構(gòu)建函數(shù)式語(yǔ)言編譯器、生成具有更好的運(yùn)行效率的目標(biāo)代碼，成為了一個(gè)關(guān)鍵的問(wèn)題。函數(shù)式語(yǔ)言的編譯過(guò)程主要包括詞法分析、語(yǔ)法分析、CPS（ContinuationPassing Style）變換、高階代碼消除、分配、目標(biāo)代碼生成和代碼優(yōu)化等幾個(gè)階段 。在性能影響方面，大部分編譯階段技術(shù)都較為成熟，但高階代碼消除階段對(duì)于目標(biāo)代碼效率的影響并未得到重視。高階代碼消除是編譯函數(shù)式語(yǔ)言的必要階段，作用是將高階的代碼翻譯為一階的代碼，使其能夠在現(xiàn)有的計(jì)算機(jī)體系結(jié)構(gòu)中運(yùn)行。閉包變換（closure conversion）和函數(shù)消除（defunctionalization）是兩種主要的高階代碼消除方式，很多函數(shù)式語(yǔ)言的實(shí)現(xiàn)采用了這兩種方式之一[8-10]。盡管現(xiàn)有研究對(duì)兩種方法進(jìn)行了理論上的探索和研究，但如何從這兩種方法的目標(biāo)代碼的執(zhí)行效率方面進(jìn)行研究和比較仍然是一個(gè)難題。關(guān)于這兩種變換方式給目標(biāo)帶來(lái)的效率影響，目前尚沒(méi)有相關(guān)結(jié)論。

本文的主要目標(biāo)是研究高階代碼消除方法對(duì)函數(shù)式語(yǔ)言運(yùn)行效率的影響。現(xiàn)有研究面臨的主要挑戰(zhàn)是：現(xiàn)有編譯系統(tǒng)的實(shí)現(xiàn)只采取單獨(dú)一種高階代碼消除方法，而不同的編譯系統(tǒng)的源語(yǔ)言特征、目標(biāo)平臺(tái)和其他編譯過(guò)程都具有較大區(qū)別，因而針對(duì)不同的高階代碼消除方法對(duì)運(yùn)行效率的影響，通過(guò)比較現(xiàn)有編譯系統(tǒng)難以得到有說(shuō)服力的結(jié)論。

為了解決這一困難，本文提出并實(shí)現(xiàn)了一種針對(duì)高階代碼消除方法對(duì)目標(biāo)代碼性能的影響進(jìn)行比較的編譯框架。該框架同時(shí)實(shí)現(xiàn)了閉包變換和函數(shù)消除兩種方式，并通過(guò)采用同等表達(dá)能力的中間表示和語(yǔ)義保持的變換過(guò)程實(shí)現(xiàn)了菱形的架構(gòu)，避免了其他轉(zhuǎn)換過(guò)程的影響，從而解決了不同編譯器的高階代碼消除方法間難以進(jìn)行比較的問(wèn)題，為得到準(zhǔn)確的比較結(jié)果提供了可能。本文首先定義了一種具有代表性的函數(shù)式語(yǔ)言——FUN語(yǔ)言；并以FUN語(yǔ)言作為系統(tǒng)的源語(yǔ)言實(shí)現(xiàn)了一個(gè)基于上述框架的完整編譯系統(tǒng)。通過(guò)該系統(tǒng)，本文對(duì)一組有代表性的源程序進(jìn)行了實(shí)驗(yàn)，實(shí)驗(yàn)結(jié)果表明，與閉包變換相比，使用函數(shù)消除方式所得的目標(biāo)代碼量更少，最多可減少33.76%的目標(biāo)代碼量；并且運(yùn)行效率更高，最多可提高69.51%。

本文的主要工作包括：

1）提出并設(shè)計(jì)了一個(gè)能夠有效地比較閉包變換和函數(shù)消除兩種方法的高階代碼消除性能比較框架，并給出了該框架的實(shí)現(xiàn)。

2）進(jìn)行了系統(tǒng)的實(shí)驗(yàn)，并對(duì)實(shí)驗(yàn)結(jié)果進(jìn)行了分析。實(shí)驗(yàn)結(jié)果表明，高階代碼消除方法的選擇對(duì)于目標(biāo)代碼的規(guī)模和運(yùn)行效率具有顯著的影響，在減少代碼量和時(shí)間效率上，函數(shù)消除優(yōu)于閉包變換。

函數(shù)outer內(nèi)定義了函數(shù)inner，并把inner作為其返回值。而函數(shù)inner中使用了函數(shù)outer的參數(shù)x，而x并未在inner中定義——即x是函數(shù)inner的自由變量。函數(shù)outer返回時(shí)，其棧幀已經(jīng)失效，然而其返回值inner函數(shù)仍可能需要被調(diào)用，即需要訪問(wèn)x的值。此外，每次調(diào)用outer函數(shù)的參數(shù)x不同，那么所返回的inner函數(shù)也具有不同的行為，即函數(shù)的具體行為依賴于函數(shù)定義處的環(huán)境（environment）。目前的計(jì)算機(jī)體系結(jié)構(gòu)不能直接支持這種抽象。

因而，要支持這種高階函數(shù)，函數(shù)式語(yǔ)言的編譯器需要將高階的程序代碼轉(zhuǎn)換為一階的程序代碼，使程序中不存在自由變量。高階代碼消除的作用就是完成這一轉(zhuǎn)換，而閉包變換和函數(shù)消除是兩種常用的高階代碼消除方法。

1.1閉包變換

閉包變換使用閉包（closure）表示一等的函數(shù)（firstclass function）。一個(gè)閉包由函數(shù)代碼（函數(shù)指針）和函數(shù)內(nèi)自由變量的值的集合兩部分組成[11]。閉包是最常用的一等函數(shù)的表示方式[12]，例如在F#語(yǔ)言就使用了閉包的概念表示函數(shù)[13]。

閉包變換是常用的高階代碼轉(zhuǎn)換方法[14]。例如GregMorrisett等[15]在從System F到有類型匯編語(yǔ)言的編譯過(guò)程中使用了保持類型的閉包變換；JamesPerconti等[16]在編譯器程序驗(yàn)證工作中也使用了閉包變換。

閉包變換過(guò)程使程序中的函數(shù)均成為閉合的，即內(nèi)層的函數(shù)中不存在對(duì)外層的函數(shù)中的變量的引用。要做到這一點(diǎn)，需要為函數(shù)增加一個(gè)額外的參數(shù)作為環(huán)境，并且使用函數(shù)代碼和相應(yīng)環(huán)境組成的閉包來(lái)表示一個(gè)函數(shù)。

閉包變換的過(guò)程可概括為：

1）計(jì)算每個(gè)函數(shù)定義內(nèi)的自由變量的集合。

2）對(duì)每個(gè)函數(shù)定義增加一個(gè)額外的參數(shù)表示環(huán)境。環(huán)境具體可看作自由變量的列表，轉(zhuǎn)換后的代碼中，函數(shù)體中的自由變量均從環(huán)境中獲得，因此函數(shù)中不再有自由變量，函數(shù)均成為閉合的。

3）在函數(shù)定義外，轉(zhuǎn)換后的代碼需構(gòu)造具體的環(huán)境變量，并將函數(shù)代碼與具體環(huán)境一起組成一個(gè)閉包，一個(gè)函數(shù)即由一個(gè)閉包表示。

對(duì)于函數(shù)調(diào)用，轉(zhuǎn)換后的代碼先從相應(yīng)的閉包中取出函數(shù)代碼和環(huán)境，再將環(huán)境與原來(lái)的參數(shù)一起作為參數(shù)調(diào)用函數(shù)代碼。

為直觀起見(jiàn)，下面以一個(gè)代碼塊為例。對(duì)于下面的代碼：

可以看到，轉(zhuǎn)換后的代碼中，原來(lái)的函數(shù)名變?yōu)榱税瘮?shù)代碼的閉包變量的名字。而使用函數(shù)時(shí)從相應(yīng)閉包的第一元獲得函數(shù)代碼，并作用于環(huán)境（閉包的第二元）和參數(shù)。

1.2函數(shù)消除

函數(shù)消除使用一階的類型來(lái)表示一等的函數(shù)[12]。函數(shù)消除由Reynolds在20世紀(jì)70年代早期提出[17]并被廣泛應(yīng)用，例如Cejtin等在MLton編譯器中使用了函數(shù)消除作為對(duì)程序的全局變換，生成具有簡(jiǎn)單類型的中間表示[8]；文獻(xiàn)[12]中，Danvy和Nielsen對(duì)函數(shù)消除在程序的CPS表示上的應(yīng)用和正確性影響

等進(jìn)行了討論；Fourtounis和Papaspyrou等[18]介紹了函數(shù)消除方法的一種變體，可以對(duì)模塊化的程序進(jìn)行分開(kāi)編譯。

此外，函數(shù)消除還有一些良好性質(zhì)，例如Bell，Bellegarde和Hook等[19]證明了函數(shù)消除是保持類型的。

函數(shù)消除的過(guò)程包括以下幾個(gè)方面：

1）對(duì)每個(gè)函數(shù)定義，計(jì)算其自由變量集合。

2）轉(zhuǎn)換后的代碼增加一個(gè)apply函數(shù)，其中包括一條case表達(dá)式，對(duì)apply函數(shù)的第一個(gè)參數(shù)進(jìn)行分支判斷。

3）對(duì)原代碼中的函數(shù)定義：將自由變量封裝進(jìn)一個(gè)環(huán)境中；函數(shù)名初始化為一個(gè)新的類型構(gòu)造符作用于該環(huán)境；函數(shù)代碼中，使自由變量從環(huán)境中初始化；最后，函數(shù)代碼作為分支語(yǔ)句加入到apply函數(shù)的case表達(dá)式中，并且該新類型構(gòu)造符作為其分支條件，自由變量均在分支語(yǔ)句中拆箱。

4）原代碼中的函數(shù)調(diào)用轉(zhuǎn)換為對(duì)apply函數(shù)的調(diào)用，并且第一個(gè)參數(shù)為原函數(shù)名，第二個(gè)參數(shù)為原來(lái)的參數(shù)。

那么對(duì)于上節(jié)中的例子，函數(shù)消除的結(jié)果為：

分析形成攜帶語(yǔ)法信息的符號(hào)流。符號(hào)流經(jīng)過(guò)語(yǔ)法分析生成程序的FUN語(yǔ)言中間表示，即源程序在內(nèi)存中的結(jié)構(gòu)化表示。

2）在中間表示轉(zhuǎn)換階段，F(xiàn)UN語(yǔ)言中間表示的程序首先要經(jīng)過(guò)CPS變換形成CPS風(fēng)格的中間表示。CPS變換的作用是使所有中間計(jì)算結(jié)果均被明確表示，并且函數(shù)不再返回，而是通過(guò)延續(xù)（Continuation）表示“下一步要做的事情”[20]。延續(xù)由一個(gè)函數(shù)表示，源語(yǔ)言原有的函數(shù)接受一個(gè)延續(xù)作為額外的參數(shù)，并且函數(shù)執(zhí)行結(jié)束通過(guò)調(diào)用延續(xù)完成控制轉(zhuǎn)移。對(duì)于所有執(zhí)行流發(fā)生轉(zhuǎn)移的表達(dá)式，例如函數(shù)調(diào)用、條件轉(zhuǎn)移等，需要定義新的延續(xù)，以表示執(zhí)行流轉(zhuǎn)移的關(guān)系。由于CPS風(fēng)格的代碼中，函數(shù)從不返回，因而程序執(zhí)行不再依靠調(diào)用棧。

中間表示轉(zhuǎn)換階段的下一個(gè)步驟是高階代碼消除。為了對(duì)比閉包變換與函數(shù)消除的效果，采用了菱形的架構(gòu)，即：同一個(gè)程序的CPS中間表示可分別經(jīng)過(guò)閉包變換和函數(shù)消除生成closure converted中間表示和defunctionalized中間表示；而這兩種中間表示分別經(jīng)過(guò)進(jìn)一步的變換形成Flat中間表示，對(duì)于兩種高階代碼消除方法形成了同一種中間表示下的不同結(jié)構(gòu)，從而保持后續(xù)處理流程的一致性。

Flat中間表示是本文設(shè)計(jì)的一種平坦的不含有高階代碼的程序中間表示，既能攜帶closure converted中間表示和defunctionalized中間表示的信息，又便于之后的變換過(guò)程。

3）后端處理階段包括分配與代碼生成階段。分配階段生成Machine中間表示，是本文設(shè)計(jì)的一種顯式地進(jìn)行內(nèi)存分配并且與機(jī)器語(yǔ)言相似的中間表示，以便于目標(biāo)代碼的生成。代碼生成階段的作用是在Machine中間表示的基礎(chǔ)上生成目標(biāo)代碼。最后，目標(biāo)代碼與運(yùn)行時(shí)支持一同構(gòu)成目標(biāo)程序。運(yùn)行時(shí)支持包括對(duì)FUN語(yǔ)言一些內(nèi)建操作的支持，以及垃圾回收算法等，運(yùn)行時(shí)支持與分配、代碼生成均需要按照一致的內(nèi)存模型。

比較框架的整體設(shè)計(jì)通過(guò)這種架構(gòu)，在使用不同的高階代碼消除方法同時(shí)共用其他流程，提高了比較結(jié)果的可靠性。

這一框架設(shè)計(jì)的基礎(chǔ)上，本文以FUN語(yǔ)言作為源語(yǔ)言、以C語(yǔ)言作為目標(biāo)語(yǔ)言搭建了一個(gè)編譯系統(tǒng)，對(duì)該框架進(jìn)行了實(shí)現(xiàn)，并提供了相應(yīng)的運(yùn)行時(shí)支持。

4實(shí)驗(yàn)設(shè)計(jì)與結(jié)果分析

本文在實(shí)現(xiàn)的編譯系統(tǒng)上進(jìn)行了實(shí)驗(yàn)，并對(duì)實(shí)驗(yàn)結(jié)果進(jìn)

行了分析。實(shí)驗(yàn)的目的是通過(guò)該系統(tǒng)比較閉包變換與函數(shù)消除對(duì)目標(biāo)代碼的運(yùn)行效率的影響。

為了全面地比較閉包變換與函數(shù)消除對(duì)目標(biāo)代碼運(yùn)行效率的各方面影響，實(shí)驗(yàn)選取了目標(biāo)代碼的代碼量和目標(biāo)程序的運(yùn)行效率兩個(gè)方面對(duì)閉包變換與函數(shù)消除兩種方式進(jìn)行比較。為了得到有代表性的結(jié)果，在測(cè)試用例上，針對(duì)數(shù)據(jù)結(jié)構(gòu)上的動(dòng)態(tài)和靜態(tài)操作、遞歸過(guò)程、函數(shù)定義和函數(shù)調(diào)用這幾個(gè)方面，編寫了7個(gè)具有代表性的源程序作為測(cè)試樣本，涵蓋了源語(yǔ)言上的所有表達(dá)式類型。

實(shí)驗(yàn)機(jī)器的CPU主頻為2.3GHz，Windows 7操作系統(tǒng)。內(nèi)存為2GB。對(duì)目標(biāo)代碼統(tǒng)一使用GCC（版本4.8.1）編譯生成目標(biāo)程序。

表2列出了使用兩種方法得到的目標(biāo)代碼量（以行為單位）之間的比較結(jié)果。通過(guò)表2的數(shù)據(jù)可以得出：對(duì)于所有測(cè)試?yán)?，使用函?shù)消除得到的目標(biāo)代碼量較少。特別是，測(cè)試?yán)齠和g分別在累加函數(shù)內(nèi)定義了大量的有名函數(shù)定義和無(wú)名函數(shù)定義，對(duì)這兩種情況，使用函數(shù)消除得到的目標(biāo)代碼量明顯少于使用閉包變換得到的結(jié)果，目標(biāo)代碼量分別減少33.76%和14.44%，說(shuō)明函數(shù)消除方法能顯著減少函數(shù)抽象的目標(biāo)代碼量。

5結(jié)語(yǔ)

本文提出了一種用于比較閉包變換與函數(shù)消除兩種高階代碼消除方法的編譯系統(tǒng)框架，給出了該框架的實(shí)現(xiàn)，并通過(guò)該系統(tǒng)進(jìn)行實(shí)驗(yàn)分析比較了兩種方法對(duì)目標(biāo)程序的效率影響。實(shí)驗(yàn)與分析結(jié)果表明，使用函數(shù)消除得到的目標(biāo)代碼具有更高的運(yùn)行效率和更少的目標(biāo)代碼量。

本文工作為比較不同的高階代碼消除方法提供了技術(shù)基礎(chǔ)，為提高函數(shù)式語(yǔ)言的運(yùn)行效率提供了參考。

參考文獻(xiàn)：

[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.