fuchencong

The way I am

0%

《lua 程序设计》读书笔记（5）：闭包 & 模式匹配

发表于 分类于

这篇文章将介绍 Lua 中的闭包，闭包特性使得我们可以在 Lua 中实现函数式编程。之后还将介绍 Lua 自己提供的模式匹配方法，这些模式匹配方法不同于一般的 Perl 正则表达式。

闭包

Lua 中，函数是严格遵循词法定界的第一类值：

  • 第一类值意味着 Lua 中函数与其他类型（如数值、字符串）的值具有同等权限，可以将函数保存到变量中或表中、将函数作为参数传递给其他函数，或者作为函数返回值等
  • 词法定界意味着 Lua 中的函数可以访问包含其自身的外部函数中的变量

这个特性允许我们在 Lua 中使用很多函数式语言的强大编程特性。

函数是第一类值

由于 Lua 中函数是第一类值，如下用法都是正确的：

1
2
3
4
5
6
7
8
9
> a = {p = print}
> a.p("hello")
hello
> print = math.sin
> a.p(print(1))
0.8414709848079
> math.sin = a.p
> math.sin(10, 20)
10      20

事实上，Lua 中常见的函数定义其实就是个语法糖：

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

等效于

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

赋值语句右侧的 function(x) body end 就是函数构造器。函数定义其实就是创建类型为 function 的值并将它赋值给一个变量的语句。

在 Lua 中，所有函数都是匿名的。像其他所有值一样，函数并没有名字。传统意义上的函数名（例如 print），实际上指的是保存该函数的变量。虽然我们通常将函数赋值给全局变量，从而似乎给函数起了一个名字，但是很多场景下仍然会保留函数的匿名性。

1
2
3
4
5
6
7
8
local network = {
    {name = "grauna", IP = "1.1.1.1"},
    {name = "arraial", IP = "1.1.1.2"},
    {name = "lua", IP = "1.1.1.3"},
    {name = "derain", IP = "1.1.1.4"},
}

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

像 sort 这种以另一个函数作为参数的函数，称之为高阶函数。

非全局函数

由于函数是第一类值，因此函数不仅可以被存储在全局变量中，还可以被存储在表字段和局部变量中。**大部分 Lua 库就是采用这种机制：将函数存储在表字段中**。

1
2
3
4
5
> lib = {}
> lib.foo = function(x, y) return x + y end
> lib.goo = function(x, y) return x - y end
> print(lib.foo(2, 3), lib.goo(2, 3))
5       -1

或者采用表构造器的方式：

1
2
3
4
5
6
> lib = {
>> foo = function(x, y) return x + y end,
>> goo = function(x, y) return x - y end
>> }
> print(lib.foo(2, 3), lib.goo(2, 3))
5       -1

Lua 还提供了另一种特殊的语法来定义这类函数：

1
2
3
4
5
> lib = {}
> function lib.foo(x, y) return x + y end
> function lib.goo(x, y) return x - y end
> print(lib.foo(2, 3), lib.goo(2, 3))
5       -1

在表字段中存储函数是在 Lua 中实现面向对象编程的关键要素。

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

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

1
2
3
local function f(params)
    body
end

在定义局部递归函数时，由于原来的方法不适用，所以有一点是极易出错的。

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

由于 Lua 编译函数体中的 fact(n-1) 调用时，局部的 fact 尚未定义，因此这个表达式会尝试调用全局的 fact 而非局部的 fact。可以通过先定义局部变量再定义函数的方式来解决这个问题。这样函数内的 fact 指向的是局部变量，尽管在定义函数时，这个局部变量的值尚未确定。但是执行函数时，fact 有了正确赋值。

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

局部函数语法糖 local function foo(params) body end 的定义会被展开成 local foo; foo = function(params) body end。所以使用这种语法来定义递归函数不会有问题。

这个技巧对于间接递归函数是无效的，在间接递归的情形下，必须使用与明确的前向声明等价的形式：

1
2
3
4
5
6
7
8
9
local f

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

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

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

词法定界

当编写一个被其他函数 B 包含的函数 A 时，被包含的函数 A 可以访问包含其的函数 B 的所有局部变量，这种特性称为词法定界。

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

这里匿名函数可以访问函数 sortbygrade 的形参 grades。在匿名函数中，grades 既不是全局变量也不是局部变量，而是 非局部变量。

如下代码展示了闭包的概念，简单来说，一个闭包就是一个函数外加能够使该函数正确访问非局部变量所需的其他机制。如下代码中 c1 和 c2 都是不同的闭包，它们建立在相同的函数之上，但是各自拥有局部变量 count 的独立实例。

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
function newCounter()
    local count = 0
    return function()
        count = count + 1
        return count
    end
