跟着 Lua 5.1 官方参考文档学习 Lua (6)

2.11 – Coroutines

Lua supports coroutines, also called collaborative multithreading. A coroutine in Lua represents an independent thread of execution. Unlike threads in multithread systems, however, a coroutine only suspends its execution by explicitly calling a yield function.

You create a coroutine with a call to coroutine.create. Its sole argument is a function that is the main function of the coroutine. The create function only creates a new coroutine and returns a handle to it (an object of type thread); it does not start the coroutine execution.

When you first call coroutine.resume, passing as its first argument a thread returned by coroutine.create, the coroutine starts its execution, at the first line of its main function. Extra arguments passed to coroutine.resume are passed on to the coroutine main function. After the coroutine starts running, it runs until it terminates or yields.

A coroutine can terminate its execution in two ways: normally, when its main function returns (explicitly or implicitly, after the last instruction); and abnormally, if there is an unprotected error.

In the first case, coroutine.resume returns true, plus any values returned by the coroutine main function. In case of errors, coroutine.resume returns false plus an error message.

A coroutine yields by calling coroutine.yield. When a coroutine yields, the corresponding coroutine.resume returns immediately, even if the yield happens inside nested function calls (that is, not in the main function, but in a function directly or indirectly called by the main function).

In the case of a yield, coroutine.resume also returns true, plus any values passed to coroutine.yield. The next time you resume the same coroutine, it continues its execution from the point where it yielded, with the call to coroutine.yield returning any extra arguments passed to coroutine.resume.

Like coroutine.create, the coroutine.wrap function also creates a coroutine, but instead of returning the coroutine itself, it returns a function that, when called, resumes the coroutine. Any arguments passed to this function go as extra arguments to coroutine.resume. coroutine.wrap returns all the values returned by coroutine.resume, except the first one (the boolean error code). Unlike coroutine.resume, coroutine.wrap does not catch errors; any error is propagated to the caller.

As an example, consider the following code:

     function foo (a)
       print("foo", a)
       return coroutine.yield(2*a)
     end
     
     co = coroutine.create(function (a,b)
           print("co-body", a, b)
           local r = foo(a+1)
           print("co-body", r)
           local r, s = coroutine.yield(a+b, a-b)
           print("co-body", r, s)
           return b, "end"
     end)
            
     print("main", coroutine.resume(co, 1, 10))
     print("main", coroutine.resume(co, "r"))
     print("main", coroutine.resume(co, "x", "y"))
     print("main", coroutine.resume(co, "x", "y"))

When you run it, it produces the following output:

     co-body 1       10
     foo     2
     
     main    true    4
     co-body r
     main    true    11      -9
     co-body x       y
     main    true    10      end
     main    false   cannot resume dead coroutine

补充：

例子：生产者和消费者

producer = coroutine.create(
	function ()
		while true do
			local x = io.read()
			send(x)
		end
	end
)

function consumer ()
	while true do
		local x = receive()
		io.write(x, "\n")
	end
end

function receive ()
	local status, value = coroutine.resume(producer)
	return value
end

function send (x)
	coroutine.yield(x)
end


consumer()

We can extend this design with filters, which are tasks that sit between the producer and the consumer doing some kind of transformation in the data. A filter is a consumer and a producer at the same time, so it resumes a producer to get new values and yields the transformed values to a consumer.

例子：管道和过滤器

function receive (prod)
	local status, value = coroutine.resume(prod)
	return value
end

function send (x)
	coroutine.yield(x)
end

function producer ()
    return coroutine.create(function ()
            while true do
            local x = io.read() -- produce new value
            send(x)
        end
    end)
end

function filter (prod)
    return coroutine.create(function ()
            for line = 1, math.huge do
            local x = receive(prod) -- get new value
            x = string.format("%5d %s", line, x)
            send(x) -- send it to consumer
        end
    end)
end

function consumer (prod)
	while true do
		local x = receive(prod)
		io.write(x, "\n")
	end
end


p = producer()
f = filter(p)
consumer(f)

If you thought about Unix pipes after reading the previous example, you are not alone. After all, coroutines are a kind of (non-preemptive) multithreading. While with pipes each task runs in a separate process, with coroutines each task runs in a separate coroutine. Pipes provide a buffer between the writer (producer) and the reader (consumer) so there is some freedom in their relative
speeds. This is important in the context of pipes, because the cost of switching between processes is high. With coroutines, the cost of switching between tasks is much smaller (roughly the same as a function call), so the writer and the reader can run hand in hand.

补充：Iterators and the Generic for

7.1 Iterators and Closures

An iterator is any construction that allows you to iterate over the elements of a collection. In Lua, we typically represent iterators by functions: each time we call the function, it returns the “next” element from the collection.

Every iterator needs to keep some state between successive calls, so that it knows where it is and how to proceed from there. Closures provide an excellent mechanism for this task. Remember that a closure is a function that accesses one or more local variables from its enclosing environment. These variables keep their values across successive calls to the closure, allowing the closure to remember where it is along a traversal. Of course, to create a new closure we must also create its non-local variables. Therefore, a closure construction typically involves two functions: the closure itself and a factory, the function that creates the closure.

