Lua 5.0實現原理學習筆記是本文要介紹的內容，Lua 作為小型軟件的開發語言誕生在一個科學實驗室中。現在被世界上許多大型項目所采用，尤其廣泛的應用于游戲開發中。我們是怎么看待Lua的廣泛應用呢？我相信答案在于我們的設計和實現目標：提供一個簡單、高效、可移植、輕量級的嵌入式腳本語言。從1993年Lua誕生之日起，它就成為了我們的主要目標。這些特點就是Lua能被業界廣泛采用的原因。

廣泛的使用必然會對對語言的特性提出許多新的要求。一些Lua新特性是應開發需要和使用反饋而產生。比如：corotine, garbage collection。這些特點對于游戲開發很重要。

本文中，我們著重討論Lua 5.0相對于Lua 4.0的實現中一些主要新特點。

Register-based virtual machine(基于寄存器的虛擬機): 

通常，大部分的虛擬機實現傾向于“基于堆棧的執行方式”。最早的有Pascal's P-machine，到今天的Java's JVM和Microsoft .Net環境。不過，目前基于寄存器的執行方式越來越受到關注，比如：Perl6(Parrot)的虛擬機就計劃采用基于寄存器的方式。據我們了 解，Lua 5.0是***個被廣泛應用的采用基于寄存器執行的虛擬機實現。虛擬機將在第七節討論。

New algorithm for optimizing tables used as arrays: 

不想其他腳本語言，Lua不提供數組類型。Lua開發人員通常會使用整數索引的Table來實現數組。Lua5.0中使用了一個新的算法，檢測table 是否被用作一個數組，如果是的，那么將把table中的值存儲在一個真正的數組中，而不是將他們加入哈希表。該算法將在第四節討論。

Closures的實現：

Lua 5.0 支持詞法范圍的first-class functions。使用基于數組的堆棧存儲當前活動的數據的機制來實現了一個著名的語言難點。Lua將本地變量存儲在一個array-based stack中。當發生內嵌函數調用時，而且超出了當前函數的執行范圍的時候，這些存儲于array-based stack中的本地變量將被復制到堆中。Closures的實現將在第五節討論。

The addition of coroutines:

Lua 5.0語言中介紹了coroutines。盡管conroutine的實現和以前版本沒有什么重大差別。為了保持本文的完整性。我們將在第六節對其進行討論。

剩 余幾個章節主要是對這些討論的一些補充和背景知識介紹。在第二節中，我們介紹了Lua的設計目標以及這些目標xxxxx。在第三節中，我們描述了Lua是 怎么表示“值”。盡管這些介紹的內容并不是Lua的***特性，但是我們需要這些來為其他章節做補充。***我們在第八節展示了一個簡單性能測試例子以及得出 一些結論。

1、Lua的設計和實現概述

就像在介紹中提到的那樣，Lua的設計目標：

簡單：我們采用最簡單的語言并且最簡單的C代碼來實現這個語言。這意味著一個簡單的語法和少量的語言結構，xxxxx。

高效：我們追求最快的編譯和最快的執行。這意味著一個快速、智能、一次掃描的編譯器和一個快速的虛擬機。

可 移植：我們希望Lua運行在盡可能多的平臺上。我們做到Lua的核心不需要任何修改就能夠在不同平臺上編譯，Lua的程序不需要任何修改就能在不同平臺上 的Lua解釋器中執行。這意味著一個干凈的ANCI C實現以及周密考慮了移植問題。比如避免使用C語言的非標準語法和非標準庫。而且保證能夠在C++編譯器中干凈編譯。我們追求無警告編譯。

可嵌入：Lua是一個擴展語言，他的是為了能夠給大型程序提供腳本功能而作。這個目標意味著現存的C API是很簡單和強大，但是需要依賴于大多數內建的C類型。

低嵌入代價：我們希望Lua能夠很容易的被加入到其他應用程序中而不會導致整個系統膨脹。這意味著緊湊的C代碼和精巧的Lua核心和擴展以library形式加入到現有應用中。

