Chapter9 闭包

在Lua语言中，函数是严格遵循词法定界（lexicalscoping）的第一类值（first-classvalue）。

“第一类值”意味着Lua语言中的函数与其他常见类型的值（例如数值和字符串）具有同等权限：一个程序可以将某个函数保存到变量中（全局变量和局部变量均可）或表中，也可以将某个函数作为参数传递给其他函数，还可以将某个函数作为其他函数的返回值返回。

“词法定界”意味着Lua语言中的函数可以访问包含其自身的外部函数中的变量（也意味着Lua语言完全支持Lambda演算）。
【
此处原文大致为”Lexical scoping means that functions can access variables of their enclosing functions”，实际上是指Lua语言中的一个函数A可以嵌套在另一个函数B中，内部的函数A可以访问外部函数B中声明的
变量。
定界是计算机科学中的专有名词，指变量与变量所对应实体之间绑定关系的有效范围，在部分情况下也常与可见性（visibility）混用。
词法定界也被称为静态定界（static scoping），常常与动态定界（dynamic scoping）比较，其中前者被大多数现代编程语言采用，后者常见于Bash等Shell语言。
使用静态定界时，一个变量的可见性范围仅严格地与组成程序的静态具体词法上下文有关，而与运行时的具体堆栈调用无关；
使用动态定界时，一个变量的可见性范围在编译时无法确定，依赖于运行时的实际堆栈调用情况。
】

上述两个特性联合起来为Lua语言带来了极大的灵活性。
例如，一个程序可以通过重新定义函数来增加新功能，也可以通过擦除函数来为不受信任的代码（例如通过网络接收到的代码）创建一个安全的运行时环境。
【
通常通过网络等方式动态加载的代码只应该具有访问其自身代码和数据的能力，而不应该具有访问除其自身代码和数据外其他固有代码和数据的能力，否则就可能出现越权或各种溢出类风险，因此可以通过在使用完成后 将这些动态加载的代码擦除的方式消除由于动态加载了非受信任代码而可能导致的安全风险。
】
更重要的是，上述两个特性允许我们在Lua语言中使用很多函数式语言（functional-language）的强大编程技巧。即使对函数式编程毫无兴趣，也不妨学习一下如何探索这些技巧，因为这些技巧可以使程序变得更加小巧和简单。

9.1 函数是第一类值

如前所述，Lua语言中的函数是第一类值。以下的示例演示了第一类值的含义：

1
2
3
4
5
6
a = { p = print }		-- 'a.p'指向'print'函数
a.p("Hello world")		--> Hello world
print = math.sin		-- 'print'现在指向math.sin函数
a.p(print(1))			--> 0.8414709848079
math.sin = a.p			-- 'sin'现在指向print函数
math.sin(10,20)			--> 10 20

如果函数也是值的话，那么是否有创建函数的表达式呢？答案是肯定的。事实上，Lua语言中常见的函数定义方式如下：

1
2
3
function foo(x)
	return 2*x
end

就是所谓的语法糖（syntactic sugar）的例子，它只是下面这种写法的一种美化形式：

1
foo = function(x) return 2*x end

赋值语句右边的表达式（function（x）body end）就是函数构造器，与表构造器{}相似。因此，函数定义实际上就是创建类型为”function”的值并把它赋值给一个变量的语句。

请注意，在Lua语言中，所有的函数都是匿名的（anonymous）。
像其他所有的值一样，函数并没有名字。当讨论函数名时，比如print，实际上指的是保存该函数的变量。虽然我们通常会把函数赋值给全局变量，从而看似给函数起了一个名字，但在很多场景下仍然会保留函数的匿名性。下面来看几个例子。

表标准库提供了函数table.sort，该函数以一个表为参数并对其中的元素排序。
这种函数必须支持各种各样的排序方式：升序或降序、按数值顺序或按字母顺序、按表中的键等。
函数sort并没有试图穷尽所有的排序方式，而是提供了一个可选的参数，也就是所谓的排序函数（ order function ），排序函数接收两个参数并根据第一个元素是否应排在第二个元素之前返回不同的值。

例如，假设有一个如下所示的表：

1
2
3
4
5
6
network = {
	{name = "grauna",IP = "210.26.30.34"},
	{name = "arraial",IP = "210.26.30.34"},
	{name = "lua",IP = "210.26.30.34"},
	{name = "derain",IP = "210.26.30.34"},
}

如果想针对name字段、按字母顺序逆序对这个表排序，只需使用如下语句：

1
table.sort(network,function(a,b) return (a.name > b.name) end)

可见，匿名函数在这条语句中显示出了很好的便利性。

像函数sort这样以另一个函数为参数的函数，我们称之为高阶函数（higher-order function）。
高阶函数是一种强大的编程机制，而利用匿名函数作为参数正是其灵活性的主要来源。不过尽管如此，请记住高阶函数也并没有什么特殊的，它们只是Lua语言将函数作为第一类值处理所带来结果的直接体现。

9.2 非全局函数

由于函数是一种“第一类值”，因此一个显而易见的结果就是：函数不仅可以被存储在全局变量中，还可以被存储在表字段和局部变量中。

我们已经在前面的章节中见到过几个将函数存储在表字段中的示例，大部分Lua语言的库就采用了这种机制（例如io.read和math.sin）。
如果要在Lua语言中创建这种函数，只需将到目前为止我们所学到的知识结合起来：

1
2
3
Lib =  {}
Lib.foo = function (x,y) return x+y end
Lib.goo = function (x,y) return x-y end

当然，也可以使用表构造器：

1
2
3
4
Lib = {
foo = function (x,y) return x+y end
goo = function (x,y) return x-y end
}

除此以外，Lua语言还提供了另一种特殊的语法来定义这类函数：

1
2
3
Lib =  {}
function Lib.foo(x,y) return x+y end
function Lib.goo(x,y) return x-y end

正如我们将在第21章中看到的，在表字段中存储函数是Lua语言中实现面向对象编程的关键要素。

当把一个函数存储到局部变量时，就得到了一个局部函数（local function），即一个被限定在指定作用域中使用的函数。
局部函数对于包（package）而言尤其有用：由于Lua语言将每个程序段（chunk）作为一个函数处理，所以在一段程序中声明的函数就是局部函数，这些局部函数只在该程序段中可见。
词法定界保证了程序段中的其他函数可以使用这些局部函数。

对于这种局部函数的使用，Lua语言提供了一种语法糖：

1
2
3
local function f(params)
	boby
end

在定义局部递归函数（recursive local function）时，由于原来的方法不适用，所以有一点是极易出错的。
考虑如下的代码：

1
2
3
4
5
6
7
local fact = function(n)
	if n == 0 then
		return 1
	else
		return n * fact(n - 1)		-- Error!
	end
end

当Lua语言编译函数体中的fact（n-1）调用时，局部的fact尚未定义。因此，这个表达式会尝试调用全局的fact而非局部的fact。

我们可以通过先定义局部变量再定义函数的方式来解决这个问题：

1
2
3
4
5
6
7
8
9
local fact

fact = function(n)
	if n == 0 then
		return 1
	else
		return n * fact(n - 1)		-- Error!
	end
end

这样，函数内的fact指向的是局部变量。尽管在定义函数时，这个局部变量的值尚未确定，但到了执行函数时，fact肯定已经有了正确的赋值。

当Lua语言展开局部函数的语法糖时，使用的并不是之前的基本函数定义。相反，形如

1
2
3
local function foo(params)
	boby
end

的定义会被展开成

1
2
3
4
local foo
foo = function (params)
	boby
end

因此，使用这种语法来定义递归函数不会有问题。

当然，这个技巧对于间接递归函数（indirect recursive function）是无效的。
在间接递归的情况下，必须使用与明确的前向声明（explicit forward declaration）等价的形式：

1
2
3
4
5
6
7
8
9
10
11
12
13
local f		-- "向前"声明

local function g()
	some code
	f()
	some code
end

function f()
	some code
	g()
	some code
end

请注意，不能在最后一个函数定义前加上local。否则，Lua语言会创建一个全新的局部变量f，从而使得先前声明的f（函数g中使用的那个）变为未定义状态。

9.3 词法定界

当编写一个被其他函数B包含的函数A时，被包含的函数A可以访问包含其的函数B的所有局部变量，我们将这种特性称为词法定界（lexical scoping）。
虽然这种可见性规则听上去很明确，但实际上并非如此。词法定界外加嵌套的第一类值函数可以为编程语言提供强大的功能，但很多编程语言并不支持将这两者组合使用。

先看一个简单的例子。
假设有一个表，其中包含了学生的姓名和对应的成绩，如果我们想基于分数对学生姓名排序，分数高者在前，那么可以使用如下的代码完成上述需求：

