高階代碼消除性能比較框架的設(shè)計與實(shí)現(xiàn)

趙迪　華保健　朱洪軍

摘要：

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

關(guān)鍵詞：

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

中圖分類號：

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

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

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

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

本文的主要工作包括：

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

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

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

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

1.1閉包變換

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

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

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

閉包變換的過程可概括為：

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

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

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

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

為直觀起見，下面以一個代碼塊為例。對于下面的代碼：

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

1.2函數(shù)消除

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

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

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

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

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

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

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

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

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

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

2）在中間表示轉(zhuǎn)換階段，F(xiàn)UN語言中間表示的程序首先要經(jīng)過CPS變換形成CPS風(fēng)格的中間表示。CPS變換的作用是使所有中間計算結(jié)果均被明確表示，并且函數(shù)不再返回，而是通過延續(xù)（Continuation）表示“下一步要做的事情”[20]。延續(xù)由一個函數(shù)表示，源語言原有的函數(shù)接受一個延續(xù)作為額外的參數(shù)，并且函數(shù)執(zhí)行結(jié)束通過調(diào)用延續(xù)完成控制轉(zhuǎn)移。對于所有執(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)換階段的下一個步驟是高階代碼消除。為了對比閉包變換與函數(shù)消除的效果，采用了菱形的架構(gòu)，即：同一個程序的CPS中間表示可分別經(jīng)過閉包變換和函數(shù)消除生成closure converted中間表示和defunctionalized中間表示；而這兩種中間表示分別經(jīng)過進(jìn)一步的變換形成Flat中間表示，對于兩種高階代碼消除方法形成了同一種中間表示下的不同結(jié)構(gòu)，從而保持后續(xù)處理流程的一致性。

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

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

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

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

4實(shí)驗設(shè)計與結(jié)果分析

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

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

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

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

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

5結(jié)語

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

本文工作為比較不同的高階代碼消除方法提供了技術(shù)基礎(chǔ)，為提高函數(shù)式語言的運(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.