end


c1 = newCounter()
print(c1())
print(c1())


c2 = newCounter()
print(c2())
print(c2())

闭包机制使得 Lua 程序能够综合运用函数式编程世界中许多精妙的编程技巧。由于函数可以被保存在局部变量中，因此在 Lua 中可以轻松重新定义函数，甚至预定义函数。这种机制也是 Lua 灵活的原因之一。如下代码使用 do 代码段来限制局部变量 oldSin 的作用范围，局部变量 oldSin 只在这部分代码段中有效，因此只有新版本的 sin 才能访问原来的 sin 函数，其他部分的代码则访问不了。可以使用同样的技巧来创建安全的运行时环境，即所谓的沙盒，借助这种机制可以根据特定的安全需求来裁剪具体的运行时环境。

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

函数式编程示例

利用高阶函数和词法定界，如下定义了一个根据指定的圆心和半径创建圆盘的工厂：

1
2
3
4
5
function disk(cx, cy, r)
    return function(x, y)
        return (x - cx)^2 + (y - cy)^2 <= r^2
    end
end

下面则创建了一个指定边界的轴对称矩形：

1
2
3
4
5
function rect(left, right, bottom, up)
    return function(x, y)
        return left <= x and x <= right and bottom <= y and y <= up
    end
end

按照该方式，每一种图形都具有完全独立的实现，所需要的仅仅是一个正确的特征函数。接下来继续考虑如何改变和组合区域：

  • 创建任何区域的补集
1
2
3
4
5
function complement(r)
    return function(x, y)
        return not r(x, y)
    end
end
  • 区域的并、交、差集
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
function union(r1, r2)
    return function(x, y)
        return r1(x, y) or r2(x, y)
    end
end

function intersection(r1, r2)
    return function(x, y)
        return r1(x, y) and r2(x, y)
    end
end

function difference(r1, r2)
    return function(x, y)
        return r1(x, y) and not r2(x, y)
    end
end

模式匹配

Lua 既没有使用 POSIX 正则表达式，也没有使用 Perl 正则表达式来进行模式匹配。之所以这么做的主要原因仍然是代码量大小的问题。尽管 Lua 的模式匹配做不到完整 POSIX 实现所需的功能，但是 Lua 语言的模式匹配仍然非常强大。

模式匹配相关的函数

string.find 用于在指定的目标字符串中搜索指定的模式，如果查找成功，会返回两个值：匹配到模式开始位置的索引和结束位置的索引。如果没有找到匹配，则返回 nil。该函数还有两个可选参数：第 3 个参数是一个索引，用于指明从目标字符串的哪个位置开始搜索，第 4 个参数是一个布尔值，用于说明是否进行简单搜索。简单搜索是指忽略模式的含义而在目标字符串中进行单纯的 查找子字符串 的动作。

string.match 也用于在一个字符串中搜索模式，但是返回的是目标字符串中与模式相匹配的那部分子串，而非模式所在的位置。

string.gsub 有 3 个必选参数：目标字符串、模式和替换字符串。其基本用法是将目标字符串中所有出现的模式的地方均换成替换字符串。其还有一个可选的第 4 个参数，用于限制替换的次数。除了替换字符串之外，第 3 个参数也可以是一个函数或者表，这个函数或表会被调用（检索）以产生替换字符串。该函数还会返回第 2 个结果，即发生替换的次数。

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

