The Implementation of Lua 5.0
1 Introduct
Lua was born in an academic laboratory as a tool for in-house software development but somehow was adopted by several industrial projects around the world and is now widely used in the game industry.
How do we account for this widespread use of Lua? We believe that the answer lies in our design and implementation goals: to provide an embeddable scripting language that is simple, efficient, portable and ligthweight. These have been our main goals since the birth of Lua in 1993 and they have been respected during its evolution. These features, plus the fact that Lua has been designed from the start to be embedded into larger application, account for its early adoption by the industry.
Widespread use generates demand for language feature. Several features of Lua have been motivated by industrial needs and user feedback. Important examples are the introduction of coroutines in Lua 5.0 and the implementation of incremental gargage collection in the upcoming Lua 5.1. Both features are specially important for games.
In this paper, we discuss the main novelties of the implementation of Lua 5.0, compared to Lua 4.0:
Register-based virtual machine: Traditionally, most virtual machines intended for actual execution are stack based, a trend that started with Pascals Pmachine and continues today with Javas JVM and Microsofts .Net environment. Currently, however, there has been a growing interest in registerbased virtual machines (for instance, the planned new virtual machine for Perl 6 (Parrot) will be register based). As far as we know, the virtual machine of Lua 5.0 is the first register-based virtual machine to have a wide use. This virtual machine is presented in Section 7.
New algorithm for optimizing tables used as arrays: Unlike other scripting languages, Lua does not offer an array type. Instead, Lua programmers use regular tables with integer indices to implement arrays. Lua 5.0 uses a new algorithm that detects whether tables are being used as arrays and automatically stores the values associated to numeric indices in an actual array, instead of adding them to the hash table. This algorithm is discussed in Section 4.
The implementation of closures: Lua 5.0 supports first-class functions with lexical scoping. This mechanism poses a well-known difficulty for languages that use an array-based stack to store activation records. Lua uses a novel approach to function closures that keeps local variables in the (array-based) stack and only moves them to the heap if they go out of scope while being referred by nested functions. The implementation of closures is discussed in Section 5.
The addition of coroutines: Lua 5.0 introduced coroutines in the language. Although the implementation of coroutines is more or less traditional, we present a short overview in Section 6 for completeness.
2 An Overview of Luas Design and Implementation
As mentioned in the introduction, the goals in our implementation of Lua are:
Simplicity:We seek the simplest language we can afford and the simplest C code that implements this language. This implies a simple syntax with a small number of language constructs, not far from the tradition.
Effciency: We seek fast compilation and fast execution of Lua programs. This implies a fast, smart, one-pass compiler and a fast virtual machine.
Portability: We want Lua to run on as many platforms as possible. We want to be able to compile the Lua core unmodified everywhere and to run Lua programs unmodified on every platform that has a suitable Lua interpreter. This implies a clean ANSI C implementation with special attention to portability issues, such as avoiding dark corners of C and its libraries, and ensuring that it also compiles cleanly as C . We seek warning-free compilations.
Embeddability: Lua is an extension language; it is designed to provide scripting facilities to larger programs. This and the other goals imply the existence of a C API that is simple and powerful, but which relies mostly on built-in C types.
Low embedding cost:We want it to be easy to add Lua to an application without bloating it. This implies tight C code and a small Lua core, with extensions being added as user libraries.
These goals are somewhat conficting. For instance, Lua is frequently used as a data-description language, for storing and loading configuration files and sometimes quite large databases (Lua programs with a few megabytes are not uncommon). This implies that we need a fast Lua compiler. On the other hand, we want Lua programs to execute fast. This implies a smart compiler, one that generates good code for the virtual machine. So, the implementation of the Lua compiler has to balance between these two requirements. However, the compiler cannot be too large; otherwise it would bloat the whole package. Currently the compiler accounts for approximately 30% of the size of the Lua core. For memory-limited applications, such as embedded systems, it is possible to embed Lua without the compiler. Lua programs are then precompiled off-line and loaded at run time by a tiny module (which is also fast because it loads binary files).
Lua uses a hand-written scanner and a hand-written recursive descent parser. Until version 3.0, Lua used a parser produced by yacc, which proved a valuable tool when the languages syntax was less stable. However, the hand-written parser is smaller, more effcient, more portable, and fully reentrant. It also provides better error messages.
The Lua compiler uses no intermediate representation. It emits instructions for the virtual machine 'on the fly' as it parses a program. Nevertheless, it does perform some optimizations. For instance, it delays the generation of code for base expressions like variables and constants. When it parses such expressions, it gener
剩余内容已隐藏，支付完成后下载完整资料
Lua 5.0的实现
1 介绍
Lua诞生于一个学术实验室，当时是作为一个内部软件开发工具的，但逐渐被移植到了全世界的各个行业的工程中，而且现在广泛的用于游戏行业。
我们该如何解释Lua的广泛应用？我们相信答案在我们的设计和实现目标中：提供一个可嵌入的脚本语言，她简单、高效、可移植和轻量级。这些目标是自1993年Lua诞生以来我们的主要目标，而且在她的演变中得到了认可。这些特性，以及Lua从一开始就设计成可嵌入到更大的应用程序中，这一特性使得她早早地得到了行业的认可。
广泛的使用产生了对语言特性的需求。Lua的一些特性是由行业需求和用户反馈驱动的。重点的例子有Lua 5.0对协程的引入和即将发布的Lua 5.1对垃圾收集的增加。这两个特性对游戏来说是极其重要的。
在这篇论文中，我们讨论了与Lua 4.0 相比 Lua 5.0实现上的主要优点：
基于寄存器的虚拟机：通常，大多数虚拟机为了执行都是基于栈的，一个从Pascal的Pmachine持续到今天的Java的JVM和微软的.Net环境都是这个趋势。然而，现在对基于寄存器的虚拟机的兴趣在增加（例如，计划中的Perl 6（Parrot）将是基于寄存器的）。据我们了解，Lua 5.0是第一个广泛应用的基于寄存器的虚拟机。这个虚拟机将在第7章节讲解。
新算法对tables用于数组时的优化：与其他脚本语言不同的是，Lua 没有提供数组类型。然而，Lua 程序员使用普通表配合整数下标来实现数组。Lua 5.0使用一个新的算法来检查tables是否用于数组，并且在真正的数组中自动存储关联到整数下标的值，而不是将他们添加到Hash表。这个算法将在第4章节讨论。
闭包的实现：Lua 5.0 从语法上支持第一类型函数。这个机制对于使用基于数组的栈来存储活动记录的语言来说，是一个众所周知的难题。Lua使用了一个新颖的解决方案来实现闭包的功能，这些闭包将局部变量保存在基于数组的栈上，并且只在他们超出作用域，同时又被包含的函数引用时，才会被移到堆上。闭包的实现将会在第5章节讨论。
协程的加入：Lua 5.0 引入了协程。尽管协程的实现有些传统，我们在第6章节进行概述来保证文章的完整性。
其他章节覆盖或给出了讨论的背景资料。在第2章节，我们给出了Lua的设计目标概述，并且说明这些目标如何驱动它的实现。在第3章节，我们描述了Lua如何表示它的值。尽管这个表示方法并无新意，但其他部分需要这些内容。最后，在第8章节，我们展示了一个小的性能测试以及给出一些结论。
2 Lua设计与实现概述
在介绍（第1章节）中，我们提到对于Lua，我们的实现目标是：
简单：我们寻求能够提供的最简单的语言以及该语言的最简单C代码实现。这意味着一个简单语法附带少数的语言构件，与传统语言实现相差不大。
高效：我们寻求Lua程序的快速编译与快速执行。这意味着Lua有一个快速、智能、单次的编译器和一个快速的虚拟机。
可移植：我们希望Lua尽可能运行在更多的平台上。我们希望能够在任何环境编译Lua核心而不需要修改Lua源代码，希望能够在拥有配套Lua解释器的每个平台运行Lua程序而不需要修改。这意味着Lua是一个纯净的ANSI C实现，同时对移植性问题（如避免C和C库的死角）特殊关注，并且保证作为C 编译时也是纯净的。我们寻求没有警告的编译。
可嵌入：Lua是一个扩展语言；它被设计成为更大的程序提供脚本基础设施。这个目标和其他目标意味着存在一些简单和强大的C API，而它们大部分依赖内置C类型。
低嵌入成本：我们希望添加Lua到应用程序是简单的，Lua内部不消耗太多内存。这意味着Lua的实现是紧凑的C代码和小的Lua内核，使用扩展来添加用户库。
这些目标有些互相冲突。例如，Lua被频繁的用作数据描述语言，来存储和加载配置文件，有时这些配置文件是较大的数据库（Lua程序使用几MB并非不常见）。这意味着，我们需要一个快速的Lua编译器。另一方面，我们希望Lua程序执行快速。这意味着，我们需要一个智能的编译器，它能为虚拟机产生高质量的代码。所以，Lua编译器的实现需要在这两个需求上做平衡。然而，编译器不能太大；否则，它的所有包都会变大。当前Lua编译器大约占Lua核心大小的30%。对于内存受限的应用程序，如嵌入式系统，嵌入Lua而不需要编译器是可行的。Lua程序将会离线预编译，在运行时由一个极小的模块加载（因为这个模块加载二进制文件，所以它也很快）。
Lua使用一个手写的扫描器和一个手写的递归下降解析器。3.0版以前，Lua使用一个由yacc产生的解析器。当语言的语法不太稳定时，yacc提供了一个有用的工具。然而，手写解析器更小，更高效，移植性更强，并且是完全可重入的。同时也提供了更好的错误信息。
Lua编译器不使用中间表示。它在解析程序时直接生成虚拟机指令。然而，它也做了一些优化。例如，它为基本表达式如变量和常量延迟生成指令。当它解析这些表达式时，它不生成任何代码；相反，它使用一个简单的结构表示他们表达式。因此，检查一个给定的指令的操作数是常量还是局部变量就很容易，并且在指令中直接使用这些值，从而避免了不必要和昂贵的内存移动（参见第3章节）。
为了跨多种C编译器和平台移植，Lua不能使用常见的解释器使用的一些技巧，例如直接线程化的代码。相对地，它使用了一个标准的while-switch分发循环。同时，某些地方的C代码看上去过于复杂，但是，这里的复杂性是为了保证移植性。这些年，随着Lua在许多不同的平台（包括一些64位平台和一些16位平台）上不同C编译器上被成编译，Lua实现代码的移植性在稳步提升。
我们认为，我们达到了我们的设计和实现目标。Lua是一个高度可移植的语言：它运行在任何拥有ANSI C编译器的机器上，包括从嵌入式系统到主要框架。Lua是真正的轻量级：例如，在Linux上它是一个独立的解释器，完整包含所有的标准库，只占用不到150KB磁盘空间；核心小于100KB。Lua是高效的：独立的性能测试表明，Lua的实现是脚本语言（即，解释和动态类型语言）中最快的语言实现之一。我们还认为，Lua是一个简单的语言，与Pascal的语法相似并且与Scheme的语义相似，但这种观点是主观的。
3 值的表示
Lua是一门动态类型语言：类型和值绑定在一起，而不是和变量绑定在一起。Lua用于8种基本类型：nil，boolean，number，string，table，function，userdata，还有thread。Nil是一个标记类型，只有一个值，也叫做nil。Boolean值是通常的true和false。Numbers是双精度浮点数，与C语言中的double类型一致，但是将Lua编译成使用float或long来代替（double）也是很容易的。（一些游戏控制台和小机器缺乏对double的硬件支持。）Strings是字节数组，包含一个明确的大小，而且可以容纳任意二进制数据，包含数据中间嵌入0的二进制数据。Tables是关联数组，可以被任意值（除了nil）索引，并且可以包含任意值。Functions可以是Lua函数也可以是C函数，（要求这些）C函数是按照Lua虚拟机的接口协议来编写的。Userdata是指向用户内存的指针，而且有两种形式：重型，内存块是由Lua分配的，并且交由gc处理内存回收，轻型，内存块是由用户分配和释放的。最后，threads表示协程。所有类型的值都是第一类型值：我们可以将他们存储在全局变量、局部变量和表的单元中，将他们作为参数传给函数，从函数返回，等等。
Lua用带标记的联合来表示值，也即，通过键值对（t;v）来表示，其中，t是一个表示值v的类型的整数。这个联合是一个实现Lua类型的C语言联合（union 类型）。Nil只有一个值。Booleans和numbers作为'未装箱'值来实现的：v直接使用联合来表示这些类型的值。这意味着，这个联合必须拥有足够的空间来存储double。Strings，tables，functions，threads，以及userdata的值通过引用来实现：v包含执行实现这些值的指针。这些结构拥有一个通用头部，用来保存垃圾收集需要的信息。结构的其他部分是每个类型特有的。
图1 Lua值实现
图1 展示了Lua值实现的概况。TObject是这个实现中主要的结构：它表示上述带标记的联合（t;v）。Value是实现值的联合。类型nil的值并没有明确的在union中表示，因为标记就足以标示它们。union中的域n是给numbers（默认情况下，lua_Number是double）用的。域b是给booleans用的。域p是给轻型userdata用的。域gc是给其他类型用的（strings，tables，functions，重型userdata，以及threads），这些都由垃圾收集来释放内存。
使用带标记的联合来表示Lua值的一个结果是，拷贝值有点昂贵：在一个32位的机器上使用64位doubles，TObject的大小是12字节（或者16字节，如果double是8字节对齐的话），因此拷贝一个值需要拷贝3（或4）个机器字。然而，使用ANSI C实现一个更好的值表示方式是困难的。一些动态类型语言（如，Smalltalk8的原始实现）使用每个指针的备用位来存储值的类型。这种技巧在大多数机器上凑效，因为，由于对齐，指针的最后2到3位总是0，从而可以用于其他目的。然而，这种技术既不具备可移植性，也不具备ANSI C可实现性。C标准甚至没有保证一个指针符合任何整型，从而没有标准方法来完成指针上的位操作。
为了减少值的大小，另一个选择是保存明确的标记，但是避免将一个double放入联合中。例如，所有的numbers必须用堆分配的对象来表示，就像strings。（Python使用这种技术，所不同的是它在内存池预分配了一些小整数值。）然而，这种重新表示会使语言变得很慢。另外，整数值本该作为“未装箱”值出现，直接在联合中，而浮点数应该在堆上。这种方案会激增所有算术运算实现的复杂性。
像早期的解释语言一样，如Snobol和Icon，Lua 使用hash表内化了strings：它使用每个string的单一拷贝而没有使用复制。此外，strings是不可变的：一旦被内化，一个string就不能修改。string的Hash值由一个简单的表达式计算，这个表达式混合了位处理和算术运算，从而使所有的位得到处理。当string内化时，Hash值得到保存，所以允许高速string比较和table索引。如果string太长，hash函数不会计算string的所有字节。这允许长string的快速hash。避免处理长string时的性能损失是非常重要的，因为这在Lua中很常见。例如，Lua中常见的处理文件的方式，是通过将他们完全读入内存，保存在单个的长string中。
4 表
表是Lua中主要的——事实上，是唯一的——数据结构实现机制。表不仅在语言上扮演关键角色，在实现上也是如此。在Lua中，花在一个好的表实现上的努力是值得肯定的，因为表用于一些内部任务，这些任务毫无疑问与性能有关。这会保证实现小巧。反过来，其他数据结构机制的缺乏，也给表的高效实现带来了压力。
在Lua中，表是关联数组，也就是说，他们可以被任意值（除了nil）索引，并且可以存储任意类型的值。更重要的是，当数据添加（通过对不存在的域赋值）以及数据删除（通过对一个域赋值nil）时，表可以扩张和收缩，他们是动态的。
与其他脚本语言不同的是，Lua没有数组类型。数组通过表和整型的keys来表示。使用tables来表示数组为Lua带来了好处。最主要的一个就是简单：Lua不需要两个不同操作来操纵tables和数组。进而，程序员不需要在两种表示间做选择。Lua中稀疏数组的实现是不值一提的。在Perl中，例如，当你运行
时，可能会内存不够用，因为它将触发创建一个拥有10亿个元素的数组。相同的Lua程序
创建一个只包含一个项的表。
直到Lua 4.0，tables一直是实现成严格的hash表：所有的键值对都是明确存储的。Lua 5.0引入了一个新算法来优化使用表来表示数组：它通过不存储键而在一个真正的数组中存储值，来优化拥有整型键的键值对。更准确的说，在Lua 5.0中，表实现成混合数据结构：他们包含一个hash部分和一个数组部分。图2展示了一个可能的设置，这个表拥有键值对'x' -gt; 9:3, 1 -gt; 100, 2 -gt; 200, 3 -gt; 300。注意右边的数组部分：它并没有存储整数keys。这种分离仅仅是在底层实现的；访问table的域是透明的，甚至对于虚拟机（来说，也是如此）。表根据他们的内容，自动地、动态地适配这两部分：数组部分尝试存储key为1到某个有限的整数n相关的值。非整数key或整数key超出数组大小的值将会存储在hash部分。
图2 一张Lua表
当一个table需要扩展时，Lua重新计算它的hash部分和数组部分。每个部分可能为空。数组部分的计算就是计算
1、使得从1到n至少一半的数组位置被使用时的最大n（为了避免稀疏数组浪费内存）而且
2、使得在n=2 1到n之间，至少有一个位置被使用（避免当n=2时重新计算n）。
新的大小计算后，Lua创建新的部分，并将老部分中的元素重新插入新部分。例如，假设一个空表；数组部分和hash部分大小都为0。如果我们执行
a[1]=v,
这个表就要扩展来匹配新的key。Lua将会选择n=1作为新的数组部分（只有一项 1-gt;v）。hash部分仍然为空。
<p
剩余内容已隐藏，支付完成后下载完整资料</p
资料编号：[499667]，资料为PDF文档或Word文档，PDF文档可免费转换为Word
以上是毕业论文外文翻译，课题毕业论文、任务书、文献综述、开题报告、程序设计、图纸设计等资料可联系客服协助查找。
