Lua SEMISH'94 论文

摘自巴西第 21 届软件和硬件研讨会论文集 (1994) 273–283。[ps]

扩展应用程序的语言设计与实现

作者：Luiz Henrique de Figueiredo、Roberto Ierusalimschy、Waldemar Celes Filho

摘要。

我们描述了 Lua 的设计和实现，Lua 是一种简单但功能强大的语言，用于扩展应用程序。虽然 Lua 是一种过程语言，但它具有数据描述功能，并且已广泛用于生产中，用于多项任务，包括用户配置、通用数据输入、用户界面描述、应用程序对象描述以及结构化图形元文件的存储。

简介

对可定制应用程序的需求与日俱增。随着应用程序变得越来越复杂，使用简单参数进行定制变得不可能：用户现在希望在执行时做出配置决策；用户还希望编写宏和脚本以提高生产力 (Ryan 1990)。因此，如今，较大的应用程序几乎总是带有自己的配置或脚本语言，供最终用户编程。这些语言通常很简单，但每种语言都有自己特定的语法。因此，用户必须为每个应用程序学习（并且开发人员必须设计、实现和调试）一种新语言。

我们第一次使用专有脚本语言是在数据输入应用程序中，为此设计了一种非常简单的声明式语言 (Figueiredo–Souza–Gattass–Coelho 1992)。（数据输入是一个特别需要用户定义操作的领域，因为预编码验证测试很难适用于所有应用程序。）当用户开始要求这种语言具有越来越大的功能时，我们决定需要一种更通用的方法，并开始设计一种通用嵌入式语言。与此同时，另一种声明式语言被添加到另一个应用程序中，用于数据描述。因此，我们决定将这两种语言合并为一种语言，并设计 Lua 成为一种具有数据描述功能的过程语言。从那时起，Lua 就超越了其最初的根源，并被用于其他几个工业项目中。

本文介绍了 Lua 的设计决策和实现细节。

扩展语言

现在，使用语言来扩展应用程序被认为是一种重要的设计技术：它允许对应用程序进行更清晰的设计，并由用户进行配置。由于大多数扩展语言都很简单，专门用于一项任务，因此它们被称为“小语言”（Bentley 1986；Vald�s 1991），与“大”主流语言形成对比，应用程序是用这些主流语言编写的。如今，这种区别并不那么明显，因为几个应用程序的主要部分实际上是使用扩展语言编写的。扩展语言有几种类型

嵌入式语言与独立语言的不同之处在于，嵌入式语言只能嵌入在称为嵌入程序的主机客户端中。此外，主机程序通常可以为嵌入式语言提供特定于域的扩展，从而创建针对其自身目的定制的嵌入式语言版本，可能通过提供更高级别的抽象来实现。为此，嵌入式语言既有其自身程序的语法，又有用于与主机交互的应用程序编程接口 (API)。因此，与用于向主机提供参数值和操作序列的更简单的扩展语言不同，嵌入式语言和主机程序之间存在双向通信。请注意，应用程序程序员使用用于主机程序的主流语言与嵌入式语言进行交互，而用户仅使用嵌入式语言与应用程序进行交互。

LISP 一直是扩展语言的热门选择，因为它具有简单、易于解析的语法和内置的可扩展性（Beckman 1991；Nahaboo）。例如，Emacs 的主要部分实际上是用其自己的 LISP 变体编写的；其他几个文本编辑器也遵循相同的路径。然而，在定制方面，LISP 不能称之为用户友好。C 和 shell 语言也不能；后者甚至有更复杂、更陌生的语法。

Lua 设计中做出的基本决策之一是它应该具有简洁但熟悉的语法：我们很快确定了简化的类似 Pascal 的语法。我们避免了基于 LISP 或 C 的语法，因为它可能会让局外人或非程序员望而生畏。因此，Lua 主要是一种过程语言。然而，如前所述，Lua 已经获得了数据描述功能以增加其表达能力。

Lua 概念

Lua 是一种通用嵌入式编程语言，旨在支持具有数据描述功能的过程编程。作为一种嵌入式语言，Lua 没有“主”程序的概念；它只能嵌入在主机客户端中（Lua 以 C 函数库的形式提供，可链接到主机应用程序）。主机可以调用函数来执行 Lua 中的一段代码，可以写入和读取 Lua 变量，并且可以注册 C 函数以供 Lua 代码调用。通过注册的 C 函数，Lua 可以扩展以应对不同的域，从而创建共享语法框架的定制编程语言（Beckman 1991）。

