Lua1.0-应用程序扩展语言的设计与实现

为了可能的版权问题，特此说明《The design and implementation of a language for extendingapplications》版权属于原作者们，我翻译的此文档，网友最好加上原始链接再转载，但不强求，因为我不敢保证我翻译，表达的准确性，正确性。这只是用中文记录了当时对内容理解，同时也只翻译了我感兴趣的东西。有确实需要的人们可以去读原文进行自己的理解。

《The design andimplementation of a language for extending applications》我分为上中下三部分进行翻译发布。同时也欢迎专业人士对翻译不对的专有词进行指正，谢谢！！！

摘要

我们在本文中描述了Lua的设计与实现。Lua是一个简单而强大的应用程序扩展语言。虽然Lua是一个编程语言，但是它还具有数据描述能力，并且在产品中得到广泛应用。例如用户配置、一般的数据入口、用户接口描述、应用程序对象描述、结构化的图像文件存储。（user configuration，data entry，user interfaces，application objects，structured graphical metafiles）

简介

定制应用程序的需求越来越多，随着应用程序变得越来越复杂，通过简单的参数进行定制应用程序变得不可能：用户现在要在应用执行的时刻产生配置策略，用户还要编写宏和脚本来增加生产力（Ryan 1990）。因此现今的稍大些的应用程序都为最终用户可编程提供配置语言和脚本语言。这些语言虽然都很简单，但每个语言都有自己的特殊语法，导致用户不得不学习，开发人员不得不学习使用各种新语言工具进行设计，调试。

有关我们第一个私有脚本语言经验，来自于应用程序的data entry。这是一个非常简单的声明式语言（declarative language）（Figueiredo-Souza-Gattass-Coelho 1992）。（Data entry 是用户定义的动作集合，由于对于所有的应用程序来说，编码前进行充分的确认测试几乎不能，因此非常需要这样的动作定义。）当用户要求在这个语言上增加更强大的功能时，我们决定需要一个更通用的方法，并且开始进行通用的嵌入语言（embedded language）设计。当时我们为了描述数据（data description），在另一个应用程序中正在开发新的声明式语言。因此我们决定将2个语言合并为一个，将Lua设计成具有数据描述能力的编程语言。自此Lua得到快速的成长，并且在多个工业项目上得到应用。

这篇文章讲述了Lua的设计决策，以及Lua实现的细节。

扩展语言（Extension languages）

经过实践验证，应用程序扩展语言的作用是一种重要的设计技术。它使应用程序设计变得简单，但同时却为用户提供配置功能。因为很多扩展语言简单的只针对某一个任务，这样的语言叫做little languages（Bentley 1986 Valdes 1991），这个小是相对于当前编写应用的主流编程语言来说。但现在这样的差别越来越不明显，因为几个应用程序的主要部分就是使用扩展语言编写的。扩展语言出现了如下几种类型：

配置语言（configuration languages）用于选择参数，通常是从命令行获取参数列表或者从配置文件读取变量值。DOS的sys配置文件，MS Windows的ini文件，X11的资源文件，Motif的UIL文件等等都属于配置语言。

脚本语言（scripting languages）用于工作自动化，有限的流程控制，例如DOS的bat批处理文件，或者各种各样的Unix Shell。

宏语言（macro languages）也用于工作自动化，但是通常是无流程控制，只是一系列顺序执行的简单动作。

嵌入语言（embedded languages）用于扩展应用程序满足用户定制功能。这样的语言一般由应用程序提供。这些语言通常功能十分强大。而相对于LISP，C这样的主流编程语言，他们又非常简单。嵌入语言与独立语言（standalonelanguages）有哪些区别？嵌入语言只能在宿主程序里工作，由宿主程序调用嵌入语言。此外，宿主程序能够为嵌入语言提供针对专业领域的扩展。因此可以为一些特殊需求，专门定制创建一个嵌入语言版本，并且提供更高层次的抽象。为此，一个嵌入语言要有自己的编程语法（syntax），还要有应用程序（宿主程序）编程接口，用于与宿主程序联系。