這 些目標在有些時候是互相沖突的。比如：Lua經常被用作一個數據描述語言，用于讀寫配置文件，有時就像一個大的數據庫（大至幾兆的Lua程序也是很常 見）。這意味著我們需要一個快速的編譯器。另外一方面，我們希望Lua程序執行起來盡可能的快速。這意味著需要一個智能的編譯器。可以為虛擬機產生優化的 代碼。于是，編譯器的實現就需要在這兩個需求中尋找一個平衡點。然而，編譯器不能太大，否則它將導致整個應用體積膨脹。當前的實現中編譯器的體積大約占整 個核心的30%。對于內存有限的應用中（比如：嵌入式系統），可以做到嵌入不帶編譯器的Lua。Lua程序需要預先編譯成二進制文件，在運行時由一個很小 的加載模塊載入。

Lua包含一個手工編寫的詞法掃描器和一個手工編寫的遞歸下降語法分析器。在3.0版本以前，Lua使用yacc生成的語法分析器。然而手工編寫的分析器更小，更高效，更可移植，而且可以完全重入（保證可以多線程并發執行）。而且可以提供更完整的錯誤信息。

Lua 編譯器不產生其他編譯器常有的中間層代碼。他在解析程序的同時直接生成虛擬機指令。盡管沒有中間層代碼，Lua編譯器仍然對代碼進行了優化。比如：他延遲 生成基本表達式（變量、常量）的代碼。當他解析到這些表達式時，他不產生指令；但使用一個簡單的結構來表示。因此就很容易判斷一個指令的操作數是常量還是 本地變量。如果是，則可以直接將這些常量或變量生成到指令中，這樣避免了無必要的“值”復制（參閱第三節）。

為了確保能夠在不同C編譯器和平臺中移植，Lua放棄了一些解釋器中常用的技巧。比如：直接使用操作系統中的線程。取而代之的是一個標準的while-switch分支循環。盡管這些地方的c代碼比較復雜難看，但這一切都是為了保證可移植性。

我 們認為我們已經達到了我們設計的目標。Lua現在是一種可移植性非常高的語言：只要有ANSI C編譯器就能夠編譯，從嵌入式系統到大型主機。Lua是真正的輕量級：在Linux上，一個獨立解釋器，包含所有的標準庫，只有不到150K大小；關鍵核 心部分只有不到100K。Lua是高效的：第三方測試結果表明Lua在腳本語言中速度最快。我們也認為Lua是一個簡單的語言，語法像Pascal，語義 類似Schema。

2、值的表示

Lua是一種動態類型的語言：類型附屬于“值”而不是變量。Lua有八種基本類 型：nil, boolean, number, string, table, function, userdata, thread。Nil是一個只有一個值的標記類型；Boolean的值只有true和false；Number是雙精度浮點數，和C語言的double一 樣，但是可以在編譯Lua內核的時候使用float或者long（一些游戲終端和小型系統在硬件上缺少對double的支持）；String是有長度說明 的字節數組，因此也可以用于存儲任意的二進制數據。Table是associative arrays，可以由任何值來進行索引（除了nil）以及可以存放任何值。

Function既可以是Lua函數也可以是根據Lua虛擬機調用協議編寫的C 函數。Userdata本質上是指向用戶內存塊的指針。有兩種風格：重型，內存塊由Lua分配并通過垃圾回收機制釋放；輕型，內存塊的分配和釋放都是由C 代碼管理。***，thread表示coroutine。所有類型的“值”都是first-clast value：可以保存在全局變量、局部變量、表中；可以當作參數傳遞給函數，可以通過函數返回值返回。

Lua中的值是tagged union。也就是pairs(t, v)，t是一個integer標志，表示了v的類型。而v是一個C語言中的union。Nil有一個單一的值，Boolean和number是用過 “unboxed”值來實現：v就是union中的值。這意味著union必須足夠大，可以放下一個double。String, table, function, thread, userdata是通過指針引用來表示：v就是一個指向這些結構的一個指針。這些結構共享一個通用的head，保留了用于垃圾回收的必要信息。結構的其他 部分有別于各個類別。

typedef struct  
{  
int t;  
Value v;  
} TObject;  
 
