lua 5.0的實作（翻譯)1,2,3

三個多月前翻譯的，今天又找出來看看,後面的待整理下繼續發,有錯誤的地方請不吝賜教。

原文：http://www.tecgraf.puc-rio.br/~lhf/ftp/doc/jucs05.pdf

轉載請注明出處，謝謝。

摘要：我們讨論了lua 5.0實作的主要新特性：基于寄存器的虛拟機，優化表的新算法以便（将表）用作數組，閉包的實作，以及coroutines（譯注：協程）

關鍵字: compilers, virtual machines, hash tables, closures, coroutines

1.    介紹

lua作為内部使用的開發工具誕生于學術實驗室中，現在卻已經被世界範圍内許多工業級項目所采用，廣泛應用于遊戲領域。lua為什麼能獲得這樣廣泛的應用呢？我們認為答案就來源于我們的設計和實作目标上：提供一種簡單、高效、可移植和輕量級的嵌入式腳本語言。這是lua自1993年誕生以來我們一直追求的目标，并在（語言的）演化過程中遵守。這些特性，以及lua一開始就被設計成嵌入大型應用的事實，才使它在早期被工業界所接受。

廣泛的應用産生了對（新的）語言的特性的需求。lua的許多特性來自于工業需求和使用者回報的推動。重要的例如lua 5.0引入的coroutines和即将到來的lua 5.1改進的垃圾收集實作，這些特性對于遊戲（程式設計）特别重要。

在這篇論文中，我們讨論了lua 5.0相比于lua 4.0的主要新特性：

基于寄存器的的虛拟機：傳統上，絕大多數虛拟機的實際執行都是基于棧，這個趨勢開始于pascal的pmachine,延續到今天的java虛拟機和微軟的.net環境。目前，盡管對于基于寄存器的虛拟機的興趣逐漸增多（比如perl6計劃中的新的虛拟機（parrot）将是基于寄存器的），但是就我們所知，lua 5.0是第一個被廣泛使用的基于寄存器的虛拟機。我們将在第7部分描述這個虛拟機。

優化表的新算法以便作為數組： 不像其他腳本語言，lua并沒有提供數組類型。lua使用整數索引的普通表來實作數組作為替代。lua 5.0使用了一個新的算法，可以檢測表是否被作為數組使用，并且可以自動将關聯着數字索引的值存儲進一個真實的數組，而不是将它們放進hash表。在第4部分我們将讨論這個算法。

閉包的實作：lua 5.0在詞法層次上支援first-class 函數（譯注：将函數作為一等公民）。這個機制導緻一個著名的語言難題：使用基于數組的棧來存儲激活記錄。lua 使用了一個新辦法來實作函數閉包，儲存局部變量在（基于數組）的棧(stack)上，當它們被内嵌函數引用而從作用域逸出的時候才将它們轉移到堆(heap)上。閉包的實作将在第5部分讨論。

添加coroutines： lua 5.0語言引入了coroutines。盡管coroutines的實作較為傳統，但為了完整性我們将在第6部分做個簡短的概況介紹。

其他部分是為了讨論的完整性或者提供背景資料。在第2部分我們介紹了lua的設計目标以及這個目标如何驅動實作的概況。在第3部分我們介紹了lua是如何表示值的。盡管就這個過程本身沒有什麼新意，但是為了（了解）其他部分我們需要這些資料。最後，在第8部分，我們介紹了一個小型的基準測試來得到一些結論。

2.    lua設計和實作概況

在介紹部分提到過的，lua實作的主要目标是：

簡單性：我們探索我們能提供的最簡單的語言，以及實作（這樣的）語言的最簡單的c代碼。這就意味着（需要）不會偏離傳統很遠的擁有很少語言結構的簡單文法。

效率：我們探索編譯和執行lua程式的最快方法，這就意味着（需要）一個高效的、聰明的一遍掃描編譯器和一個高效的虛拟機。

可移植性：我們希望lua能跑在盡可能多的平台上。我們希望能在任何地方不用修改地編譯lua核心，在任何一個帶有合适的lua解釋器的平台上不用修改地運作lua程式。這就意味着一個對可移植性特别關注的幹淨的ansi c的實作，例如避開c和标準庫庫中的陷阱缺陷，并確定能以c++方式幹淨地編譯。我們追求warning-free的編譯（實作）。