所以，简单的扩展语言只能提供简单编程，为宿主程序提供顺序的执行动作。而在嵌入语言中，嵌入语言与宿主程序有2种通信方式，应用程序实现者可以使用嵌入式语言编程，反之应用程序的使用者可以独立的使用嵌入语言编程。

LISP已经是非常受欢迎的扩展语言，它的语法简单，容易解析，本身具有扩展性（Beckman1991;Nahaboo）。
例如，Emacs主要部件都是用LISP写的，后来一些其他的文本编辑器也采用同样的方法实现。但是LISP用于客户定制时，并不能叫做用户友好的编程语言。C和shell语言也都不是。这些语言的语法都复杂难懂，不常见。

Lua设计的一个基本原则就是要有一个简洁，熟悉的语法。我们很快解决这个问题，因为我们采用了简单的类Pascal语法。我们没有使用基于LISP或者C的语法，因为这样的语法增加外行或者没有编程经验的人学习/使用成本。因此，Lua首先是一个过程式语言（procedural language），另外Lua也是具有数据描述（data description）能力的语言，这更增加了Lua的表现能力。

通过《应用程序扩展语言的设计与实现》，我了解了扩展语言分了几种类型：配置语言，脚本语言，宏语言，嵌入语言。而Lua是嵌入语言，但同时具有配置语言，脚本语言能力，Lua的语法采用了类Pascal语法。

Lua的思想

Lua是一个具有过程式（procedural）编程和数据描述能力的嵌入式编程语言。作为一个嵌入语言，Lua没有“main”函数，只能嵌入到宿主程序（host）运行。Lua作为一个库文件，链接到宿主程序中。宿主程序可以调用接口执行lua代码获取或修改lua的变量，并且可以注册C函数给Lua代码调用。

因此我们可以通过一个共享的语法框架，创建一个定制化的编程语言，将Lua扩展后就可以处理不同领域的事情（Beckman 1991）。

这部分主要简单描述了Lua的主要概念。代码案例及语法定义可在《Lua参考手册》（Ierusalimschy-Figueiredo-Celes1994）上面找到。

语法Syntax

前面提到过，我们确定将Lua设计为一个简洁，熟悉的语法。因此Lua支持一个常见的语句，含蓄但明确的语句块终止结构。

传统的语句包括简单的assignment，例如控制结构while-do-end，repeat-until，if-then-elseif-else-end以及function

非传统的语句包括 multiple assignment：局部变量声明可以放在一个语句块的任意位置，table的建立，可以包含用户要求的validationfunctions。

此外，Lua的函数可以接受可变参数，也可以返回多个值，这样当需要返回多个结果时，可以不需要通过函数参数返回。

环境与模块Environment and modules

Lua里的所有可执行语句都保存在一个全局环境里（globalenvironment）。宿主程序开始时初始化全局环境，并持续到宿主程序结束。全局环境保存了所有的全局变量（global variables），函数。Lua代码可以修改全局环境，宿主程序也可以修改。

Lua的执行单元（unit）叫做模块（module）。一个模块可以包含多个语句和函数定义，可以存储在一个文件里，也可以存储在宿主程序的一个字符串里。

当要执行一个模块时，首先所有的函数和语句都会被编译，同时函数也会加入到全局环境，然后按顺序执行语句。一个模块对全局环境的修改是永久的，即使这个模块执行结束了。这些修改包括全局变量和新的函数。实际上一个函数定义就是一个assignment to a global variable。

数据类型和变量Data types and variables

Lua是动态类型语言，变量没有类型，只有变量的值有类型。所有的值都有他们自己的类型信息。因此在Lua里没有类型定义。

Lua有垃圾回收机制（garbage collection），它能够保留那些在使用的值，丢弃那些没有在使用的值。这样就不需要内存分配与管理。Lua里有7种基本数据类型：

1. nil 一个叫做nil的类型，这个类型只有一个值nil
2. number 浮点数数字
3. string 字符数组
4. function 用户定义的函数
5. Cfunction 宿主程序提供的函数
6. userdata 指向宿主程序的数据空间
7. table 关联数组

