《lua 程序设计》读书笔记（9）：迭代器 & 元表

迭代器是一种可以让我们遍历一个集合中所有元素的代码结构，这篇文章将介绍 Lua 的迭代器机制，而泛型 for 正是为简化迭代器的使用而设计的。之后则将介绍 Lua 的元表，元表的功能非常强大，通过元表，可以实现其他编程语言中 运算符 重载的效果、或者实现面向对象编程的 继承。

迭代器和闭包

在 Lua 中，通常使用函数表示迭代器：每一次调用该函数时，函数会返回集合中的下一个元素，例如 io.read。

所有迭代器都需要在连续的调用之间保存一些状态，这样才能知道当前迭代所处的位置以及如何从当前位置步进到下一个位置。闭包为保存状态提供了一种良好的机制。一个闭包就是一个可以访问其自身环境中的一个或多个局部变量的函数。一个闭包结构通常涉及两个函数：闭包本身和一个用于创建该闭包及其封装变量的工厂。

如下是一个为列表编写的简单迭代器，在该示例中，values 就是工厂，每次调用这个工厂，就会创建一个新的闭包（即迭代器本身）。该闭包将其状态保存在其外部的变量 t 和 i 中，这两个变量由 values 创建：

function values(t)
    local i = 0
    return function()
        i = i + 1
        return t[i]
    end
end


local t = {10, 20, 30}
local iter = values(t)

while true do
    local e = iter()
    if e == nil then
        break
    end
    print(e)
end

在该示例中，使用泛型 for 会更简单，因为泛型 for 正是为这种迭代而设计的：

for e in values(t) do
    print(e)
end

泛型 for 为一次迭代循环做了所有的记录工作：

• 它在内部保存了迭代器，因此不需要变量 iter
• 它在每次做新的迭代时都会再次调用迭代器，并在迭代器返回 nil 时结束循环

如下是一个更高级的示例：

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

泛型 for 的用法

上述这些迭代器都有一个缺点，即需要为每个新的循环创建一个新的闭包。在某些情况下可以通过使用泛型 for 自己保存迭代状态。泛型 for 在循环过程中保存了迭代器，实际上，泛型 for 保存了三个值：

• 一个迭代器
• 一个不可变状态
• 一个控制变量

泛型 for 语法如下：

for var-list in exp-list do
    body
end

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

变量列表的第一个变量称为控制变量，其值在循环过程中永远不是 nil，当其值为 nil 时循环就结束了。

for 首先对 in 后面的表达式进行求值，该表达式应该返回 3 个值供 for 保存：迭代器、不可变状态和控制变量的初始值。类似于多重赋值，只有最后一个表达式能够产生多个值，表达式列表的结果只会保留 3 个，多余的值会被丢弃，不足三个则以 nil 补齐。

在完成初始化后，for 使用不可变状态和控制变量作为参数调用迭代器，然后将迭代器的返回值赋给变量列表中声明的变量。如果第一个返回值（赋给控制变量）为 nil，那么循环结束，否则 for 执行它的循环体并再次调用迭代器，并不断重复上述过程。

因此 for var_1, ... var_n in explist do block end 等效于如下代码：

do
    local _f, _s, _var = explist
    while true do
        local var_1, ..., var_n = _f(_s, _var)
        _var = var_1
        if _var == nil then
            break
        end
        block
    end
end

因此假设迭代函数为 f，不可变状态为 s，控制变量的初始值为 a0，那么循环中控制变量的值依次为 a1=f(s, a0)、a2=f(s, a1)，以此类推，直至 ai 为 nil。

无状态迭代器

无状态迭代器就是一种自身不保存任何状态的迭代器，因此可以在多个循环中使用同一个无状态迭代器，从而避免创建新闭包的开销。由于 for 循环会以不可变状态和控制变量为参数调用迭代器，一个无状态迭代器只根据这两个值来为迭代生成下一个元素。

