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

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

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

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

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

New algorithm for optimizing tables used as arrays: 

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

Closures的實現(xiàn)：

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

The addition of coroutines:

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

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

1、Lua的設(shè)計和實現(xiàn)概述

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

簡單：我們采用最簡單的語言并且最簡單的C代碼來實現(xiàn)這個語言。這意味著一個簡單的語法和少量的語言結(jié)構(gòu)，xxxxx。

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

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

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

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

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

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

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

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

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

2、值的表示

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

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

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

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

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

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

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

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

3、Tables

Table可以說是Lua中唯一的數(shù)據(jù)結(jié)構(gòu)。Table無論是在語言中還是語言的實現(xiàn)中都是一個關(guān)鍵角色。從另一方面來說，由于沒有其他的數(shù)據(jù)結(jié)構(gòu)機制，迫使Table的實現(xiàn)必需足夠高效和功能強大。

Figure 2

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

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

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

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

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

xxxxxxxx 

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

xxxxxxxxxxxx 

4、函數(shù)和閉包 Functions and Closures

當Lua編譯一個函數(shù)時，他產(chǎn)生了一個原型包含虛擬機指令、常量、調(diào)試信息。在運行的時候，他創(chuàng)建一個閉包。閉包中保存了以下內(nèi)容：一個到他的原型的引用，一個到執(zhí)行環(huán)境的引用，一個存放upvalues引用的數(shù)組。

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

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

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

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

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

5、Threads and Coroutines

從 5.0起，Lua實現(xiàn)了非對稱協(xié)程（也叫半對稱協(xié)程或半?yún)f(xié)程）。通過三個Lua庫函數(shù)來實現(xiàn)：create, resume, yield。create函數(shù)接受一個main函數(shù)值作為參數(shù)，然后創(chuàng)建一個協(xié)程來執(zhí)行這個函數(shù)。返回一個thread值來表示這個協(xié)程。（像其他類型一 樣，協(xié)程也是一類值）。resume函數(shù)啟動或繼續(xù)執(zhí)行某個協(xié)程。yield函數(shù)掛起一個協(xié)程，并把執(zhí)行權(quán)返回給調(diào)用resume的函數(shù)所在的那個協(xié)程。

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

小結(jié)：詳解關(guān)于Lua 5.0實現(xiàn)原理學(xué)習(xí)筆記的內(nèi)容介紹完了，希望通過本文的學(xué)習(xí)能對你有所幫助！