3 值表示
Lua 是一种动态类型语言：类型附加到值而不是变量。 Lua 有八种基本类型：nil、boolean、number、string、table、function、userdata 和 thread。 Nil 是一种只有一个值的标记类型，也称为 nil。 布尔值通常是 true 和 false。 Numbers 是双精度浮点数，对应 C 中的 double 类型，但是使用 float 或 long 来编译 Lua 很容易。 （一些游戏机和较小的机器缺乏双的硬件支持。）字符串是具有明确大小的字节数组，因此可以包含任意二进制数据，包括嵌入的零。 表是关联数组，可以由任何值（nil 除外）索引并且可以保存任何值。 函数是根据与 Lua 虚拟机接口的协议编写的 Lua 函数或 C 函数。 Userdata 本质上是指向用户内存块的指针，有两种类型：heavy，其块由 Lua 分配并进行垃圾回收，以及 light，其块由用户分配和释放。 最后，线程代表协程。 所有类型的值都是第一类值：我们可以将它们存储在全局变量、局部变量和表字段中，将它们作为参数传递给函数，从函数中返回它们等。
图 1：Lua 值表示为tagged unions
typedef union {
GCObject *gc;
void *p;
lua_Number n;
int b;
} Value;
typedef struct {
int t;
Value v;
} TObject;
Lua 将值表示为tagged unions，即成对 (t, v)，其中 t 是标识值 v 类型的整数标记，它是实现 Lua 类型的 C 类型的union。 Nil 有一个值。 布尔值和数字被实现为“未装箱”的值：v 直接在union中表示这些类型的值。 这意味着union必须有足够的空间来容纳双精度数。 字符串、表、函数、线程和用户数据值通过引用实现： v 包含指向实现这些值的结构的指针。 这些结构共享一个公共header，用于保存垃圾收集所需的信息。 结构的其余部分特定于每种类型。
图 1 显示了 Lua 值的实际实现的一瞥。 TObject 是此实现中的主要结构：它表示上述标记的联合 (t, v)。 v 是实现值的union。 nil 类型的值在union中没有明确表示，因为标签足以识别它们。 字段 n 用于数字（默认情况下，lua_Number 是 double）。 字段 b 用于布尔值。 字段 p 用于light userdata。 字段 gc 用于其他值（字符串、表、函数、大量用户数据和线程），这些值受垃圾收集的影响。
使用tagged unions来表示 Lua 值的一个后果是复制值有点昂贵：在具有 64 位双精度的 32 位机器上，TObject 的大小是 12 字节（或 16 字节，如果双精度在 8 - 字节边界），因此复制一个值需要复制 3（或 4）个机器字。 然而，很难在 ANSI C 中实现更好的值表示。 几种动态类型语言（例如 Smalltalk80 [9] 的原始实现）在每个指针中使用备用位来存储值的类型标记。 这个技巧适用于大多数机器，因为由于对齐，指针的最后两位或三位始终为零，因此可以用于其他目的。 然而，这种技术在 ANSI C 中既不可移植也不可实现。C 标准甚至不能确保指针适合任何整数类型，因此没有标准方法来对指针执行位操作。
减小值大小的另一种选择是保留显式标记，但要避免在union中放置双精度值。 例如，所有数字都可以表示为堆分配的对象，就像字符串一样。 （Python 使用这种技术，只是它预先分配了一些小的整数值。）但是，这种表示会使语言变得很慢。 或者，整数值可以直接在union内部表示为未装箱的值，而浮点值将进入堆。 该解决方案将大大增加所有算术运算实现的复杂性。
像早期的解释型语言，如 Snobol [11] 和 Icon [10]，Lua 使用哈希表将字符串内部化：它为每个字符串保留一个副本，没有重复。 此外，字符串是不可变的：一旦内化，字符串就无法更改。 字符串的哈希值由一个简单的表达式计算，该表达式混合了按位和算术运算，从而对所有涉及的位进行混洗。 当字符串被内部化以允许快速字符串比较和表索引时，会保存哈希值。 如果字符串太长，哈希函数不会查看字符串的所有字节。 这允许对长字符串进行快速散列。 在处理长字符串时避免性能损失很重要，因为它们在 Lua 中很常见。 例如，在 Lua 中处理文件的方式通常是将它们完全读入内存并转换为一个长字符串。
4 Tables
tables是 Lua 中主要的——事实上，唯一的——数据结构机制。 tables不仅在语言中而且在其实现中都起着关键作用。 为tables的良好实现所付出的努力在语言中得到了回报，因为tables用于多个内部任务，对性能没有任何疑虑。 这有助于保持实现较小。 相反，没有任何其他数据结构化机制会给表的有效实现带来压力。
Lua 中的表是关联数组，也就是说，它们可以被任何值（nil 除外）索引，并且可以保存任何类型的值。 此外，它们是动态的，因为当数据添加到它们时它们可能会增长（通过为迄今为止不存在的字段分配一个值）并在从中删除数据时收缩（通过将 nil 分配给一个字段）。
与许多其他脚本语言不同，Lua 没有数组类型。 数组表示为带有整数键的表。 将表用于数组给语言带来了好处。 最主要的是简单：Lua 不需要两组不同的运算符来操作表和数组。 此外，程序员不必在两种表示之间进行选择。 稀疏数组的实现在 Lua 中很简单。 例如，在 Perl 中，如果您尝试运行 $a[1000000000]=1; 程序，可能会耗尽内存，因为它会触发创建一个包含 10 亿个元素的数组。 等效的 Lua 程序 a={[1000000000]=1} 创建一个包含单个条目的表。
在 Lua 4.0 之前，table被严格地实现为哈希表：所有对都被显式存储。 Lua 5.0 带来了一种新算法来优化表作为数组的使用：它通过不存储键并将值存储在实际数组中来优化具有整数键的对。更准确地说，在 Lua 5.0 中，table被实现为混合数据结构：它们包含一个散列部分和一个数组部分。图 2 显示了一个表的可能配置，其中包含“x”→9.3、1→100、2→200、3→300 对。注意右边的数组部分：它不存储整数键。这种划分只是在较低的实施级别上进行的；对表字段的访问是透明的，甚至对虚拟机也是如此。表根据它们的内容自动和动态地调整它们的两个部分：数组部分尝试存储与从 1 到某个限制 n 的整数键对应的值。与非整数键或数组范围外的整数键对应的值存储在哈希部分中。
当table需要增长时，Lua 会重新计算其散列部分和数组部分的大小。 任何部分都可能是空的。 数组部分的计算大小是最大的 n 使得至少有一半的 1 和 n 之间的槽在使用中（以避免在稀疏数组中浪费空间）并且在 n/2 + 1 和 n 之间至少有一个已使用的槽 （避免在 n/2 时使用大小 n）。 在计算出新的尺寸后，Lua 会创建新的部分并将旧部分的元素重新插入到新部分中。 例如，假设 a 是一个空表； 它的数组部分和散列部分的大小都为零。 如果我们执行 a[1]=v，表需要增长以容纳新键。 Lua 将选择 n = 1 作为新数组部分的大小（单个条目 1 → v）。 哈希部分将保持为空。
这种混合方案有两个优点。 首先，使用整数键访问值更快，因为不需要散列。 其次，更重要的是，如果数组部分存储在散列部分中，它所占用的内存大约是其一半，因为键在数组部分中是隐式的，但在散列部分中是显式的。 因此，如果table被用作数组，只要它的整数键是密集的，它就会作为数组执行。 此外，没有为哈希部分支付内存或时间损失，因为它甚至不存在。 反之亦然：如果table被用作关联数组，而不是用作数组，则数组部分可能为空。 这些内存节省很重要，因为 Lua 程序创建许多小table是很常见的，例如当table用于实现对象时。
哈希部分混合使用链式散点表和 Brent 的变体 [3]。 这些table的一个主要不变量是，如果一个元素不在其主要位置（即由其散列值给出的原始位置），则碰撞元素在其自己的主要位置。 换句话说，只有当两个元素具有相同的主位置（即该table大小的相同哈希值）时才会发生冲突。 没有二次碰撞。 正因为如此，这些表的负载因子可以是 100% 而不会有性能损失。
5 函数与闭包
当 Lua 编译一个函数时，它会生成一个原型，其中包含该函数的虚拟机指令、它的常量值（数字、文字字符串等）和一些调试信息。 在运行时，每当 Lua 执行 function...end 表达式时，它都会创建一个新的闭包。 每个闭包都有一个对其相应原型的引用，一个对其环境的引用（一个在其中查找全局变量的表），以及一个对 upvalue 的引用数组，用于访问外部局部变量。
词法作用域与第一类值函数的结合为访问外部局部变量带来了众所周知的困难。 考虑图 3 中的示例。当 add2 被调用时，它的主体访问外部局部变量 x（Lua 中的函数参数是局部变量）。 但是，在调用 add2 时，创建 add2 的函数 add 已经返回。 如果 x 在堆栈中创建，则其堆栈槽将不再存在。
大多数过程语言通过限制词法范围（例如 Python）、不提供一流函数（例如 Pascal）或两者（例如 C）来避免这个问题。 函数式语言没有这些限制。 对诸如 Scheme 和 ML 之类的非纯函数式语言的研究已经创造了关于闭包编译技术的大量知识。3然而，这些工作并没有试图限制编译器的复杂性 . 例如，仅 Bigloo 的控制流分析，一个优化器 Scheme 编译器 ，就比整个 Lua 实现大十倍以上：Bigloo 2.6f 的模块 Cfa 的源代码有 106,350 行，而Lua 5.0核心代码的则为 10,155 行。 如第 2 节所述，Lua 需要更简单的东西。
Lua 使用一种称为 upvalue 的结构来实现闭包。 通过upvalue 间接访问任何外部局部变量。 upvalue 最初指向变量所在的堆栈槽（图 4，左）。 当变量超出范围时，它会迁移到 upvalue 本身内部的一个槽中（图 4，右）。 由于访问是通过 upvalue 中的指针间接进行的，因此这种迁移对于读取或写入变量的任何代码都是透明的。 与其内部函数不同，声明变量的函数在访问它自己的局部变量时访问它：直接在堆栈中。
通过为每个变量最多创建一个 upvalue 并根据需要重用它，可以在闭包之间正确共享可变状态。 为了确保这种唯一性，Lua 保留了一个链表，其中包含一个堆栈（图 4 中的挂起 vars 列表）的所有打开的 upvalues（即那些仍然指向堆栈的值）。 当 Lua 创建一个新的闭包时，它会遍历它所有的外部局部变量。 对于每一个，如果它可以在列表中找到一个开放的 upvalue，它就会重用那个 upvalue。 否则，Lua 会创建一个新的 upvalue 并将其链接到列表中。 请注意，列表搜索通常只探测几个节点，因为对于嵌套函数使用的每个局部变量，列表最多包含一个条目。 一旦关闭的 upvalue 不再被任何闭包引用，它最终会被垃圾回收。
函数可以访问不属于其直接封闭函数但属于外部函数的外部局部变量。 在这种情况下，即使在创建闭包时，该变量也可能不再存在于堆栈中。 Lua 通过使用扁平闭包解决了这种情况。 使用平面闭包，每当函数访问外部变量不是其封闭函数的局部变量时，该变量也会进入封闭函数的闭包。 因此，当一个函数被实例化时，所有进入其闭包的变量要么在封闭函数的堆栈中，要么在封闭函数的闭包中。
6 Threads and Coroutines
从 5.0 版本开始，Lua 实现了非对称协程（也称为半对称协程或半协程）。 Lua 标准库中的三个函数支持这些协程：create、resume 和 yield。 （这些函数位于协程命名空间中。） create 函数接收一个“main”函数并使用该函数创建一个新的协程。 它返回一个代表该协程的thread类型值。 （与 Lua 中的所有值一样，协程是第一类值。）resume 函数（重新）开始执行给定的协程，调用其主函数。 yield 函数暂停正在运行的协程的执行，并将控制权返回给恢复该协程的调用。
从概念上讲，每个协程都有自己的堆栈。 （具体来说，每个协程都有两个堆栈，我们将在第 7 节中讨论，但我们可以将它们视为单个抽象堆栈。）Lua 中的协程是堆栈的，从某种意义上说，我们可以从任意数量的嵌套中挂起协程 调用。 解释器只是将整个堆栈放在一边供以后使用，并继续在另一个堆栈上运行。 程序可以随意重启任何挂起的协程。 垃圾收集器收集其协程不再可访问的堆栈。
堆栈性和第一类值状态的结合使得在 Lua 中实现的协程相当于一次性延续。 因此，它们允许程序员实现多种高级控制机制，例如协作多线程、生成器、对称协程、回溯等。
在 Lua 中实现协程的一个关键点是解释器不能使用其内部的 C 堆栈来实现解释代码中的调用。 （Python 社区将遵循该限制的解释器称为无堆栈解释器。）当主解释器循环执行调用操作时，它会在堆栈中创建一个新槽，调整几个指针，并使用以下指令继续循环被调用的函数。 类似地，返回操作移除顶部堆栈槽，调整指针，并使用调用函数的指令继续循环。 并非巧合，这正是真正的 CPU 执行函数调用时所做的。
然而，当解释器执行 resume 时，它会递归调用主解释器函数。 这个新的调用负责执行恢复的协程，使用协程堆栈来执行调用和返回。 当这个新循环执行一个 yield 时，它返回到之前的解释器调用，将所有挂起的调用留在协程堆栈中。 换句话说，Lua 使用 C 堆栈来跟踪任何给定时间的活动协程堆栈。 每个 yield 返回到前一个解释器循环，也就是调用相应 resume 的那个循环。
在某些语言中实现协程的一个困难来源是如何处理对外部局部变量的引用。 因为在协程中运行的函数可能是在另一个协程中创建的，所以它可能会引用不同堆栈中的变量。 这导致了一些作者所说的仙人掌结构。 正如我们在第 5 节中讨论的那样，使用平面闭包完全避免了这个问题。