1
2
3
4
5
6
7
> s = 'some thing'
> words = {}
> for w in string.gmatch(s, "%a+") do
>>  words[#words + 1] = w
>> end
> #words
2

模式

对 Lua 解释器而言，模式仅仅是普通的字符串，模式与其他字符串一样遵循相同的规则，不会被特殊对待。只有模式匹配相关的函数才会把它们当做模式进行解析。Lua 中的模式使用 % 作为转义符，总体上被转义的字母都具有某些特殊含义，而所有被转义的非字母则代表其自身含义。下面列出了所有预置的字符分类及其对应的含义，所谓字符分类，就是模式中能够与一个特定集合中的任意字符相匹配的一项：

  • .：任意字符
  • %a：字母
  • %c：控制字符
  • %d：数字
  • %g：除空格外的可打印字符
  • %l：小写字母
  • %p：标点符号
  • %s：空白字符
  • %u：大写字母
  • %w：字母和数字
  • %x：十六进制数字

这些类的大写形式表示类的补集。在模式使用中，还有一些被称为魔法字符的字符具有特殊含义，包括 ().%+-*?[]^$，% 同样可以对魔法字符进行转义。% 不仅可以对魔法字符进行转义，还可以用于其他所有字母和数字之外的字符，当不确定是否需要转义时，保险起见总是可以使用转义符。

可以使用字符集来创建自定义的字符分类，只需要在方括号内将单个字符和字符分类组合起来即可。还可以在字符集中包含一段字符的范围，即写出字符范围的第一个字符和最后一个字符，并使用 - 将它们连接起来。在字符集前加上一个补字符 ^ 就可以得到该字符集对应的补集。

可以通过描述模式中重复和可选部分的修饰符来让模式更加有用。Lua 提供了 4 种修饰符。Lua 中的修饰符只能作用于一个字符模式，而无法作用于一组分类。

  • +：重复一次或多次
  • *：重复零次或多次
  • -：重复零次或多次（最小匹配）
  • ?：可选（出现零次或一次）

以 ^ 开头的模式表示从目标字符串的开头开始匹配，以 $ 结尾的模式表示匹配到目标字符串的结尾。这两个字符只有位于模式的开头和结尾才具有特殊含义，否则仅仅就是与其自身相匹配的普通字符。

%b 用于匹配成对的字符，%bxy 匹配以 x 开始、以 y 结束的子串。%f[char-set] 表示前置模式，该模式匹配一个空字符，其该空字符的后一个字符位于 char-set 内而前一个字符不在 char-set。注意目标字符串中的第一个字符之前被认为拥有一个空字符，最后一个字符之后也被认为拥有一个空字符。所以如下模式会匹配两次 the，包括开头的 the：

1
2
> print(string.gsub(s, '%f[%w]the%f[%W]', 'one'))
one anthem is one theme 2

捕获

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

对于具有捕获的模式，string.match 会将所有捕获到的值作为单独的结果返回：

1
2
3
4
> p = "name = Anna"
> k, v = string.match(p, "(%a+)%s*=%s*(%a+)")
> print(k, v)
name    Anna

在模式中，形如 %n 的分类（n 是一个数字）表示匹配第 n 个捕获的副本：

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

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

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

被捕获对象的第 3 个用途是在函数 gsub 的替代字符串中。和模式一样，替换字符串同样可以包含像 %n，当发生替换时会被替换为相应的捕获，%0 意味着整个匹配。

替换

上文讲过，string.gsub 的第 3 个参数不仅可以是字符串，还可以是一个函数或者表：

  • 当参数为函数时，string.gsub 会在每次查找到匹配时都调用该函数，参数是捕获到的内容而返回值则被作为替换字符串
  • 当参数为表时，string.gsub 会把第一个捕获到的内容作为 key，然后将表中对应的该 key 的值作为替换字符串

如果函数返回 nil 或者表中不包含该键，那么 gsub 不改变匹配。

1
2
3
4
5
6
7
8
function expand(s)
    return (string.gsub(s, "$(%w+)", _G))
end


name = "Lua"
status = "great"
print(expand("$name is $status, isn't it"))

在这段代码中使用到了 _G 这个表，它是预先定义的包括所有全局变量的表。

1
2
3
4
5
6
7
8
9
10
11
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}"))

在 Lua 中，() 空白捕获具有特殊的含义，该模式并不代表捕获空内容，而是捕获模式在目标字符串中的位置（该位置是数值）：

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

诀窍

  • 模式匹配是进行字符串处理的强大工具之一。但是模式匹配代替不了传统的解析器，对于那些用后即弃的程序来说，确实可以在源代码中做一些有用的操作，但是却很难构建出高质量的产品
  • 尽管 Lua 中使用模式匹配时的效率是足够高的，但是仍然需要注意，应该永远使用尽可能精确的模式
  • 要留心空模式，即匹配空字符串的模式，例如使用 %a* 来匹配名字，会发现到处是名字
  • 有时使用 Lua 来构造一个模式也很有用，例如 string.rep("[^\n]", 70) .. "+" 可以构造出一个模式，用来匹配超过 70 个字符的行
  • 模式匹配另一个有用的技巧是：在进行实际工作前先对目标字符串进行预先处理。
  • 是否能够将模式匹配函数用于 UTF-8 字符串取决于模式本身，恰当的模式能够为 Unicode 带来额外的能力。例如预定义模式 uft8.charpattern 可以用来精确匹配一个 UTF-8 字符

一个示例程序

如下代码用于统计出现频率最高的单词：

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
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)



local n = math.min(tonumber(arg[1]) or math.huge, #words)
for i = 1, n do
    io.write(words[i], "\t", counter[words[i]], "\n")
end