本节简要描述了 Lua 中的主要概念。包括了一些实际代码示例，以了解该语言的风格。可以在其参考手册（Ierusalimschy–Figueiredo–Celes 1994）中找到该语言的精确定义。

语法

如前所述，我们明确设计 Lua 具有简单、熟悉的语法。因此，Lua 支持几乎传统的语句集，具有隐式但明确终止的块结构。传统语句包括简单赋值；控制结构，如 while-do-end、repeat-until、if-then-elseif-else-end；以及函数调用。非传统语句包括多重赋值；局部变量声明，可以放置在块内的任何位置；以及表构造函数，可以包含用户定义的验证函数（见下文）。此外，Lua 中的函数可以采用可变数量的参数，并且可以返回多个值。当需要返回多个结果时，这避免了按引用传递参数的需要。

环境和模块

Lua 中的所有语句都在全局环境中执行。此环境保存所有全局变量和函数，在嵌入式程序开始时初始化，并持续到其结束。全局环境可以通过 Lua 代码或嵌入式程序进行操作，后者可以使用 Lua 实现库中的函数来读写全局变量。

Lua 的执行单元称为模块。模块可以包含语句和函数定义，可以位于文件或宿主程序中的字符串中。当执行模块时，首先编译其所有函数和语句，并将函数添加到全局环境中；然后按顺序执行语句。模块对全局环境执行的所有修改在其结束后仍然存在。这些修改包括对全局变量的修改和新函数的定义（函数定义实际上是对全局变量的赋值；见下文）。

数据类型和变量

Lua 是一种动态类型语言：变量没有类型；只有值有。所有值都带有自己的类型。因此，语言中没有类型定义。没有变量类型声明，表面上看是一个小问题，但实际上是简化语言的一个重要因素；在许多修改为用作扩展语言的类型语言变体中，它经常被作为主要特性提出。此外，Lua 具有垃圾回收功能：它跟踪哪些值正在使用，并丢弃未使用的值。这避免了显式管理内存分配的需要，这是编程错误的主要来源。Lua 中有七种基本数据类型

Lua 提供了一些自动类型转换。如果可能，参与算术运算的字符串将转换为数字。相反，每当数字在需要字符串时使用时，该数字将转换为字符串。这种强制转换很有用，因为它简化了程序，避免了对显式转换函数的需求。

全局变量不需要声明；只有局部变量需要。任何变量都被假定为全局变量，除非明确声明为局部变量。局部变量声明可以放在块内的任何位置。因此，由于只有局部变量被声明，并且这些声明可以靠近变量的使用位置，因此通常很容易决定给定变量是局部变量还是全局变量。

在第一次赋值之前，变量的值为 nil。因此，Lua 中没有未初始化的变量，这是编程错误的另一个主要来源。然而，对 nil 唯一有效的操作是赋值和相等性测试（nil 的主要属性是与任何其他值不同）。因此，在需要“实际”值（例如算术表达式）的情况下使用“未初始化”变量会导致执行错误，提醒程序员该变量未正确初始化。因此，使用 nil 自动初始化变量的目的是不是鼓励程序员避免初始化变量，而是使 Lua 能够发出实际未初始化变量的使用信号。

函数在 Lua 中被视为一等值：它们可以存储在变量中，作为参数传递给其他函数并作为结果返回。当 Lua 中的函数被定义时，它的主体被编译并存储在具有给定名称的全局变量中。Lua 可以调用（和操作）用 Lua 和 C 编写的函数；后者类型为 Cfunction。

userdata 类型用于允许将任意（void*）C 指针存储在 Lua 变量中；它在 Lua 中唯一有效的操作是赋值和相等性测试。

table 类型实现了关联数组，即可以用数字和字符串索引的数组。因此，此类型不仅可以用来表示普通数组，还可以表示符号表、集合、记录等。为了表示记录，Lua 使用字段名称作为索引。该语言通过提供 a.name 作为 a["name"] 的语法糖来支持此表示。

关联数组是一种强大的语言结构；许多算法被简化为琐碎的程度，因为搜索它们的所需数据结构和算法是由语言提供的（Aho-Kerninghan-Weinberger 1988；Bentley 1988）。例如，统计文本中每个单词出现次数的程序的核心可以写成 

        table[word] = table[word] + 1
而无需搜索单词列表。（然而，按字母顺序排列的报告需要一些实际工作，因为表中的索引在 Lua 中是任意排序的。）

表可以通过多种方式创建。最简单的方式对应于普通数组 

        t = @(100)