Lua提供运行时字符串到数字的自动转换。任何对字符串的数学运算操作都会尝试用一般的转换规则把这个字符串转换成一个数字。相反，无论何时，一个数字需要作为字符串来使用时，数字都会以合理的格式转换为字符串。这样的特性非常有用，因为它编程简单，避免显示的转换函数。

全局变量（Global variables）不需要声明定义，只有局部变量（local variables）需要声明定义。如果一个变量没有显示的声明为local，这个变量等同于全局变量。局部变量可以放在语句块的任意位置。

由于给变量赋值前，变量的值是nil，因此Lua中没有未初始化的变量。因此对nil的有效操作就是赋值和相等测试。nil的这种特性不同于其他任何的值，因此如果在一个上下文中需要一个实际的数字进行数学运算时，使用了未赋值的变量，将引起执行错误警告：这个变量没有初始化。所以自动初始化变量为nil也是不被鼓励。

function在Lua里是first-class values ,Lua函数体被编译后，函数名作为变量名存储在全局变量里。Lua可以调用Lua写的函数，也可以调用C写的函数。C实现的函数有个专有类型Cfunction.

userdata类型允许任意类型的C指针存储在Lua变量里，对其有效操作就是赋值和相等测试

table类型用关联数组实现，关联数组的值可以通过数字和字符串2种方式进行索引。因此这个类型不仅可以用于表达一般的数组，还是可以表示记录集合。为了表达一个记录，Lua使用域名（fieldname）作为索引。Lua支持像a.name这样的语法糖(syntactic sugar)表示a["name"]。

关联数组是一个强大的语言创新。很多算法由于这个特性变得简单，因为语言本身已经提供搜索的算法和结构（Aho-Kerninghan-Weinberger 1988，Bentley 1988）。

例如 table[word] = table[word] + 1 不需要在列表里搜索word，就可以实现遍历计数功能。 但是现实工作中常需要一个按字母顺序排列（alphabetically）的报告，而通常在lua中table的目录是无序存放的。

有很多方法创建table,最简单的方法是类似于普通的数组: t = @()

这样的表达式将创建一个空的table，在上面的表达式中table的大小是可选项，也可以给一个初始值。 Lua中的table都是随需动态扩展的，与是否初始化大小并无关系。因此t[200]和t["day"]都是有效的。

有2种方式创建带数据内容的table，一个是列表方式@[]，一个是记录方式@{}。

t=@["red","green","blue",3]

与之等价的语句如下

t = @()

t[1] = "red"

t[2] = "green"

t[3] = "blue"

t[4] = 3

另外在创建列表和记录时，还可以table作为函数，如

t = @colors["red","green","blue","yellow"]

t =@employee{name="huangyuxi",age=32}

在table创建后，colors和employee就是2个用户函数了，我们可以调用它们。如上面的employee域的赋值可以这样实现

t = @()

t.name = huangyuxi

t.age =32

employee(t)

这样的表达式在lua里非常强大。

预定义函数和库Predefined functions and libraries

在Lua里预先定义了一些函数，这些函数很少，但是作用却不小。预定义函数具有如下功能：

1. 执行一个文件或字符串里的lua模块
2. 枚举table里的所有成员
3. 枚举所有全局变量
4. 类型查询和转换

库对于Lua语言来说不是必须的，但是却提供了些有用的接口供lua编程使用。因此库作为独立C模块提供出来，可以有选择的链接到宿主程序里。目前提供的库有字符串操作，算术函数，io等。

数据固化Persistence

在lua里枚举函数可以用于全局环境的固化。也可以写lua代码写lua代码，通过执行，存储所有的全局变量。

我们现在展示一些方法来存储，恢复在lua里使用的变量。

为了通过name存储数值，下面的代码就可以

function store(name，value)

write(name,..'=') -- write is a library function for output,'..'is the string concatenation operator

write_value(value) -- outputs a suitablerepresentation of a value based on its type

end

function write_value(value)

local t = type(value)

if t = 'nil' then write nil

elseif t = 'number' then write(value)

elseif t = 'string' then write('"'..value..'"')

end

end

保存一个table要稍微复杂一些。首先write_value要增加一个elseif t = 'table' then write_record(value)，假设table是一个records，table的值可以直接通过table的结构进行直接保存。

