Chapter18 迭代器和泛型for

18.1 迭代器和闭包

迭代器（iterator）是一种可以让我们遍历一个集合中所有元素的代码结构。

所有的迭代器都需要在连续的调用之间保存一些状态，这样才能知道当前迭代所处的位置及如何从当前位置步进到下一位置。
对于函数io.read而言，C语言会将状态保存在流的结构体中。
对于我们自己的迭代器而言，闭包则为保存状态提供了一种良好的机制。
请注意，一个闭包就是一个可以访问其自身的环境中一个或多个局部变量的函数。这些变量将连续调用过程中的值并将其保存在闭包中，从而使得闭包能够记住迭代所处的位置。
当然，要创建一个新的闭包，我们还必须创建非局部变量。
因此，一个闭包结构通常涉及两个函数：闭包本身和一个用于创建该闭包及其封装变量的工厂（factory）。

作为示例，让我们来为列表编写一个简单的迭代器。
与ipairs不同的是，该迭代器并不是返回每个元素的索引而是返回元素的值：

1
2
3
4
5
6
7
8
9
function values(t)
    local i = 0;

    return function ()
        i = i + 1;
        return t[i];
    end
end

在这个例子中，values就是工厂。
每当调用这个工厂时，它就会创建一个新的闭包（即迭代器本身）。
这个闭包将它的状态保存在其外部的变量t和i中，这两个变量也是由values创建的。
每次调用这个迭代器时，它就从列表t中返回下一个值。
在遍历完最后一个元素后，迭代器返回nil，表示迭代结束。

1
2
3
4
5
6
7
8
9
10
11
12
13
14
t = {10,20,30};

iter = values(t);--创建迭代器

while true do
    local element = iter();--调用迭代器

    if element == nil then
        break;
    end

    print(element);
end

不过，使用泛型for更简单。毕竟，泛型for正是为了这种迭代而设计的：

1
2
3
for element in values(t) do
    print(element);
end

泛型for为一次迭代循环做了所有的记录工作：它在内部保存了迭代函数，因此不需要变量iter；它在每次做新的迭代时都会再次调用迭代器，并在迭代器返回nil时结束循环。

18.2 泛型for的语法

泛型for在循环过程中在其内部保存了迭代函数。
实际上，泛型for保存了三个值：一个迭代函数、一个不可变状态（invariant state）和一个控制变量（control variable）。

下面让我们进行进一步学习。
泛型for的语法如下：

1
2
3
for var-list in exp-list do
	body
end

其中，var-list是由一个或多个变量名组成的列表，以逗号分隔；exp-list是一个或多个表达式组成的列表，同样以逗号分隔。
通常，表达式列表只有一个元素，即一句对迭代器工厂的调用。

例如，在如下代码中，变量列表是k,v，表达式列表只有一个元素pairs（t）：

1
2
3
for k,v in pairs(t) do
	print(k,v)
end

我们把变量列表的第一个（或唯一的）变量称为控制变量（ control variable），其值在循环过程中永远不会是nil，因为当其值为nil时循环就结束了。
for做的第一件事情是对in后面的表达式求值。这些表达式应该返回三个值供for保存：迭代函数、不可变状态和控制变量的初始值。

因此，假设迭代函数为f，不可变状态为s，控制变量的初始值为a0，那么在循环中控制变量的值依次为a1=f（s,a0）,a2=f（s,a1），依此类推，直至ai为nil。
如果for还有其他变量，那么这些变量只是简单地在每次调用f后得到额外的返回值。

18.3 无状态迭代器

顾名思义，无状态迭代器（stateless iterator）就是一种自身不保存任何状态的迭代器。
因此，可以在多个循环中使用同一个无状态迭代器，从而避免创建新闭包的开销。

正如刚刚所看到的，for循环会以不可变状态和控制变量为参数调用迭代函数。
一个无状态迭代器只根据这两个值来为迭代生成下一个元素。
这类迭代器的一个典型例子就是ipairs，它可以迭代一个序列中的所有元素：

1
2
3
4
a = {"one","two","three"};
for index, value in ipairs(a) do
	print(index,value);
end

迭代的状态由正在被遍历的表（一个不可变状态，它不会在循环中改变）及当前的索引值（控制变量）组成。
ipairs（工厂）和迭代器都非常简单，我们可以在Lua语言中将其编写出来：

1
2
3
4
5
6
7
8
9
10
11
local function iter(t,i)
	i = i + 1;
	local v = t[i];
	if v then
		return i,v;
	end
end

function ipairs(t)
	return iter,t,0;
end

当调用for循环中的ipairs（t）时，ipairs（t）会返回三个值，即迭代函数iter、不可变状态表t和控制变量的初始值0。
然后，Lua语言调用iter（t,0），得到1,t[1]（除非t[1]已经变成了nil）。
在第二次迭代中，Lua语言调用iter（t,1），得到2,t[2]，依此类推，直至得到第一个为nil的元素。

函数pairs与函数ipairs类似，也用于遍历一个表中的所有元素。
不同的是，函数pairs的迭代函数是Lua语言中的一个基本函数next：

1
2
3
function pairs(t)
	return next,t,nil
end

在调用next（t,k）时，k是表t的一个键，该函数会以随机次序返回表中的下一个键及k对应的值（作为第二个返回值）。
调用next（t,nil）时，返回表中的第一个键值对。
当所有元素被遍历完时，函数next返回nil。

我们可以不调用pairs而直接使用next：

1
2
3
for key, value in next,t do
	loop body
end

请注意，for循环会把表达式列表的结果调整为三个值，因此上例中得到的是next、t和nil，这也正与pairs（t）的返回值完全一致。

18.4 按顺序遍历表

一个常见的困惑发生在开发人员想要对表中的元素进行排序时。
由于一个表中的元素没有顺序，所以如果想对这些元素排序，就不得不先把键值对拷贝到一个数组中，然后再对数组进行排序。

假设我们要读取一个源文件，然后构造一个表来保存每个函数的名称及其声明所在的行数，形式如下：