type union  
{  
GCObject *gc;  
void *p;  
lua_Number n;  
int b;  
}Value; 

圖 一展示了Lua的值的具體實現。TObject實現了tagged units (t, v)。Value就是實現value的union。Nil的值不需要顯示的表示出來，因為它的tag就足以標識了。字段n用于表示number(缺省情況 下，lua_Number就是double)。字段b表示boolean。字段p表示輕型userdata。字段gc表示其他類型的值（string, table, function, 重型userdata, thread），gc指向的內容包含了垃圾回收時所必需的信息。

由于采用了 tagged union來表示“值”，導致復制數據的代價增大：在一個32位支持64位浮點的硬件上。TObject占據12個字節（如果硬件讓double類型按8 字節對齊，則需要16字節）。那么拷貝一個value需要復制3（或4）個機器字長。這確實是一個問題，使用ANSI C很難找到一個更好的辦法。一些動態類型語言（smalltalk80）使用每個指針的空余的位來存儲類型信息。這個在很多硬件上都可以實現。由于通常會 按照某個數值對齊（4字節，8字節）。那么指針的***2個位始終是為零。那么就可以用于其它用途。但是這種方法失去了可移植性，而且在ANSI C中也是做不到。標準C語言不保證指針類型和任何數值類型匹配，也沒有針對指針的標準的“位”操作方法。

另外一個減少“值”的大小的觀 點：保持tag，但是不把double放入union。舉例來說，所有的成員都是在堆中分配的對象（就像string）。（Python就使用這種技 術，xxxx）然而這樣會導致性能急劇下降。可以做一些改進，一個整數可以表示成unboxed value并直接放入union中，而浮點數放到堆中。這樣做性能和空間都能夠解決，但是這樣導致實現起來非常復雜。

像早期的解釋型語 言，比如：Snobol和Icon，Lua用hash表來存儲string：保存不同字符串的唯一版本。字符串是不可更改：一旦初始化，就不能被修改。字 符串的Hash值通過一些位操作和計算得出，Hash值在字符串用于進行快速比較和作為table的索引之前計算出來并保存。如果字符串很長，Hash值 的計算并不會遍歷整個字符串。提高長字符串操作性能很重要，因為長字符串在Lua程序中相當常見。比如，經常會把整個文件讀入到內存中當作一個長字符串來 存儲。

3、Tables

Table可以說是Lua中唯一的數據結構。Table無論是在語言中還是語言的實現中都是一個關鍵角色。從另一方面來說，由于沒有其他的數據結構機制，迫使Table的實現必需足夠高效和功能強大。

Figure 2

Table在Lua中是associative array。也就是他們可以被任何類型的值索引（除了nil）以及可以存放任何類型的值。array的大小也會根據操作動態改變。

不 像其他腳本語言，Lua不提供數組類型。數組是由以整數作為索引的table來實現。用table來實現array給語言帶來了一些好處。***，簡單性： 不需要分別對于table和array提供兩套不同的操作。而且程序員在開發時不需要在table和array之間進行選擇。因為只有table，沒有其 他選擇。稀疏數組在Lua中很容易實現。舉例來說：在Perl中，如果你執行下面的語句$a[1000000000]=1；那么會導致“out of memory”錯誤。這條語句導致分配了十億個元素。
而在Lua程序中，a={[1000000000]=1}，僅僅是創建了一個只有一個元素的表。

在Lua 4.0之前，table都是用hash表來實現：所有的鍵值對都被完整的保存起來。

對于數組來說a={10, 10, 10}，其鍵值對就是(1, 10), (2, 10), (3, 10)。

針 對把table當作數組使用這種情況，Lua 5.0 提供了一種新的優化算法。當發現table是被當作數組來使用時，他并不存儲整數的索引，也就是上面的1, 2, 3。而是將這些值放入一個真正的數組中。這樣可以大大提高存取效率。更準確地說，在Lua 5.0中table被實現成一種混合結構。包含一個hash表部分和一個數組部分。圖 2詳細介紹了這個實現。從程序來看這些都是透明的。程序員無需關心他的數據究竟是存于hash表還是數組。Lua的內部會自動和動態的對table中的數 據進行調整。那些鍵是從1到n的放入數組部分；那些鍵根本就不是整數或者是整數但超出數組大小范圍的放入hash表部分。

