TimothyQiu's Blog

keep it simple stupid

Lua 学习笔记:协程

分类:技术

协程(coroutine)并不是 Lua 独有的概念,如果让我用一句话概括,那么大概就是:一种能够在运行途中主动中断,并且能够从中断处恢复运行的特殊函数。(嗯,其实不是函数。)

举个最原始的栗子

下面给出一个最简单的 Lua 中 coroutine 的用法演示:

function greet()
    print "hello world"
end

co = coroutine.create(greet) -- 创建 coroutine

print(coroutine.status(co))  -- 输出 suspended
print(coroutine.resume(co))  -- 输出 hello world
                             -- 输出 true (resume 的返回值)
print(coroutine.status(co))  -- 输出 dead
print(coroutine.resume(co))  -- 输出 false    cannot resume dead coroutine (resume 的返回值)
print(type(co))              -- 输出 thread

协程在创建时,需要把协程体函数传递给创建函数 create()。新创建的协程处于 suspended 状态,可以使用 resume 让其运行,全部执行完成后协程处于 dead 状态。如果尝试 resume 一个 dead 状态的,则可以从 resume 返回值上看出执行失败。另外你还可以注意到 Lua 中协程(coroutine)的变量类型其实叫做「thread」Orz...

乍一看可能感觉和线程没什么两样,但需要注意的是 resume() 只有在 greet() 以某种形式「返回」后才会返回(所以说协程像函数)。

函数执行的中断与再开

单从上面这个例子,我们似乎可以得出结论:协程果然就是某种坑爹的函数调用方式啊。然而,协程的真正魅力来自于 resumeyield 这对好基友之间的羁绊。

函数 coroutine.resume(co[, val1, ...])

开始或恢复执行协程 co

如果是开始执行,val1 及之后的值都作为参数传递给协程体函数;如果是恢复执行,val1 及之后的值都作为 yield() 的返回值传递。

第一个返回值(还记得 Lua 可以返回多个值吗?)为表示执行成功与否的布尔值。如果成功,之后的返回值是 yield 的参数;如果失败,第二个返回值为失败的原因(Lua 的很多函数都采用这种错误处理方式)。

当然,如果是协程体函数执行完毕 return 而不是 yield(),那么 resume() 第一个返回值后跟着的就是其返回值。

函数 coroutine.yield(...)

中断协程的执行,使得开启该协程的 coroutine.resume() 返回。再度调用 coroutine.resume() 时,会从该 yield() 处恢复执行。

当然,yield() 的所有参数都会作为 resume() 第一个返回值后的返回值返回。

OK,总结一下:当 co = coroutine.create(f) 时,yield()resume() 的关系如下图:

lua yield resume

How coroutine makes life easier

如果要求给某个怪写一个 AI:先向右走 30 帧,然后只要玩家进入视野就往反方向逃 15 帧。该怎么写?

传统做法

经典的纯状态机做法。

-- 每帧的逻辑
function Monster:frame()
    self:state_func()
    self.state_frame_count = self.state_frame_count + 1
end

-- 切换状态
function Monster:set_next_state(state)
    self.state_func = state
    self.state_frame_count = 0
end

-- 首先向右走 30 帧
function Monster:state_walk_1()
    local frame = self.state_frame_count
    self:walk(DIRECTION_RIGHT)
    if frame > 30 then
        self:set_next_state(state_wait_for_player)
    end
end

-- 等待玩家进入视野
function Monster:state_wait_for_player()
    if self:get_distance(player) < self.range then
        self.direction = -self:get_direction_to(player)
        self:set_next_state(state_walk_2)
    end
end

-- 向反方向走 15 帧
function Monster:state_walk_2()
    local frame = self.state_frame_count;
    self:walk(self.direction)
    if frame > 15 then
        self:set_next_state(state_wait_for_player)
    end
end

协程做法

-- 每帧的逻辑
function Monster:frame()
    -- 首先向右走 30 帧
    for i = 1, 30 do
        self:walk(DIRECTION_RIGHT)
        self:wait()
    end

    while true do
        -- 等待玩家进入视野
        while self:get_distance(player) >= self.range do
            self:wait()
        end

        -- 向反方向走 15 帧
        self.direction = -self:get_direction_to(player)
        for i = 1, 15 do
            self:walk(self.direction)
            self:wait()
        end
    end
end

-- 该帧结束
function Monster:wait()
    coroutine.yield()
end

额外说一句,从 wait() 函数可以看出,Lua 的协程并不要求一定要从协程体函数中调用 yield(),这是和 Python 的一个区别。

Lua 学习笔记:沙盒

分类:技术

背景知识

Lua 给我的感觉是:各种内置函数和标准库的存在感都是比较强的。如果执行这句:

for name in pairs(_G) do print(_G) end

就会把各种环境中已存在名称的打印出来:

这里的全局变量 _G 就是存放环境的表(于是会有 _G 中存在着 _G._G 的递归)。

于是,平时对于全局变量的访问就可以等同于对 _G 表进行索引:

value = _G[varname]  --> value = varname
_G[varname] = value  --> varname = value