无状态迭代器的一个典型示例是 ipairs，它可以迭代一个序列中的所有元素：

a = {"one", "two", "three"}
for i, v in ipairs(a) do
    print(i, v)
end

迭代的状态由 正在被遍历的表（一个不可变状态，它不会在循环中改变）以及 当前的索引值（控制变量）组成。因此 ipairs 的实现逻辑大致如下：

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

函数 pairs 与函数 ipairs 类似，也用于遍历一个表中的所有元素。但是 pairs 返回的迭代器是 Lua 中的一个基本函数 next。在调用 next(t, k) 时，k 是表 t 的一个键，该函数会以随机次序返回表中的下一个键即 k 对应的值。调用 next(t, nil) 则返回表中第一个键值对，当所有元素被遍历完成，则返回 nil。

如下通过无状态迭代器实现了对链表的迭代：

local function getnext(list, node)
    if not node then
        return list
    else
        return node.next
    end
end


function traverse(list)
    return getnext, list, nil
end

在该示例中，除了将当前节点作为控制变量，还要将头结点作为不可变状态返回。第一次调用 getnext 时，node 为 nil，因此直接返回 list 头结点，之后的调用中 node 不再是 nil，因此返回 node.next。

按顺序遍历表

由于一个表中元素没有顺序，所以如果想对这些元素排序，通常会先把键值对拷贝到一个数组中，然后再对数组进行排序。其实数组本身也没有顺序（数组也是表），但是当我们使用有序的索引访问数组时，就实现了按顺序访问数组。因此应该总是通过 ipairs 来遍历数组，它通过有序的键 1、2... 来实现有序。而 pairs 则是天然的随机顺序。

如下实现了一个按照键顺序来遍历表的迭代器：

