函數(shù)式語言編譯器中的Ｇ－Ｍａｃｈｉｎｅ技術(shù)研究

摘要：函數(shù)式程序設(shè)計語言具有程序簡潔，易于進行推理和正確性證明等優(yōu)點。抽象機技術(shù)完成函數(shù)式程序設(shè)計語言的規(guī)約計算到傳統(tǒng)體系結(jié)構(gòu)的狀態(tài)轉(zhuǎn)移計算之間的轉(zhuǎn)換，是函數(shù)式語言編譯技術(shù)的核心。本文基于Spineless G-Machine抽象機的圖規(guī)約機模型，并在其基礎(chǔ)上進行了改進，通過增加閉包，構(gòu)造全懶惰表達式等，得到了一個更容易理解和易于優(yōu)化的抽象機模型。并且在此模型上使用了擴展MKAP指令和G-code窺孔優(yōu)化等方法提高抽象機的效率。

關(guān)鍵詞：函數(shù)式語言；圖規(guī)約；抽象機；G-Machine

中圖分類號：TP311文獻標識碼：A文章編號：1009-3044(2008)20-30311-03

Research on G-Machine Technology in Functional Language Compiler

CHEN Zi-xin

(City College Of DongGuan University of Technology，Dongguan 523106，China)

Abstract:In this paper Spineless G-Machine is improved to gain the advantages of STG-Machine but remain the operational semantics of Spineless G-Machine codes.This model is easier to understand and explore optimization space than STG-Machine. Based on this improved Spineless G-Machine， some optimizations on the abstract machine codes are added to explore the improve space，including extend the MKAP instruction and G-code peephole optimizations.

Key words:Functional language;graph reduction;abstract machine;G-Mach

1 前言

隨著計算機軟件變得越來越復雜，軟件的結(jié)構(gòu)化也越來越重要。良好結(jié)構(gòu)的軟件應該容易編寫、容易調(diào)試并且能提供一系列可以重用的模塊以減少將來編程的重復工作，這些需要也對程序設(shè)計語言提出了新的要求。傳統(tǒng)的計算機基于指令集的串行執(zhí)行，這種計算模型已經(jīng)存在了很久，并且為大家所熟悉，該計算模型也深刻的影響了程序設(shè)計語言，以致直到現(xiàn)在我們也在一定程度上總把程序看成是傳統(tǒng)指令序列的高級表示。[1]但是傳統(tǒng)的程序設(shè)計語言從概念上限制了問題的模塊化。于是程序設(shè)計語言發(fā)展的一個趨勢是：把編寫程序的模型與計算機底層的計算模型分離開，犧牲一些程序的執(zhí)行效率，換取程序的簡單與清晰。

函數(shù)式程序設(shè)計就是這樣一種計算模型的嘗試，它是一種強調(diào)表達式求值而不是執(zhí)行命令的程序設(shè)計風格。在這樣的語言中表達式由函數(shù)將基本的數(shù)值聯(lián)合起來構(gòu)成。目前限制函數(shù)式語言推廣的一個重要原因是在傳統(tǒng)的馮諾依曼體系結(jié)構(gòu)的計算機上，函數(shù)式語言的執(zhí)行效率不高。因此通過編譯器來優(yōu)化程序，生成高效代碼，對函數(shù)式語言來說至關(guān)重要。

本文研究了函數(shù)式語言編譯技術(shù)，特別是對函數(shù)式語言的G-Machine編譯模型進行了分析。然后在Spineless G-Machine抽象機的圖規(guī)約機模型的基礎(chǔ)上進行改進，通過增加閉包，構(gòu)造全懶惰表達式等方法，得到了一個更容易理解和易于優(yōu)化的抽象機模型。并且在此模型上使用了擴展MKAP指令和G-code窺孔優(yōu)化等方法進一步提高了抽象機的效率。通過上述改進，本文得到了一種比傳統(tǒng)STG-Machine更高效的混合G-Machine模型。

2 函數(shù)式語言的編譯技術(shù)

函數(shù)式語言（functional language或者applicative language）是支持和鼓勵用函數(shù)式風格編寫程序的一類語言。 函數(shù)式語言的程序由“純函數(shù)”（pure functions）構(gòu)成，純函數(shù)的一個特點是沒有副作用（side effect）即純函數(shù)的計算不會改變計算的環(huán)境，就是說函數(shù)式程序中沒有“狀態(tài)”這一傳統(tǒng)程序設(shè)計的基本概念。和其它的語言模型相比，函數(shù)語言有如下特征：