嵌入性：lua是一門擴充語言，它被設計用來為大型程式提供腳本設施。這個以及其他目标就意味着一個簡單并且強大的c api實作，但這樣将更多地依賴内建的c類型。

嵌入的低成本：我們希望能容易地将lua添加進一個應用，而不會使應用變的臃腫。這就意味着（需要）緊湊的c代碼和一個小的lua核心，擴充将作為使用者庫來添加。

這些目标是有所權衡的。例如，lua經常被用作資料描述語言，用于儲存和加載檔案，有時是非常大的資料庫(幾m位元組的lua程式不常見)。這就意味着我們需要一個快速的lua編譯器。另一方面，我們想讓lua程式運作快速，這就意味着（需要）一個可以為虛拟機産生優秀代碼的聰明的編譯器。是以，lua編譯器的實作必須在這兩種需求中尋找平衡。盡管如此，編譯器還是不能太大，否則将使整個發行包變的臃腫。目前編譯器大約占lua核心大小的30%。在記憶體受限的應用中，比如嵌入式系統，嵌入不帶有編譯器的lua是可能的，lua程式将被離線預編譯，然後被一個小子產品（這個小子產品也是快速的，因為它加載的是二進制檔案）在運作時加載。

lua使用了一個手寫的掃描器和一個手寫的遞歸下降解釋器。直到3.0版本，lua還在使用一個yacc産生的解釋器，這在語言的文法不夠穩定的時候很有價值的。然而，手寫的解釋器更小、更高效、更輕便以及完全可重入，也能提供更好的出錯資訊（error message）。

lua編譯器沒有使用中間代碼表示（譯注：也就是不生成中間代碼）。當解釋一個程式的時候，它以“on-the-fly”的方式給虛拟機發出指令。不過，它會進行一些優化。例如，它會推遲像變量和常量這樣的基本表達式的代碼生成。當它解釋這樣的表達式的時候，沒有産生任何代碼，而是使用一種簡單的結構來表示它們。是以，判斷一個給定指令的操作數是常量還是變量以及将它們的值直接應用在指令都變的非常容易，避免了不必要的和昂貴的移動。

為了輕便地在許許多多不同的c編譯器和平台之間移植，lua不能使用許多解釋器通常使用的技巧，例如direct threaded code [8, 16]。作為替代，它（譯注：指lua解釋器）使用了标準的while-switch分發循環。此處的c代碼看起來過于複雜，但是複雜性也是為了確定可移植性。當lua在許多不同的平台上（包括64位平台和一些16位平台）被很多不同的c編譯器編譯，lua實作的可移植性一直以來變的越來越穩定了。

我們認為我們已經達到我們的設計和實作目标了。lua是一門非常輕便的語言，它能跑在任何一個帶有ansi c編譯器的平台上，從嵌入式系統到大型機。lua确實是輕量級的：例如，它在linux平台上的獨立解釋器包括所有的标準庫，占用的空間小于150k;核心更是小于100k。lua是高效的：獨立的基準測試表明lua是腳本語言（解釋的、動态類型的語言）領域中最快的語言之一。主觀上我們也認為lua是一門簡單的語言，文法上類似pascal，語義上類似scheme（譯注：lisp的一種方言）。

3、值的表示

lua是動态類型語言：類型依附于值而不是變量。lua有8種基本類型：nil, boolean, number, string, table, function,userdata, 和thread。nil是一個标記類型，它隻擁有一個值也叫nil。boolean就是通常的true和false。number是雙精度浮點數，對應于c語言中的double類型，但用float或者long作為替代來編譯lua也很容易（不少遊戲consoles或者小機器都缺乏對double的硬體支援）。string是有顯式大小的位元組數組，是以可以存儲任意的二進制類型，包括嵌入零。table類型就是關聯的數組，可以用任何值做索引（除了nil），也可以持有任何值。function是依據與lua虛拟機連接配接的協定編寫的lua函數或者c函數。userdata本質上是指向使用者記憶體區塊（user memory block）的指針，有兩種風格：重量級,由lua配置設定塊并由gc回收；輕量級，由使用者配置設定和釋放（記憶體）塊。最後，thread表示coroutines。所有類型的值都是first-class值：我們可以将它們作為全局變量、局部變量和table的域來存儲，作為參數傳遞給函數，作為函數的傳回值等等。