这种表达式将生成一个新的空表。维度（上面的示例中为 100）是可选的，可以作为初始表大小的提示。独立于初始维度，Lua 中的所有表都会根据需要动态扩展。因此，引用 t[200] 甚至 t["day"] 是完全有效的。

有两种替代语法可以创建表，而无需显式填充每个条目：一种用于列表 (@[])，一种用于记录 (@{})。例如，通过提供元素来创建列表要比使用等效的显式代码容易得多，如下所示 

        t = @["red", "green", "blue", 3]
而不是使用等效的显式代码 
        t = @()
        t[1] = "red"
        t[2] = "green"
        t[3] = "blue"
        t[4] = 3
此外，在创建列表和记录时可以提供用户函数，如下所示 
        t = @colors["red", "green", "blue", "yellow"]
        t = @employee{name="john smith", age=34}
此处，colors 和 employee 是用户函数，在创建表后会自动调用。此类函数可用于检查字段值、创建默认字段或用于任何其他副作用。因此，employee 记录的代码等效于 
        t = @()
        t.name = "john smith"
        t.age  = 34
        employee(t)
请注意，即使 Lua 没有类型声明，但可以在创建表后自动调用用户函数，这实际上为 Lua 提供了用户控制的类型构造函数。这种非常规构造是一个非常强大的特性，是使用 Lua 进行声明式编程的表达。

应用程序编程接口

实现 Lua 的库具有 API，即一组用于在 Lua 与主机程序之间进行接口的 C 函数（大约有 30 个此类函数）。这些函数将 Lua 表征为嵌入式语言，并处理以下任务：执行包含在文件或字符串中的 Lua 代码；在 C 和 Lua 之间转换值；读取和写入包含在全局变量中的 Lua 对象；调用 Lua 函数；注册由 Lua 调用的 C 函数，包括错误处理程序。可以编写一个简单的 Lua 解释器，如下所示 

        #include "lua.h"
        int main(void)
        {
         char s[1000];
         while (gets(s))
           lua_dostring(s);
         return 0;
        }
这个简单的解释器可以使用用 C 编写的特定于领域的函数进行扩充，并通过 API 函数 lua_register 提供给 Lua。扩展函数遵循协议来接收和向 Lua 返回值。

预定义函数和库

Lua 中预定义函数的集合很小但很强大。它们中的大多数都提供了允许语言具有一定程度反射性的特性。这些特性无法通过语言的其余部分或标准 API 模拟。预定义函数处理以下任务：执行包含在文件或字符串中的 Lua 模块；枚举表的所有字段；枚举所有全局变量；类型查询和转换。

另一方面，库提供了通过标准 API 直接实现的有用例程。因此，它们对于语言来说不是必需的，而是作为单独的 C 模块提供的，可以根据需要链接到应用程序。目前，有用于字符串操作、数学函数以及输入和输出的库。

持久性

枚举函数可用于提供 Lua 中全局环境的持久性，即，可以编写 Lua 代码来编写 Lua 代码，当执行时，它会恢复所有全局变量的值。我们现在展示一些使用以该语言本身编写的文本文件作为存储介质在 Lua 中存储和检索值的方法。要恢复以这种方式保存的值，只需执行输出文件即可。

要使用名称存储单个值，以下代码就足够了 

        function store(name, value)
          write(name .. '=')
          write_value(value)
        end
此处，“..”是字符串连接运算符，write 是用于输出的库函数。函数 write_value 根据其类型输出值的适当表示，使用预定义函数 type 返回的字符串 
        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

存储表稍微复杂一些。首先，write_value 进行了扩充 

          elseif t = 'table' then write_record(value)
假设表用作记录（即，没有循环引用，所有索引都是标识符），则可以使用表构造函数直接写入表的值 
        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

实现

扩展语言总是以某种方式由应用程序解释。简单的扩展语言可以直接从源代码解释。另一方面，嵌入式语言通常是功能强大的编程语言，具有复杂的语法和语义。针对嵌入式语言的更有效的实现技术是设计一个适合语言需求的虚拟机，将扩展程序编译成此机器的字节码，然后通过解释字节码来模拟虚拟机（Betz 1988, 1991；Franks 1991）。我们为实现 Lua 选择了这种混合架构；它具有以下优点，优于直接解释源代码

这种架构最早在 Smalltalk（Goldberg-Robson 1983；Budd 1987）中开创（术语字节码由此借用而来），并且还在基于 P 代码的成功 UCSD Pascal 系统中使用（Clark-Koehler 1982）。在这些系统中，虚拟机的字节码既用于降低复杂性，也用于提高可移植性。此路径还用于移植 BCPL 编译器（Richards-Whitby-Strevens 1980）。