function pairsByKeys(t, f)
    local a = {}
    for n in pairs(t) do
        a[#a + 1] = n
    end

    table.sort(a, f)

    local i = 0
    return function()
        i = i + 1
        return a[i], t[a[i]]
    end
end


for k, v in pairsByKeys({c=1, b=2, a=3}) do
    print(k, v)
end

迭代器的真实含义

以上 迭代器 并没有进行实际的迭代，真正的迭代是在 for 循环中完成的，迭代器只不过为每次的迭代提供连续的值。还有一种创建迭代器的方式可以让迭代器进行实际的迭代操作，当使用这种迭代器时，就不再需要编写循环了。相反，只需要调用该迭代器，并传入一个描述在每次迭代时需要做什么的参数即可。即迭代器接收一个函数作为参数，这个函数在循环内部被调用，这种迭代器就被称为真正的迭代器。

例如：

function allwords(f)
    for line in io.lines() do
        for word in string.gmatch(line, "%w+") do
            f(word)
        end
    end
end

真正的迭代器在老版本的 Lua 中曾经非常流行，那时还没有 for 语句。但是总体来说，还是 生成器风格的迭代器 更加灵活。

马尔可夫链算法

接下来实现马尔可夫链文本生成器，它根据 基础文本中由前 n 个单词组成的序列之后的单词，来生成伪随机文本，这里将 n 设置为 2。也就是说，随机文本中，每个单词出现在 它之前两个单词后的概率 与出现在 基础文本中相同两个前序单词后 的概率相同，这样就可以得到一串相对比较随机的文本。

function allwords()
    local line = io.read()
    local post = 1
    return function()
        local w, e = string.match(line, "(%w+[,;.:]?)()", pos)
        if w then
            pos = e
            return w
        else
            line = io.read()
            pos = 1
        end
        return nil
    end
end


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


local statetab = {}


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


local MAXGEN = 20
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, w2 = NOWORD, NOWORD
for i = 1, MAXGEN 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

元表和元方法

通常 Lua 中的每种类型都有一套可以预见的操作集合，而元表可以修改一个值在面对一个未知操作时的行为。元表定义的是实例的行为，而且元表只能给出预先定义的操作集合的行为。例如当对两个表相加时，它会首先检查两者之一是否有元表而且该元表中是否有 __add 字段。如果存在，就调用该字段对应的值，即所谓的元方法（是一个函数）。

Lua 中每一个值都可以有元表，每一个表和用户数据类型都具有各自独立的元表，而其他类型的值则共享对应类型所属的同一个元表。

Lua 在新建一个表时，是不带元表的，可以使用函数 setmetatable 来设置或修改任意表的元表：

> q = {}
> print(getmetatable(q))
nil

> q1 = {}
> setmetatable(q, q1)
table: 0x557232d1f4e0
> getmetatable(q) == q1
true

在 Lua 中，只能为表设置元表，如果要为其他类型的值设置元表，则必须通过 C 代码或调试库完成（这样是为了防止过度使用对某种类型的所有值生效的元表）。字符串标准库为所有字符串都设置了同一个元表，而其他类型的值默认情况下没有元表：

> getmetatable("test")
table: 0x557232d1cd50
> getmetatable("hi")
table: 0x557232d1cd50
> getmetatable(1)
nil
> getmetatable(false)
nil

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

算术相关的元方法

假设有一个模块，它使用表来表示集合，并提供相关函数来计算集合的交、并等操作。所有表示集合的表共享一个元表，该元表定义了这些表应该如何执行加法操作、乘法操作

local Set = {}
local mt = {}

function Set.new(l)
    local set = {}
    setmetatable(set, mt)
    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


mt.__add = Set.union
mt.__mul = Set.intersection
mt.__tostring = Set.tostring

return Set

> set = require "set"
> s1 = set.new{1, 2, 3}
> s2 = set.new{2, 3, 4}
> print(s1 + s2)
{1, 2, 3, 4}
> print(s1 * s2)
{2, 3}

每种算术运算符都有一个对应的元方法：

• 加法：__add
• 减法：__sub
• 乘法：__mul
• 除法：__div
• floor 除法：__idiv
• 负数：__unm
• 取模：__mod
• 幂运算：__pow

位操作也由元方法：

• 位与：__band
• 位或：__bor
• 位异或：__bxor
• 位取反：__bnot
• 向左位移：__shl
• 向右位移：__shr

还可以使用 __concat 来定义连接运算符的行为。

当一个表达式中混合了两种具有不同元表的值时，Lua 会按照如下步骤查找元方法：

• 如果第一个值具有元表且存在所需的元方法，则使用该元方法
• 否则查看第二个值是否具有元表且存在所需的元方法，如果满足，则使用该元方法
• 否则抛出异常

Lua 并不关心混合类型，但是我们元方法实现就需要关心混合类型：

> s1 + 8
./set.lua:16: bad argument #1 to 'for iterator' (table expected, got number)
stack traceback:
        [C]: in function 'next'
        ./set.lua:16: in function 'set.union'
        stdin:1: in main chunk
        [C]: in ?

一种方法是在试图进行操作前显式地检查操作数的类型：

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

关系运算相关的元方法

元表也支持我们指定关系运算符的含义，其中的方法包括：

• 等于：__eq
• 小于：__lt
• 小于等于：__le

其他三个关系运算符没有单独的元方法，Lua 会将 a ~= b 转换为 not (a == b)，a > b 转换为 b < a，a >= b 转换为 b <= a。

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

库定义相关的元方法

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

tostring 就是一个典型例子，函数 tostring 可以将 table 表示为一种简单的格式：

> print({})
table: 0x5610a4a89870

print 调用 tostring 来进行格式化输出，而 tostring 则首先检查值是否有一个元方法 __tostring。如果存在，则调用该元方法来完成工作。上例中就将 mt.__tostring 设置为 Set.tostring，用于将集合表示为字符串。

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

> set = require "set"
> s1 = set.new{}
> print(getmetatable(s1))
not your business
> setmetatable(s1, {})
stdin:1: cannot change a protected metatable
stack traceback:
        [C]: in function 'setmetatable'
        stdin:1: in main chunk
        [C]: in ?

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

表相关的元方法

Lua 还提供了一种改变表在两种正常情况下的行为方式，即访问和修改表中不存在的字段。

• 当访问一个表中不存在的字段时，该访问会引发解析器去寻找一个名为 __index 的元方法，如果没有这个元方法，那么就返回 nil，否则由这个元方法来提供最终结果（会以原始的表、key 作为参数）。
• 当对一个表中不存在的索引赋值时，解释器会查找 __newindex 元方法：如果这个元方法存在，解释器就调用它而不执行赋值。

如下通过 __index 实现了类似于 继承 的效果，new 创建的对象包含一些默认字段：

prototype = {x = 0, y = 0, width = 100, height = 100}

local mt = {}

function new(o)
    setmetatable(o, mt)
    return o
end

mt.__index = function(_, key)
        return prototype[key]
end

w = new{x = 10, y = 20}
print(w.width)

在 Lua 中，使用元方法 __index 来实现继承是很普遍的方法，虽然被称为方法，但是 __index 并不一定必须是一个函数，它还可以是一个表。当元方法是一个函数时，Lua 会以表和 key 作为参数参数调用该函数，如果元方法是一个表，Lua 就直接访问这个表。因此上面的示例也可以直接使用 mt.__index = prototype。

将一个表作为 __index 为实现单继承提供了一种简单快捷方式，而用函数作为元方法则更加灵活：可以通过函数实现多继承、缓存和一些变体。如果希望一个表时不调用 __index 元方法，那么可以考虑使用函数 rawget，它会对表进行原始的访问，即不考虑元表的情况下对表进行简单的访问。

__newindex 如果是一个表，解释器在该表中执行赋值，而不是原始的表中进行赋值。类似地，调用 rawset(t, k, v) 等价于 t[k] = v，但不涉及任何元方法。

组合使用 __index 和 __newindex 可以实现 Lua 中的一些强大结构，例如只读的表、具有默认值的表和面向对象编程中的继承。

如下示例中，通过 setDefault 为表中的所有字段提供默认值：

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

tab = {x = 10, y = 20}
print(tab.x, tab.z)
setDefault(tab, 0)
print(tab.x, tab.z)

在该函数中，为所有需要默认值的表创建了一个新的闭包和一个新的元表。如果有很多需要默认值的表，开销会比较大，如下对该函数进行优化，它将每个表的默认值存放在表自身中（使用了键 ___ 防止命名冲突）。

local mt = {__index = function(t) return t.___ end}
function setDefault(t, d)
    t.___ = d
    setmetatable(t, mt)
end

如果担心命名冲突，要确保这个特殊键的唯一性也是很容易的：

local key = {}
local mt = {__index = function(t) return t[key] end}
function setDefault(t, d)
    t[key] = d
    setmetatable(t, mt)
end

如果要跟踪对某个表的所有访问，由于 __index 和 __newindex 元方法都是在表中的索引不存在时才有用，因此捕获对一个表所有访问的唯一方式是保持表是空的：

function track(t)
    local proxy = {}

    local mt = {
        __index = function(_, k)
            print("visit " .. tostring(k))
            return t[k]
        end,

        __newindex = function(_, k, v)
            print("update to " .. 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("iterate" .. tostring(k))
                end
                return nextkey, nextvalue
            end
        end,

        __len = function()
            return #t
        end
    }


    setmetatable(proxy, mt)
    return proxy
end

local t = {}
t = track(t)
t[2] = "hello"
print(t[2])

t = {10, 20}
print(#t)

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

如下实现一个只读表：

function readonly(t)
    local proxy = {}
    local mt = {
        __index = t,
        __newindex = function(t, k, v)
            error("attemp to udpate a readonly table", 2)
        end
    }
    setmetatable(proxy, mt)
    return proxy
end

local t = {1, 2}
t = readonly(t)
print(t[1])
t[1] = 1