xxxxxxxx 

混 合模式有兩個優勢。***，當用整數索引來訪問時，由于不需要計算hash值，所以提高了性能。第二，由于不需要存儲索引值，節約了不少空間。也就是當 table被當作數組使用時，他內部會使用一個真正的數組，那么索引值就不需要額外分配空間存儲。如果table僅當作數組時，他的hash部分是不存 在；如果僅當作associative array，他的數組部分將不存在。這個確保了內存空間沒有浪費。這點很重要，因為在Lua程序中通常會用到大量的小table。

xxxxxxxxxxxx 

4、函數和閉包 Functions and Closures

當Lua編譯一個函數時，他產生了一個原型包含虛擬機指令、常量、調試信息。在運行的時候，他創建一個閉包。閉包中保存了以下內容：一個到他的原型的引用，一個到執行環境的引用，一個存放upvalues引用的數組。

一類函數要應用于詞法范圍導致了一個問題。就是如何訪問到外部函數的局部變量。請看圖3中的例子。當add2被調用時，他訪問的是他的外部函數的局部變量。然后在那個時候，add已經退出了。如果x是在堆棧上，由于函數的堆棧已經消失，那么局部變量也就消失了。

大多數的過程類語言都采取各種辦法來避免類似問題：嚴格定義詞法范圍（e.g., Python），不提供一類函數（e.g., Pascal），或者兩者都采用（e.g., C）。函數類語言不存在這樣的問題。xxxxxxxxxxx

Lua 使用了一個叫upvalue的結構來實現closure。任何外部的局部變量都可以通過upvalue間接訪問到。upvalue最初存放的是指向堆棧單 元的指針。當局部變量需要超出函數范圍的時候，變量本身將被移動到upvalue內部。由于訪問外部局部變量都是通過upvalue間接來完成，所以這種 移動對于程序來說是透明的。對于聲明這個局部變量的函數來說，他訪問的是他自己的局部變量，可以直接從堆棧中得到。

如果一個函數產生了多 個內部閉包，那么這些閉包需要能夠正確的訪問相同的局部變量。為了實現這個需求，Lua對于每一個堆棧的所有upvalue維護了一個鏈表。當一個新的閉 包被創建出來，他將遍歷所有的外部局部變量。對于每一個局部變量，他都試圖在鏈表中尋找一個匹配的upvalue。如果能夠找到，則直接引用這個 upvalue；否則就創建一個新的upvalue并且加入鏈表。注意：鏈表的搜索過程相當快捷，因為對于每一個局部變量只會創建一個upvalue節 點。一旦upvalue不再被引用，將自動由垃圾收集器負責回收。

在多層函數嵌套的情況下，內層函數仍然可以訪問到非直接外層函數所定義的局部變量。Lua通過flat closure來解決這個問題。xxxxxxxxxxxxxx

5、Threads and Coroutines

從 5.0起，Lua實現了非對稱協程（也叫半對稱協程或半協程）。通過三個Lua庫函數來實現：create, resume, yield。create函數接受一個main函數值作為參數，然后創建一個協程來執行這個函數。返回一個thread值來表示這個協程。（像其他類型一 樣，協程也是一類值）。resume函數啟動或繼續執行某個協程。yield函數掛起一個協程，并把執行權返回給調用resume的函數所在的那個協程。

理 論上，每一個協程擁有一個屬于他自己的堆棧。（實際上，每個協程又兩個堆棧，但是我們視之為一個抽象的堆棧）。Lua中的協程是可堆疊的，也就是我們不管 在多深的函數嵌套中，我們都可以通過調用suspend來掛起當前協程。解釋器簡單的停用當前協程的整個堆棧，而啟用另外一個協程的堆棧。程序可以隨時啟 動一個掛起的協程。垃圾回收器會回收那些不再被使用的協程的堆棧。

小結：詳解關于Lua 5.0實現原理學習筆記的內容介紹完了，希望通過本文的學習能對你有所幫助！