详解关于Lua 5.0实现原理学习笔记
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的函数所在的那个协程。