(1)函數(shù)式語言式以問題為導向的，它是從“what”的角度來描述問題，而命令式的語言（C，Pascal，Java）是從“how”的角度來解決問題。因此，函數(shù)式語言對問題的描述更接近問題本身。

(2)函數(shù)式語言的數(shù)學基礎(chǔ)－－λ演算，具有非常簡潔的表示方式。λ演算在定理證明方面相對與命令式語言有優(yōu)勢。

(3)純的（pure）函數(shù)式語言沒有副作用（Side-effects），即程序或者函數(shù)的輸出完全由輸入決定，而與系統(tǒng)的狀態(tài)無關(guān)。函數(shù)式語言的可并行性和代碼復用性大大超過了其它語言類型。[2]

2.1 λ演算

λ演算對計算機科學具有重要的意義，它提供函數(shù)的表示和轉(zhuǎn)換規(guī)則，是函數(shù)式程序設(shè)計的數(shù)學基礎(chǔ)，多數(shù)函數(shù)式語言編譯器都采用λ演算或擴展的λ演算作為編譯器的內(nèi)部核心語言。λ演算中的計算通過規(guī)約來表示，它不同于馮諾依曼體系結(jié)構(gòu)的狀態(tài)轉(zhuǎn)移模型。

簡單地說，λ演算提供了一種匿名函數(shù)地表達式，語法如下：

<λ expression> ::=

|

|λ.<λ expression>

|<λ expression><λ expression>

定義了兩個基本的歸約（reduction）：δ歸約和β歸約。

δ歸約：可看成是函數(shù)應用的計算，比如+13→δ4（即1+3可歸約為4，函數(shù)‘+’在這里用前綴表示法）

β歸約：可看成λ抽象的應用，比如（λx*xx）2→δ*22

函數(shù)式語言的執(zhí)行過程就是對表達式的計算，即利用兩種規(guī)約把表達式簡化為最終需要結(jié)果的過程。規(guī)約的效率直接關(guān)系到函數(shù)式程序的執(zhí)行效率。經(jīng)典的規(guī)約方法有：串規(guī)約（string reduction）、標準環(huán)境規(guī)約（standrad environment reduction）、圖規(guī)約（graph reduction）等。可選擇的方法也更多，通常有SECD抽象機、圖規(guī)約機、基于組合子的圖規(guī)約機等。

圖規(guī)約的思想是：用圖來表示λ表達式，并通過圖的轉(zhuǎn)化規(guī)則來完成λ表達式的求值。其優(yōu)點是：公共表達式容易共享，不需要特殊的結(jié)構(gòu)來保存環(huán)境，表達清晰并且效率相對較高。

組合子是一種特殊的函數(shù)，它具有和原始函數(shù)一樣的常量特征。組合子可以看成不包括自由變量的λ表達式，如何可計算函數(shù)都能轉(zhuǎn)換成組合子的應用。基于組合子的圖規(guī)約機是目前使用廣泛的函數(shù)式語言的編譯方法。在此基礎(chǔ)上進一步提高對公共表達式的優(yōu)化又提出了超組合子（super-combinators）和范疇邏輯（categorical combinatory logic）等方法。

一般的函數(shù)轉(zhuǎn)換為組合子描述后具有如下的形式：

f1x1…xn1=e1

…

fmx1…xm1=em

e0

其中f1…fm是超組合子的定義，e0是要計算的表達式。

2.2 G-Machine及其演化

G-Machine[3]的出現(xiàn)極大地提高了圖規(guī)約的效率，它注意到超組合子能夠被編譯成固定的指令序列，順序執(zhí)行這些指令能建立超組合子的應用實例。并且G-Machine為更多的優(yōu)化提供了機會。

G-Machine的核心部分是一個棧，用來保存局部變量的綁定和結(jié)合函數(shù)（組合子）應用時的形式參數(shù)與實際參數(shù)，它的每個元素式一個指向圖的指針。抽象機定義了一系列的棧操作和圖操作的指令集。

G-Machine的一個缺點是幾乎所有的優(yōu)化都關(guān)注于使每一步規(guī)約更高效，每次規(guī)約完成后圖的表示都被升級作為下一次規(guī)約的初始狀態(tài)。Spineless G-Machine[4]的提出提高了規(guī)約的效率，它只在有可能失去共享（loss of sharing）時才對圖進行升級。它即保留了全懶惰性規(guī)約的特性，又省略了無用的中間操作。