1
2
3
4
5
6
names = {"Peter","Paul","Mary"}
grades = {Mary = 10,Paul = 7,Peter = 8}

table.sort(names,function(n1,n2)
	return grades[n1] > grades[n2]
end)

现在，假设我们想创建一个函数来完成这个需求：

1
2
3
4
5
function sortbygrade(names,grade)
	table.sort(names,function(n1,n2)
		return grades[n1] > grades[n2]
	end)
end

在后一个示例中，有趣的一点就在于传给函数sort的匿名函数可以访问grades，而grades是包含匿名函数的外层函数sortbygrade的形参。
在该匿名函数中，grades既不是全局变量也不是局部变量，而是我们所说的非局部变量（non-local variable）（由于历史原因，在Lua语言中非局部变量也被称为上值）。

这一点之所以如此有趣是因为，函数作为第一类值，能够逃逸（escape）出它们变量的原始定界范围。
考虑如下的代码：

1
2
3
4
5
6
7
8
9
10
11
function newCounter()
	local count = 0
	return function()	-- 匿名函数
		count = count + 1
		return count
	end
end

c1 = newCounter()
print(c1())	--> 1
print(c1())	--> 2

在上述代码中，匿名函数访问了一个非局部变量（count）并将其当作计数器。
然而，由于创建变量的函数（newCounter）己经返回，因此当我们调用匿名函数时，变量count似乎已经超出了作用范围。
但其实不然，由于闭包（closure）概念的存在，Lua语言能够正确地应对这种情况。
简单地说，一个闭包就是一个函数外加能够使该函数正确访问非局部变量所需的其他机制。
如果我们再次调用newCounter，那么一个新的局部变量count和一个新的闭包会被创建出来，这个新的闭包针对的是这个新变量：

1
2
3
4
c2 = newCounter()
print(c2())	--> 1
print(c1())	--> 3
print(c2())	--> 2

因此，c1和c2是不同的闭包。它们建立在相同的函数之上，但是各自拥有局部变量count的独立实例。

从技术上讲，Lua语言中只有闭包而没有函数。函数本身只是闭包的一种原型。不过尽管如此，只要不会引起混淆，我们就仍将使用术语“函数”来指代闭包。

闭包在许多场合中均是一种有价值的工具。
正如我们之前已经见到过的，闭包在作为诸如sort这样的高阶函数的参数时就非常有用。
同样，闭包对于那些创建了其他函数的函数也很有用，例如我们之前的newCounter示例及求导数的示例；这种机制使得Lua程序能够综合运用函数式编程世界中多种精妙的编程技巧。
另外，闭包对于回调（callback）函数来说也很有用。
对于回调函数而言，一个典型的例子就是在传统GUI工具箱中创建按钮。每个按钮通常都对应一个回调函数，当用户按下按钮时，完成不同的处理动作的回调函数就会被调用。
例如，假设有一个具有10个类似按钮的数字计算器（每个按钮代表一个十进制数字），我们就可以使用如下的函数来创建这些按钮：

1
2
3
4
5
6
7
8
function digitButton(digit)
	return Button{
		label = tostring(digit),
		action = function()
			add_to_display(digit)
		end,
	}
end

在上述示例中，假设Button是一个创建新按钮的工具箱函数，label是按钮的标签，action是当按钮按下时被调用的回调函数。回调可能发生在函数digitButton早已执行完后，那时变量digit已经超出了作用范围，但闭包仍可以访问它。

闭包在另一种很不一样的场景下也非常有用。
由于函数可以被保存在普通变量中，因此在Lua语言中可以轻松地重新定义函数，甚至是预定义函数。
这种机制也正是Lua语言灵活的原因之一。通常，当重新定义一个函数的时候，我们需要在新的实现中调用原来的那个函数。
例如，假设要重新定义函数sin以使其参数以角度为单位而不是以弧度为单位。那么这个新函数就可以先对参数进行转换，然后再调用原来的sin函数进行真正的计算。
代码可能形如：

1
2
3
4
local oldSin = math.sin
math.sin = function(x)
	return oldSin(x * (math.pi / 180))
end

另一种更清晰一点的完成重新定义的写法是：

1
2
3
4
5
6
7
do
	local oldSin = math.sin
	local k = math.pi / 180
	math.sin = function(x)
		return oldSin(x * k)
	end
end

上述代码使用了do代码段来限制局部变量oldSin的作用范围；根据可见性规则，局部变量oldSin只在这部分代码段中有效。
因此，只有新版本的函数sin才能访问原来的sin函数，其他部分的代码则访问不了。

我们可以使用同样的技巧来创建安全的运行时环境（secure environment），即所谓的沙盒（sandbox）。
当执行一些诸如从远程服务器上下载到的未受信任代码（untrusted code）时，安全的运行时环境非常重要。
例如，我们可以通过使用闭包重定义函数io.open来限制一个程序能够访问的文件：

1
2
3
4
5
6
7
8
9
10
11
12
13
do
	local oldOpen = io.open
	local access_ok = function(filename,mode)
		check access
	end
	io.open = function(filename,mode)
		if access_ok (filename,mode) then
			return oldOpen(filename,mode)
		else
			return nil,"access denied" 
		end
	end
end

上述示例的巧妙之处在于，在经过重新定义后，一个程序就只能通过新的受限版本来调用原来未受限版本的io.open函数。
示例代码将原来不安全的版本保存为闭包的一个私有变量，该变量无法从外部访问。
通过这一技巧，就可以在保证简洁性和灵活性的前提下在Lua语言本身上构建Lua沙盒。
相对于提供一套大而全（one-size-fits-all）的解决方案，Lua语言提供的是一套“元机制（meta-mechanism）”，借助这种机制可以根据特定的安全需求来裁剪具体的运行时环境（真实的沙盒除了保护外部文件外还有更多的功能，我们会在25.4节中再次讨论这个话题）。

补充：闭包的实现原理

当Lua编译一个函数时，它会生成一个原型（prototype），原型中包括函数的虚拟机指令、函数中的常量（数值和字符串等）和一些调试信息。
在任何时候只要Lua执行一个function … end表达时，它都会创建一个新的闭包（closure）。每个闭包都有一个相应函数原型的引用以及一个数组，数组中每个元素都是一个对upvalue的引用，可以通过该数组来访问外部的局部变量（outer local variables）。
值得注意的是，在Lua 5.2之前，闭包中还包括一个对环境（environment）的引用，环境实质就是一个table，函数可以在该表中索引全局变量，从Lua 5.2开始，取消了闭包中的环境，而引入一个变量_ENV来设置闭包环境。
由此可见，函数是编译期概念，是静态的，而闭包是运行期概念，是动态的。

作用域（生成期）规则下的嵌套函数给如何实现内存函数存储外部函数的局部变量是一个众所周知的难题（The combination of lexical scoping with first-class functions creates a well-known difficulty for accessing outer local variables）。
比如例子：

1
2
3
4
5
6
7
8
function add (x) 
	return function (y) 
		return x+y
	end
end

add2 = add(2)
print(add2(5))

当add2被调用时，其函数体访问了外部的局部变量x（在Lua中，函数参数也是局部变量）。
然而，当调用add2函数时，创建add2的add函数已经返回了，如果x在栈中创建，则当add返回时，x已经不存在了（即x的存储空间被回收了）。
为了解决上面的问题，不同语言有不同的方法，比如python通过限定作用域、Pascal限制函数嵌套以及C语言则两者都不允许。
在Lua中，使用一种称为upvalue结构来实现闭包。任何外部的局部变量都是通过upvalue来间接访问。
upvalue初始值是指向栈中，即变量在栈中的位置。如下图左边。
当运行时，离开变量作用域时（即超过变量生命周期），则会把变量复制到upvalue结构中（注意也只是在此刻才执行这个操作），如下图右边。
由于对变量的访问都是通过upvalue结构中指针间接进行的，因此复制操作对任何读或写变量的代码来说都是没有影响的。
与内部函数（inner functions）不同的是，声明该局部变量的函数都是直接在栈中操作它的。

通过为每个变量最多创建一个upvalue并按需要重复利用这个upvalue，保证了未决状态（未超过生命周期）的局部变量（pending vars）能够在闭包之间正确地共享。
为了保证这种唯一性，Lua维护这一条链表，该链表中每个节点对应一个打开的upvalue（opend upvalue）结构，打开的upvalue是指当前正指向栈局部变量的upvalue，如上图的未决状态的局部变量链表（the pending vars list）。
当Lua创建一个新的闭包时，Lua会遍历当前函数所有的外部的局部变量，对于每一个外部的局部变量，若在上面的链表中能找到该变量，则重复使用该打开的upvalue，否则，Lua会创建一个新的打开的upvalue，并把它插入链表中。
当局部变量离开作用域时（即超过变量生命周期），这个打开的upvalue就会变成关闭的upvalue（closed upvalue），并把它从链表中删除，如上图右图所示意。
一旦某个关闭的upvalue不再被任何闭包所引用，那么它的存储空间就会被回收。