改变函数的环境

函数的上下文环境可以通过 setfenv(f, table) 函数改变,其中 table 是新的环境表,f 表示需要被改变环境的函数。如果 f 是数字,则将其视为堆栈层级(Stack Level),从而指明函数(1 为当前函数,2 为上一级函数):

a = 3          -- 全局变量 a
setfenv(1, {}) -- 将当前函数的环境表改为空表
print(a)       -- 出错,因为当前环境表中 print 已经不存在了

没错,不仅是 a 不存在,连 print 都一块儿不存在了。如果需要引用以前的 print 则需要在新的环境表中放入线索:

a = 3
setfenv(1, { g = _G })
g.print(a)             -- 输出 nil
g.print(g.a)           -- 输出 3

沙盒

于是,出于安全或者改变一些内置函数行为的目的,需要在执行 Lua 代码时改变其环境时便可以使用 setfenv 函数。仅将你认为安全的函数或者新的实现加入新环境表中:

local env = {}  -- 沙盒环境表,按需要添入允许的函数

function run_sandbox(code)
  local func, message = loadstring(code)
  if not func then return nil, message end  -- 传入代码本身错误
  setfenv(func, env)
  return pcall(func)
end

Lua 5.2 的 _ENV 变量

Lua 5.2 中所有对全局变量 var 的访问都会在语法上翻译为 _ENV.var。而 _ENV 本身被认为是处于当前块外的一个局部变量。(于是只要你自己定义一个名为 _ENV 的变量,就自动成为了其后代码所处的「环境」(enviroment)。另有一个「全局环境」(global enviroment)的概念,指初始的 _G 表。)

Lua 的作者之一 Roberto Ierusalimschy 同志在介绍 Lua 5.2 时说:

the new scheme, with _ENV, allows the main benefit of setfenv with a little more than syntactic sugar.

就我的理解来说,优点就是原先虚无缥缈只能通过 setfenvgetfenv 访问的所谓「环境」终于实体化为一个始终存在的变量 _ENV 了。

于是以下两个函数内容大致是一样的:

-- Lua 5.1
function foobar()
  setfenv(1, {})
  -- code here
end

-- Lua 5.2
function foobar()
  local _ENV = {}
  -- code here
end

而更进一步的是,5.2 中对 load 函数作出了修改。(包括但不限于 :))合并了 loadstring 功能,并可以在参数中指定所使用的环境表:

local func, message = load(code, nil, "t", env)

参考

Lua 学习笔记:面向对象

分类:技术

没错,Lua 中只存在表(Table)这么唯一一种数据结构,但依旧可以玩出面向对象的概念。

添加成员函数

好吧,如果熟悉 C++ 还是很好理解类似的演化过程的:如果说 struct 里可以添加函数是从 C 过渡到 C++ 的第一认识的话,为 Table 添加函数也可以算是认识 Lua 是如何面向对象的第一步吧。

player = { health = 200 }  --> 一个普通的 player 表,这里看作是一个对象
function takeDamage(self, amount)
  self.health = self.health - amount
end

takeDamage(player, 20)  --> 调用

如何将独立的 takeDamage 塞进 player 中咧?答案是直接定义进去:

player = { health = 200 }
function player.takeDamage(self, amount)
  self.health = self.health - amount
end

player.takeDamage(player, 20)  --> 调用

这样就相当于在 player 表中添加了一个叫做 takeDamage 的字段,和下面的代码是一样的:

player = {
  health = 200,
  takeDamage = function(self, amount)  --> Lua 中的函数是 first-class value
    self.health = self.health - amount
  end
}

player.takeDamage(player, 20)  --> 调用

调用时的 player.takeDamage(player, 20) 稍显不和谐(据说用术语叫做 DRY),于是就要出动「冒号操作符」这个专门为此而生的语法糖了:

player:takeDamage(20)              --> 等同于 player.takeDamage(player, 20)
function player:takeDamage(amount) --> 等同于 function player.takeDamage(self, amount)

从对象到类

类的意义在于提取一类对象的共同点从而实现量产(我瞎扯的 >_<)。同样木有 Class 概念的 Javascript 使用 prototype 实现面向对象,Lua 则通过 Metatable 实现与 prototype 类似的功能。

Player = {}

function Player:create(o)    --> 参数 o 可以暂时不管
  o = o or { health = 200 }  --> Lua 的 or 与一般的 || 不同,如果非 nil 则返回该非 nil 值
  setmetatable(o, self)
  self.__index = self
  return o
end

function Player:takeDamage(amount)
  self.health = self.health - amount
end

playerA = Player:create()  --> 参数 o 为 nil
playerB = Player:create()

playerA:takeDamage(20)
playerB:takeDamage(40)

顾名思义 Metatable 也是一个 Table,可以通过在其中存放一些函数(称作 metamethod)从而修改一些默认的求值行为(如何显示为字符串、如何相加、如何连接、如何进行索引)。Metatable 的 __index 域设置了「如何进行索引」的方法。例如调用 foo.bar 时,如果在 foo 中没有找到名为 bar 的域时,则会调用 Metatable:__index(foo, bar)。于是:

