高階代碼消除性能比較框架的設計與實現

趙迪　華保健　朱洪軍

摘要：

函數式語言編譯中，閉包變換和函數消除是廣泛采用的高階代碼消除方法。為了提高函數式語言的運行效率，針對函數式語言編譯階段的高階代碼消除過程對目標代碼效率的影響，設計并實現了一種函數式語言編譯框架。該框架采用了菱形的架構，平行地使用了閉包變換與函數消除兩種高階代碼消除方法。設計了一種具有代表性的函數式語言——FUN語言，并以FUN語言為基礎，給出了比較框架的一個完整實現。通過該系統(tǒng)，對閉包變換與函數消除的效率影響進行對比實驗，選取具有典型特征的測試例，分別從生成代碼的規(guī)模和運行效率方面對閉包變換與函數消除兩種方法的結果進行比較。實驗結果表明，與閉包變換相比，使用函數消除方式所得的目標代碼量更少，最多可減少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引言

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

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

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

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

本文的主要工作包括：

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

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

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

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

1.1閉包變換

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

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

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

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

1）計算每個函數定義內的自由變量的集合。

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

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

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

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

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

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

4）原代碼中的函數調用轉換為對apply函數的調用，并且第一個參數為原函數名，第二個參數為原來的參數。

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

分析形成攜帶語法信息的符號流。符號流經過語法分析生成程序的FUN語言中間表示，即源程序在內存中的結構化表示。

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

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

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

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

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

這一框架設計的基礎上，本文以FUN語言作為源語言、以C語言作為目標語言搭建了一個編譯系統(tǒng)，對該框架進行了實現，并提供了相應的運行時支持。

4實驗設計與結果分析

本文在實現的編譯系統(tǒng)上進行了實驗，并對實驗結果進

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

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

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

表2列出了使用兩種方法得到的目標代碼量（以行為單位）之間的比較結果。通過表2的數據可以得出：對于所有測試例，使用函數消除得到的目標代碼量較少。特別是，測試例f和g分別在累加函數內定義了大量的有名函數定義和無名函數定義，對這兩種情況，使用函數消除得到的目標代碼量明顯少于使用閉包變換得到的結果，目標代碼量分別減少33.76%和14.44%，說明函數消除方法能顯著減少函數抽象的目標代碼量。

5結語

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

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

參考文獻：

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