扩展程序的编译代码可以使用标准工具来构建，例如lex和yacc（Levine-Mason-Brown 1992）。在七十年代末期，编译器构建的良好工具开始广泛使用，这是小语言激增的主要原因，尤其是在 Unix 环境中。我们对 Lua 的实现使用yacc进行语法分析。最初，我们使用lex编写词法分析器。在对生产程序进行性能分析后，我们发现该模块几乎占加载和执行扩展程序所需时间的一半。然后，我们直接用 C 重写了该模块；新的词法分析器比旧分析器快两倍以上。

Lua 虚拟机

我们在 Lua 实现中使用的虚拟机是堆栈机。这意味着它没有随机存取存储器：所有临时值和局部变量都保存在堆栈中。此外，它没有通用寄存器，只有特殊控制寄存器，用于控制堆栈和程序执行。这些寄存器是堆栈基址、堆栈顶和程序计数器。

虚拟机的程序是指令序列，称为字节码。程序的执行是通过解释字节码来实现的，每个字节码对应于对堆栈顶部操作的指令。例如，语句 

        a = b + f(c)
被编译成 
        PUSHGLOBAL   "b"
        PUSHGLOBAL   "f"
        PUSHMARK
        PUSHGLOBAL   "c"
        CALLFUNC
        ADJUST        2
        ADD
        STOREGLOBAL  "a"
Lua 虚拟机有大约 60 条指令；因此，可以使用 8 位字节码。许多指令（例如ADD）不需要其他参数；这些指令直接在堆栈上操作，并在编译代码中占用正好一个字节。其他指令（例如PUSHGLOBAL和STOREGLOBAL）需要其他参数，并且占用多个字节。由于参数占用一个、两个或四个字节，因此在某些架构中会产生对齐问题，可以通过使用NOP填充到对齐边界来解决这些问题。

许多指令仅用于优化。例如，有一个PUSH指令，它将一个数字作为参数并将其压入堆栈，但还有一些单字节优化版本用于压入常见值，例如零和一。因此，我们有PUSHNIL、PUSH0、PUSH2、PUSH3。此类优化既减少了编译字节码所需的空间，又减少了解释指令所需的时间。

回想一下，Lua 支持多重赋值和函数的多重返回值。因此，有时必须在运行时将值列表调整到给定长度：如果值多于需要的值，则会丢弃多余的值；如果需要的值多于现有值，则会使用尽可能多的nil来扩展列表。调整在堆栈上使用ADJUST指令完成。

尽管多重赋值和返回是 Lua 的强大功能，但它们是编译器和解释器中复杂性的重要来源。由于函数没有类型声明，因此编译器不知道函数将返回多少个值。因此，必须在运行时进行调整。类似地，编译器不知道函数需要多少个参数。由于此数字在运行时可能有所不同，因此参数列表位于 PUSHMARK 和 CALLFUNC 指令之间。

使用主机提供的函数扩展 Lua 的一种方法是为每个此类函数分配一个字节码（Betz 1988）。尽管此策略会简化解释器，但它有一个缺点，即只能添加不到 200 个外部函数，因为 Lua 具有 8 位字节码，并且已经将其中的大约 60 个用于其原始指令。我们选择让主机显式注册外部函数，并将这些函数像本机 Lua 函数一样处理。因此，只有一个 CALLFUNC 指令；解释器根据被调用函数的类型决定要执行的操作。

Franks（1991）提出了一个截然不同的策略：嵌入式语言可以调用主机中的所有外部函数；不需要显式注册。这是通过读取和解释链接器生成的映射来完成的。此解决方案对应用程序程序员非常方便，但不可移植，因为它依赖于映射文件格式和操作系统使用的重定位策略（Franks 使用了 DOS 的特定编译器）。

内部数据结构

如前所述，Lua 中的变量没有类型；只有值有类型。因此，值在 struct 中实现，该 struct 有两个字段：一个类型和一个包含实际值的 union。这些 struct 发生在堆栈和符号表中，符号表保存所有全局符号。

数字直接存储到 union 中。字符串保存在单个数组中；string 类型的包含指向此数组的指针。function 类型的包含指向字节码数组的指针。Cfunction 类型的包含由主机程序提供的 C 函数的实际指针；userdata 类型的也一样。

表实现为哈希表，通过单独链接处理冲突（这解释了为什么表中的索引是任意排序的）。如果在创建表时给出了维度，则此维度将用作哈希表的大小。因此，通过提供大约等于表中预期索引数的维度，将很少发生冲突，从而导致非常有效的索引位置。此外，如果表用作数组，仅包含数字索引，那么在创建时选择正确的维度可以确保不会发生冲突。