function write_record(t)

local i,v = next(t,nil) -- next enumerates the fields of t

write('@{') -- starts constructor

while i do

store(i,v)

i, v = next(t,i)

if i then write(', ') end

end

write('}') -- closes constructor

end

通过对这部分的理解，我了解了：

1 lua的设计思想

2 lua的流程控制while-do-end，repeat-until，if-then-elseif-else-end

3 lua函数参数为可变参数，返回值可以同时返回多个

4 lua执行一个模块，会改变全局环境，是永久性的改变

5 lua是动态类型语言，变量的类型至于变量的值有关系。

6 lua本身提供垃圾回收机制，编程不需要考虑内存分配

7 lua具有7个基本数据类型

8 lua有预定义函数，一个例子参见 Lua1.0使用与研究- globals.lua

9 lua库，可以自己扩展，本身提供的库有字符串操作，算术函数，io库，可以按需使用连接到宿主程序

10 文中提到一些代码后面我会做些验证，测试，重点table的使用；提到的垃圾回收也是测试验证的重点。

实现

扩展语言一般都是通过应用程序解释执行的。简单的扩展语言直接从源码解释执行，另一方面嵌入语言是编程语言，拥有复杂的语法（syntax）和语义（semantics）。

嵌入语言一个更有效的实现技术就是设计一个适合语言的虚拟机，将扩展程序编译为虚拟机的字节码，通过虚拟机仿真模拟解释字节码。(Betz 1988,1991;Franks 1991)。

我们为Lua的实现选择一个混合的架构，它比直接解释lua代码有如下优势：因为词法语法分析（lexical and syntactical）只做一遍，使用一个外部解析器，在实际嵌入前，能够发现简单的错误，缩短开发周期，执行速度快。

如果用一个外部编译器，为在字节码级别扩展程序提供可能，预先编译可以提高下载速度，安全的环境和更小的运行时间。

扩展语言可以通过标准工具（如lex和yacc）产生语法语义解析代码（Levine-Mason-Brown 1992）。尤其是在Unix环境，由于存在良好的编译器构造工具，产生了至少70种小语言。而Lua的实现使用yacc做语义分析器，一开始我们使用lex写语法分析器，经过实际项目的性能分析，我们发现这个模块在下载和执行扩展程序时消耗了一半的时间，后来我们直接用C重新写了这个模块，这个新的语法分析器速度比以前提高了2倍。

Lua虚拟机

在Lua实现中，我们使用了堆栈虚拟机（stack virtual machine）。这就意味着Lua里没有RAM（随机访问存储器），所有的临时的值和局部变量都保存在一个堆栈里。

此外，Lua里也没有通用寄存器（general purpose registers），只有用于控制堆栈和执行程序的专用控制寄存器（special control registers）这些寄存器有：栈的基址寄存器，栈顶寄存器和程序计数寄存器（base of stack,top of stack and program counter）。虚拟机顺序执行程序指令，这样的程序叫做字节码（bytecodes）。

程序的执行通过解释字节码来完成，每一个指令的操作对应到栈顶部分的操作。例如语句：a = b + f(c)

被编译成：

PUSHGLOBAL b

PUSHGLOBAL f

PUSHMARK

PUSHGLOBAL c

CALLFUNC

ADJUST 2

ADD

STOREGLOBAL a

Lua虚拟机大约有60个指令，因此它可以用8bit字节编码。

许多指令是不需要参数的，如ADD，这些指令直接在栈上获取正确的一个字节进行编译。其他指令需要参数，并且超过一个字节，如PUSHGLOBAL，STOREGLOBAL。有些体系结构通过NOP指令进行对齐边界的填充，在这样的架构上，无论这些参数采用1个字节，2个字节还是4个字节，都会面临对齐问题。有很多指令只是为了优化而存在的，例如有一种PUSH指令，只将数字作为参数，将这个数字压入栈，但是还有单字节优化版本，只用于将一般的值压入栈，如0和1。因此，我们有PUSHNIL，PUSH0，PUSH1，PUSH2等。这样的优化指令减少了编译后字节码的空间，同时解释指令的时间也减少了。

