768
lua 5.0的實現（翻譯)1,2,3
三個多月前翻譯的，今天又找出來看看,後麵的待整理下繼續發,有錯誤的地方請不吝賜教。
原文：https://www.tecgraf.puc-rio.br/~lhf/ftp/doc/jucs05.pdf
翻譯：dennis zhuang (killme2008@gmail.com) https://www.blogjava.net/killme2008
轉載請注明出處，謝謝。
摘要：我們討論了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處理文件的時候經常將整個文件內容作為一個單獨的長字符串讀入內存
文章轉自莊周夢蝶 ，原文發布時間
最後更新：2017-05-17 18:01:41