Lua 中的所有内部数据结构都是动态分配的数组。当其中一个数组中没有更多空闲槽位时，将使用标准的标记清除算法自动执行垃圾回收。如果没有回收空间（因为所有值都被引用），则将使用当前大小的两倍重新分配数组。

垃圾回收对程序员非常方便，因为它避免了显式内存管理。当 Lua 被用作独立语言（它经常被用作独立语言）时，垃圾回收是一种优势。但是，当 Lua 被嵌入到宿主程序中（这是其主要目的）时，垃圾回收会给需要与 Lua 交互的应用程序程序员带来新的担忧：应注意不要将 Lua 表和字符串存储到 C 变量中，因为如果这些值在 Lua 环境中没有进一步的引用，它们可能会在垃圾回收期间被回收。更确切地说，程序员必须在将控制权返回 Lua 之前，将这些值显式复制到 C 变量中。虽然这是一个不同的范例，但它并不比使用标准 C 库进行内存管理的熟悉的 malloc-free 协议更差。

结论

Lua 自 93 年中期以来已在生产中得到广泛使用，用于以下任务

此外，Lua 目前正被考虑作为可视化编程系统基础。

在运行时加载和执行 Lua 程序的能力已被证明是使配置成为用户和开发人员的简单任务的主要组成部分。此外，单一通用嵌入式语言的存在阻碍了不兼容语言的倍增，并鼓励更好的设计，该设计清楚地将应用程序中包含的主要技术与其配置问题分开。

本文中描述的 Lua 实现可以通过匿名 ftp 从 https://lua.ac.cn/ftp/lua-1.1.tar.gz 获得。

致谢

我们要感谢 ICAD 和 TeCGraf 的工作人员使用和测试 Lua。文中提到的工业应用正在与巴西石油公司 (CENPES) 和巴西电力公司 (CEPEL) 的研究中心合作开发。

参考文献

M. Abrash、D. Illowsky，“使用迷你解释器编写自己的迷你语言”，Dr. Dobb's Journal 14 (9) (1989 年 9 月) 52–72。

A. V. Aho、B. W. Kerninghan、P. J. Weinberger，AWK 编程语言，Addison-Wesley，1988 年。

B. Beckman，“用于交互式图形的小语言方案”，Software, Practice & Experience 21 (1991) 187–207。

J. Bentley，“编程精华：小语言”，Communications of the ACM 29 (1986) 711–721。

J. Bentley，更多编程精华，Addison-Wesley，1988 年。

D. Betz，“嵌入式语言”，Byte 13 #12 (1988 年 11 月) 409–416。

D. Betz，“您自己的微型面向对象语言”，Dr. Dobb's Journal 16 (9) (1991 年 9 月) 26–33。

T. Budd，Smalltalk 入门，Addison-Wesley，1987 年。

R. Clark、S. Koehler，UCSD Pascal 手册：程序员参考和指南，Prentice-Hall，1982 年。

M. Cowlishaw，REXX 编程语言，Prentice-Hall，1990 年。

L. H. de Figueiredo、C. S. de Souza、M. Gattass、L. C. G. Coelho，“生成用于捕获设计数据的界面”，Anais do SIBGRAPI V (1992) 169–175 [葡萄牙语]。

N. Franks，“向您的软件添加扩展语言”，Dr. Dobb's Journal 16 (9) (1991 年 9 月) 34–43。

A. Goldberg、D. Robson，Smalltalk-80：语言及其实现，Addison-Wesley，1983 年。

R. Ierusalimschy、L. H. de Figueiredo、W. Celes Filho，“Lua 编程语言参考手册”，Monografias em Ci�ncia da Computa��o 4/94，PUC-Rio 计算机科学系，1994 年。

J. R. Levine、T. Mason、D. Brown，Lex & Yacc，O'Reilly and Associates，1992 年。

C. Nahaboo，嵌入式语言目录，可从 [email protected] 获得。

M. Richards、C. Whitby-Strevens，BCPL：语言及其编译器，剑桥大学出版社，1980 年。

B. Ryan，“无限制脚本”，Byte 15 (8) (1990 年 8 月) 235–240。

R. Vald�s，“小语言，大问题”，Dr. Dobb's Journal 16 (9) (1991 年 9 月) 16–25。

上次更新：2015 年 3 月 30 日星期一上午 9:29:59 巴西利亚时间