一个函数有可能存取其更外层函数而非直接外层函数的局部变量。在这种情况下，当创建闭包时，这个局部变量可能不在栈中。
Lua使用flat 闭包(flat closures)来处理这种情况。使用flat闭包，无论何时一个函数访问一个外部的局部变量并且该变量不在直接外部函数中，该变量也会进入直接外部函数的闭包中。
当一个函数被实例化时，其对应闭包的所有变量要么在直接外部函数的栈中要么在直接外部函数的闭包中。

Chapter10 模式匹配

与其他几种脚本语言不同，Lua语言既没有使用POSIX正则表达式，也没有使用Perl正则表达式来进行模式匹配（pattern matching）。
之所以这样做的主要原因在于大小问题：一个典型的POSIX正则表达式实现需要超过4000行代码，这比所有Lua语言标准库总大小的一半还大。相比之下，Lua语言模式匹配的实现代码只有不到600行。
尽管Lua语言的模式匹配做不到完整POSIX实现的所有功能，但是Lua语言的模式匹配仍然非常强大，同时还具有一些与标准POSIX不同但又可与之媲美的功能。

10.1 模式匹配的相关函数

字符串标准库提供了基于模式（pattern）的4个函数。

10.1.1 函数string.find

函数string.find用于在指定的目标字符串中搜索指定的模式。

最简单的模式就是一个单词，它只会匹配到这个单词本身。
函数string.find找到一个模式后，会返回两个值：匹配到模式开始位置的索引和结束位置的索引。如果没有找到任何匹配，则返回nil。

函数string.find具有两个可选参数。
第3个参数是一个索引，用于说明从目标字符串的哪个位置开始搜索。
第4个参数是一个布尔值，用于说明是否进行简单搜索（plain search）。
字如其名，所谓简单搜索就是忽略模式而在目标字符串中进行单纯的“查找子字符串”的动作：

1
2
3
4
> string.find("a [word]","[")
stdin:1: malformed pattern (missing ']')

> string.find("a [word]","[",1,true)	--> 3 3