Lua支持可变参数（multiple assignment），以及函数支持多个返回值(multiple return values)，因此有时数值列表必须在运行时进行调整。考虑到可变参数长度，如果比我们需要的数值多，多余的数值将被抛弃，如果比我们需要的数值少，数值列表使用多个nil扩展到我们需要的个数。这样的调整通过ADJUST指令在栈上进行调整。

虽然多返回值，可变参数是Lua的强大功能，但是这也正是Lua解释器，编译器复杂的源头。由于没有函数类型声明，编译器不知道一个函数会返回多少参数，因此调整必须在运行时执行。同样编译器不知道一个函数有多少参数，因为参数个数在运行时是变化的，参数列表在PUSHMARK和CALLFUNC指令之间。

扩展Lua的一个方式就是通过宿主程序分配字节码来实现，虽然这个策略（strategy）对于解释器来说非常简单，但这样做的缺点是为Lua增加外部扩展程序不足200个，因为Lua有8bit字节码，而且已经使用了约60个用于原始指令集。我们选择了宿主程序通过注册外部函数，像执行Lua原生函数一样执行这些外部函数。因此就有了单一指令CALLFUNC，解释器根据被调用的函数类型决定做什么。

Franks推荐了一个不同的策略，宿主程序的所有扩展函数都可以在嵌入语言里调用，也不需要明确的注册。这个动作通过读取，解释链接器产生的map文件自动完成。这个方案对于应用程序开发人员非常方便，但是不便的是需要依赖格式化的map文件和使用操作系统的重定位功能（Franks使用了DOS的一个特殊编译器）。

内部数据结构

就像前面说的，Lua里的变量是无类型的，只有值有类型。因此值的结构里有2个成员，一个type，一个union包含实际的值。这样的结构出现在栈里，也出现在符号表（symbol table）里。符号表保存了所有的全局符号。

Numbers直接存在union里，Strings串保存在独立的数组里，function的值保存在一个指向字节码数组的指针里，Cfunction类型的值包含一个由宿主程序提供的实际的C函数指针。userdata类型的值与Cfunction类型的值一样。

Tables值的保存由哈希表实现(hash tables)(collisions handled by separate chaining),如果在创建一个table时指定大小，对应的哈希表的大小就是用指定的大小。因此根据预期的table目录数目确定table的尺寸，发生冲突的可能就越小，而且通过index定位效果也好。另外，如果table用做数字数组，在创建时设定正确的尺寸，保证不会发生冲突。

Lua里所有的内部数据结构都是动态分配数组。当在这些数组中没有足够的空闲slots时，垃圾回收自动完成。垃圾回收采用标记-清除（mark-sweep）算法。如果因为所有大的值都在引用致使没有重新找到空间，就重新分配一个数组，这个数组大小为原来数组的2倍。

由于避免了显式的内存管理，垃圾回收对于编程人员是非常方便的。当Lua作为一个独立的语言时，垃圾回收机制是个优点。但是Lua主要是作为嵌入语言，当Lua在宿主程序作为一个嵌入语言时，对于通过lua与宿主程序进行接口编程的人来说，垃圾回收带来一个新的问题，他们不能将Lua的各种table和string存放在C变量里，因为当这些值在Lua的环境里没有任何进一步的引用时，这些值会在垃圾回收执行时被回收。说白了，编程人员必须在返回lua控制之前，将lua里的这些值复制到C的变量里。

总结

从1993年下半年开始，Lua应经被广泛用于生产环境，主要应用在一下几方面：

user configuration of application environment

general purpose data-entry with user defined dialogs and validation procedures

description of user interfaces

programmer description of application objects

storage of structured graphical metafiles，used for communication between graphical

editors and application programs

这部分内容主要描述了lua解释器的实现，基于栈式虚拟机来实现，并且通过一个简单的例子，解释了从lua源码到字节码的转换。这对我们理解c代码中lua虚拟机的实现将会有所帮助。

另外也提到了垃圾回收的机制，也可能对理解其实现代码有所帮助，同时也提到了垃圾回收机制带来一个新问题。