typedef struct {                        typedef union {

int t;                                      gcobject *gc;

value v;                                   void *p;

} tobject;                                 lua_number n;

int b;

} value;

figure 1: 帶标簽的union表示lua值

lua将值表示為帶标簽的union(tagged unions)，也就是pairs(t,v)，其中t是一個決定了值v類型的整數型标簽，而v是一個實作了lua類型的c語言的union結構。nil擁有一個單獨的值（譯注：也就是nil）。booleans和numbers被實作為“拆箱式”的值：v在union中直接表示這些類型的值。這就意味着union（譯注：指圖中的value）必須有足夠的空間容納double（類型）。strings,tables, functions, threads, 和 userdata類型的值通過引用來實作：v擁有指向實作這些類型的結構的指針。這些結構（譯注：指實作strings,tables, functions, threads, 和 userdata這些類型的具體結構）共享一個共同的head，用來儲存用于垃圾收集的資訊。結構的剩下的部分專屬于各自的類型。

 figure1展示了一個實際的lua值的實作。tobject是這個實作的主要結構體：它表示了上文描述的帶标簽的聯合體（tagged unions） (t,v)。value是實作了值的union類型。類型nil的值沒有顯式表示在這個union類型中是因為标簽已經足夠辨別它們。域n用來表示numbers類型（lua_number預設是double類型）。同樣，域b是給booleans類型用的，域p是給輕量級的userdata類型。而域gc是為會被垃圾回收的其他類型準備的（(strings, tables, functions, 重量級userdata, 和threads)。

使用帶标簽的union實作lua值的一個後果就是拷貝值的代價稍微昂貴了一點：在一台支援64位double類型的32位機器上，tobject的大小是12位元組（或者16位元組，如果double按8位元組對齊的話），是以拷貝一個值将需要拷貝3（或者4）個機器字長。盡管如此，想在ansi c中實作一個更好的值的表示是困難的。一些動态類型語言（例如smalltalk80的原始實作）在每個指針中使用多餘的位來存儲值的類型标簽。這個技巧在絕大多數機器上正常工作，這是因為一個指針的最後兩個或者三個位由于對齊将總是0，是以可以被用作他途。但是，這項技術既不是可移植的也無法在ansi c中實作，c 語言标準甚至都不保證指針适合任何整數類型，是以沒有在指針上操作位的标準方法。

減小值大小的另一個觀點就是持有顯式标簽，進而避免在union中放置一個double類型。例如，所有的number類型可以表示為堆配置設定的對象，就像string那樣。（python使用了這項技術，除了預先配置設定了一些小的整數值）。盡管如此，這樣的表示方法将使語言變的非常緩慢。作為選擇，整數的值可以表示位“拆箱式”的值，直接存儲在union中，而浮點值放在堆中。這個辦法将極大地增加所有算術運算操作的實作複雜度。

類似早期的解釋型語言，例如snobol [11] 和 icon [10]，lua在一個hash表中“拘留”(internalizes)字元串：（hash表）沒有重複地持有每個字元串的單獨拷貝。此外，string是不可變的：一個字元串一旦被“拘留”，将不能再被改變。字元串的哈希值依據一個混合了位和算術運算的簡單表達式來計算，囊括所有的位。當字元串被“拘留”時，hash值儲存（到hash表），以支援更快的字元串比較和表索引。如果字元串太長的話，hash函數并不會用到字元串的所有位元組，這有利于快速地散列長字元串。避免處理長字元串帶來的性能損失是重要的，因為（這樣的操作）在lua中是很普遍的。例如，用lua處理檔案的時候經常将整個檔案内容作為一個單獨的長字元串讀入記憶體

文章轉自莊周夢蝶  ，原文釋出時間2008-04-07