Spineless G-Machine進一步發(fā)展的結(jié)果是Spineless Tagless G-Machine（STG-Machine）。STG-Machine增加了很多新特點：

(1)STG-Machine抽象機語言本身就是一種簡單的函數(shù)式語言，它具有通常的指稱語義（denotation semantics），并且每個語言成分又一個直接的操作語義。

(2))直接操作unboxed value，執(zhí)行效率高。

(3)采用嚴格性分析（strictness analysis）和共享分析（sharing analysis）改進執(zhí)行效率。

(4)沒有采用其他函數(shù)式編譯技術(shù)常用的λ提升技術(shù)。

(5)STG-Machine很適合并行的實現(xiàn)。

3 G-Machine編譯技術(shù)的改進

Spineless Tagless G-Machine是當前最先進的抽象機之一，但是它也具有明顯的缺點：沒有更多的優(yōu)化空間。每個語言成分有一個直接的操作語義的特點使得語言成分之間的關(guān)系相互獨立，不易于針對其聯(lián)系進行改進。基于上述原因，本文中沒有直接采用基于STG-Machine的抽象機，而是改造Spineless G-Machine的操作語義，通過增加閉包，表達式全懶惰構(gòu)造使其具有和STG-Machine類似的優(yōu)點。由此得到一個比STG-Machine更容易理解和改進的抽象機。在此模型上，可以進行一些STG-Machine上無法完成的優(yōu)化工作。

3.1 增加閉包

高階語言（high order language）的實現(xiàn)中必須要提供一種表示函數(shù)的方法，這種表示可以被看成一種掛起的計算（suspended computation），當它應用到參數(shù)上時完成計算。

STG-Machine中采用了一種很緊湊的方式表示函數(shù)：靜態(tài)的代碼（被所有實例共享）和自由變量合在一起表示函數(shù)，通常這種結(jié)構(gòu)叫做閉包（closure）。閉包物理上是一塊在堆中分配的內(nèi)存，它包含一個指向靜態(tài)代碼的指針合指向自由變量的指針，靜態(tài)代碼執(zhí)行時會訪問閉包中指向的自由變量。

不讓函數(shù)的靜態(tài)代碼直接訪問自由變量的理由是：閉包存在的時間通常比創(chuàng)建它的環(huán)境（stack frame）長，因此當閉包被計算時它需要的自由變量很可能已經(jīng)不在棧里了。

例如：

f=let

x1 = E1

in

f1 x =

let

x2 = E2

in

+ x1 (+x2 x)

當f的表示構(gòu)造好的時候x1，x2已經(jīng)不在棧里了，以后f可能多次被用到，通過閉包，能保留x1，x2的指針以訪問自由變量。為了使Spineless G-Machine能夠不進行λ提升，我們在抽象機中引入了閉包。

3.2 表達式全懶惰構(gòu)造

G-Machine和Spineless G-Machine雖然實現(xiàn)了惰性計算，即表達式只有在真的需要知道其值的時候才會被計算到。但是他們有一個缺點，不管表達式會不會被計算到，表達式的圖表示總是會被創(chuàng)建，而且圖創(chuàng)建的開銷使運行時的。這極大地降低了抽象機的效率。

例如表達式：f x y = g E1 E2

其中E1，E2為任意表達式。無論如果函數(shù)g值使用其中一個參數(shù)，甚至不使用任何一個參數(shù)，圖都會被創(chuàng)建成一個復雜的結(jié)構(gòu)。

TIM（Tree Instruction Machine）[6]的出現(xiàn)節(jié)省了這樣無用的工作。它引入了兩個輔助函數(shù)c1，c2：

f x y = g (c1 x y) (c2 x y)

c1 x y = E1

c2 x y = E2

這些做的好處是無論E1，E2有多么復雜，f x y規(guī)約時只需要構(gòu)造(c1 x y)，(c2 x y)就即可。另外，在G-Machine中，f x y = g E1 E2中E1和E2將被C scheme編譯，而c1 x y = E1和c2 x y = E2將被E scheme編譯，E scheme中的優(yōu)化（B scheme）將會被用到。

如果參數(shù)個數(shù)很多的時候，可以把所有的參數(shù)放在一個元組（tuple）中，并讓輔助函數(shù)共享。上述表達式則變?yōu)椋?/p>

f x y =

let

tup = (x， y)

c1 x y = E1

c2 x y = E2

in

g (c1 x y) (c2 x y)

