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

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

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

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

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

New algorithm for optimizing tables used as arrays: 

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

Closures的實(shí)現(xiàn)：

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

The addition of coroutines:

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

剩 余幾個(gè)章節(jié)主要是對(duì)這些討論的一些補(bǔ)充和背景知識(shí)介紹。在第二節(jié)中，我們介紹了Lua的設(shè)計(jì)目標(biāo)以及這些目標(biāo)xxxxx。在第三節(jié)中，我們描述了Lua是 怎么表示“值”。盡管這些介紹的內(nèi)容并不是Lua的***特性，但是我們需要這些來(lái)為其他章節(jié)做補(bǔ)充。***我們?cè)诘诎斯?jié)展示了一個(gè)簡(jiǎn)單性能測(cè)試?yán)右约暗贸?一些結(jié)論。

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

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

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

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

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

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

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

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

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

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

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

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

2、值的表示

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

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

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

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

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

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

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

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

3、Tables

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

Figure 2

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

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

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

對(duì)于數(shù)組來(lái)說(shuō)a={10, 10, 10}，其鍵值對(duì)就是(1, 10), (2, 10), (3, 10)。

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

xxxxxxxx 

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

xxxxxxxxxxxx 

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

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

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

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

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

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

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

5、Threads and Coroutines

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

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

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