1
2
3
4
5
lines = {
	["luaH_set"] = 10,
	["luaH_get"] = 24,
	["luaH_present"] = 48,
}

现在，我们想按照字母顺序输出这些函数名。
如果使用pairs遍历表，那么函数名会按照随机的顺序出现。
由于这些函数名是表的键，所以我们无法直接对其进行排序。
不过，如果我们把它们放到数组中，那么就可以对它们进行排序了。

首先，我们必须创建一个包含函数名的数组，然后对其排序，再最终输出结果。

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
lines = {
	["luaH_set"] = 10,
	["luaH_get"] = 24,
	["luaH_present"] = 48,
}

a = {};

for n in pairs(lines) do
	a[#a + 1] = n;
end

table.sort(a);

for _,n in ipairs(a) do
	print(n);
end

有些人可能会困惑。毕竟，对于Lua语言来说，数组也没有顺序（毕竟它们是表）。
但是我们知道如何数数！因此，当我们使用有序的索引访问数组时，就实现了有序。
这正是应该总是使用ipairs而不是pairs来遍历数组的原因。
第一个函数通过有序的键1、2等来实现有序，然而后者使用的则是天然的随机顺序（虽然大多数情况下顺序随机也无碍，但有时可能并非我们想要的）。

现在，我们已经准备好写一个按照键的顺序来遍历表的迭代器了：

1
2
3
4
5
6
7
8
9
10
11
function pairsByKeys(t,f)
	local a = {};
	for n in pairs(t) do 	--创建一个包含所有键的表
		a[#n + 1] = n;
	end
	table.sort(a,f);		--对列表排序
	local i = 0;			--迭代变量
	return	function ()		--迭代函数
		i = i + 1;
		return a[i],t[a[i]]	--返回键和值
	end

Chapter19 小插曲：马尔可夫链算法

马尔可夫链算法根据哪个单词能出现在基础文本中由 n个前序单词组成的序列之后，来生成伪随机（pseudo-random）文本。
对于本例中的实现，我们假定n为2。

程序的第一部分读取原始文本并创建一个表，该表的键为每两个单词组成的前缀，值为紧跟这个前缀的单词所组成的列表。
当这个表构建好后，程序就利用它来生成随机文本，随机文本中每个单词出现在它之前两个单词后的概率与其出现在基础文本中相同两个前序单词后的概率相同。
最终，我们会得到一串相对比较随机的文本。例如，以本书的英文原版作为基础文本，那么该程序的输出形如“Constructorscan also traverse a table constructor,thenthe parentheses in the following line does the whole file in a field n to store the contents of each function,but to show its only argument.If you want to find the maximum element in an array can return both the maximum value and continues showing the prompt and running the code.The following words are reserved and cannot be used to convert between degrees and radians.”

要将由两个单词组成的前缀作为表的键，需要使用空格来连接两个单词：

1
2
3
function prefix(w1,w2)
	return w1 .." "..w2
end

我们使用字符串NOWORD（换行符）初始化前缀单词及标记文本的结尾。例如，对于文本”the more we try the more we do”而言，构造出的表如下：

1
2
3
4
5
6
7
8
{
	["\n \n"] = {"the"},
	["\n the"] = {"more"},
	["the more"] = {"we","we"},
	["we try"] = {"the"},
	["try the"] = {"more"},
	["we do"] = {"\n"},
}

程序将表保存在变量statetab中。如果要向表中的某个前缀所对应的列表中插入一个新单词，可以使用如下的函数：

1
2
3
4
5
6
7
8
function insert(prefix,value)
	local list = statetab[prefix];
	if list == nil then
		statetab[prefix] = {value};
	else
		list[#list+1] = value;
	end
end

为了构造表statetab，我们使用两个变量w1和w2来记录最后读取的两个单词。
我们使用18.1节中的allwords迭代器读取单词，只不过修改了其中“单词”的定义以便将可选的诸如逗号和句号等标点符号包括在内（参见示例19.1）。
对于新读取的每一个单词，把它添加到与w1–w2相关联的列表中，然后更新w1和w2。

在构造完表后，程序便开始生成具有MAXGEN个单词的文本。
首先，程序重新初始化变量w1和w2。
然后，对于每个前缀，程序从其对应的单词列表中随机地选出一个单词，输出这个单词，并更新w1和w2。

示例19.1和示例19.2给出了完整的程序。

19.1 马尔可夫链程序的辅助定义

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
function allwords()
	local line = io.read()			--当前行
	local pos = 1					--当前行的当前位置

	return function ()				--迭代函数
		while line do				--当还有行时循环
			local w,e = string.match(line,"(%w+[,;.:]?)()",pos)
			if w then				--发现一个单词
				pos = e				--更新位置
				return w			--返回该单词
			else
				line = io.read() 	--没找到单词;尝试下一行
				pos = 1				--从第一个位置重新开始
			end
		end

		return nil;					--没有行了：迭代结束
	end
end

function prefix(w1,w2)
	return w1 .." "..w2
end

local statetab = {}

function insert(prefix,value)
	local list = statetab[prefix];
	if list == nil then
		statetab[prefix] = {value};
	else
		list[#list+1] = value;
	end
end

19.2　马尔可夫链程序

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
local MAXGEN = 200
local NOWORD = "\n"

--创建表
local w1,w2 = NOWORD,NOWORD
for nextword in allwords() do
	insert(prefix(w1,w2),nextword);
	w1 = w2;w2 = nextword;
end
insert(prefix(w1,w2),NOWORD);

--生成文本
w1 = NOWORD;w2 = NOWORD--重新初始化
for i = 1, MAXGEN, 1 do
	local list = statetab[prefix(w1,w2)]
	--从列表中随机挑选出一个元素
	local r = math.random(#list)
	local nextword = list[r]
	if nextword == NOWORD then
		return;
	end
	io.write(nextword," ")
	w1 = w2;w2 = nextword
end

Chapter20 元表和元方法

通常，Lua语言中的每种类型的值都有一套可预见的操作集合。

元表可以修改一个值在面对一个未知操作时的行为。
例如，假设a和b都是表，那么可以通过元表定义Lua语言如何计算表达式a+b。
当Lua语言试图将两个表相加时，它会先检查两者之一是否有元表（metatable）且该元表中是否有__add字段。
如果Lua语言找到了该字段，就调用该字段对应的值，即所谓的元方法（metamethod）（是一个函数），在本例中就是用于计算表的和的函数。

可以认为，元表是面向对象领域中的受限制类。
像类一样，元表定义的是实例的行为。
不过，由于元表只能给出预先定义的操作集合的行为，所以元表比类更受限；同时，元表也不支持继承。

Lua语言中的每一个值都可以有元表。
每一个表和用户数据类型都具有各自独立的元表，而其他类型的值则共享对应类型所属的同一个元表。
Lua语言在创建新表时不带元表：

1
2
t = {}
print(getmetatable(t))	--> nil

可以使用函数setmetatable来设置或修改任意表的元表：

1
2
3
t1 = {}
setmetatable(t,t1)
print(getmetatable(t) == t1);	--> true

在Lua语言中，我们只能为表设置元表；如果要为其他类型的值设置元表，则必须通过C代码或调试库完成
（该限制存在的主要原因是为了防止过度使用对某种类型的所有值生效的元表。Lua语言老版本中的经验表明，这样的全局设置经常导致不可重用的代码）。
字符串标准库为所有的字符串都设罝了同一个元表，而其他类型在默认情况中都没有元表：

1
2
3
4
print(getmetatable("hi"))	--> table:0x80772e0
print(getmetatable("xuxu"))	--> table:0x80772e0
print(getmetatable(10))		--> nil
print(getmetatable(print))		--> nil

一个表可以成为任意值的元表；一组相关的表也可以共享一个描述了它们共同行为的通用元表；一个表还可以成为它自己的元表，用于描述其自身特有的行为。
总之，任何配置都是合法的。

20.1 算术运算相关的元方法

假设有一个用表来表示集合的模块，该模块还有一些用来计算集合并集和交集等的函数。

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
39
40
41
42
43
44
45
46
47
48
49
50
local Set = {}

-- 使用指定的列表创建一个新的集合
function Set.new(l)
	local set = {}
	for _,v in ipairs(l) do
		set[v] = true;
	end

	return set;
end

--并集
function Set.union(a,b)
	local res = Set.new({})

	for k in pairs(a) do
		res[k] = true
	end

	for k in pairs(b) do
		res[k] = true
	end

	return res;
end

--交集
function Set.intersection(a,b)
	local res = Set.new({})

	for k in pairs(a) do
		res[k] = b[k]
	end

	return res
end

--将集合表示为字符串
function Set.tostring(set)
	local l = {}	--保存集合中所有元素的列表

	for e in pairs(set) do
		l[#l + 1] = tostring(e)
	end

	return "{"..table.concat(l,",").."}"
end

return Set

现在，假设想使用加法操作符来计算两个集合的并集，那么可以让所有表示集合的表共享一个元表。
这个元表中定义了这些表应该如何执行加法操作。
首先，我们创建一个普通的表，这个表被用作集合的元表：

1
local mt = {}	--集合的元表

然后，修改用于创建集合的函数Set.new。
在新版本中只多了一行，即将mt设置为函数Set.new所创建的表的元表：

1
2
3
4
5
6
7
8
9
function Set.new(l)
	local set = {}
	setmetatable(set,mt)
	for _,v in ipairs(l) do
		set[v] = true;
	end

	return set;
end

在此之后，所有由Set.new创建的集合都具有了一个相同的元表。

最后，向元表中加入元方法（metamethod）__add，也就是用于描述如何完成加法的字段：

1
mt.__add = Set.union

此后，只要Lua语言试图将两个集合相加，它就会调用函数Set.union，并将两个操作数作为参数传入。

类似地，还可以使用乘法运算符来计算集合的交集：

1
mt.__mul = Set.intersection

每种算术运算符都有一个对应的元方法。
除了加法和乘法外，还有减法（__sub）、除法（__div）、floor除法（__idiv）、负数（__unm）、取模（__mod）和幂运算（__pow）。
类似地，位操作也有元方法：按位与（__band）、按位或（__bor）、按位异或（__bxor）、按位取反（__bnot）、向左移位（__shl）和向右移位（__shr）。
我们还可以使用字段__concat来定义连接运算符的行为。

当我们把两个集合相加时，使用哪个元表是确定的。
然而，当一个表达式中混合了两种具有不同元表的值时，例如：

1
2
s = set.new({1,2,3})
s = s + 8

Lua语言会按照如下步骤来查找元方法：
如果第一个值有元表且元表中存在所需的元方法，那么Lua语言就使用这个元方法，与第二个值无关；
如果第二个值有元表且元表中存在所需的元方法，Lua语言就使用这个元方法；
否则，Lua语言就抛出异常。
因此，上例会调用Set.union，而表达式10+s和”hello”+s同理（由于数值和字符串都没有元方法__add）。

Lua语言不关心这些混合类型，但我们在实现中需要关心混合类型。
如果我们执行了s=s+8，那么在Set.union内部就会发生错误：

1
bad argument #1 to 'pairs'(table expected,got number)

如果想要得到更明确的错误信息，则必须在试图进行操作前显式地检查操作数的类型，例如：

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
function Set.union(a,b)
	local res = Set.new({})

	if getmetatable(a) ~= mt or getmetatable(b) ~= mt then
		error("attempt to 'add' a set with a non-set value",2)
	end

	for k in pairs(a) do
0		res[k] = true
	end

	for k in pairs(b) do
		res[k] = true
	end

	return res;
end

请注意，函数error的第二个参数（上例中的2）说明了出错的原因位于调用该函数的代码中。

20.2 关系运算相关的元方法

元表还允许我们指定关系运算符的含义，其中的元方法包括等于（__eq）、小于（__lt）和小于等于（__le）。
其他三个关系运算符没有单独的元方法，Lua语言会将a～=b转换为not（a==b），a>b转换为b<a，a>=b转换为b<=a。

在Lua语言的老版本中，Lua语言会通过将a<=b转换为not（b<a）来把所有的关系运算符转化为一个关系运算符。
不过，这种转化在遇到部分有序（partial order）时就会不正确。所谓部分有序是指，并非所有类型的元素都能够被正确地排序。
例如，由于Not a Number（NaN）的存在，大多数计算机中的浮点数就不是完全可以排序的。
根据IEEE 754标准，NaN代表未定义的值，例如0/0的结果就是NaN。
标准规定任何涉及NaN的比较都应返回假，这就意味着NaN<=x永远为假，x<NaN也为假。因此，在这种情况下，a<=b到not（b<a）的转化也就不合法了。

相等比较有一些限制。如果两个对象的类型不同，那么相等比较操作不会调用任何元方法而直接返回false。

20.3 库定义相关的元方法

Lua语言虚拟机（virtual machine）会检测一个操作中涉及的值是否有存在对应元方法的元表。
不过，由于元表是一个普通的表，所以任何人都可以使用它们。
因此，程序库在元表中定义和使用它们自己的字段也是一种常见的实践。

函数tostring就是一个典型的例子。
正如我们此前所看到的，函数tostring能将表表示为一种简单的文本格式：

1
print({})	--> table:0x8062ac0

函数print总是调用tostring来进行格式化输出。
不过，当对值进行格式化时，函数tostring会首先检查值是否有一个元方法__tostring。
如果有，函数tostring就调用这个元方法来完成工作，将对象作为参数传给该函数，然后把元方法的返回值作为函数tostring的返回值。

函数setmetatable和getmetatable也用到了元方法，用于保护元表。
假设想要保护我们的集合，就要使用户既不能看到也不能修改集合的元表。
如果在元表中设置__metatable字段，那么getmetatable会返回这个字段的值，而setmetatable则会引发一个错误：

1
2
3
4
s1 = Set.new({})
print(getmetatable(s1))		--> not your business
setmetatable(s1,{})
--stdin:1: cannot change protected metatable

从Lua 5.2开始，函数pairs也有了对应的元方法，因此我们可以修改表被遍历的方式和为非表的对象增加遍历行为。
当一个对象拥有__pairs元方法时，pairs会调用这个元方法来完成遍历。

20.4 表相关的元方法

算术运算符、位运算符和关系运算符的元方法都定义了各种错误情况的行为，但它们都没有改变语言的正常行为。
Lua语言还提供了一种改变表在两种正常情况下的行为的方式，即访问和修改表中不存在的字段。

20.4.1 __index元方法

正如我们此前所看到的，当访问一个表中不存在的字段时会得到nil。这是正确的，但不是完整的真相。
实际上，这些访问会引发解释器查找一个名为__index的元方法。
如果没有这个元方法，那么像一般情况下一样，结果就是nil；否则，则由这个元方法来提供最终结果。

在Lua语言中，使用元方法__index来实现继承是很普遍的方法。
虽然被叫作方法，但元方法__index不一定必须是一个函数，它还可以是一个表。
当元方法是一个函数时，Lua语言会以表和不存在的键为参数调用该函数，正如我们刚刚所看到的。当元方法是一个表时，Lua语言就访问这个表。

如果我们希望在访问一个表时不调用__index元方法，那么可以使用函数rawget。
调用rawget（t,i）会对表t进行原始（raw）的访问，即在不考虑元表的情况下对表进行简单的访问。
进行一次原始访问并不会加快代码的执行（一次函数调用的开销就会抹杀用户所做的这些努力），但是，我们后续会看到，有时确实会用到原始访问。

20.4.2　__newindex元方法

元方法__newindex与__index类似，不同之处在于前者用于表的更新而后者用于表的查询。
当对一个表中不存在的索引赋值时，解释器就会查找__newindex元方法：如果这个元方法存在，那么解释器就调用它而不执行赋值。
像元方法__index一样，如果这个元方法是一个表，解释器就在此表中执行赋值，而不是在原始的表中进行赋值。

此外，还有一个原始函数允许我们绕过元方法：调用rawset（t,k,v）来等价于t[k]=v，但不涉及任何元方法。

20.4.3　具有默认值的表

一个普通表中所有字段的默认值都是nil。通过元表，可以很容易地修改这个默认值：

1
2
3
4
function setDefault(t,d)
	local mt = {__index == function () return d end}
	setmetatable(t,mt)
end

在调用setDefault后，任何对表tab中不存在字段的访问都将调用它的__index元方法，而这个元方法会返回零（这个元方法中的值是d）。

函数setDefault为所有需要默认值的表创建了一个新的闭包和一个新的元表。如果我们有很多需要默认值的表，那么开销会比较大。
然而，由于具有默认值d的元表是与元方法关联在一起的，所以我们不能把同一个元表用于具有不同默认值的表。
为了能够使所有的表都使用同一个元表，可以使用一个额外的字段将每个表的默认值存放到表自身中。
如果不担心命名冲突的话，我们可以使用形如”___”这样的键作为额外的字段：

1
2
3
4
5
local mt = {__index == function (t) return t.___ end}
function setDefault(t,d)
	t.___ = d
	setmetatable(t,mt)
end

请注意，这里我们只在setDefault外创建了一次元表mt及对应的元方法。

如果担心命名冲突，要确保这个特殊键的唯一性也很容易，只需要创建一个新的排除表，然后将它作为键即可：

1
2
3
4
5
6
local key = {}	--唯一的键
local mt = {__index == function (t) return t[key] end}
function setDefault(t,d)
	t[key] = d
	setmetatable(t,mt)
end

20.4.4　跟踪对表的访问

假设我们要跟踪对某个表的所有访问。
由于__index和__newindex元方法都是在表中的索引不存在时才有用，因此，捕获对一个表所有访问的唯一方式是保持表是空的。
如果要监控对一个表的所有访问，那么需要为真正的表创建一个代理（proxy）。
这个代理是一个空的表，具有用于跟踪所有访问并将访问重定向到原来的表的合理元方法。

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
function track(t)
	local proxy = {}	--'t'的代理表

	--为代理创建元表
	local mt = {
		__index = function (_,k)
			print("*access to element"..tostring(k));
			return t[k]	--访问原来的表
		end
	}

	__newindex = function (_,k,v)
		print("*update of element"..tostring(k).."to"..tostring(v));\
		t[k] = v --更新原来的表
	end

	__pairs = function ()
		return function (_,k)	--迭代函数
			local nextkey,nextvalue = next(t,k)
			if nextkey ~= nil then	--避免最后一个值
				print("*traversing element"..tostring(nextkey))
			end
			return nextkey,nextvalue
		end
	end

	__len = function ()
		return #t
	end
end

如果想要同时监控几个表，并不需要为每个表创建不同的元表。
相反，只要以某种形式将每个代理与其原始表映射起来，并且让所有的代理共享一个公共的元表即可。
这个问题与上节所讨论的把表与其默认值关联起来的问题类似，因此可以采用相同的解决方式。
例如，可以把原来的表保存在代理表的一个特殊的字段中，或者使用一个对偶表示建立代理与相应表的映射。

20.4.5　只读的表

使用代理的概念可以很容易地实现只读的表，需要做的只是跟踪对表的更新操作并抛出异常即可。
对于元方法__index，由于我们不需要跟踪查询，所以可以直接使用原来的表来代替函数。这样做比把所有的查询重定向到原来的表上更简单也更有效率。
不过，这种做法要求为每个只读代理创建一个新的元表，其中__index元方法指向原来的表：

1
2
3
4
5
6
7
8
9
10
11
12
13
function readOnly(t)
	local proxy = {}

	local mt = {
		__index = t,
		__newindex = function (_,k,v)
			error("attempt to update a read-only table",2)
		end
	}

	setmetatable(t,mt)
	return proxy
end

Chapter21 面向对象（Object-Oriented）编程

从很多意义上讲，Lua语言中的一张表就是一个对象。
首先，表与对象一样，可以拥有状态。
其次，表与对象一样，拥有一个与其值无关的的标识（self）；
特别地，两个具有相同值的对象（表）是两个不同的对象，而一个对象可以具有多个不同的值；
最后，表与对象一样，具有与创建者和被创建位置无关的生命周期。

使用参数self是所有面向对象语言的核心点。
大多数面向对象语言都向程序员隐藏了这个机制，从而使得程序员不必显式地声明这个参数（虽然程序员仍然可以在方法内使用self或者this）。
Lua语言同样可以使用冒号操作符（colon operator）隐藏该参数。

冒号的作用是在一个方法调用中增加一个额外的实参，或在方法的定义中增加一个额外的隐藏形参。
冒号只是一种语法机制，虽然很便利，但没有引入任何新的东西。
我们可以使用点分语法来定义一个函数，然后用冒号语法调用它，反之亦然，只要能够正确地处理好额外的参数即可。

21.1　类（Class）

大多数面向对象语言提供了类的概念，类在对象的创建中扮演了模子（mold）的作用。在这些语言中，每个对象都是某个特定类的实例（instance）。
Lua语言中没有类的概念；虽然元表的概念在某种程度上与类的概念相似，但是把元表当作类使用在后续会比较麻烦。
相反，我们可以参考基于原型的语言（prototype-based language）中的一些做法来在Lua语言中模拟类，例如Self语言（JavaScript采用的也是这种方式）。在这些语言中，对象不属于类。
相反，每个对象可以有一个原型（prototype）。
原型也是一种普通的对象，当对象（类的实例）遇到一个未知操作时会首先在原型中查找。
要在这种语言中表示一个类，我们只需要创建一个专门被用作其他对象（类的实例）的原型对象即可。
类和原型都是一种组织多个对象间共享行为的方式。

继承不仅可以作用于方法，还可以作用于其他在新账户中没有的字段。
因此，一个类不仅可以提供方法，还可以为实例中的字段提供常量和默认值。

21.2　继承（Inheritance）

Lua语言中的对象有一个有趣的特性，就是无须为了指定一种新行为而创建一个新类。
如果只有单个对象需要某种特殊的行为，那么我们可以直接在该对象中实现这个行为。

21.3　多重继承（Multiple Inheritance）

这种实现的关键在于把一个函数用作__index元方法。
请注意，当一个表的元表中的__index字段为一个函数时，当Lua不能在原来的表中找到一个键时就会调用这个函数。基于这一点，就可以让__index元方法在其他期望的任意数量的父类中查找缺失的键。

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
--一种多重继承的实现

--在表'plist'的列表中查找'k'
local function search(k,plist)
	for i = 1, #plist, 1 do
		local v = plist[i][k]
		if v then
			return v
		end
	end
end

function createClass(...)
	local c = {}			--新类
	local parents = {...}	--父类列表

	--在父类列表中查找类缺失的方法
	setmetatable(c,{__index = function (t,k)
		return search(k,parents)
	end})0

	--将'c'作为其实例的元表
	c.__index = c

	--为新类定义一个新的构造函数
	function c:new(o)
		o = o or {}
		setmetatable(o,c)
		return o
	end

	return c	--返回新类
end

21.4　私有性（Privacy）

这种做法的基本思想是通过两个表来表示一个对象：一个表用来保存对象的状态，另一个表用于保存对象的操作（或接口）。
我们通过第二个表来访问对象本身，即通过组成其接口的操作来访问。
为了避免未授权的访问，表示对象状态的表不保存在其他表的字段中，而只保存在方法的闭包中。

21.5　单方法对象（Single-method Object）

单方法对象的另一种有趣情况是，这个方法其实是一个根据不同的参数完成不同任务的分发方法（dispatch method）。
这种对象的一种原型实现如下：

1
2
3
4
5
6
7
8
9
10
11
function newObject(value)
	return function (action,v)
		if action == "get" then
			return value
		elseif action == "set" then
			value = v
		else
			error("invalid action")
		end
	end
end

每个对象使用一个闭包，要比使用一个表的开销更低。
虽然使用这种方式不能实现继承，但我们却可以拥有完全的私有性：访问单方法对象中某个成员只能通过该对象所具有的唯一方法进行。

21.6　对偶表示（Dual Representation）

这里的关键在于：我们不仅可以通过数值和字符串来索引一个表，还可以通过任何值来索引一个表，尤其是可以使用其他的表来索引一个表。

1
2
3
function Account.withdraw(self,v)
	balance[self] = balance[self] - v
end

这样做的好处在于私有性。
即使一个函数可以访问一个账户，但是除非它能够同时访问表balance，否则也不能访问余额。
如果表balance是一个在模块Account内部保存的局部变量，那么只有模块内部的函数才能访问它。
因此，只有这些函数才能操作账户余额。

在我们继续学习前，必须讨论一下这种实现的一个大的缺陷。
一旦我们把账户作为表balance中的键，那么这个账户对于垃圾收集器而言就永远也不会变成垃圾，这个账户会留在表中直到某些代码将其从表中显式地移除。
这对于银行账户而言可能不是问题（除非销户，否则一个账户通常需要一直有效），但对于其他场景来说则可能是一个较大的缺陷。
我们会在23.3节中学习如何解决这个问题，但现在我们先忽略它。

对偶表示无须修改即可实现继承。
这种实现方式与标准实现方式在内存和时间开销方面基本相同。
新对象需要一个新表，而且在每一个被使用的私有表中需要一个新的元素。
访问balance[self]会比访问self.balance稍慢，这是因为后者使用了局部变量而前者使用了外部变量。通常，这种区别是可以忽略的。
正如我们后面会看到的，这种实现对于垃圾收集器来说也需要一些额外的工作。

Chapter22 环境（Environment）

全局变量在大多数编程语言中是让人爱恨交织又不可或缺的。
一方面，使用全局变量会明显地使无关的代码部分纠缠在一起，容易导致代码复杂。
另一方面，谨慎地使用全局变量又能更好地表达程序中真正的全局概念；
此外，虽然全局常量看似无害，但像Lua语言这样的动态语言是无法区分常量和变量的。
像Lua这样的嵌入式语言更复杂：虽然全局变量是在整个程序中均可见的变量，但由于Lua语言是由宿主应用调用代码段（chunk）的，因此“程序”的概念不明确。

Lua语言通过不使用全局变量的方法来解决这个难题，但又不遗余力地在Lua语言中对全局变量进行模拟。
在第一种近似的模拟中，我们可以认为Lua语言把所有的全局变量保存在一个称为全局环境（global environment）的普通表中。

22.1　具有动态名称的全局变量

22.2　全局变量的声明

22.3　非全局环境

在Lua语言中，全局变量并不一定非得是真正全局的。
正如笔者此前所提到的，Lua语言甚至根本没有全局变量。
由于我们在本书中不断地使用全局变量，所以一开始听上去这可能很诡异。
正如笔者所说，Lua语言竭尽全力地让程序员有全局变量存在的幻觉。现在，让我们看看Lua语言是如何构建这种幻觉的。

首先，让我们忘掉全局变量而从自由名称的概念开始讨论。
一个自由名称（free name）是指没有关联到显式声明上的名称，即它不出现在对应局部变量的范围内。
例如，在下面的代码段中，x和y是自由名称，而z则不是：

1
2
local z = 10
x = y + z

接下来就到了关键的部分：Lua语言编译器将代码段中的所有自由名称x转换为_ENV.x。
因此，此前的代码段完全等价于：

1
2
local z = 10
_ENV.x = _ENV.y + z

但是这里新出现的_ENV变量又究竟是什么呢？
我们刚才说过，Lua语言中没有全局变量。因此，_ENV不可能是全局变量。

在这里，编译器实际上又进行了一次巧妙的工作。
笔者已经提到过，Lua语言把所有的代码段都当作匿名函数。
所以，Lua语言编译器实际上将原来的代码段编译为如下形式：

1
2
3
4
5
local _ENV = some value(某些值)
return function(...)
	local z = 10
	_ENV.x = _ENV.y + z
end

也就是说，Lua语言是在一个名为_ENV的预定义上值（一个外部的局部变量，upvalue）存在的情况下编译所有的代码段的。
因此，所有的变量要么是绑定到了一个名称的局部变量，要么是_ENV中的一个字段，而_ENV本身是一个局部变量（一个上值）。

_ENV的初始值可以是任意的表（实际上也不用一定是表，我们会在后续讨论）。任何一个这样的表都被称为一个环境。
为了维持全局变量存在的幻觉，Lua语言在内部维护了一个表来用作全局环境（global environment）。
通常，当加载一个代码段时，函数load会使用预定义的上值来初始化全局环境。
因此，原始的代码段等价于：

1
2
3
4
5
local _ENV = the global environment(全局环境)
return function(...)
	local z = 10
	_ENV.x = _ENV.y + z
end

上述赋值的结果是，全局环境中的字段x得到全局环境中字段y加10的结果。

乍一看，这可能像是操作全局变量的一种相当拐弯抹角的方式。笔者也不会去争辩说这是最简单的方式，但是，这种方式比那些更简单的实现方法具有更多的灵活性。
在继续学习前，让我们总结一下Lua语言中处理全局变量的方式：

  • 编译器在编译所有代码段前，在外层创建局部变量_ENV；
  • 编译器将所有自由名称var变换为_ENV.var；
  • 函数load（或函数loadfile）使用全局环境初始化代码段的第一个上值，即Lua语言内部维护的一个普通的表。实际上，这也不是太复杂。

有些人由于试图从这些规则中引申出额外的“魔法”而感到困惑；其实，这些规则并没有额外的含义。
尤其是，前两条规则完全是由编译器进行的。
除了是由编译器预先定义的，_ENV只是一个单纯的普通变量。
抛开编译器，名称_ENV对于Lua语言来说根本没有特殊含义。
类似地，从x到_ENV.x的转换是纯粹的语法转换，没有隐藏的含义。
尤其是，在转换后，按照标准的可见性规则，_ENV引用的是其所在位置所有可见的_ENV变量。

22.4　使用_ENV

Chapter23　垃圾收集

Lua语言使用自动内存管理。
程序可以创建对象（表、闭包等），但却没有函数来删除对象。
Lua语言通过垃圾收集（garbage collection）自动地删除成为垃圾的对象，从而将程序员从内存管理的绝大部分负担中解放出来。

弱引用表（weak table）、析构器（finalizer）和函数collectgarbage是在Lua语言中用来辅助垃圾收集器的主要机制。
弱引用表允许收集Lua语言中还可以被程序访问的对象；
析构器允许收集不在垃圾收集器直接控制下的外部对象；
函数collectgarbage则允许我们控制垃圾收集器的步长。

23.1　弱引用表

弱引用表就是这样一种用来告知Lua语言一个引用不应阻止对一个对象回收的机制。所谓弱引用（weak reference）是一种不在垃圾收集器考虑范围内的对象引用。
如果对一个对象的所有引用都是弱引用，那么垃圾收集器将会回收这个对象并删除这些弱引用。
Lua用语言通过弱引用表实现弱引用，弱引用表就是元素均为弱引用的表，这意味着如果一个对象只被一个弱引用表持有，那么Lua语言最终会回收这个对象。

表由键值对组成，其两者都可以容纳任意类型的对象。
在正常情况下，垃圾收集器不会回收一个在可访问的表中作为键或值的对象。也就是说，键和值都是强（strong）引用，它们会阻止对其所指向对象的回收。
在一个弱引用表中，键和值都可以是弱引用的。
这就意味着有三种类型的弱引用表，即具有弱引用键的表、具有弱引用值的表及同时具有弱引用键和值的表。
不论是哪种类型的弱引用表，只要有一个键或值被回收了，那么对应的整个键值对都会被从表中删除。

1
2
3
4
5
6
7
8
9
10
11
12
a = {}
mt = {__mode = "k"}
setmetatable(a,mt)	--现在'a'的键是弱引用的了
key = {}			--创建第一个键
a[key] = 1
key = {}			--创建第二个键
a[key] = 2
collectgarbage()	--强制进行垃圾回收

for key, value in pairs(a) do
	print(value)	--> 2
end

在本例中，第二句赋值key={}覆盖了指向第一个键的索引。
调用collectgarbage强制垃圾收集器进行一次完整的垃圾收集。
由于已经没有指向第一个键的其他引用，因此Lua语言会回收这个键并从表中删除对应的元素。
然而，由于第二个键仍然被变量key所引用，因此Lua不会回收它。

请注意，只有对象可以从弱引用表中被移除，而像数字和布尔这样的“值”是不可回收的。
例如，如果我们在表a（之前的示例）中插入一个数值类型的键，那么垃圾收集器永远不会回收它。
当然，如果在一个值为弱引用的弱引用表中，一个数值类型键相关联的值被回收了，那么整个元素都会从这个弱引用表中被删除。

字符串在这里表现了一些细微的差别，虽然从实现的角度看字符串是可回收的，但字符串又与其他的可回收对象不同。
其他的对象，例如表和闭包，都是被显式创建的。例如，当Lua语言对表达式{}求值时会创建一个新表。然而，当对表达式”a”..”b”求值时，Lua语言会创建一个新字符串么？
如果当前系统中已有了一个字符串”ab”会怎么样？Lua语言会创建一个新的字符串么？编译器会在运行程序前先创建这个字符串吗？其实，这些都无关紧要，因为它们都是实现上的细节。
从程序员的角度看，字符串是值而不是对象。
所以，字符串就像数值和布尔值一样，对于一个字符串类型的键来说，除非它对应的值被回收，否则是不会从弱引用表中被移除的。

23.2　记忆函数（Memorize Function）

空间换时间是一种常见的编程技巧。
我们可以通过记忆（memorize）函数的执行结果，在后续使用相同参数再次调用该函数时直接返回之前记忆的结果，来加快函数的运行速度。

记忆技术（memorization technique）还可以用来确保某类对象的唯一性。

23.3　对象属性（Object Attribute）

23.4　回顾具有默认值的表

23.5　瞬表（Ephemeron Table）

在Lua语言中，一个具有弱引用键和强引用值的表是一个瞬表。
在一个瞬表中，一个键的可访问性控制着对应值的可访问性。
更确切地说，考虑瞬表中的一个元素（k,v），指向的v的引用只有当存在某些指向k的其他外部引用存在时才是强引用，否则，即使v（直接或间接地）引用了k，垃圾收集器最终会收集k并把元素从表中移除。

23.6　析构器（Finalizer）

Lua语言中，析构器的一个微妙之处在于“将一个对象标记为需要析构”的概念。
通过给对象设置一个具有非空__gc元方法的元表，就可以把一个对象标记为需要进行析构处理。
如果不标记对象，那么对象就不会被析构。

有关析构器的另一个微妙之处是复苏（resurrection）。
当一个析构器被调用时，它的参数是正在被析构的对象。因此，这个对象会至少在析构期间重新变成活跃的。笔者把这称为临时复苏（transient resurrection）。
在析构器执行期间，我们无法阻止析构器把该对象存储在全局变量中，使得该对象在析构器返回后仍然可访问，笔者把这称为永久复苏（permanent resurrection）。

由于复苏的存在，Lua语言会在两个阶段中回收具有析构器的对象。
当垃圾收集器首次发现某个具有析构器的对象不可达时，垃圾收集器就把这个对象复苏并将其放入等待被析构的队列中。
一旦析构器开始执行，Lua语言就将该对象标记为已被析构。
当下一次垃圾收集器又发现这个对象不可达时，它就将这个对象删除。
如果想保证我们程序中的所有垃圾都被真正地释放了的话，那么必须调用collectgarbage两次，第二次调用才会删除第一次调用中被析构的对象。

23.7　垃圾收集器

一直到Lua 5.0，Lua语言使用的都是一个简单的标记-清除（mark-and-sweep）式垃圾收集器（Garbage Collector，GC）。
这种收集器又被称为“stop-the-world（全局暂停）”式的收集器，意味着Lua语言会时不时地停止主程序的运行来执行一次完整的垃圾收集周期（garbagecollection cycle）。

每一个垃圾收集周期由四个阶段组成：标记（mark）、清理（cleaning）、清除（sweep）和析构（finalization）。

标记阶段把根结点集合（ root set）标记为活跃，根结点集合由Lua语言可以直接访问的对象组成。
在Lua语言中，这个集合只包括C注册表（在30.3.1节中我们会看到，主线程和全局环境都是在这个注册表中预定义的元素）。
保存在一个活跃对象中的对象是程序可达的，因此也会被标记为活跃（当然，在弱引用表中的元素不遵循这个规则）。
当所有可达对象都被标记为活跃后，标记阶段完成。

在开始清除阶段前，Lua语言先执行清理阶段，在这个阶段中处理析构器和弱引用表。
首先，Lua语言遍历所有被标记为需要进行析构、但又没有被标记为活跃状态的对象。
这些没有被标记为活跃状态的对象会被标记为活跃（复苏，resurrected），并被放在一个单独的列表中，这个列表会在析构阶段用到。
然后，Lua语言遍历弱引用表并从中移除键或值未被标记的元素。

清除阶段遍历所有对象（为了实现这种遍历，Lua语言把所有创建的对象放在一个链表中）。
如果一个对象没有被标记为活跃，Lua语言就将其回收。否则，Lua语言清理标记，然后准备进行下一个清理周期。

最后，在析构阶段，Lua语言调用清理阶段被分离出的对象的析构器。
使用真正的垃圾收集器意味着Lua语言能够处理对象引用之间的环。
在使用环形数据结构时，我们不需要花费额外的精力，它们会像其他数据一样被回收。

Lua 5.1使用了增量式垃圾收集器（incremental collector）。
这种垃圾收集器像老版的垃圾收集器一样执行相同的步骤，但是不需要在垃圾收集期间停止主程序的运行。相反，它与解释器一起交替运行。
每当解释器分配了一定数量的内存时，垃圾收集器也执行一小步（这意味着，在垃圾收集器工作期间，解释器可能会改变一个对象的可达性。为了保证垃圾收集器的正确性，垃圾收集器中的有些操作具有发现危险改动和纠正所涉及对象标记的内存屏障[barrier]）。

Lua 5.2引入了紧急垃圾收集（emergency collection）。
当内存分配失败时，Lua语言会强制进行一次完整的垃圾收集，然后再次尝试分配。
这些紧急情况可以发生在Lua语言进行内存分配的任意时刻，包括Lua语言处于不一致的代码执行状态时，因此，这些收集动作不能运行析构器。

23.8　控制垃圾收集的步长（Pace）

通过函数collectgarbage可以对垃圾收集器进行一些额外的控制，该函数实际上是几个函数的集合体：第一个参数是一个可选的字符串，用来说明进行何种操作；有些选项使用一个整型作为第二个参数，称为data。
第一个参数的选项包括如下七个。
“stop”：停止垃圾收集器，直到使用选项”restart”再次调用collectgarbage。
“restart”：重启垃圾收集器。
“collect”：执行一次完整的垃圾收集，回收和析构所有不可达的对象。这是默认的选项。
“step”：执行某些垃圾收集工作，第二个参数data指明工作量，即在分配了data个字节后垃圾收集器应该做什么。
“count”：以KB为单位返回当前已用内存数，该结果是一个浮点数，乘以1024得到的就是精确的字节数。该值包括了尚未被回收的死对象。
“setpause”：设置收集器的pause参数（间歇率）。参数data以百分比为单位给出要设定的新值：当data为100时，参数被设为1（100%）。
“setstepmul”：设置收集器的stepmul参数（步进倍率，step multiplier）。参数data给出新值，也是以百分比为单位。

两个参数pause和stepmul控制着垃圾收集器的角色。任何垃圾收集器都是使用CPU时间换内存空间。
在极端情况下，垃圾收集器可能根本不会运行。但是，不耗费CPU时间是以巨大的内存消耗为代价的。
在另外一种极端的情况下，收集器可能每进行一次赋值就得运行一次完整的垃圾收集。程序能够使用尽可能少的内存，但是是以巨大的CPU消耗为代价的。
pause和stepmul的默认值正是试图在这两个极端之间找到的对大多数应用来说足够好的平衡点。不过，在某些情况下，还是值得试着对它们进行优化。

参数pause用于控制垃圾收集器在一次收集完成后等待多久再开始新的一次收集。
当值为零时表示Lua语言在上一次垃圾回收结束后立即开始一次新的收集。当值为200%时表示在重启垃圾收集器前等待内存使用翻番。
如果想使消耗更多的CPU时间换取更低的内存消耗，那么可以把这个值设得小一点。
通常，我们应该把这个值设在0到200%之间。

参数stepmul控制对于每分配1KB内存，垃圾收集器应该进行多少工作。这个值越高，垃圾收集器使用的增量越小。
一个像100000000%一样巨大的值会让收集器表现得像一个非增量的垃圾收集器。
默认值是200%。低于100%的值会让收集器运行得很慢，以至于可能一次收集也完不成。

函数collectgarbage的另外一些参数用来在垃圾收集器运行时控制它的行为。
同样，对于大多数程序员来说，默认值已经足够好了，但是对于一些特殊的应用，用手工控制可能更好，游戏就经常需要这种类型的控制。
例如，如果我们不想让垃圾收集在某些阶段运行，那么可以通过调用函数collectgarbage（”stop”）停止垃圾收集器，然后再调用collectgarba ge（”restart”）重新启动垃圾收集器。
在一些具有周期性休眠阶段的程序中，可以让垃圾收集器停止，然后在程序休眠期间调用collectgarbage（”step”,n）。
要设置在每一个休眠期间进行多少工作，要么为n实验性地选择一个恰当的值，要么把n设成零（意为最小的步长），然后在一个循环中调用函数collectgarbage直到休眠结束。