As an example, let us write a simple iterator for a list. Unlike ipairs, this iterator does not return the index of each element, only its value:

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

In this example, values is the factory. Each time we call this factory, it creates a new closure (the iterator itself). This closure keeps its state in its external variables t and i. Each time we call the iterator, it returns a next value from the list t. After the last element the iterator returns nil, which signals the end of the iteration.

We can use this iterator in a while loop:

t = { 10, 20, 30 }
iter = values(t)       -- creates the iterator
while true do
    local element = iter() -- calls the iterator
    if element == nil then break end
    print(element)
end

However, it is easier to use the generic for. After all, it was designed for this kind of iteration:

t = { 10, 20, 30 }
for element in values(t) do
    print(element)
end

The generic for does all the bookkeeping for an iteration loop: it keeps the iterator function internally, so we do not need the iter variable; it calls the iterator on each new iteration; and it stops the loop when the iterator returns nil. (In the next section we will see that the generic for does even more than that.)

例子：Iterator to traverse all words from the input file

function allwords()
    local line = io.read()                    -- current line
    local pos = 1                             -- current position in the line
    return function()                         -- iterator function
        while line do                         -- repeat while there are lines
            local s, e = string.find(line, "%w+", pos)
            if s then                         -- found a word?
                pos = e + 1                   -- next position is after this word
                return string.sub(line, s, e) -- return the word
            else
                line = io.read()              -- word not found; try next line
                pos = 1                       -- restart from first position
            end
        end
        return nil -- no more lines: end of traversal
    end
end

for word in allwords() do
    print(word)
end

A for statement like

     for var_1, ···, var_n in explist do block end

is equivalent to the code:

     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

We call the first variable var_1 in the list the control variable. Its value is never nil during the loop, because when it becomes nil the loop ends.

The first thing the for does is to evaluate the expressions after the in. These expressions should result in the three values kept by the for: the iterator function, the invariant state, and the initial value for the control variable. Like in a multiple assignment, only the last (or the only) element of the list【explist】 can result in more than one value; and the number of values is adjusted to three, extra values being discarded or nils added as needed.

(When we use simple iterators, the factory returns only the iterator function, so the invariant state and the control variable get nil.)

After this initialization step, the for calls the iterator function with two arguments: the invariant state and the control variable. (From the standpoint of the for construct, the invariant state has no meaning at all. The for only passes the state value from the initialization step to the calls to the iterator function.) Then the for assigns the values returned by the iterator function to the variables declared by its variable list. If the first value returned (the one assigned to the control variable) is nil, the loop terminates. Otherwise, the for executes its body and calls the iteration function again, repeating the process.

7.3 Stateless Iterators

As the name implies, a stateless iterator is an iterator that does not keep any state by itself. Therefore, we may use the same stateless iterator in multiple loops, avoiding the cost of creating new closures.

For each iteration, the for loop calls its iterator function with two arguments: the invariant state and the control variable. A stateless iterator generates the next element for the iteration using only these two values.

例子：ipairs 和 pairs 函数

local function iter(a, i)
    i = i + 1
    local v = a[i]
    if v then
        return i, v
    end
end

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

local a = {"a", "b", "c" ,"d"}
for i,v in ipairs(a) do
    print(i, v)
end

-- The call next(t,k), where k is a key of the table t, returns a next key in the
-- table, in an arbitrary order, plus the value associated with this key as a second
-- return value. The call next(t,nil) returns a first pair. When there are no more
-- pairs, next returns nil.
function pairs(t)
    return next, t, nil
end

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

7.4 Iterators with Complex State

Frequently, an iterator needs to keep more state than fits into a single invariant state and a control variable. The simplest solution is to use closures. An alternative solution is to pack all it needs into a table and use this table as the invariant state for the iteration. Using a table, an iterator can keep as much data as it needs along the loop. Moreover, it can change this data as it goes.
Although the state is always the same table (and therefore invariant), the table contents change along the loop. Because such iterators have all their data in the state, they typically ignore the second argument provided by the generic for (the iterator variable).

As an example of this technique, we will rewrite the iterator allwords, which traverses all the words from the current input file. This time, we will keep its state using a table with two fields: line and pos.

例子：重写 allwords 迭代器

local iterator -- to be defined later
function allwords()
    local state = { line = io.read(), pos = 1 }
    return iterator, state
end

function iterator(state)
    while state.line do -- repeat while there are lines
        -- search for next word
        local s, e = string.find(state.line, "%w+", state.pos)
        if s then -- found a word?
            -- update next position (after this word)
            state.pos = e + 1
            return string.sub(state.line, s, e)
        else               -- word not found
            state.line = io.read() -- try next line...
            state.pos = 1  -- ... from first position
        end
    end
    return nil -- no more lines: end loop
