lua 5.0的实现（翻译)4,5

4、 表

    Table是lua的主要——实际上，也是唯一的——数据结构。Table不仅在语言中，同时也在语言的实现中扮演着重要角色。Effort spent on a good implementation of tables is rewarded in the language,because tables are used for several internal tasks, with no qualms about performance。这有助于保持实现的小巧。相反的，任何其他数据结构的机制的缺乏也为table的高效实现带来了很大压力

       Lua中的table是关联数组，也就是可以用任何值做索引（除了nil），也可以持有任何值。另外，table是动态的，也就是说当加进数据的时候它们将增长（给迄今不存在的域赋值）而移除数据的时候将萎缩（给域赋nil值）。

不像大多数其他脚本语言，lua没有数组类型。数组被表示为以整数做键的table。用table作为数组对于语言是有益的。主要的（益处）显而易见：lua并不需要操纵表和数组的两套不同的运算符。另外，程序员不用对两种实现做出艰难选择。在lua中实现稀疏数组是轻而易举的。例如，在Perl里面，如果你尝试去跑$a[1000000000]=1 这样的程序，你能跑出个内存溢出！（you can run out of memory），因为它触发了一个10亿个元素的数组的创建（译注，Perl的哲学是：去除不必要的限制）。而等价的lua程序 a={[1000000000]=1},（只是）创建了有一个单独的项的表（而已）。

<!----><!---->
<!---->

直到lua 4.0，table都是作为hash表严格地实现：所有的pair都被显式地保存。Lua5.0引入了一个新算法来优化作为数组的table：它将以整数为键的pair不再是存储键而是优化成存储值在真正的数组中。更精确地说，在lua 5.0中，table被实现为一个混合数据结构：它们包括一个hash部分和一个数组部分。图2展示了一个有"x"→ 9.3, 1 → 100,2 → 200, 3 → 300对子的表的一种可能结构。注意到数组部分在右边，并没有存储整数的key。这个划分仅仅是在一个低的实现层次进行的，访问table仍然是透明的，甚至在虚拟机内部（访问table）也是如此。Table根据内容自动并且动态地对两个部分进行适配：数组部分试图从1到n的相应地存储值，关联非整数键或者整数键超过数组范围的值被存储在hash部分。

当一个table需要增长时，lua重新计算hash部分和数组部分的大小。任一部分都可能是空的。重新计算后的数组大小是至少是当前使用的数组部分从1到n的一半情况下的最大n值（原文：The computed size of the array part is the largest n such that at least half the slots between 1 and n are in use）（稀疏数组时避免浪费空间），并至少有一个（元素）处在n/2+1到n的槽中（当n被2整除时，避免n的这样的数组大小）。计算完大小后，lua创建了“新”的部分并将“旧”的部分的元素重新插入到的“新”的部分。作为一个例子，假设a是一个空表；它的数组部分和hash部分的大小都是0。当我们执行a[1]=v时，这个表需要增长到足够容纳新的键。Lua将为新的数组部分的大小选择n=1（带有一个项1→v）。hash部分仍然保持为空。

这个混合的方案有两个优点。首先，访问以整数为键的值加快了，因为不再需要任何的散列行为。其次，也是最重要的，数组部分占用的内存大概是将数组部分存储在hash部分时的一半，因为key在数组中是隐式的（译注：也就是数组的下标）而在hash部分却是显式的。因而，当一个table被用作数组的时，它表现的就像一个数组，只要整数键是密集。另外，不用为hash部分付出任何内存和时间上的惩罚，因为它（译注：hash部分）甚至都不存在。相反的控制：如果table被用作关联数组而非一个数组，数组部分可能就是空的。这些内存上的节省是比较重要的，因为lua程序经常创建一些小的table，例如table被用来实现对象（Object）（译注，也就是用table来模仿对象，有点类似javascript中的json）。

Hash部分采用Brent's variation[3]的组合的链状发散表。这些table的主要不变式是如果一个元素没有在它的主要位置上（也就是hash值的原始位置），则冲突的元素在它自己的主要位置上。换句话说，仅当两个元素有相同的主要位置（也就是在当时table大小情况下的hash值）时才有冲突的。没有二级冲突。正因为那样，这些table的加载因子可以是100%而没有性能上的损失。这部分不是很明白，附上原文：

