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 这对好基友之间的羁绊。

阅读剩余部分...

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)这么唯一一种数据结构,但依旧可以玩出面向对象的概念。

阅读剩余部分...

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