上述變換在文本中稱之為表達式全懶惰構(gòu)造，完成該變換后Spineless G-Machine和STG-Machine的行為已經(jīng)十分類似。不同的是本文的抽象機仍然采用先編譯各種語言成分到G-code，然后在抽象機上執(zhí)行G-code的運行模式。

3.2.1. 擴展MKAP指令

觀察G-Machine生成的代碼序列，在構(gòu)造表達式的時候能看到幾個PUSH，PUSHINT操作后面緊跟幾個MKAP操作。例如：C[let x = 5 in + x x ] r 0 ＝PUSHINT 5; PUSH 0; PUSH 1; PUSHFUN +; MKAP; MKAP; SLIDE 1。可以看出，PUSH 0和PUSH 1的作用僅僅是為了讓MKAP能夠找到正確的指針，他們?nèi)霔：篑R上出棧，這包含了一些多余的操作。下面的方法擴展了MKAP指令，減少了棧操作。

引入一個新的操作MKAP_EX(n，m，pop)，它的作用是創(chuàng)建一個新的應用節(jié)點，用棧中TOS-n位置指向的圖作為其左子樹（函數(shù)），用TOS-m位置指向的圖作為其右子樹（參數(shù)），然后從棧中彈出pop個元素（pop=0，1，2），然后把新的應用節(jié)點的指針入棧。由此上例可變?yōu)椋篊[let x = 5 in + x x ]r 0 = PUSHINT 5; PUSHFUN x; MKAP_EX(0，1，1); MKAP_EX(0，1，1); SLIDE 1。可以看出減少了2個PUSH操作，從而減少了棧的使用。

3.3 G-code窺孔優(yōu)化

把各種語言成分先編譯成G-code的好處是能在抽象機一級進行代碼變換，可以對G-code序列進行窺孔優(yōu)化（peephole optimization）：

(1)G-Machine產(chǎn)生的代碼有時候會包含連續(xù)的SLIDE操作，根據(jù)SLIDE的定義：將TOS向下滑動m個位置，可以把相鄰的SLIDE合并，即SLIDE(m); SLIDE(n)用SLIDE(n+m)代替。

(2)在棧中生存周期很短的指針，可以經(jīng)過寄存器來中轉(zhuǎn)，減少棧的操作。

(3)如果PUSH操作后緊跟GET操作，可以直接把要入棧的圖壓入操作數(shù)棧，這樣可以減少對棧的連續(xù)PUSH和POP操作。

改進的抽象機模型為G-code級的優(yōu)化提供了很好的基礎(chǔ)。很多源碼級的優(yōu)化技術(shù)可以極大提高抽象機的效率。

4 結(jié)束語

本文主要研究了函數(shù)式語言的編譯技術(shù)，特別是實現(xiàn)規(guī)約計算模型到狀態(tài)轉(zhuǎn)移計算模型之間變換的抽象機技術(shù)。本文在Spineless G-Machine抽象機模型的基礎(chǔ)上進行改進，得到了一個更容易理解和易于優(yōu)化的抽象機模型。

本文強調(diào)了對抽象機代碼序列的優(yōu)化，以得到更多的優(yōu)化機會。實現(xiàn)編譯器對Spineless G-Machine的改進，包括引入閉包和表達式全懶惰構(gòu)造變換，使其具有STG-Machine的優(yōu)點，同時又可以嘗試在抽象機代碼上的優(yōu)化工作，其中包括擴展MKAP指令和窺孔優(yōu)化。

參考文獻：

[1] A.J.Field and P.G.Harrison， Functional Programming: Addison-Wesley，1988.

[2] J.Backus， Can programming be liberated from the von Neumann style?: a functional style and its algebra of program， Commun.ACM，1978(21):613-641.

[3] T.Johnsson，Efficient compilation of lazy evaluation，in Proceedings of the 1984 SIGPLAN symposium on Compiler construction. Montreal， Canada: ACM Press，1984.

[4] G.L.Burn， S.L.P.Jones， and J.D.Robson， “the spineless G-machine”， ub Proceedings of the 1988ACM conference on LISP and functional programming. Snowbird， Utah， United States: ACM Press， 1988

[5] W.Taha， Multi-Stage Programming: Its Theory and Applications， 1999， PhD thesis， Oregon Graduate Institute School of Science and Engineering.

[6] S.P.Jones and D.Lester， Implementing functional languages: a tutorial: Prentice Hall，1992.

注：“本文中所涉及到的圖表、注解、公式等內(nèi)容請以PDF格式閱讀原文。”