泛型for

本章前面几节介绍了闭包。闭包最典型的应用场景是迭代器（iterator），而迭代器最常见的地方是for语句。以至于《Lua程序设计》和《Rust程序设计语言》这两本书中都把闭包、迭代器和for语句放在一起介绍。Lua语言中的for语句有两种格式，数值型和泛型。之前已经介绍了数值型for语句，本节来介绍使用迭代器的泛型for语句。

在介绍完闭包后，迭代器本身的概念是很简单的。本章前面几节一直用来举例的计数器闭包就可以认为是一个迭代器，每次生成一个递增数字。下面再看一个稍微复杂的迭代器，遍历一个表中的数组部分。这也是Lua语言自带的ipairs()函数的功能：

function ipairs(t)
    local i = 0
    return function ()
        i = i + 1
        local v = t[i]
        if v then
            return i, v
        end
    end
end

上述代码中，ipairs()是工厂函数，创建并返回一个闭包作为迭代器。这个迭代器有2个Upvalue，一个是固定不变的表t，另外一个是遍历的位置i。我们可以称这两个Upvalue为迭代环境。在遍历过程中，迭代器返回数组的索引和值；而当遍历结束时不返回值，也可以认为是返回了nil。

可以直接调用这个迭代器，但更常见的是在泛型for语句中使用：

-- 直接调用迭代器
local iter = ipairs(t)
while true do
    local i, v = iter()
    if not i then break end
    block -- do something
end

-- 在泛型for语句中使用
for i, v in ipairs(t) do
    block -- do something
end

迭代器这样的使用方式固然很方便，但是前面几节也介绍了，创建一个闭包比创建一个普通函数要有额外的开销，即无论对Lua闭包还是Rust闭包，都需要额外的2次内存分配和2次指针跳转。所以Lua语言中的泛型for语句为此做了特殊的优化，即由泛型for语句本身代替闭包来保存迭代环境（也就是Upvalue）。既然不需要Upvalue，那迭代器也就不需要使用闭包，而只需要普通函数了。

具体说来，泛型for语句的语法如下：

stat ::= for namelist in explist do block end
namelist ::= Name {‘,’ Name}

其执行流程如下：

循环开始时，对explist求值，得到3个值：迭代函数、不可变状态、和控制变量。大部分情况下explist是函数调用语句，那么求值就遵循函数返回值的求值规则，即如果不足3个就用nil补上，如果超过3个就丢弃多余的。当然也可以不使用函数调用，而是直接罗列3个值。
然后，每次执行循环前，都用后面两个值（不可变状态和控制变量）作为参数来调用迭代函数，并判断第一个返回值：如果为nil则终止循环；否则把返回值赋值给namelist，并额外把第一个返回值赋值给控制变量，以作为后续再次调用迭代函数的参数。

可以看到explist返回的这3个值拼起来就是一个闭包的功能：迭代函数是函数原型，后面两个是Upvalue。只不过泛型for语句帮忙维护了这两个Upvalue。利用泛型for语句的这个特性，重新实现上述的遍历数组的迭代器如下：

local function iter(t, i) -- t和i都从Upvalue变成了参数
    i = i + 1
    local v = t[i]
    if v then
        return i, v
    end
end

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

相比于上面的闭包版本，这里t和i都从Upvalue变成了参数，而iter也就变成了一个普通的函数。

这么看来，并不需要闭包（比如在上一章介绍完函数后）就可以完成泛型for语句。但是这毕竟是基于闭包所做的优化，在掌握闭包的基础上才能理解为什么这么做。所以我们才在介绍完闭包后才来实现泛型for语句。

另外，这里的函数调用语句ipairs(t)只是返回了3个变量，另外也可以在泛型for语句中直接罗列这3个变量：

for i, v in ipairs(t) do ... end
for i, v in iter, t, 0 do ... end  -- 直接罗列3个变量

下面这种直接罗列的做法省略一次函数调用，但是不方便。所以常见的还是第一种做法。

介绍完Lua中泛型for语句的特性，下面开始实现。

实现

根据上面的介绍，泛型for语句自己保存并维护迭代环境。那保存在哪里？自然还是在栈上。就像数值型for语句在栈上会自动创建3个变量（1个计数变量和2个匿名变量）一样，泛型for语句也需要自动创建3个匿名变量，对应上述的迭代环境：迭代函数、不可变状态、控制变量。这3个变量是对explist求值后得到，如下面左图显示的栈示意图：

|           |        |           |     |           |
+-----------+        +-----------+     +-----------+
| iter func |entry   | iter func |     | iter func |
+-----------+        +-----------+     +-----------+
| state     |\       | state     |     | state     |
+-----------+ 2args  +-----------+     +-----------+
| ctrl var  |/       | ctrl var  |     | ctrl var  |<--first return value
+-----------+        +-----------+   ->+-----------+
|           |        :           :  /  | name-     | i
                     +-----------+ /   | list      | v
                     | return-   |-    |           |
                     | values    |
                     |           |

接下来就执行循环，包括3个步骤：调用迭代函数、判断是否继续循环、控制变量赋值。