playerA:takeDamage(20)

因为在 playerA 中并不存在 takeDamge 函数,于是求助于 Metatable:

getmetatable(playerA).__index.takeDamage(playerA, 20)

带入 Metatable 后:

Player.__index.takeDamage(playerA, 20)

因为 Player__indexcreate 时被指定为 self,所以最终变为:

Player.takeDamage(playerA, 20)

于是 takeDamageself 得到了正确的对象 playerA

继承

继承是面向对象的一大特性,明白了如何创建「类」,那么继承也就比较明了了,还记得大明湖畔的参数 o 么?

RMBPlayer = Player:create()
function RMBPlayer:broadcast(message)  --> 为子类添加新的方法
  print(message)
end
function RMBPlayer:takeDamage(amount)  --> 子类重载父类方法
  self.health = self.health - amount / (self.money / 100)
end

vip = RMBPlayer:create { money = 200 } --> 子类添加新成员(单个 Table 作为参数可以省略括号)

vip:takeDamage(20)
vip:broadcast("F*ck")

以上便是 Lua 中实现面向对象的基本方法。

Lua 学习笔记:贰

分类:技术

最近不是特别忙,于是就抽空开始继续看 PIL 了。

变量声明与 C 语言的不同

Lua 中有一个常见的用法,不论变量、函数都可以用下面这种方法保存到局部变量中(同时加快访问速度):

local foo = foo

书里加了个括号来解释这种写法:

The local foo becomes visible only after its declaration.

这一点需要瞎扯的是 C 语言里相应的东西。

int foo = 12;
int bar = 6;

void foobar(void)
{
    int foo = foo;
    int bar[bar];
}

与 Lua 不同,在 C 语言中初始赋值是声明之后的事情。所以这里函数 foobar 中的 foo 会被初始化为自己(而不是全局的 foo,所以值不确定),bar 却被合法地定义为一个含有 6 个元素的数组。

看似多余的限制

另一个有趣的现象是在 4.4 节中说到:

For syntactic reasons, a break or return can appear only as the last statement of a block; in other words, as the last statement in your chunk or just before an end, an else, or an until.

乍一看觉得加上这个限制真是麻烦,但想想这不正是 break/return 的正确用法么?因为其后的语句都永远不会被执行到,所以如果不是在块的最后写 break/return 是毫无意义的(调试除外)。虽然看上去是挺多余的一段话,但也算是说出了事物的本源。

函数的本质

第六章 More About Functions 中说到我们平时在 Lua 中写的函数声明

function foo (x) return 2*x end

其实是一种语法糖,本质上我们可以把它写成如下代码:

foo = function (x) return 2*x end

于是也就可以说

终于有用的知识

在第 47 页看到了一段令人泪流满面的代码和运行结果:

function derivative (f, delta)
  delta = delta or 1e-4
  return function (x)
           return (f(x + delta) - f(x))/delta
         end
end

c = derivative(math.sin)
print(math.cos(10), c(10))
  --> -0.83907152907645 -0.83904432662041

最初我并不知道 derivative 是什么意思,但看了示例代码和运行结果,顿时恍然大悟:这货不就是导数吗?

高数里的东西竟然真的在现实生活中出现了!顿时觉得世界真美好 =ω=

睡眠排序算法

分类:技术

4chan 上有个家伙发帖说他发明了一种很牛叉的排序算法:睡眠排序(Sleep Sort):

#!/bin/bash
function f() {
    sleep "$1"
    echo "$1"
}
while [ -n "$1" ]
do
    f "$1" &
    shift
done
wait

主要就是对输入的每一个数都新开一个进程,进程里用这个数进行倒数,倒数到0就输出这个数。于是较小数就先输出、较大数后输出。睡排成功~

当然啦群众的眼睛是雪亮的,纷纷指出这个会存在竞态条件,而且如果的数比较大会很悲催(比如要排的数字里有86400的话,那么至少要等86400秒,也就是一整天 =。=),时间复杂度是 O(最大的那个数)……

在这个欢乐的帖子里还看到了各种其它语言对睡眠排序的实现,包括一个 Lua 的(#165):

#!/usr/bin/env lua
function sleepsort(arr)
    local res, thread = {}, {}
    local nthreads = #arr

    for i = 1, #arr do
        thread[i] = coroutine.create(function()
            for n=arr[i], 0, -1 do coroutine.yield() end
            nthreads = nthreads - 1
            thread[i] = nil
            res[#res+1] = arr[i]
        end)
    end
    while nthreads > 0 do
        for i = 1, #arr do
            if thread[i] then coroutine.resume(thread[i]) end
        end
    end
    return res
end

math.randomseed(os.time())
local arr = {}
for i = 1,10 do arr[i] = math.random(1,99) end
print(unpack(sleepsort(arr)))

嗯哼~ Lua 的 coroutine 还是很强大滴(<ゝω·)

p.s. 终于还是见识到了最无厘头撞大运的 Bogo 排序算法

while not inOrder(deck) do
    shuffle(deck);