由于’[‘在模式中具有特殊含义，因此第1个函数调用会报错。在第2个函数调用中，函数只是把’[‘当作简单字符串。请注意，如果没有第3个参数，是不能传入第4个可选参数的。

10.1.2 函数string.match

由于函数string.match也用于在一个字符串中搜索模式，因此它与函数string.find非常相似。不过，函数string.match返回的是目标字符串中与模式相匹配的那部分子串，而非该模式所在的位置。

1
print(string.math("hello world","hello"))		--> hello

对于诸如’hello’这样固定的模式，使用这个函数并没有什么意义。
然而，当模式是变量时，这个函数的强大之处就显现出来了，例如：

1
2
3
data = "Today is 17/7/1990"
d = string.match(data," %d+/%d+/%d+");
print(d)		--> 17/7/1990

10.1.3 函数string.gsub

函数string.gsub有3个必选参数：目标字符串、模式和替换字符串（replacementstring），其基本用法是将目标字符串中所有出现模式的地方换成替换字符串。

此外，该函数还有一个可选的第4个参数，用于限制替换的次数：

1
2
3
4
s = string.gsub("all lii","l","x",1)
print(s)		--> axl lii
s = string.gsub("all lii","l","x",2)
print(s)		--> axx lii

除了替换字符串以外，string.gsub的第3个参数也可以是一个函数或一个表，这个函数或表会被调用（或检索）以产生替换字符串；我们会在10.4节中学习这个功能。

函数string.gsub还会返回第2个结果，即发生替换的次数。

10.1.4 函数string.gmatch

函数string.gmatch返回一个函数，通过返回的函数可以遍历一个字符串中所有出现的指定模式。

例如，以下示例可以找出指定字符串s中出现的所有单词：

1
2
3
4
5
6
s = "some thing"
words = {}

for w in string.gmatch(s,"%a+") do
	words[#words + 1] = w
end

后续我们马上会学习到，模式’%a+’会匹配一个或多个字母组成的序列（也就是单词）。
因此，for循环会遍历所有目标字符串中的单词，然后把它们保存到列表words中。

10.2 模式

大多数模式匹配库都使用反斜杠（backslash）作为转义符。然而，这种方式可能会导致一些不良的后果。
对于Lua语言的解析器而言，模式仅仅是普通的字符串。模式与其他的字符串一样遵循相同的规则，并不会被特殊对待；只有模式匹配相关的函数才会把它们当作模式进行解析。
由于反斜杠是Lua语言中的转义符，所以我们应该避免将它传递给任何函数。模式本身就难以阅读，到处把”"换成”\“就更加火上浇油了。

我们可以使用双括号把模式括起来构成的长字符串来解决这个问题（某些语言在实践中推荐这种办法）。然而，长字符串的写法对于通常比较短的模式而言又往往显得冗长。此外，我们还会失去在模式内进行转义的能力（某些模式匹配工具通过再次实现常见的字符串转义来绕过这种限制）。

Lua语言的解决方案更加简单：Lua语言中的模式使用百分号（percent sign）作为转义符（C语言中的一些函数采用的也是同样的方式，如函数printf和函数strftime）。
总体上，所有被转义的字母都具有某些特殊含义（例如’%a’匹配所有字母），而所有被转义的非字母则代表其本身（例如’%.’匹配一个点）。

我们首先来学习字符分类（character class）的模式。
所谓字符分类，就是模式中能够与一个特定集合中的任意字符相匹配的一项。
例如，分类%d匹配的是任意数字。因此，可以使用模式’%d%d/%d%d/%d%d%d%d’来匹配dd/mm/yyyy格式的日期：

1
2
3
s = "Dealine is 30/05/1999, firm"
data = "%d%d/%d%d/%d%d%d%d"
print(string.match(s,data))	--> 30/05/1999

下表列出了所有预置的字符分类及其对应的含义：

1
2
3
4
5
6
7
8
9
10
11
.			任意字符
%a			字母
%c			控制字符
%d			数字
%g			除空格外的可打印字符
%l			小写字母
%p			标点符号
%s			空白字符
%u			大写字母
%w			字母和数字
%x			十六进制数字

这些类的大写形式表示类的补集。例如，’%A’代表任意非字母的字符：

1
2
print((string.gsub("hello, up-down!","%A",".")))
-->	hello.up.down.

在输出函数gsub的返回结果时，我们使用了额外的括号来丢弃第二个结果，也就是替换发生的次数。

当在模式中使用时，还有一些被称为魔法字符（magic character）的字符具有特殊含义。
Lua语言的模式所使用的魔法字符包括：

1
( ) . % + - * ? [ ] ^ $

正如我们之前已经看到的，百分号同样可以用于这些魔法字符的转义。
因此，’%？’匹配一个问号，’%%’匹配一个百分号。我们不仅可以用百分号对魔法字符进行转义，还可以将其用于其他所有字母和数字外的字符。当不确定是否需要转义时，为了保险起见就可以使用转义符。

可以使用字符集（char-set）来创建自定义的字符分类，只需要在方括号内将单个字符和字符分类组合起来即可。
例如，字符集’[%w_]’匹配所有以下画线结尾的字母和数字，’[01]’匹配二进制数字，’[%[%]]’匹配方括号。
如果想要统计一段文本中元音的数量，可以使用如下的代码：

1
_,nvow = string.gsub(text,"AEIOUaeiou","")

还可以在字符集中包含一段字符范围，做法是写出字符范围的第一个字符和最后一个字符并用横线将它们连接在一起。
由于大多数常用的字符范围都被预先定义了，所以这个功能很少被使用。例如，’%d’相当于’[0-9]’，’%x’相当于’[0-9a-fA-F]’。不过，如果需要查找一个八进制的数字，那么使用’[0-7]’就比显式地枚举’[01234567]’强多了。

在字符集前加一个补字符^就可以得到这个字符集对应的补集：模式’[^0-7]’代表所有八进制数字以外的字符，模式’[^\n]’则代表除换行符以外的其他字符。
尽管如此，我们还是要记得对于简单的分类来说可以使用大写形式来获得对应的补集：’%S’显然要比’[^%s]’更简单。

还可以通过描述模式中重复和可选部分的修饰符（modifier，在其他语言中也被译为限定符）来让模式更加有用。
Lua语言中的模式提供了4种修饰符：

1
2
3
4
+		重复一次或多次
*		重复零次或多次
-		重复零次或多次（最小匹配）
?		可选（出现零次或一次）

修饰符+匹配原始字符分类中的一个或多个字符，它总是获取与模式相匹配的最长序列。
例如，模式’%a+’代表一个或多个字母（即一个单词）：

1
2
print((string.gsub("one, and two; and three","%a+","word")))
--> word, word word; word word

模式’%d+’匹配一个或多个数字（一个整数）：

1
2
print((string.match("the number 1298 is even","%d+")))
--> 1298

修饰符 * 类似于修饰符 +，但是它还接受对应字符分类出现零次的情况。
该修饰符一个典型的用法就是在模式的部分之间匹配可选的空格。
例如，为了匹配像（）或（）这样的空括号对，就可以使用模式’%（%s*%）’，其中的’%s*’匹配零个或多个空格（括号在模式中有特殊含义，所以必须进行转义）。
另一个示例是用模式’[ _ %a][_%w]*’匹配Lua程序中的标识符：标识符是一个由字母或下画线开头，并紧跟零个或多个由下画线、字母或数字组成的序列。

修饰符 - 和修饰符 * 类似，也是用于匹配原始字符分类的零次或多次出现。
不过，跟修饰符 * 总是匹配能匹配的最长序列不同，修饰符-只会匹配最短序列。
虽然有时它们两者并没有什么区别，但大多数情况下这两者会导致截然不同的结果。
例如，当试图用模式’[_ %a][_ %w]-‘查找标识符时，由于’[_%w]-‘总是匹配空序列，所以我们只会找到第一个字母。
又如，假设我们想要删掉某C语言程序中的所有注释，通常会首先尝试使用’/%* .* %* /‘（即”/* “和”* /“之间的任意序列，使用恰当的转义符对* 进行转义）。然而，由于’.* ‘会尽可能长地匹配
，因此程序中的第一个”/* “只会与最后一个”*/“相匹配：

1
2
3
test = "int x; /* x */ int y; /* y */"
print((string.gsub(test,"/%*.*%*/","")))
--> int x;

相反，模式’.-‘则只会匹配到找到的第一个”*/“，这样就能得到期望的结果：

1
2
3
test = "int x; /* x */ int y; /* y */"
print((string.gsub(test,"/%*.-%*/","")))
--> int x; int y;

最后一个修饰符？可用于匹配一个可选的字符。
例如，假设我们想在一段文本中寻找一个整数，而这个整数可能包括一个可选的符号，那么就可以使用模式’[+-]？%d+’来完成这个需求，该模式可以匹配像”-12”、”23”和”+1009”这样的数字。其中，字符分类’[+-]’匹配加号或减号，而其后的问号则代表这个符号是可选的。

与其他系统不同的是，Lua语言中的修饰符只能作用于一个字符模式，而无法作用于一组分类。
例如，我们不能写出匹配一个可选的单词的模式（除非这个单词只由一个字母组成）。通常，可以使用一些将在本章最后介绍的高级技巧来绕开这个限制。

以补字符^开头的模式表示从目标字符串的开头开始匹配。
类似地，以$结尾的模式表示匹配到目标字符串的结尾。
我们可以同时使用这两个标记来限制匹配查找和锚定（anchor）模式。例如，如下的代码可以用来检查字符串s是否以数字开头：

1
if string.find(s,"^%d") then ...

如下的代码用来检查字符串是否为一个没有多余前缀字符和后缀字符的整数：

1
if string.find(s,"^[+-]?%d+$") then ...

^和$字符只有位于模式的开头和结尾时才具有特殊含义；否则，它们仅仅就是与其自身相匹配的普通字符。

模式’%b’匹配成对的字符串，它的写法是’%bxy’，其中x和y是任意两个不同的字符，x作为起始字符而y作为结束字符。
例如，模式’%b（）’匹配以左括号开始并以对应右括号结束的子串：

1
2
3
s = "a (enclosed  (in) parentheses) line"
print((string.gsub(s,"%b()","")))
--> a line;

通常，我们使用’%b（）’、’%b[]’、’%b{}’或’%b<>’等作为模式，但实际上可以用任意不同的字符作为分隔符。

最后，模式’%f[char-set]’代表前置模式（frontier pattern）。
该模式只有在后一个字符位于char-set内而前一个字符不在时匹配一个空字符串：

1
2
3
s = "the anthem is the anthem"
print((string.gsub(s,"%f[%w]the%f[%W]","one")))
--> one anthem is one anthem;

模式’%f[%w]’匹配位于一个非字母或数字的字符和一个字母或数字的字符之间的前置，
而模式’%f[%W]’则匹配一个字母或数字的字符和一个非字母或数字的字符之间的前置。
因此，指定的模式只会匹配完整的字符串”the”。
请注意，即使字符集只有一个分类，也必须把它用括号括起来。

前置模式把目标字符串中第一个字符前和最后一个字符后的位置当成空字符（ASCII编码的\0）。
在前例中，第一个”the”在不属于集合’[%w]’的空字符和属于集合’[%w]’的t之间匹配了一个前置。

10.3 捕获

捕获（capture）机制允许根据一个模式从目标字符串中抽出与该模式匹配的内容来用于后续用途，可以通过把模式中需要捕获的部分放到一对圆括号内来指定捕获。

对于具有捕获的模式，函数string.match会将所有捕获到的值作为单独的结果返回；换句话说，该函数会将字符串切分成多个被捕获的部分：

1
2
3
pair = "name = zwt"
key,value= string.match(pair,"(%a+)%s*=%s*(%a+)")
print(key,value)	--> name zwt

模式’%a+’表示一个非空的字母序列，模式’%s*’表示一个可能为空的空白序列。
因此，上例中的这个模式表示一个字母序列、紧跟着空白序列、一个等号、空白序列以及另一个字母序列。
模式中的两个字母序列被分别放在圆括号中，因此在匹配时就能捕获到它们。

下面是一个类似的示例：

1
2
3
date = "Today is 17/7/1990"
d,m,y = string.match(date,"(%d+)/(%d+)/(%d+)")
print(d,m,y)	--> 17 7 1990

在这个示例中，使用了3个捕获，每个捕获对应一个数字序列。

在模式中，形如’%n’的分类（其中n是一个数字），表示匹配第n个捕获的副本。
举一个典型的例子，假设想在一个字符串中寻找一个由单引号或双引号括起来的子串。
那么可能会尝试使用模式’[“‘].-[“‘]’，它表示一个引号后面跟任意内容及另外一个引号；但是，这种模式在处理像”it’s all right”这样的字符串时会有问题。
要解决这个问题，可以捕获第一个引号然后用它来指明第二个引号：

1
2
3
4
s = [[then he said: "it's all right"!]]
q,quotedPart = string.match(s,"([\"'])(.-)%1")
print(quotedPart)	--> it's all right
print(q)	--> "

第1个捕获是引号本身，第2个捕获是引号中的内容（与’.-‘匹配的子串）。

下例是一个类似的示例，用于匹配Lua语言中的长字符串的模式：

1
%[(=*)%[(.-)%]%1%]

它所匹配的内容依次是：一个左方括号、零个或多个等号、另一个左方括号、任意内容（即字符串的内容）、一个右方括号、相同数量的等号及另一个右方括号：

1
2
3
p = "%[(=*)%[(.-)%]%1%]"
s = "a = [=[[[ something ]] ]==] ]=]; print(a)"
print(string.match(s,p))	--> = [[ something ]] ]==]

第1个捕获是等号序列（在本例中只有一个），第2个捕获是字符串内容。

被捕获对象的第3个用途是在函数gsub的替代字符串中。
像模式一样，替代字符串同样可以包括像”%n”一样的字符分类，当发生替换时会被替换为相应的捕获。
特别地，”%0”意味着整个匹配，并且替换字符串中的百分号必须被转义为”%%”。

下面这个示例会重复字符串中的每个字母，并且在每个被重复的字母之间插入一个减号：

1
2
print((string.gsub("hello lua!","%a","%0-%0")))
-->	h-he-el-ll-lo-o l-lu-ua-a!

下例交换了相邻的字符：

1
2
print((string.gsub("hello lua!","(.)(.)","%2%1")))
-->	ehll oul!a

以下是一个更有用的示例，让我们编写一个原始的格式转换器，该格式转换器能读取LATEX风格的命令，并将它们转换成XML风格：

1
\command{some text}		--> <command>some text</command>

如果不允许嵌套的命令，那么以下调用函数string.gsub的代码即可完成这项工作：

1
2
3
4
s = [[the \quote{task} is to \em{change} that.]]
s = string.gsub(s,"\\(%a+){(.-)}","<%1>%2</%1>")
print(s)
-->	the <quote>task</quote> is to <em>change</em> that.

另一个有用的示例是剔除字符串两端空格：

1
2
3
4
function trim(s)
	s = string.gsub(s,"^%s*(.-)%s*$","%1")
	return s
end

请注意模式中修饰符的合理运用。两个定位标记（^和$）保证了我们可以获取到整个字符串。由于中间的’.-‘只会匹配尽可能少的内容，所以两个’%s*’便可匹配到首尾两端的空格。

10.4 替换

正如我们此前已经看到的，函数string.gsub的第3个参数不仅可以是字符串，还可以是一个函数或表。
当第3个参数是一个函数时，函数string.gsub会在每次找到匹配时调用该函数，参数是捕获到的内容而返回值则被作为替换字符串。
当第3个参数是一个表时，函数string.gsub会把第一个捕获到的内容作为键，然后将表中对应该键的值作为替换字符串。
如果函数的返回值为nil或表中不包含这个键或表中键的对应值为nil，那么函数gsub不改变这个匹配。

最后一个例子，让我们再回到上一节中提到的格式转换器。
我们仍然是想将LATEX风格的命令（\example{text}）转换成XML风格的（text），但这次允许嵌套的命令。
以下的函数用递归的方式完成了这个需求：

1
2
3
4
5
6
7
8
9
10
11
12
function toxml(s)
	s = string.gsub(s,"\\(%a+)(%b{})",function(tag,body)
		body = string.sub(body,2,-2)	-- 移除括号
		body = toxml(body)				-- 处理嵌套的命令
		return string.format("<%s>%s</%s>",tag,body,tag)
	end)
	
	return s
end

print(toxml("\\title{The \\bold{big} example}"))
-->	<title>The <bold>big</bold> example</title>

10.4.1 URL编码

我们的下一个示例中将用到URL编码，也就是HTTP所使用的在URL中传递参数的编码方式。
这种编码方式会将特殊字符（例如=、＆和+）编码为”%xx”的形式，其中xx是对应字符的十六进制值。此外，URL编码还会将空格转换为加号。

例如，字符串”a+b = c”的URL编码为”a%2Bb+%3D+c”。
最后，URL编码会将每对参数名及其值用等号连接起来，然后将每对name=value用＆连接起来。
例如，值

1
name = "al"; query = "a+b = c";q = "yes or no"

对应的URL编码为”name=al＆query=a%2Bb+%3D+c＆q=yes+or+no”。

10.4.2 制表符展开

在Lua语言中，像’（）’这样的空白捕获（empty capture）具有特殊含义。
该模式并不代表捕获空内容（这样的话毫无意义），而是捕获模式在目标字符串中的位置（该位置是数值）：

1
print(string.match("hello","()ll()"))	--> 3 5

（请注意，由于第2个空捕获的位置是在匹配之后，所以这个示例的结果与调用函数string.find得到的结果并不一样。）

10.5 诀窍

模式匹配是进行字符串处理的强大工具之一。虽然通过多次调用函数string.gsub就可以完成许多复杂的操作，但是还是应该谨慎地使用该函数。

通常，在Lua程序中使用模式匹配时的效率是足够高的：笔者的新机器可以在不到0.2秒的时间内计算出一个4.4MB大小（具有85万个单词）的文本中所有单词的数量。
但仍然需要注意，应该永远使用尽可能精确的模式，不精确的模式会比精确的模式慢很多。
一个极端的例子是模式’（.-）%$’，它用于获取字符串中第一个$符号前的所有内容。
如果目标字符串中有$符号，那么这个模式工作很正常；但是，如果字符串中没有$符号，那么模式匹配算法就会首先从字符串起始位置开始匹配，直至为了搜索$符号而遍历完整个字符串。当到达字符串结尾时，这次从字符串起始位置开始的模式匹配就失败了。
之后，模式匹配算法又从字符串的第二个位置开始第二次搜索，结果仍然是无法匹配这个模式。这个匹配过程会在字符串的每个位置上进行一次，从而导致O（n2）的时间复杂度。
在笔者的新机器上，搜索20万个字符需要耗费超过4分钟的时间。
要解决这个问题，我们只需使用’^（.-）%$’将模式锚定在字符串的开始位置即可。这样，如果不能从起始位置开始找到匹配，搜索就会停止。有了^的锚定以后，该模式匹配就只需要不到0.01秒的时间了。

此外，还要留心空模式，也就是那些匹配空字符串的模式。
例如，如果试图使用模式’%a*’来匹配名字，那么就会发现到处都是名字：

1
2
i,j = string.find(";$% **#$hello13","%a*")
print(i,j)		--> 1 0

在这个示例中，函数string.find在字符串的开始位置正确地找到一个空的字母序列。

在模式的结束处使用修饰符-是没有意义的，因为这样只会匹配到空字符串。该修饰符总是需要在其后跟上其他的东西来限制扩展的范围。同样，含有’.*’的模式也非常容易出错，这主要是因为这种模式可能会匹配到超出我们预期范围的内容。

Chapter11 小插曲：出现频率最高的单词

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
local counter = {}

for line in io.lines() do
	for	word in string.gmatch(line,"%w+") do
		counter[word] = (counter[word] or 0) + 1
	end
end

local words = {}		-- 文本中所有单词的列表

for w in pairs(counter) do
	words[#words + 1] = w
end

table.sort(words,function(w1,w2)
	return counter[w1] > counter[w2] or (counter[w1] == counter[w2] and w1 < w2)
end)

Chapter12 日期和时间

Lua语言的标准库提供了两个用于操作日期和时间的函数，这两个函数在C语言标准库中也存在，提供的是同样的功能。虽然这两个函数看上去很简单，但依旧可以基于这些简单的功能完成很多复杂的工作。

Lua语言针对日期和时间使用两种表示方式。

第1种表示方式是一个数字，这个数字通常是一个整型数。
尽管并非是ISO C所必需的，但在大多数系统中这个数字是自一个被称为纪元（epoch）的固定日期后至今的秒数。特别地，在POSIX和Windows系统中这个固定日期均是Jan 01,1970,0:00 UTC。

Lua语言针对日期和时间提供的第2种表示方式是一个表。
日期表（date table）具有以下几个重要的字段：year、month、day、hour、min、sec、wday、yday和isdst，除isdst以外的所有字段均为整型数。
前6个字段的含义非常明显，而wday字段表示本周中的第几天（第1天为星期天）；yday字段表示当年中的第几天（第1天是1月1日）；isdst字段表示布尔类型，如果使用夏时令则为真。

例如，Sep 16,1998,23:48:10（星期三）对应的表是：

1
2
{year = 1998,month = 9,day = 16,yday = 259,wday = 4,
 hour = 23,min = 48,sec = 10,isdst = false}

日期表中不包括时区，程序需要负责结合相应的时区对其正确解析。

12.1 函数os.time

不带任何参数调用函数os.time，会以数字形式返回当前的日期和时间：

1
2
local time = os.time()
print(time)	--> 1659428550

对应的时间是08 02,2022,08:22:30。在一个POSIX系统中，可以使用一些基本的数学运算分离这个数值：

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
local date = 1659428550

local day2year = 365.242				-- 一年的天数
local sec2hour = 60 * 60 				-- 一小时的秒数
local sec2day  = sec2hour * 24			-- 一天的秒数
local sec2year = sec2day * day2year		-- 一年的秒数

-- 年
print(date // sec2year + 1970)		--> 2022

-- 小时（UTC格式）
print(date % sec2day // sec2hour)	--> 8

-- 分钟
print(date % sec2hour // 60)		--> 22

-- 秒
print(date % 60)					--> 30

如果以一个日期表作为参数调用函数os.time，那么该函数会返回该表中所描述日期和时间对应的数字。
year、month和day字段是必需的，hour、min和sec字段如果没有提供的话则默认为12:00:00，其余字段（包括wday和yday）则会被忽略。

1
2
local time = os.time({year = 2022,month = 8,day = 2,hour = 8,min = 22,sec = 30})
print(time)	--> 1659399750

12.2 函数os.date

函数os.date在一定程度上是函数os.time的反函数（尽管这个函数的名字写的是date），它可以将一个表示日期和时间的数字转换为某些高级的表示形式，要么是日期表要么是字符串。
该函数的第1个参数是描述期望表示形式的格式化字符串（format string），第2个参数是数字形式的日期和时间（如果不提供，则默认为当前日期和时间）。
要生成一个日期表，可以使用格式化字符串”*t”。例如，调用函数os.date（”*t”,906000490）会返回下列表：

1
2
{year = 1998,month = 9,day = 16,yday = 259,wday = 4,
 hour = 23,min = 48,sec = 10,isdst = false}

大致上，对于任何有效的时间t，os.time（os.date（”*t”,t））==t均成立。

对于其他格式化字符串，函数os.date会将日期格式化为一个字符串，该字符串是根据指定的时间和日期信息对特定的指示符进行了替换的结果。
所有的指示符都以百分号开头紧跟一个字母，例如：

1
2
print(os.date("a %A in %B"))			--> a Tuesday in August
print(os.date("%d/%m/%Y",906000490))	-->	17/09/1998

下表列出了主要的指示符，这些指示符使用的时间为1998年9月16日（星期三）23:48:10。
【函数os.date的指示符】

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
%a		星期几的简写（例：Wed）
%A		星期几的全名（例：Wednesday）
%b		月份的简写（例：Sep）
%B		月份的全名（例：September）
%c		日期和时间（例：09/16/98 23：48:18）
%d		一个月中的第几天（16）[01-31]
%H		24小时制中的小时数（23）[00-23]
%I		12小时制中的小时数（11）[01-12]
%j		一年中的第几天（259）[001-365]
%m		月份（09）[01-12]
%M		分钟（48）[00-59]
%p		"am"或"pm"（pm）
%S		秒数（10）[00-60]
%w		星期（3）[0-6 = Sunday-Saturday]
%W		一年中的第几周（37）[00-53]
%x		日期（例：09/16/98）
%X		时间（例：23:48:10）
%y		两位数的年份（98）[00-99]
%Y		完整的年份（1998）
%z		时区（例：-0300）
%%		百分号

如果格式化字符串以叹号开头，那么函数os.date会以UTC格式对其进行解析：

1
2
-- 纪元
print(os.date("!%c",0))	--> 01/01/70 00:00:00

如果不带任何参数调用函数os.date，那么该函数会使用格式%c，即以一种合理的格式表示日期和时间信息。
请注意，%x、%X和%c会根据不同的区域和系统而发生变化。如果需要诸如dd/mm/yyyy这样的固定表示形式，那么就必须显式地使用诸如”%d/%m/%Y”这样的格式化字符串。

12.3 日期和时间处理

当函数os.date创建日期表时，该表的所有字段均在有效的范围内。当我们给函数os.time传入一个日期表时，其中的字段并不需要归一化。这个特性对于日期和时间处理非常重要。

函数os.difftime用来计算两个时间之间的差值，该函数以秒为单位返回两个指定数字形式表示的时间的差值。
对于大多数系统而言，这个差值就是一个时间相对于另一个时间的减法结果。但是，与减法不同，函数os.difftime的行为在任何系统中都是确定的。

我们还可以使用函数os.difftime来计算一段代码的执行时间。
不过，对于这个需求，更好的方式是使用函数os.clock，该函数会返回程序消耗的CPU时间（单位是秒）。
函数os.clock在性能测试（benchmark）中的典型用法形如：

1
2
3
4
5
6
local x = os.clock()
local s = 0
for i = 1,100000 do
	s = s + 1
end
print(string.format("elapsed time: %.2f\n",os.clock() - x))	-->	elapsed time: 0.81

与函数os.time不同，函数os.clock通常具有比秒更高的精度，因此其返回值为一个浮点数。具体的精度与平台相关，在POSIX系统中通常是1毫秒。

Chapter13 位和字节

Lua语言处理二进制数据的方式与处理文本的方式类似。
Lua语言中的字符串可以包含任意字节，并且几乎所有能够处理字符串的库函数也能处理任意字节。我们甚至可以对二进制数据进行模式匹配。

13.1 位运算

Lua语言从5.3版本开始提供了针对数值类型的一组标准位运算符（bitwise operator）。
与算术运算符不同的是，位运算符只能用于整型数。
位运算符包括＆（按位与）、|（按位或）、～（按位异或）、>>（逻辑右移）、<<（逻辑左移）和一元运算符～（按位取反）。
（请注意，在其他一些语言中，异或运算符为^，而在Lua语言中^代表幂运算。）

两个移位操作都会用0填充空出的位，这种行为通常被称为逻辑移位（logical shift）。
Lua语言没有提供算术右移（arithmetic right shift），即使用符号位填充空出的位。

如果移位数等于或大于整型表示的位数（标准Lua为64位，精简Lua为32位），由于所有的位都被从结果中移出了，所以结果是0。

13.2 无符号整型数

整型表示中使用一个比特来存储符号位。
因此，64位整型数最大可以表示2^63-1而不是2^64-1。通常，这点区别是无关紧要的，因为2^63-1已经相当大了。

不过，由于我们可能需要处理使用无符号整型表示的外部数据或实现一些需要64位整型数的算法，因而有时也不能浪费这个符号位。
此外，在精简Lua中，这种区别可能会很重要。
例如，如果用一个32位有符号整型数表示文件中的位置，那么能够操作的最大文件大小就是2GB；而一个无符号整型数能操作的最大文件大小则是有符号整型数的2倍，即4GB。

13.3 打包和解包二进制数据

Lua 5.3还引入了一个在二进制数和基本类型值（数值和字符串类型）之间进行转换的函数。
函数string.pack会把值“打包（pack）”为二进制字符串，而函数string.unpack则从字符串中提取这些值。
函数string.pack和函数string.unpack的第1个参数是格式化字符串，用于描述如何打包数据。
格式化字符串中的每个字母都描述了如何打包/解包一个值，例如：

1
2
3
s = string.pack("iii",3,-27,450)
#s		--> 12
string.unpack("iii",s)		--> 3 -27 450 13

13.4 二进制文件

函数io.input和io.output总是以文本方式（text mode）打开文件。
在POSIX操作系统中，二进制文件和文本文件是没有差别的。
然而，在其他一些像Windows之类的操作系统中，必须用特殊方式来打开二进制文件，即在io.open的模式字符串中使用字母b。

Chapter14 数据结构

Lua语言中的表并不是一种数据结构，它们是其他数据结构的基础。
我们可以用Lua语言中的表来实现其他语言提供的数据结构，如数组、记录、列表、队列、集合等。而且，用Lua语言中的表实现这些数据结构还很高效。

14.1 数组

在Lua语言中，简单地使用整数来索引表即可实现数组。因此，数组的大小不用非得是固定的，而是可以按需增长的。

14.2 矩阵及多维数组

在Lua语言中，有两种方式来表示矩阵。

第一种方式是使用一个不规则数组（jagged array），即数组的数组，也就是一个所有元素均是另一个表的表。

在Lua中表示矩阵的第二种方式是将两个索引合并为一个。
典型情况下，我们通过将第一个索引乘以一个合适的常量再加上第二个索引来实现这种效果。

14.3 链表

由于表是动态对象，所以在Lua语言中可以很容易地实现链表（linked list）。
我们可以把每个节点用一个表来表示（也只能用表表示），链接则为一个包含指向其他表的引用的简单表字段。

14.4 队列及双端队列

在Lua语言中实现队列（queue）的一种简单方法是使用table标准库中的函数insert和remove。
正如我们在5.6节中所看到的，这两个函数可以在一个数组的任意位置插入或删除元素，同时根据所做的操作移动其他元素。不过，这种移动对于较大的结构来说开销很大。
一种更高效的实现是使用两个索引，一个指向第一个元素，另一个指向最后一个元素。

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
-- 一个双端队列
function ListNew()
	return {first = 0,last = -1};
end

function PushFirst(list,value)
	local first = list.first - 1;
	list.first = first;
	list[first] = value;
end

function PushLast(list,value)
	local last = list.last + 1;
	list.last = last;
	list[last] = value;
end

function PopFirst(list)
	local first = list.first;
	if first > list.last then
		error("list is empty");
	end
	local value = list[first];
	list[first] = nil;		--使得元素能够被垃圾回收
	list.first = first + 1;
	return value;
end

function PopLast(list)
	local last = list.last;
	if list.first > last then
		error("list is empty");
	end
	local value = list[last];
	list[last] = nil;		--使得元素能够被垃圾回收
	list.last = last - 1;
	return value;
end

14.5 反向表

正如此前提到的，我们很少在Lua语言中进行搜索操作。相反，我们使用被称为索引表（index table）或反向表（reverse table）的数据结构。

1
2
3
4
5
6
7
-- 反向表
local days = {"Sunday","Monday","Tuesday","Wednesday","Thursday","Friday","Saturday"};

local revDays = {}
for k,v in pairs(days) do
	revDays[v] = k;
end

14.6 集合与包

假设我们想列出一个程序源代码中的所有标识符，同时过滤掉其中的保留字。
一些C程序员可能倾向于使用字符串数组来表示保留字集合，然后搜索这个数组来决定某个单词是否属于该集合。
为了提高搜索的速度，他们还可能会使用二叉树来表示该集合。

在Lua语言中，还可以用一种高效且简单的方式来表示这类集合，即将集合元素作为索引放入表中。
那么，对于指定的元素无须再搜索表，只需用该元素检索表并检查结果是否为nil即可。

以上述需求为例，代码形如：

1
2
3
4
5
6
7
-- 集合
local reserved = {
	["while"] = true,
	["if"] = true,
	["else"] = true,
	["do"] = true,
}

包（bag），也被称为多重集合（multiset），与普通集合的不同之处在于其中的元素可以出现多次。在Lua语言中，包的简单表示类似于此前集合的表示，只不过其中的每一个键都有一个对应的计数器。

14.7 字符串缓冲区

假设我们正在开发一段处理字符串的程序，比如逐行地读取一个文件。
典型的代码可能形如：

1
2
3
4
local buff = "";
for line in io.lines() do
	buff = buff..line.."\n";
end

虽然这段Lua语言代码看似能够正常工作，但实际上在处理大文件时却可能导致巨大的性能开销。例如，在笔者的新机器上用这段代码读取一个4.5MB大小的文件需要超过30秒的时间。

这是为什么呢？为了搞清楚到底发生了什么，让我们想象一下读取循环中发生了什么。
假设每行有20字节，当我们读取了大概2500行后，buff就会变成一个50KB大小的字符串。
在Lua语言中进行字符串连接buff..line..”\n”时，会创建一个50020字节的新字符串，然后从buff中复制50000字节中到这个新字符串中。
这样，对于后续的每一行，Lua语言都需要移动大概50KB且还在不断增长的内存。
因此，该算法的时间复杂度是二次方的。
在读取了100行（仅2KB）以后，Lua语言就已经移动了至少5MB内存。当Lua语言完成了350KB的读取后，它已经至少移动了50GB的数据。
（这个问题不是Lua语言特有的：在其他语言中，只要字符串是不可变值（immutable value），就会出现类似的问题，其中最有名的例子就是Java。）

在继续学习之前，我们必须说明，上述场景中的情况并不常见。
对于较小的字符串，上述循环并没什么问题。
当读取整个文件时，Lua语言提供了带有参数的函数io.read（”a”）来一次性地读取整个文件。
不过，有时候我们必须面对这个问题。
Java提供了StringBuffer类来解决这个问题；而在Lua语言中，我们可以把一个表当作字符串缓冲区，其关键是使用函数table.concat，这个函数会将指定列表中的所有字符串连接起来并返回连接后的结果。

使用函数concat可以这样重写上述循环：

1
2
3
4
5
local t = {};
for line in io.lines() do
	t[#t + 1] = line .. "\n";
end
local s = table.concat(t);

我们还可以做得更好。函数concat还有第2个可选参数，用于指定插在字符串间的分隔符。有了这个分隔符，我们就不必在每行后插入换行符了。

1
2
3
4
5
local t = {};
for line in io.lines() do
	t[#t + 1] = line;
end
local s = table.concat(t,"\n").."\n";

虽然函数concat能够在字符串之间插入分隔符，但我们还需要增加最后一个换行符。
最后一次字符串连接创建了结果字符串的一个副本，这个副本可能已经相当长了。
虽然没有直接的选项能够让函数concat插入这个额外的分隔符，但我们可以想办法绕过，只需在字符串t后面添加一个空字符串就行了：

1
2
t[#t + 1] = "";
s = table.concat(t,"\n");

14.8 图形

我们使用一个由两个字段组成的表来表示每个节点，即name（节点的名称）和adj（与此节点邻接的节点的集合）。
由于我们会从一个文本文件中加载图对应的数据，所以需要能够根据节点的名称来寻找指定节点的方法。
因此，我们使用了一个额外的表来建立节点和节点名称之间的映射。
函数name2node可以根据指定节点的名称返回对应的节点：

1
2
3
4
5
6
7
8
9
local function name2node(graph,name)
	local node = graph[name];
	if not node then
		--节点不存在，创建一个新节点
		node = {name = name,adj = {}};
		graph[name] = node;
	end
	return node;
end

从文件中加载图：

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
function ReadGraph()
	local graph = {};
	
	for line in io.lines() do
		--把一行分割为两个名字
		local nameform,nameto = string.match(line,"(%S+)%s+(%S+)");
		--找到对应节点
		local from = name2node(graph,nameform);
		local to = name2node(graph,nameto);
		--把'to'增加到邻接集合'from'中
		from.adj[to] = true;
	end

	return graph;
end

寻找两个节点之间的路径：

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
function findpath(curr,to,path,visited)
	path = path or {};
	visited = visited or {};

	if visited[curr] then--是否节点已被访问
		return nil;
	end
	visited[curr] = true;--标记节点为已被访问
	path[#path+1] = curr;
	if curr == to then
		return path;
	end
	--尝试所有的邻接节点
	for node in pairs(curr.adj) do
		local p = findpath(node,to,path,visited);

		if p then
			return p;
		end
	end
	table.remove(path);--从路径中删除节点
end

函数findpath使用深度优先遍历搜索两个节点之间的路径。
该函数的第1个参数是当前节点，第2个参数是目标节点，第3个参数用于保存从起点到当前节点的路径，最后一个参数为所有已被访问节点的集合（用于避免回路）。

Chapter15 数据文件和序列化

15.2 序列化

我们可以使用一种安全的方法来括住一个字符串，那就是使用函数string.format的”%q”选项。
该选项被设计为以一种能够让Lua语言安全地反序列化字符串的方式来序列化字符串，它使用双引号括住字符串并正确地转义其中的双引号和换行符等其他字符。

1
2
local a = 'a "problematic" \\string';
print(string.format("%q",a));	--> "a \"problematic\" \\string"

Lua 5.3.3对格式选项”%q”进行了扩展，使其也可以用于数值、nil和Boolean类型，进而使它们能够正确地被序列化和反序列化。（特别地，这个格式选项以十六进制格式处理浮点类型以保留完整的精度。）

Chapter16 编译、执行和错误

虽然我们把Lua语言称为解释型语言（interpreted language），但Lua语言总是在运行代码前先预编译（precompile）源码为中间代码（这没什么大不了的，很多解释型语言也这样做）。
编译（compilation）阶段的存在听上去超出了解释型语言的范畴，但解释型语言的区分并不在于源码是否被编译，而在于是否有能力（且轻易地）执行动态生成的代码。
可以认为，正是由于诸如dofile这样函数的存在，才使得Lua语言能够被称为解释型语言。

16.1 编译

此前，我们已经介绍过函数dofile，它是运行Lua代码段的主要方式之一。
实际上，函数dofile是一个辅助函数，函数loadfile才完成了真正的核心工作。
与函数dofile类似，函数loadfile也是从文件中加载Lua代码段，但它不会运行代码，而只是编译代码，然后将编译后的代码段作为一个函数返回。
此外，与函数dofile不同，函数loadfile只返回错误码而不抛出异常。
可以认为，函数dofile就是：

1
2
3
4
function dofile(filename)
	local f = assert(loadfile(filename));
	return f();
end

对于简单的需求而言，由于函数dofile在一次调用中就做完了所有工作，所以该函数非常易用。不过，函数loadfile更灵活。
在发生错误的情况中，函数loadfile会返回nil及错误信息，以允许我们按自定义的方式来处理错误。
此外，如果需要多次运行同一个文件，那么只需调用一次loadfile函数后再多次调用它的返回结果即可。
由于只编译一次文件，因此这种方式的开销要比多次调用函数dofile小得多（编译在某种程度上相比其他操作开销更大）。

通常，用函数load来加载字符串常量是没有意义的。
例如，如下的两行代码基本等价：

1
2
3
4
f = load("i = i + 1");
f = function ()
	i = i + 1
end

但是，由于第2行代码会与其外层的函数一起被编译，所以其执行速度要快得多。与之对比，第一段代码在调用函数load时会进行一次独立的编译。

由于函数load在编译时不涉及词法定界，所以上述示例的两段代码可能并不完全等价。
为了清晰地展示它们之间的区别，让我们稍微修改一下上面的例子：

1
2
3
4
5
6
7
8
9
i = 32;
local i = 0;
f = load("i = i + 1;print(i)");
g = function ()
	i = i + 1;
	print(i);
end
f()		--> 33
g()		--> 1

函数g像我们所预期地那样操作局部变量i，但函数f操作的却是全局变量i，这是由于函数load总是在全局环境中编译代码段。

我们也可以使用读取函数（reader function）作为函数load的第1个参数。
读取函数可以分几次返回一段程序，函数load会不断地调用读取函数直到读取函数返回nil（表示程序段结束）。
作为示例，以下的调用与函数loadfile等价：

1
f = load(io.lines(filename,"*L"));

函数load和函数loadfile从来不引发错误。当有错误发生时，它们会返回nil及错误信息：

1
2
print(load("i i"));
--> nil [string "i i"]:1: '=' expected near 'i'

此外，这些函数没有任何副作用，它们既不改变或创建变量，也不向文件写入等。
这些函数只是将程序段编译为一种中间形式，然后将结果作为匿名函数返回。
一种常见的误解是认为加载一段程序也就是定义了函数，但实际上在Lua语言中函数定义是在运行时而不是在编译时发生的一种赋值操作。
例如，假设有一个文件foo.lua：

1
2
3
function foo(x)
	print(x);
end

当执行

1
f = loadfile("foo.lua");

时，编译foo的命令并没有定义foo，只有运行代码才会定义它：

1
2
3
4
f = loadfile("foo.lua");
print(foo);	--> nil
f();	-- 运行代码
foo("ok")	--> ok

16.2 预编译的代码

16.3 错误

16.4 错误处理和异常

假设要执行一段Lua代码并捕获（try-catch）执行中发生的所有错误，那么首先需要将这段代码封装到一个函数中，这个函数通常是一个匿名函数。
之后，通过pcall来调用这个函数：

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
local ok,msg = pcall(function ()
	some code
	if unexpected_condition then
		error();
	end
	some code
	print(a[i]);	-- 潜在错误：'a'可能不是一个表
	some code
end)

if ok then-- 执行被保护的代码时没有错误发生
	regular code
else-- 执行被保护的代码时有错误发生：进行恰当的处理
	error-handling code
end

函数pcall会以一种保护模式（protected mode）来调用它的第1个参数，以便捕获该函数执行中的错误。无论是否有错误发生，函数pcall都不会引发错误。
如果没有错误发生，那么pcall返回true及被调用函数（作为pcall的第1个参数传入）的所有返回值；
否则，则返回false及错误信息。

16.5 错误信息和栈回溯

通常，除了发生错误的位置以外，我们还希望在错误发生时得到更多的调试信息。至少，我们希望得到具有发生错误时完整函数调用栈的栈回溯（traceback）。
当函数pcall返回错误信息时，部分的调用栈已经被破坏了（从pcall到出错之处的部分）。
因此，如果希望得到一个有意义的栈回溯，那么就必须在函数pcall返回前先将调用栈构造好。
为了完成这个需求，Lua语言提供了函数xpcall。该函数与函数pcall类似，但它的第2个参数是一个消息处理函数（message handler function）。
当发生错误时，Lua会在调用栈展开（stack unwind）前调用这个消息处理函数，以便消息处理函数能够使用调试库来获取有关错误的更多信息。
两个常用的消息处理函数是debug.debug和debug.traceback，前者为用户提供一个Lua提示符来让用户检查错误发生的原因；
后者则使用调用栈来构造详细的错误信息，Lua语言的独立解释器就是使用这个函数来构造错误信息的。

Chapter17 模块和包

从用户观点来看，一个模块（module）就是一些代码（要么是Lua语言编写的，要么是C语言编写的），这些代码可以通过函数require加载，然后创建和返回一个表。
这个表就像是某种命名空间，其中定义的内容是模块中导出的东西，比如函数和常量。

使用表来实现模块的显著优点之一是，让我们可以像操作普通表那样操作模块，并且能利用Lua语言的所有功能实现额外的功能。
在大多数语言中，模块不是第一类值（即它们不能被保存在变量中，也不能被当作参数传递给函数等），所以那些语言需要为模块实现一套专门的机制。
而在Lua语言中，我们则可以轻易地实现这些功能。

17.1 函数require

  • 函数require尝试对模块的定义做最小的假设。

对于该函数来说，一个模块可以是定义了一些变量（比如函数或者包含函数的表）的代码。
典型地，这些代码返回一个由模块中函数组成的表。
不过，由于这个动作是由模块的代码而不是由函数require完成的，所以某些模块可能会选择返回其他的值或者甚至引发副作用（例如，通过创建全局变量）。

  • 首先，函数require在表package.loaded中检査模块是否已被加载。

如果模块已经被加载，函数require就返回相应的值。
因此，一旦一个模块被加载过，后续的对于同一模块的所有require调用都将返回同一个值，而不会再运行任何代码。

  • 如果模块尚未加载，那么函数require则搜索具有指定模块名的Lua文件（搜索路径由变量package.path指定，我们会在后续对其进行讨论）。

如果函数require找到了相应的文件，那么就用函数loadfile将其进行加载，结果是一个我们称之为加载器（loader）的函数（加载器就是一个被调用时加载模块的函数）。

如果函数require找不到指定模块名的Lua文件，那么它就搜索相应名称的C标准库。（在这种情况下，搜索路径由变量package.cpath指定。）
如果找到了一个C标准库，则使用底层函数package.loadlib进行加载，这个底层函数会查找名为luaopen_modname的函数。
在这种情况下，加载函数就是loadlib的执行结果，也就是一个被表示为Lua函数的C语言函数luaopen_modname。

不管模块是在Lua文件还是C标准库中找到的，函数require此时都具有了用于加载它的加载函数。
为了最终加载模块，函数require带着两个参数调用加载函数：模块名和加载函数所在文件的名称（大多数模块会忽略这两个参数）。
如果加载函数有返回值，那么函数require会返回这个值，然后将其保存在表package.loaded中，以便于将来在加载同一模块时返回相同的值。
如果加载函数没有返回值且表中的package.loaded[@rep{modname}]为空，函数require就假设模块的返回值是true。
如果没有这种补偿，那么后续调用函数require时将会重复加载模块。

17.1.1 模块重命名

为了进行这种重命名，函数require运用了一个连字符的技巧：如果一个模块名中包含连字符，那么函数require就会用连字符之前的内容来创建luaopen_*函数的名称。
例如，如果一个模块的名称为mod-v3.4，那么函数require会认为该模块的加载函数应该是luaopen_mod而不是luaopen_mod-v3.4（这也不是有效的C语言函数名）。
因此，如果需要使用两个名称均为mod的模块（或相同模块的两个不同版本），那么可以对其中的一个进行重命名，如mod-v1。
当调用m1=require”mod-v1”时，函数require会找到改名后的文件mod-v1并将其中原名为luaopen_mod的函数作为加载函数。

17.1.2 搜索路径

在搜索一个Lua文件时，函数require使用的路径与典型的路径略有不同。典型的路径是很多目录组成的列表，并在其中搜索指定的文件。
不过，ISO C（Lua语言依赖的抽象平台）并没有目录的概念。
所以，函数require使用的路径是一组模板（template），其中的每项都指定了将模块名（函数require的参数）转换为文件名的方式。
更准确地说，这种路径中的每一个模板都是一个包含可选问号的文件名。
对于每个模板，函数require会用模块名来替换每一个问号，然后检查结果是否存在对应的文件；如果不存在，则尝试下一个模板。
路径中的模板以在大多数操作系统中很少被用于文件名的分号隔开。

例如，考虑如下路径：

1
?;?.lua;c:\windows\?;/usr/local/lua/?/?.lua

在使用这个路径时，调用require”sql”将尝试打开如下的Lua文件：

1
2
3
4
sql
sql.lua
c:\windows\sql
/usr/local/lua/sql/sql.lua

函数require只处理分号（作为分隔符）和问号，所有其他的部分（包括目录分隔符和文件扩展名）则由路径自己定义。

函数require用于搜索Lua文件的路径是变量package.path的当前值。

搜索C标准库的路径的逻辑与此相同，只不过C标准库的路径来自变量package.cpath而不是package.path。

函数package.searchpath中实现了搜索库的所有规则，该函数的参数包括模块名和路径，然后遵循上述规则来搜索文件。
函数package.searchpath要么返回第一个存在的文件的文件名，要么返回nil外加描述所有文件都无法成功打开的错误信息。

17.1.3 搜索器

数组package.searchers列出了函数require使用的所有搜索器。
在寻找模块时，函数require传入模块名并调用列表中的每一个搜索器直到它们其中的一个找到了指定模块的加载器。
如果所有搜索器都被调用完后还找不到，那么函数require就抛出一个异常。

预加载（preload）搜索器使得我们能够为要加载的模块定义任意的加载函数。
预加载搜索器使用一个名为package.preload的表来映射模块名称和加载函数。
当搜索指定的模块名时，该搜索器只是简单地在表中搜索指定的名称。如果它找到了对应的函数，那么就将该函数作为相应模块的加载函数返回；否则，则返回nil。
预加载搜索器为处理非标场景提供了一种通用的方式。
例如，一个静态链接到Lua中的C标准库可以将其luaopen_函数注册到表preload中，这样luaopen_函数只有当用户加载这个模块时才会被调用。
用这种方式，程序不会为没有用到的模块浪费资源。

17.2 Lua语言中编写模块的基本方法

17.3 子模块和包