end

for word in allwords() do
    print(word)
end

Whenever possible, you should try to write stateless iterators, those that keep all their state in the for variables. With them, you do not create new objects when you start a loop. If you cannot fit your iteration into this model, then you should try closures. Besides being more elegant, typically a closure is more efficient than an iterator using tables is: first, it is cheaper to create a closure than a table; second, access to non-local variables is faster than access to table fields. Later we will see yet another way to write iterators, with coroutines. This is the most powerful solution, but a little more expensive.

补充：9.3 Coroutines as Iterators

We can see loop iterators as a particular example of the producer–consumer pattern: an iterator produces items to be consumed by the loop body. Therefore, it seems appropriate to use coroutines to write iterators. Indeed, coroutines provide a powerful tool for this task. Again, the key feature is their ability to turn upside-down the relationship between caller and callee. With this feature, we can write iterators without worrying about how to keep state between successive
calls to the iterator.

To illustrate this kind of use, let us write an iterator to traverse all permutations of a given array.

例子：生成排列

function printResult (a)
    for i = 1, #a do
        io.write(a[i], " ")
    end
    io.write("\n")
end

function permgen (a, n)
    n = n or #a -- default for ’n’ is size of ’a’
    if n <= 1 then -- nothing to change?
        printResult(a)
    else
        for i=1,n do
            -- put i-th element as the last one
            a[n], a[i] = a[i], a[n]
            -- generate all permutations of the other elements
            permgen(a, n - 1)
            -- restore i-th element
            a[n], a[i] = a[i], a[n]
        end
    end
end

permgen ({1,2,3,4})

改写成协程的版本：

function printResult (a)
    for i = 1, #a do
        io.write(a[i], " ")
    end
    io.write("\n")
end

function permgen (a, n)
    n = n or #a -- default for ’n’ is size of ’a’
    if n <= 1 then -- nothing to change?
        coroutine.yield(a)
    else
        for i=1,n do
            -- put i-th element as the last one
            a[n], a[i] = a[i], a[n]
            -- generate all permutations of the other elements
            permgen(a, n - 1)
            -- restore i-th element
            a[n], a[i] = a[i], a[n]
        end
    end
end

function permutations (a)
    local co = coroutine.create(function () permgen(a) end)
    return function () -- iterator
        local code, res = coroutine.resume(co)
        return res
    end
end

for p in permutations{"a", "b", "c"} do
    printResult(p)
end

The permutations function uses a common pattern in Lua, which packs a call to resume with its corresponding coroutine inside a function. This pattern is so common that Lua provides a special function for it: coroutine.wrap. Like create, wrap creates a new coroutine. Unlike create, wrap does not return the coroutine itself; instead, it returns a function that, when called, resumes the
coroutine. Unlike the original resume, that function does not return an error code as its first result; instead, it raises the error in case of error. Using wrap, we can write permutations as follows:

function permutations(a)
    return coroutine.wrap(function() permgen(a) end)
end

Usually, coroutine.wrap is simpler to use than coroutine.create. It gives us exactly what we need from a coroutine: a function to resume it. However, it is also less flexible. There is no way to check the status of a coroutine created with wrap. Moreover, we cannot check for runtime errors.

例子：使用协程下载多个文件

local socket = require "socket"


function receive(connection)
    connection:settimeout(0) -- do not block
    local s, status, partial = connection:receive(2 ^ 10)
    if status == "timeout" then
        coroutine.yield(connection)
    end
    return s or partial, status
end

function download(host, file)
    local c = assert(socket.connect(host, 80))
    local count = 0 -- counts number of bytes read
    c:send("GET " .. file .. " HTTP/1.0\r\n\r\n")
    while true do
        local s, status, partial = receive(c)
        count = count + #(s or partial)
        if status == "closed" then break end
    end
    c:close()
    print(file, count)
end

threads = {} -- list of all live threads
function get(host, file)
    -- create coroutine
    local co = coroutine.create(function()
        download(host, file)
    end)
    -- insert it in the list
    table.insert(threads, co)
end

function dispatch()
    local i = 1
    local connections = {}
    while true do
        if threads[i] == nil then -- no more threads?
            if threads[1] == nil then break end
            i = 1                 -- restart the loop
            connections = {}
        end
        local status, res = coroutine.resume(threads[i])
        if not res then -- thread finished its task?
            table.remove(threads, i)
        else            -- time out
            i = i + 1
            connections[#connections + 1] = res
            if #connections == #threads then -- all threads blocked?
                -- wait for any of these connections to change status
                socket.select(connections)
            end
        end
    end
end

host = "www.w3.org"
get(host, "/TR/html401/html40.txt")
get(host, "/TR/2002/REC-xhtml1-20020801/xhtml1.pdf")
get(host, "/TR/REC-html32.html")
get(host, "/TR/2000/REC-DOM-Level-2-Core-20001113/DOM2-Core.txt")

dispatch()

需要安装 luasocket 库

luarocks install luasocket