Корутины (сопрограммы) — функции, которые могут приостанавливать исполнение и возобновлять впоследствии. Lua поддерживает их из коробки. В гайде — история об этих зверях с подробностями.
Введение
Концепт корутин не новый: появился он в шестидесятых годах прошлого века. Корутины использовали в те времена для реализации многопоточности, так как полноценные потоки требовали много ресурсов. В конце девяностых — начале нулевых дороговизна перестала сильно мешаться, и о корутинах подзабыли.
Но люди одумались, когда стали писать много сетевого (по сути, вебовского) софта. Серверы, обрабатывающие по десятку тысяч запросов в секунду, теперь не редкость. Потому серверы делают быстрыми. Чтобы убрать оверхед от полноценных потоков, снова потребовались корутины. Новые версии языков: JavaScript, Rust, Kotlin, Python, Go, C++ и т. д. — пытаются выделиться их поддержкой.
В Lua корутины появились в версии 5.0 — она выпущена в 2003 году, до этого хайпа. Если понять, как они работают в этом языке, проще изучать аналогичные реализации в других. Поэтому приступим.
1. Итератор Фибоначчи
Начнём с наивного примера: обнаружив итеративный цикл for, вам почему-то захотелось создать итератор последовательности Фибоначчи.
1
2
3
4
5
6
7
8
9
10
11
12
13
local function fibonacciSeq(n)
local result = {} (1)
for i = 1, n do
result[i] = (result[i - 2] or 0) + (result[i - 1] or 1) (2)
end
return ipairs(result) (3)
end
for _, n in fibonacciSeq(10) do (4)
print(n)
end
1 | Создаём таблицу. |
2 | Наполняем её числами из последовательности Фибоначчи. |
3 | Возвращаем итератор. |
4 | Запускаем цикл на 10 элементов. |
Функция fibonacciSeq
сначала готовит сразу все элементы, а потом отдаёт итератор.
Решение это плохое: если n
слишком большое, закончится память.
Переделаем функцию так, чтобы считать по одному числу, а не сразу все:
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
local function fibonacciSeq(n)
local penultimate = 1
local i = 0
return function(_, previous) (1) (2)
local result = penultimate + previous
penultimate = previous
i = i + 1
if i <= n then
return result
end
end, nil, 0 (3)
end
for n in fibonacciSeq(10) do (4)
print(n)
end
1 | Здесь создаём замыкание: функция обрастает стейтом и обращается к нему за предпоследним значением. |
2 | Итераторы в Lua первым аргументом получают иммутабельный стейт, а вторым — предыдущий элемент. |
3 | Для запуска цикла for нужны три значения:
|
4 | И снова запускаем на 10 элементов. |
Это решение лучше.
Если сделать break
, лишние значения считаться не будут.
Однако для такой задачи код странно многословен.
Другое решение — на корутинах:
1
2
3
4
5
6
7
8
9
10
11
12
13
14
local function fibonacciSeq(n)
return coroutine.wrap(function()
local penultimate, previous = 1, 0
for i = 1, n do
penultimate, previous = previous, penultimate + previous
coroutine.yield(previous)
end
end)
end
for n in fibonacciSeq(10) do
print(n)
end
Напоминает первый вариант.
Здесь тоже цикл.
Однако с толку сбивают coroutine.wrap
и coroutine.yield
.
Давайте разбираться.
2. Принцип работы корутин
Корутина — надстройка над функцией, в которой можно вернуть значения несколько раз. Вот как они работают:
-
Создаём корутину.
-
Запускаем корутину, передаём аргументы.
-
Корутина запускается, обрабатывает аргументы, возвращает какие-то значения.
-
Значения снаружи получаем и снова запускаем корутину, передавая уже другие значения.
-
Корутина принимает их и продолжает работу с момента остановки.
Затем она так же может приостановить исполнение. Продолжается так, пока корутина не завершится насовсем. Или можно её не вызвать в очередной раз.
Перенесём всё это в код.
-
Создаёт корутину
coroutine.create
— ей нужна функция, которая станет кодом корутины.1 2 3 4
local co = coroutine.create(function(a, b) print(a, b) ... end)
-
Запускаем через
coroutine.resume
, передавая корутину и аргументы.1 2 3 4 5 6
local co = coroutine.create(function(a, b) print(a, b) ... end) coroutine.resume(co, 42, 24)
-
Пока корутина работает, как обычная функция. Получает
a
,b
, принтит их. Приостановим её: используемcoroutine.yield
.1 2 3 4 5 6 7
local co = coroutine.create(function(a, b) print(a, b) coroutine.yield(a + b) ... end) local success, sum = coroutine.resume(co, 42, 24)
-
Теперь мы снаружи.
coroutine.resume
рапортует об успехе и отдаёт, что вернула корутина. Успех сохраним вsuccess
, а отданное — вsum
. Опять запустим корутину.1 2 3 4 5 6 7 8
local co = coroutine.create(function(a, b) print(a, b) local c, d = coroutine.yield(a + b) ... end) local success, sum = coroutine.resume(co, 42, 24) coroutine.resume(co, sum, 12)
-
Корутина приняла
sum
(вc
) и12
(вd
) и желает завершиться насовсем. Делает она этоreturn
ом. И тоже передаёт значения.1 2 3 4 5 6 7 8
local co = coroutine.create(function(a, b) print(a, b) local c, d = coroutine.yield(a + b) return a * b * c * d end) local success, sum = coroutine.resume(co, 42, 24) local success, product = coroutine.resume(co, sum, 12)
-
coroutine.resume
исправно отдаёт произведение.
Подытожим.
coroutine.create(f)
-
Создаёт корутину из функции
f
. coroutine.resume(co, ...)
-
Запускает корутину
co
и передаёт ей все дополнительные аргументы. Когда корутина останавливается или завершается насовсем,coroutine.resume
вернётtrue
и всё, что передала корутина. Если же возникла ошибка, вернётfalse
и сообщение об ошибке. coroutine.yield(...)
-
Приостановит корутину, а всё, что функции дано, передаст в
coroutine.resume
. Если корутина затем снова возобновляется,coroutine.yield
вернёт всё, что передали извне. coroutine.wrap(f)
-
Возвращает обёртку, создавая корутину из функции
f
. Обёртка — функция, которая работает, какcoroutine.resume
. С тремя отличиями:-
Не надо самому передавать корутину.
-
Не добавляет
true
илиfalse
в начало. -
Пробрасывает ошибку наружу.
-
Подробнее — в главе ниже.
2.1. Корутины в движении
Чтобы понять работу корутин, нужно знать, как Lua интерпретирует код. Это легко разъясняется на видео.
Кнопочки мотают видео на один кадр вперёд/назад. |
Дальше в гайде будут такие же видяхи.
3. Coroutine API
Раскроем подробнее весь функционал, который Lua предоставляет для работы с корутинами.
coroutine.create(f)
-
Создаёт корутину из функции
f
. Эта функция называется главной. coroutine.resume(co, ...)
-
Запускает корутину
co
и передаёт ей содержимое...
:-
Если корутина запускается в первый раз, то эти значения функция получает как аргументы.
Листинг 3.1. Отправка данных корутине при первом запуске.1 2 3 4 5 6
local co = coroutine.create(function(...) print(...) end) coroutine.resume(co, 7, 21, 42) --> 7 21 42
-
Иначе данные эти возвращаются функцией
coroutine.yield
:Листинг 3.2. Отправка данных при последующем запуске.1 2 3 4 5 6 7 8 9 10 11 12
local co = coroutine.create(function(a) (1) print("Got value a = " .. a) local b = coroutine.yield() (2) print("Got value b = " .. b) return a + b end) coroutine.resume(co, 2) (1) --> Got value a = 2 coroutine.resume(co, 8) (2) --> Got value b = 8
1 Первый запуск: корутина получает данные как аргументы. 2 Последующий запуск: значения возвращает coroutine.yield
.
Возвращаемые значения- Если возникла ошибка
-
Первое значение —
false
, второе — сообщение об ошибке.Листинг 3.3. Ошибка внутри корутины.1 2 3 4 5 6 7 8 9
local co = coroutine.create(function() error("error example") end) print(coroutine.resume(co)) --> false example.lua:2: error example print(coroutine.resume(co)) --> false cannot resume dead coroutine
Стэк вызовов при ошибке в корутине не "разматывается". Это означает, что можно использовать debug.traceback
,debug.getlocal
и прочие функции из либыdebug
, чтобы получить подробную информацию об ошибке. - Если корутина вызвала
coroutine.yield
-
Первое значение —
true
, остальные — аргументы функцииcoroutine.yield
.Листинг 3.4. Вызовcoroutine.yield
.1 2 3 4 5 6
local co = coroutine.create(function() coroutine.yield(42, 21, 7) end) print(coroutine.resume(co)) --> true 42 21 7
- Если корутина достигла конца исполнения
-
Первое значение —
true
, остальные — то, что вернула корутина.Листинг 3.5. Возврат в корутине.1 2 3 4 5 6
local co = coroutine.create(function() return 7, 21, 42 end) print(coroutine.resume(co)) --> true 7 21 42
-
coroutine.yield(...)
-
Приостанавливает выполнение корутины.
Аргументы этой функции возвращаются в вызов
coroutine.resume
.Возвращает данные, переданные аргументами при следующем вызове
coroutine.resume
.Эту функцию можно вызвать только внутри корутины. Если попытаться сделать это вне корутины (в главном потоке), выбросит ошибку.
Листинг 3.6. Вызовcoroutine.yield
вне корутины.1 2 3 4 5 6
coroutine.yield() --! attempt to yield from outside a coroutine --! stack traceback: --! [C]: in function 'coroutine.yield' --! example.lua:1: in main chunk --! [C]: in ?
Рисунок 1. Опасная схема вызовов.coroutine.yield
может выбросить ошибку даже внутри корутины. Это бывает, если вызватьcoroutine.yield
внутри Lua-функции, которую вызывает определённая C-функция внутри корутины. Конкретно то, какие это C-функции, зависит от их внутренностей, в которые не будем вдаваться. Вот все найденные мною случаи (y
во всех случаях — это функция, вызывающаяcoroutine.yield
):- Нет проблем
-
-
load("coroutine.yield()")()
-
pcall(y)
-
xpcall(y)
-
- Могут быть проблемы
-
-
Внутри метаметода
__gc
-
load(y)
-
xpcall(f, y)
-
ipairs(t)
, если уt
метаметод__ipairs
—y
-
pairs(t)
, если уt
метаметод__pairs
—y
-
require
, если уpackage.searchers
метаметод__index
—y
-
require
, если уpackage.loaded
метаметод__index
—y
-
require
, если уpackage.preload
метаметод__index
—y
-
require
, если уpackage.loaded
метаметод__newindex
—y
-
print(t)
, если уt
метаметод__tostring
—y
-
tostring(t)
, если уt
метаметод__tostring
—y
-
string.format("%s", t)
, если уt
метаметод__tostring
—y
-
string.gsub(s, pattern, y)
-
string.gsub(s, pattern, t)
, если уt
метаметод__index
—y
-
table.insert(t)
, если уt
метаметод__index
—y
-
table.insert(t)
, если уt
метаметод__newindex
—y
-
table.insert(t)
, если уt
метаметод__len
—y
-
table.concat(t)
, если уt
метаметод__len
—y
-
table.concat(t)
, если уt
метаметод__index
—y
-
table.move(t1, f, e, t, t2)
, если уt1
метаметод__index
—y
-
table.move(t1, f, e, t, t2)
, если уt2
метаметод__newindex
—y
-
table.remove(t)
, если уt
метаметод__len
—y
-
table.remove(t)
, если уt
метаметод__index
—y
-
table.remove(t)
, если уt
метаметод__newindex
—y
. -
table.sort(t, f)
, если уt
метаметод__len
—y
-
table.sort(t, f)
, если уt
метаметод__index
—y
-
table.sort(t, y)
-
table.unpack(t)
, если уt
метаметод__len
—y
-
table.unpack(t)
, если уt
метаметод__index
—y
-
os.time(t)
, если уt
метаметод__index
—y
-
debug.sethook(y, mask)
-
Поэтому будьте осторожны, если будете вызывать
coroutine.yield
внутри метаметодов.Листинг 3.7. Ошибка"attempt to yield across a C-call boundary"
.1 2 3 4 5 6
print(coroutine.resume(coroutine.create(function() return pairs(setmetatable({}, {__pairs = function() return coroutine.yield() end})) end))) --> false attempt to yield across a C-call boundary
coroutine.running()
-
Возвращает корутину, в которой вызвана эта функция.
Вторым значением также возвращает
true
, если функция вызвана в главном потоке, илиfalse
в противном случае.Листинг 3.8. Вызовcoroutine.running
в корутине.1 2 3 4
coroutine.resume(coroutine.create(function() print(coroutine.running()) end)) --> thread: 0x558a80ef07e8 false
Листинг 3.9. Вызовcoroutine.running
в главном потоке.1 2
print(coroutine.running()) --> thread: 0x558a80e92268 true
coroutine.wrap(f)
-
Создаёт новую корутину из функции
f
.Возвращает новую функцию: при её вызове корутина возобновляется с переданными аргументами. Возвращает эта функция всё, что передаст корутина.
Если возникает ошибка,
coroutine.wrap
не перехватывает её, в отличие отcoroutine.resume
.Листинг 3.10. Вариантcoroutine.wrap
на чистом Lua.1 2 3 4 5 6 7 8 9 10 11 12 13
function coroutine.wrap(f) local co = coroutine.create(f) return function(...) local executionResult = table.pack(coroutine.resume(co, ...)) if executionResult[1] then return table.unpack(executionResult, 2, executionResult.n) (1) else error(executionResult[2], 2) end end end
1 coroutine.wrap
возвращает только то, что передала корутина. Этим она также отличается отcoroutine.resume
: та добавляет ещёtrue
/false
первым значением. coroutine.status(co)
-
Возвращает статус корутины
co
:"running"
co
— корутина, которая вызвалаcoroutine.status
.Листинг 3.11. Статус"running"
.1 2 3 4
coroutine.resume(coroutine.create(function() print(coroutine.status(coroutine.running())) end)) --> running
"suspended"
Корутина ещё не запускалась или была приостановлена вызовом
coroutine.yield
.Листинг 3.12. Статус"suspended"
.1 2 3 4 5 6 7 8 9 10
local co = coroutine.create(function() coroutine.yield() end) print(coroutine.status(co)) (1) --> suspended coroutine.resume(co) (2) print(coroutine.status(co)) --> suspended
1 Корутина ещё не запущена. 2 Корутина приостановлена вызовом coroutine.yield
."normal"
Корутина запустила другую корутину.
Листинг 3.13. Статус"normal"
.1 2 3 4 5 6
local mainThread = coroutine.running() coroutine.resume(coroutine.create(function() print(coroutine.status(mainThread)) end)) --> normal
"dead"
Корутина завершила свою работу: или достигнув конца, или из-за ошибки.
Исполнение такой корутины больше нельзя возобновить.
Листинг 3.14. Статус"dead"
.1 2 3 4 5 6 7 8 9
local co = coroutine.create(function() end) print(coroutine.resume(co)) --> true print(coroutine.status(co)) --> dead print(coroutine.resume(co)) --> false cannot resume dead coroutine
Листинг 3.15. Статус"dead"
в результате ошибки.1 2 3 4 5 6 7
local co = coroutine.create(function() error("error example") end) coroutine.resume(co) print(coroutine.status(co)) --> dead
coroutine.isyieldable()
-
Возвращает
true
, если можно вызватьcoroutine.yield
.Если эта функция вернула
true
, то:-
она была вызвана в работающей корутине
-
и вызов этой функции не находится внутри C-функции, откуда нельзя вызвать
coroutine.yield
.
-
4. Классификация корутин
В разных языках корутины тоже разные.
-
Асимметричный: есть иерархия корутин.
Используется в Lua.
-
У любой корутины, кроме главной, есть вызвавшая её “родительская” корутина.
-
Когда корутина завершается, она не может выбрать, куда отдать значение: его получит родитель.
-
Функция обычная работает так же: когда завершается, значения тоже возвращаются вызвавшему её коду.
-
Есть отдельные операции
resume
иyield
. -
Проще в понимании.
-
Применяют в языках, где в основном корутины — итераторы.
Рисунок 2. Иерархия асимметричных корутин. -
-
Симметричный: иерархии корутин нет.
-
Корутины могут выбрать, куда передать значение.
-
Сделать просто
yield
, не указывая корутины, они не могут. -
resume
иyield
— одна операция: корутина приостанавливает себя и запускает другую. -
Управлять ими гораздо сложнее.
-
Обычно присутствуют в языках, которые реализуют через них многопоточность.
Рисунок 3. Иерархия симметричных корутин. -
Здесь не тот случай, когда сложность компенсируется мощью. Из асимметричных корутин делаются симметричные и наоборот. Поэтому языкам достаточно предоставить одну из двух реализаций.
-
В Lua корутина — объект первого класса (как и числа, строки, функции — и другие типы данных в Lua):
-
Её можно записать в переменную.
-
Её можно передать аргументом функции.
-
Она может не иметь имени (то есть не требуется в переменную сложить сначала, чтобы использовать).
-
Её может вернуть функция.
-
Её можно создать в процессе работы программы (в рантайме).
-
-
Бывают ограниченные корутины: например, если использовать можно только в цикле.
Ещё один вид классификации — по тому, откуда делается yield
:
-
Только в главной функции.
Если вызвать внутри корутины функцию, то
yield
внутри её будет ошибкой. (Пример: генераторы в Python.) -
Откуда угодно — то есть у них есть свой стэк вызовов.
Это путь Lua. Такие корутины удобнее и мощнее.
Листинг 4.1.coroutine.yield
из функции внутри корутины.1 2 3 4 5 6 7 8 9 10 11 12 13
local function inner(x) return coroutine.yield(x) end local co = coroutine.wrap(function(x) return 2 * inner(x) end) print(co(3)) --> 3 print(co(21)) --> 42
Итак, корутины в Луа асимметричные, являются объектами первого класса и имеют стэк вызовов. Дальше будем использовать это.
5. Преобразования
Корутины в Lua используются редко, ибо часто можно обойтись без них. Но если знать, как переписать код без корутин, станет понятно, когда делать обратное.
5.1. Преобразование в симметричную корутину
Чтобы реализовать симметричный механизм передачи управления, придумаем функцию transfer
,
которая сочетает в себе yield
работающей корутины и resume
другой.
Первое сделать просто: вызвать coroutine.yield
.
Второе — проблема: если корутина останавливает себя, то кому запускать другую корутину?
Поэтому нужен "оркестратор": он запускает все корутины, и поэтому к нему они возвращаются при yield
.
Так мы минимизируем высоту иерархии.
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
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
local mainThread = coroutine.running()
local function transfer(co, ...)
if coroutine.running() ~= mainThread then
return coroutine.yield(co, ...) (1)
end
local data = table.pack(...)
while true do
data = table.pack(
coroutine.resume(
co,
table.unpack(data,
1,
data.n)
) (2)
)
local success = table.remove(data, 1)
if not success then
error(data[1]) (3)
end
data.n = data.n - 1
if coroutine.status(co) == "dead" then
return table.unpack(data, 1, data.n) (4)
end
co = table.remove(data, 1)
data.n = data.n - 1
if co == mainThread then
return table.unpack(data, 1, data.n) (5)
end
(6)
end
end
1 | Вызвано внутри корутины — делаем yield в главный поток. |
2 | Вызвано в главном потоке. Запускаем корутину, передаём все данные. |
3 | Если корутина завершается с ошибкой, то её выбрасываем. |
4 | Если корутина сделала ретурн, то возвращаем результат. |
5 | Если корутина передала исполнение в главную, также возвращаем результат. |
6 | Корутина передала исполнение в другую корутину — зацикливаемся. |
Эта реализация позволяет корутине завершаться с помощью return
, а не transfer(mainThread)
.
Можно сделать обёртку вокруг coroutine.create
, которая бы добавляла error
в таком случае.
coroutine.create
.1
2
3
4
5
6
local function createCoroutine(f)
return coroutine.create(function()
f()
error("coroutine returned") (1)
end)
end
1 | Если исполнение достигает этой строки, то вызов f() выше завершился.
То есть функция или дошла до конца, или сделала return .
Поэтому кидаем ошибку. |
Воспользуемся симметричными корутинами для построчного копирования файла.
Конкретно потребности в симметричных тут нет (на асимметричных даже удобнее), но сойдёт как первый пример в этом гайде, который делает что-то полезное. |
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 writer, reader
writer = coroutine.create(function(f)
while true do
local line = transfer(reader)
if line then
f:write(line)
else
break
end
end
transfer(mainThread, f)
end)
reader = coroutine.create(function()
for line in io.lines("sym.lua", "L") do
transfer(writer, line)
end
transfer(writer, nil)
end)
local f = transfer(writer, io.open("sym-copy.lua", "w"))
f:close()
5.2. Переписывание без корутин
В большинстве случаев от корутин можно избавиться в принципе.
Если можно переписать содержимое главной функции, то во всех.
Один такой пример я уже показывал — смотрите секцию про итератор.
Идея состоит в том, чтобы вынести весь стейт в нелокальные переменные, а сам код превратить в замыкание.
Например, из цикла for i = …
вынести переменную i
и в функции самому увеличивать счётчик.
Ещё вариант. Если делается coroutine.yield
посреди функции, то её можно разделить на две части:
в первой всё, что до yield
, во второй то, что после.
1
2
3
4
5
6
7
8
9
local f = coroutine.wrap(function(a)
local b = coroutine.yield(a * 2)
return a + b * 2
end)
print(f(3))
--> 6
print(f(6))
--> 15
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
local f do
local beforeYield = true
local a, b
f = function(val)
if beforeYield then
a = val
beforeYield = false
return a * 2
else
b = val
return a + b * 2
end
end
end
print(f(3))
--> 6
print(f(6))
--> 15
Без корутин получилось страшнее, не так ли?
Третий способ избавиться от корутин — поменяться местами между генератором и обработчиком. То есть сделать так, чтобы не обработчик вызвал генератор, а наоборот. Например, передать обработчик как коллбэк.
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
local dfsPreOrder do
local function traverse(node)
coroutine.yield(node) (1)
for _, child in ipairs(node.children) do
traverse(child) (2)
end
end
dfsPreOrder = function(node)
return coroutine.wrap(traverse), node (3)
end
end
local count = 0
for node in dfsPreOrder(node) do
print(node.content)
count = count + 1
if count > 30 then
break (4)
end
end
1 | Возвращаем текущую ноду. |
2 | Затем обрабатываем детей (рекурсивно). |
3 | Возвращаем саму функцию-итератор и первое значение. |
4 | Останавливаем итерацию привычным break . |
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
local function dfsPreOrder(node, f)
if f(node) then
return true
end
for _, child in ipairs(node.children) do
if dfsPreOrder(child, f) then
return true
end
end
end
local count = 0
dfsPreOrder(node, function(node)
print(node.content)
count = count + 1
return count > 30
end)
Без корутин кажется проще. Однако я бы выбрал вариант первый:
-
Сам алгоритм (
traverse
) на самом деле занимает 7 строк против 11 в другом варианте. Остальное — обёртки, которые опциональны. -
Можно использовать в цикле
for
— и останавливать черезbreak
, а не костылями. -
Алгоритм проще расширять. Ниже разберём пайпинг — его можно здесь использовать.
-
Более строгое разделение обязанностей. Итератор итерирует, и ему не важно, что с выхлопными значениями делают.
Есть итератор дерева, который итерируется в for , как и первый вариант, но не содержит корутин.
Но его код сложнее, особенно если дерево не бинарное.
|
6. Применение
Есть несколько юз-кейсов, где корутины очень полезны. Одно из таких типичных применений корутин — обход дерева. О нём я уже рассказал в предыдущей главе. В этой секции — ещё несколько.
6.1. Пайпинг. Итераторы
Если использовали какого-нибудь родственника юникса, вы наверняка знакомы с пайпингом. Одна программа генерирует данные, другая их читает и генерирует свои.
$ find lua | (1) head -n512 | (2) gzip > test.gz (3)
1 | Пролистывает список файлов в директории lua . |
2 | Читает список, отрезает первые 512 строк и отдаёт их. |
3 | Принимает их, сжимает и выплёвывает байты в test.gz . |
Сделаем программу на Lua, которая делает то же, что и команда выше.
Программы запустим в корутинах, а читать и передавать данные заставим через yield
и resume
.
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
27
28
29
30
31
32
33
34
35
36
37
local function executeRead(cmd)
local proc = io.popen(cmd, "r") (1)
return coroutine.wrap(function()
for line in proc:lines("L") do (2)
coroutine.yield(line) (3)
end
proc:close()
end)
end
local function head(n, producer) (4)
return coroutine.wrap(function()
for i = 1, n do
local line = producer() (5)
if not line then
break
end
coroutine.yield(line) (6)
end
end)
end
local function executeWrite(cmd, producer) (7)
local proc = io.popen(cmd, "w")
for data in producer do (8)
assert(proc:write(data))
end
proc:close()
end
executeWrite("gzip > test.gz", head(512, executeRead("find lua"))) (9)
1 | Запускаем команду для чтения. |
2 | Читаем по одной строчке (вместе с \n , чтобы было проще). |
3 | Передаём строку через coroutine.yield . |
4 | Так как head должен откуда-то читать данные, передаём функции корутину. |
5 | Все корутины заключены в coroutine.wrap для простоты, поэтому просто вызываем функцию, чтобы получить строку. |
6 | После того как проверили, что строка есть, передаём её следующему. |
7 | Здесь тоже надо корутину передавать, откуда брать данные. Так как функция не отдаёт данных каких-либо, корутина здесь не нужна. |
8 | Читаем строку, проверяем её наличие и скармливаем процессу. |
9 | Теперь можно всё сложить в однострочник. Красота! |
Конкретно эта программа вам может и не понадобиться. Но пайпинг полезен не только для такого. В коде выше мы реализовали три вида функций:
-
executeRead
— итератор. Это функция, которая каждый раз возвращает очередное значение. Её можно также уместить в циклfor
. -
head
— адаптер. Адаптер принимает один итератор (или несколько) и возвращает другой. Этот отдаёт первыеn
значений. -
executeWrite
— потребитель (обработчик). Потребляет значения из итератора и завершает цепочку.
В следующем примере придумаем ещё несколько похожих функций, которые встречаются в других языках программирования.
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
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89
90
91
92
93
94
95
96
97
98
99
100
101
102
103
104
105
106
107
108
109
110
111
112
113
114
115
116
117
118
119
local function unpack(t)
return table.unpack(t, 1, t.n)
end
local function filter(f, iterator)
return coroutine.wrap(function()
while true do
local values = table.pack(iterator())
if values[1] == nil then
break
end
if f(unpack(values)) then
coroutine.yield(unpack(values))
end
end
end)
end
local function map(f, iterator)
return coroutine.wrap(function()
while true do
local values = table.pack(iterator())
if values[1] == nil then
break
end
coroutine.yield(f(unpack(values)))
end
end)
end
local function takeFirst(n, iterator)
return coroutine.wrap(function()
for i = 1, n do
local values = table.pack(iterator())
if values[1] == nil then
break
end
coroutine.yield(unpack(values))
end
end)
end
local function zip(...)
local iterators = {...}
return coroutine.wrap(function()
while true do
local merged = {n = 0}
for _, iterator in ipairs(iterators) do
local values = table.pack(iterator())
if not values[1] then
goto exhausted
end
table.move(values, 1, values.n, merged.n + 1, merged)
merged.n = merged.n + values.n
end
coroutine.yield(unpack(merged))
end
::exhausted::
end)
end
local function chain(...)
local iterators = {...}
return coroutine.wrap(function()
for _, iterator in ipairs(iterators) do
while true do
local values = table.pack(iterator())
if values[1] == nil then
break
end
coroutine.yield(unpack(values))
end
end
end)
end
local function only(nth, iterator)
return coroutine.wrap(function()
while true do
local value = select(nth, iterator())
if value == nil then
break
end
coroutine.yield(value)
end
end)
end
local function iter(f, state, var)
return coroutine.wrap(function()
while true do
local values = table.pack(f(state, var))
var = values[1]
if var == nil then
break
end
coroutine.yield(unpack(values))
end
end)
end
iter
-
Преобразовывает итераторы, которые требуют стейт и предыдущее значение, в функцию-замыкание. Такую можно использовать с другими функциями из этого кода.
filter
-
Адаптер, который возвращает те значения, для которых
f
вернёт истинное значение. Позволяет удобно отфильтровать значения.1 2 3 4 5 6 7 8 9
local function even(_, v) return v % 2 == 0 end for k, v in filter(even, iter(ipairs({1, 2, 3, 4, 5}))) do print(k, v) end --> 2 2 --> 4 4
map
-
Адаптер, который вызывает
f
и отдаёт возвращённые значения. Так их можно преобразовать на лету.1 2 3 4 5 6 7
for v in map(math.sqrt, only(2, iter(ipairs({1, 9, 25, 81})))) do print(v) end --> 1.0 --> 3.0 --> 5.0 --> 9.0
takeFirst
-
Адаптер, который берёт первые
n
элементов. Подобенhead
в прошлом примере, но спокойно работает с итераторами, возвращающими несколько значений.1 2 3 4 5 6
for k, v in takeFirst(3, iter(ipairs({1, 2, 3, 4, 5}))) do print(k, v) end --> 1 1 --> 2 2 --> 3 3
zip
-
Адаптер, который соединяет несколько итераторов параллельно.
1 2 3 4 5
for k1, v1, k2, v2 in zip(iter(ipairs({1, 2})), iter(ipairs({3, 4, 5}))) do print(k1, v1, k2, v2) end --> 1 1 1 3 --> 2 2 2 4 (1)
1 Третьей итерации нет, ибо zip
итерирует, пока любой из итераторов не закончится. chain
-
Адаптер, который соединяет несколько итераторов последовательно.
1 2 3 4 5 6 7 8
for k, v in chain(iter(ipairs({1, 2})), iter(ipairs({5, 4, 3}))) do print(k, v) end --> 1 1 --> 2 2 --> 1 5 (1) --> 2 4 --> 3 3
1 Первый итератор закончился, теперь берёт значения из второго. only
-
Адаптер, который возвращает только
n
-ое значение итератора.1 2 3 4 5 6
for v in only(2, iter(pairs({42, 21, 7}))) do print(v) end --> 42 --> 21 --> 7
Продолжим тему итераторов. На корутинах легко сделать стримы — бесконечные итераторы. Бесконечные они, конечно, только в теории, используют же ограниченное количество значений.
1
2
3
4
5
6
7
8
9
local function natural(start)
start = start or 1
return coroutine.wrap(function()
for i = start, math.huge, 1 do
coroutine.yield(i)
end
end)
end
Теперь, если поместить natural()
в цикл for
, он будет генерировать эти числа до посинения — пока не дойдёт до break
.
natural
в цикле for
. 1
2
3
4
5
6
7
8
9
10
11
12
13
for i in natural() do
print(i)
if i >= 50 then
break
end
end
--> 1
--> 2
--> 3
--...it goes on and on...
--> 49
--> 50
Сам по себе такой стрим удивительно бесполезен, но с функциями из примера выше он сияет. Вот как прицепить номер итерации:
natural
вместе с адаптерами.1
2
3
4
5
6
7
for i, k, v in zip(natural(), iter(pairs({foo = "bar", bar = "baz", baz = "spam", spam = "eggs"}))) do
print(i, k, v)
end
--> 1 foo bar
--> 2 baz spam
--> 3 spam eggs
--> 4 bar baz
Итератор — жутко универсальная вещь. Позволяет удобно работать со структурами данных, файлами, различными объектами. Если они грамотно сделаны, разработчики рады использовать итераторы в своих программах. Скрасьте жизнь и вы.
6.2. Многопоточность
На корутинах можно запилить многопоточность. Она бывает двух видов:
-
вытесняющей — между потоками переключается планировщик;
-
кооперативной — тогда потоки сами отдают исполнение.
Разумеется, если делать многопоточность на корутинах, то получится кооперативная. Тогда если один поток зависнет, то заглохнут и все остальные. Зачем же они такие нужны тогда?
-
Для разделения программ. Корутина — это подпрограмма, как и функция (а функция — это подмножество корутин). Функции используют, чтобы поделить функциональность на независимые кусочки. То же делается и с корутинами.
-
Для работы с асинхронными данными без километровых цепей коллбэков и промисов.
В асинхронных программах ключевой элемент — event loop. Ивент луп — это цикл в программе, который ждёт событий и вызывает обработчиков. Эта конструкция есть в большинстве UI-библиотек. Ещё используют в серверах, которые занимаются обработкой запросов по сети, ибо сеть асинхронна. И так далее.
Плюс корутины в том, что она умеет останавливаться несколько раз.
- С корутинами
-
Ивент луп получил событие A и вызвал корутину-обработчик. Корутина же отправила HTTP-запрос и уснула. Теперь ивент луп её разбудит, когда получит событие B, что соединение установлено. И корутина продолжит работу с того момента в коде, как уснула, что очень удобно. А пока она спит, могут работать другие корутины.
- Без корутин
-
Ивент луп запускает корутину, а она сделала HTTP-запрос. Теперь все остальные корутины работать не будут, пока запрос не завершится и корутина его не обработает.
Преобразованием можно избавиться от корутин:
нацепить коллбэков или вместо yield
делать return
с именем следующего ивента и функцией-обработчиком его.
Однако это только усложнит код (попробуйте переписать и сравнить).
Поэтому сделаем на корутинах:
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
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
local handlers = {}
local function _add(eventType, handler, default)
handlers[eventType] = handlers[eventType] or {}
handlers[eventType][handler] = default
end
local function _del(eventType, handler)
handlers[eventType][handler] = nil
end
local function addHandler(eventType, f)
local handler = coroutine.create(f)
_add(eventType, handler, eventType)
end
addHandler("relay", function(event)
while true do
local responseUrl = event.responseUrl
sendRequest(event.url) (1)
sendRequest(responseUrl, coroutine.yield("http-connected").body) (2)
event = coroutine.yield() (3)
end
end)
while true do
local event = waitForEvent()
if handlers[event.type] then
for handler, defaultEvent in pairs(handlers[event.type]) do
local nextEvent = select(2, assert(coroutine.resume(handler, event))) (4)
if coroutine.status(handler) == "dead" then (5)
_del(event.type, handler)
elseif not nextEvent and defaultEvent ~= event.type then (6)
_del(event.type, handler)
_add(defaultEvent, handler, defaultEvent)
elseif nextEvent and nextEvent ~= event.type then (7)
_del(event.type, handler)
_add(nextEvent, handler, defaultEvent)
end
end
end
end
1 | Отправляем запрос. |
2 | Ждём ответа, затем снова отправляем запрос. |
3 | Так как ответ от второго запроса неинтересен, принимаем следующий ивент. |
4 | assert выбросит ошибку, если она была в корутине, а select уберёт ненужный булеан. |
5 | Если корутина сдохла, удаляем её из обработчиков. |
6 | Если корутина вернула пустоту, переставляем её обработчиком оригинального ивента (удобство!). |
7 | Иначе переставляем её на другой ивент. |
Мы предполагаем, что sendRequest
не блокирует программу, а waitForEvent
проверяет статус соединения.
Такое справедливо в большинстве случаев.
Если это не так, обычно есть опция специальная.
Но если и опции нет, то смысла в таком дизайне немного.
"Тяжёлые" функции должны быть асинхронными, чтобы схема выше работала.
6.3. Конечные автоматы
Объяснить, что такое конечный автомат, можно тремя способами:
-
формально;
-
корректно;
-
и по-простому.
Первые два объяснения можно найти, например, на Википедии. Здесь попробуем простой вариант.
Есть дверь.
-
У неё 2 состояния: открыта, закрыта.
-
С ней можно проделать 3 действия: пройти, открыть, закрыть.
-
Когда она закрыта, нельзя пройти и нельзя закрыть её. Зато её можно открыть — тогда дверь становится открытой.
-
Когда она открыта, нельзя открыть её. Но можно пройти. Ещё её можно закрыть — дверь становится закрытой.
Во-первых, оказывается, что дверь — это сложный механизм. Во-вторых, это конечный автомат. Не знаю, какой из этих фактов удивительнее, но докажу второй.
Конечный автомат — это штука, у которой есть определённое число состояний, и она пребывает в одном из них. На вход автомату подаются какие-то действия. И в зависимости от действия и текущего состояния автомат переходит в новое состояние.
В примере с дверью я говорил, что какие-то действия сделать нельзя. Например, нельзя закрыть закрытую дверь. Иначе можно сказать, что действие закрыть, когда дверь закрыта, меняет состояние на закрытое. Звучит бредово, зато понятно, почему дверь — конечный автомат.
Конечным же он называется только потому, что конечно число состояний. В английском языке прямо так называют — finite-state machine.
Вернёмся, впрочем, к программированию. Конечный автомат (и его более фичастые родственники) используется для моделирования:
-
сетевых протоколов;
-
компиляторов, в частности лексеров;
-
графических интерфейсов;
-
и т. д.
Эти вещи очень удобно реализовывать с помощью корутин. Текущее состояние хранится как явно (переменные), так и неявно (стэк вызовов и исполняемая операция).
Рассмотрим сетевой протокол FTP. Типичный сценарий:
-
Подключиться к серверу. Подождать ответа.
-
Послать юзернейм. Подождать ответа.
-
Отослать пароль. Получить подтверждение входа.
-
Попросить его открыть порт для передачи данных. Получить подтверждение.
-
Подключиться на этот порт.
-
Отправить запрос на получение файла. Получить подтверждение.
-
Считать файл.
-
Завершить подключение.
Состояние описывается текущим этапом подключения. То есть позицией в коде. Поэтому легко реализовать клиент на корутинах.
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
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
local function send(data)
return coroutine.yield("send", data)
end
local function pasv()
local response = send("PASV\r\n")
expectResponse(227, response)
-- ...
return dataAddr
end
local function newConnection(address, co)
local socket = establishConnection(address)
socket:setBlocking(true)
return function()
while socket:isConnected() do
local response = socket:readLine()
local tag, data = select(2, assert(coroutine.resume(co, response)))
if tag == "send" then
socket:send(data)
end
if coroutine.status(co) == "dead" then
socket:close()
end
end
end
end
local function getFile(addr, user, pass, filename)
return newConnection(addr, coroutine.create(function(response)
expectResponse(220, response) (1)
expectResponse(331, send("USER " .. user .. "\r\n")) (2)
expectResponse(230, send("PASS " .. pass .. "\r\n")) (3)
local dataAddr = pasv() (4)
local f = assert(io.open("./" .. filename, "w"))
local dataSocket = newConnection(dataAddr, coroutine.create(function(chunk) (5)
while chunk do
f:write(chunk)
chunk = coroutine.yield()
end
f:close()
end))
expectResponse(150, send("RETR " .. filename .. "\r\n")) (6)
dataSocket() (7)
send("QUIT\r\n") (8)
end))()
end
Чтобы показать, как близко транслируется протокол в код, я расставил номера шагов.
Если доделать pasv
, establishConnection
, expectResponse
, то FTP-клиент будет готов.
И код будет выглядеть очень красиво.
Допилить код до нужного состояния проблемы тоже не составит.
6.4. Ещё применения
-
Лексер (разбивает код на токены, чтобы парсить).
-
Регулярные выражения.
-
Сложные системы логирования.
-
Модель акторов.
-
Дебаггер (запустить программу для дебага в корутине и общаться с помощью
yield
). -
Обработка ошибок (благодаря тому, что значения переменных остаются даже после
error
). -
Рисование анимаций.
7. Заключение
Тур по корутинам завершён. Опираясь на этот материал, я надеюсь, вы сможете побороть страх перед ними. Вопросы можно задать мне в IRC: #cc.ru @ irc.esper.net.
Ниже — дополнительный материал. Рекомендую полистать, если хочется что-то прояснить.
Библиография
-
Ana L ́ucia de Moura and Roberto Ierusalimschy. 2004. Revisiting Coroutines. ACM Transactions on Programming Languages and Systems.
-
Roberto Ierusalimschy. 2004. Coroutines. Programming in Lua (1st ed.). Lua.org.
-
Roberto Ierusalimschy. Coroutines. Programming in Lua (4th ed.), стр. 194–204.
-
Coroutine Manipulation. Lua 5.3 Reference Manual. Lua.org.
-
Coroutines. Lua Programming/Standard Libraries. Wikibooks.org.
-
Coroutine. Wikipedia.org.
Приложение A: Примеры
Приложение B: Корутины в дикой природе
По ссылкам — код, который использует корутины. Для каждого примера есть причина, почему там корутины к месту. Если нечем заняться, предлагаю её найти и понять, как работает код.
Корутины используются довольно редко, что печалит. Но список выше должен состоять явно не из 3 пунктов. Если знаете программу на Lua, которая использует корутины для забавных вещей (например, из этого списка), расскажите мне о ней в IRC. |
Приложение C: Видяхи с интерпретацией
Сгенерировал своей программой. Ссылка на неё: crateriform.
Там же — код примеров, который использовался для рендера видео.
Приложение D: Сырцы и лицензия
Исходный код документа и сопровождающий контент доступен в репозитории.
Контент доступен по лицензии Creative Commons Attribution 4.0 International. См. LICENSE в репозитории.