首先，以不可变状态state和控制变量ctrl var为两个参数，调用迭代函数iter func。看左图中栈示意图，刚好已经排列成函数调用的阵型，所以可以直接调用函数；

其次，调用完函数后（上面中图），判断第一个返回值是否为nil，如果是则退出循环；如果没有返回值也退出循环；否则继续执行循环。在执行循环体前，需要处理返回值（上面右图）：

把第一个返回值赋值给控制变量（上图中的ctrl-var），作为下次调用迭代函数的参数；
把返回值赋值给变量列表，也就是上面BNF里的namelist。比如上面遍历数组的例子中，就是i, v。如果返回值个数少于变量列表，则用nil补足。这个补齐操作跟普通的函数调用一致。而不一致的地方是，普通函数调用的返回值会挪到函数入口处，即上图中iter func的位置；而这里是向下偏移了3个位置。

这里需要说明的一点是，控制变量ctrl-var就是namelist的第一个name。所以实际上，栈上并不需要特意给ctrl-var保留位置；每次调用完迭代函数后，直接把所有返回值挪到图中ctrl-var的地方即可，这样第一个返回值刚好也就在ctrl-var的位置。下图是这两个方案的对比。左图是开始的方案，特意给ctrl-var保留位置；右图是新方案，只需要2个匿名变量来保存迭代环境，而ctrl-var跟第一个name重叠：

 |           |      |           |
 +-----------+      +-----------+
 | iter func |      | iter func |
 +-----------+      +-----------+
 | state     |      | state     |
 +-----------+      +-----------+
 | ctrl var  |     i| name-     | <--ctrl var
 +-----------+     v| list      |
i| name-     |      |           |
v| list      |
 |           |

右面的方案更简单，少一次变量赋值。而且正常情况下，这两个方案的功能一样。但在一个情况下功能会有差别，即在循环体内修改控制变量的时候。比如下面的示例代码：

for i, v in ipairs(t) do
    i = i + 1  -- 修改控制变量`i`
    print(i)
end

按照上面左图的方案，这里修改的i是暴露给程序员的变量，而控制变量ctrl var是隐藏的匿名变量，这两个变量是独立的。所以对i的修改不影响控制变量ctrl var。于是这个循环依旧可以遍历全部数组。

而按照右图的方案，i和ctrl var是一个值，修改i就是修改了ctrl var，也就影响了下一次的迭代函数调用，最终导致无法正常遍历整个数组。

哪个行为更合理呢？Lua手册的说明是：You should not change the value of the control variable during the loop。也就是说对这种行为并没有明确定义，所以那个方案都可以。不过Lua的官方实现是按照左图中的行为，为了保持一致我们这里也选择左图的方案。

字节码

上面介绍了泛型for语句在循环中的操作。这些操作需要一个新的字节码ForCallLoop来完成。

在定义这个字节码之前，先来看下这个字节码要放置在哪里？是循环开始，还是循环结束？如果按照Lua代码，那应该是放在循环开始，然后在循环结束的地方生成一个Jump字节码跳转回来继续循环，就像下面这样：

ForCallLoop # 如果调用迭代函数返回nil，则跳转到最后
... block ...
Jump (back-to-ForCallLoop)

但是这样的话每次循环都要执行2条字节码，开头的ForCallLoop和结尾的Jump。为了减少一次字节码，可以把ForCallLoop放在循环结束的位置，这样只有第一次循环时要执行2条字节码，后续每次循环就只需要执行1条字节码了：

Jump (forward-to-ForCallLoop)
... block ...
ForCallLoop # 如果调用迭代函数返回不是nil，则跳转到上面block处

确定字节码位置之后，再来看定义。这个字节码需要关联3个参数：

迭代函数iter func的栈索引；
变量个数，用于返回值的赋值。如果返回值个数小于变量个数，则需要填上nil；
跳转距离。

前面2个参数都可以用1个字节表示，那最后的跳转距离就也只剩1个字节的空间了，只能表示255的距离，不太够。为此只能再加上一个Jump字节码一起来完成这个功能。但是大部分情况循环体并不大，不超过255的距离，为了少数的大循环体而再加一个字节码有点浪费。这种情况下最好的办法就是：

对于小循环体可以把跳转距离编入到ForCallLoop字节码中，只用这1个字节码；
对于大循环体，把ForCallLoop字节码中的第3个参数跳转距离就设置为0，并新增一个Jump字节码做配合。

这样在虚拟机执行的时候：

在继续循环需要向后跳转的情况：对于小循环体就直接根据第3个参数跳转；对于大循环体，第3个参数是0，实际跳转到下一条Jump字节码，然后再执行循环体的跳转。
在要结束循环需要继续向前执行的情况：对于小循环体无需特殊处理；对于大循环体，需要跳过下一条Jump字节码。

综上可得，字节码ForCallLoop定义如下：

pub enum ByteCode {
    ForCallLoop(u8, u8, u8),

具体的语法分析和虚拟机执行代码，这里就省略掉了。

至此，完成泛型for语句。我们也完成了Lua所有的语法！（此处应有掌声）

用Rust实现Lua解释器

泛型for

实现

字节码