The hash part uses a mix of chained scatter table with Brent's variation [3].

A main invariant of these tables is that if an element is not in its main position

(i.e., the original position given by its hash value), then the colliding element

is in its own main position. In other words, there are collisions only when two

elements have the same main position (i.e., the same hash values for that table

size). There are no secondary collisions. Because of that, the load factor of these

tables can be 100% without performance penalties.

 

 

5、函数和闭包

当lua编译一个函数的时候，它产生一个模型（prototype），包括了函数的虚拟机指令、常量值（数字，字符串字面量等）和一些调试信息。运行的时候，无论何时lua执行一个function…end表达式，它都创建一个新的闭包。每个闭包都有一个引用指向相应的模型，一个引用指向环境（environment）（一张查找全局变量的表，译注：指所谓环境就是这样一张表），和一组用来访问外部local变量的指向upvalue的引用。

词法范围以及first-class函数的组合导致一个关于（如何）访问外部local变量的著名难题。考虑图3中的例子。当add2被调用的时候，它的函数体（body）部分引用了外部local变量x (函数参数在lua里是local变量，译注：x就是所谓的自由变量，这里形成了闭包)。尽管如此，当add2被调用时，生成add2的函数add已经返回。如果在栈中生成变量x，（x在栈的）其栈槽将不复存在。（译注，此处的意思应该是说如果在栈保存变量x，那么在调用add2的时候，add函数早已经返回，x也在add2调用前就不在栈里头了，这就是那个著名难题）。

<!----><!---->
<!---->

 

 

大多数过程语言通过限制词法范围（例如python），不提供first-class函数（例如Pascal），或者都两者都采用（例如c,译注：也就是说c既不把函数当一等公民，也限制词法范围）来回避这个问题。函数式语言就没有那些限制。围绕着非纯粹函数语言比如Scheme和ML的研究已经产生了大量的关于闭包的编译技术的知识（参见[19, 1, 21]）。尽管如此，这些工作并没有尽力去限制编译器的复杂性。以优化的Scheme编译器Bigloo的控制流分

析阶段为例，（它的实现）比lua实现的10倍还大：Bigloo 2.6f的Cfa模块源码有106,350行 VS. 10,155行的lua5.0核心。正如第2部分已经解释过的（原因），lua需要简单。<!----><!----><!---->

Lua使用了一个称为upvalue的结构来实现闭包。任何外部local变量的访问都是通过一个upvalue间接进行的。Upvalue初始指向的是变量存活位置的栈槽（参见图4的左半部分）。当变量（x）已经离开作用域（译注，也就是这里的add函数返回时），它就迁移到upvalue结构本身一个槽中（参见图4的右半部分）。因为（对变量的）访问是间接地通过upvalue结构中的一个指针进行的，因此这个迁移对于任何写或者读该变量的代码都是透明的。不像它的内嵌函数（译注：例子的add2，它是指外部函数add），声明变量的函数访问该变量就像访问它的local变量一样：直接到栈。

通过每个变量最多创建一个upvalue结构并且在必要的时候复用它们，可变状态得以在闭包之间正确地共享。为了保证这一约束，lua维持一个链表，里面是一个栈里（图4中的pending vars列表）的所有open upvalue（所谓open upvalue，是指仍然指向栈的upvalue结构）。当lua创建一个新的闭包的时候，它遍历所有的外部local变量。对于每个（外部local）变量，如果它在列表中找到一个open upvalue，那么它就复用这个upvalue结构。否则，lua就创建一个新的upvalue并将它放入链表。注意到列表搜索只是探测了少数几个节点，因为列表最多包含一个被内嵌函数使用的local变量的项。当一个closed upvalue不再被任何闭包引用的时候，它最后将被当作垃圾并回收。

一个函数允许访问一个不是它的直接外围函数的外部local变量，只要（这个local变量）是外部函数的（outer function）。在那种情况下，甚至在闭包被创建的时候，（外部local）变量可能就不在栈里了。Lua使用扁平闭包（flat closures）解决这种情况[5]。通过扁平闭包，一个函数无论何时去访问一个不属于它的外围函数的外部变量，这个变量都将进入外围函数的闭包。从而当一个函数被实例化的时候，所有进入它闭包的变量要么在外围函数的栈里面，要么在外围函数的闭包里。