Корутины (сопрограммы) — функции, которые могут приостанавливать исполнение и возобновлять впоследствии. Lua поддерживает их из коробки. В гайде — история об этих зверях с подробностями.

Введение

Концепт корутин не новый: появился он в шестидесятых годах прошлого века. Корутины использовали в те времена для реализации многопоточности, так как полноценные потоки требовали много ресурсов. В конце девяностых — начале нулевых дороговизна перестала сильно мешаться, и о корутинах подзабыли.

Но люди одумались, когда стали писать много сетевого (по сути, вебовского) софта. Серверы, обрабатывающие по десятку тысяч запросов в секунду, теперь не редкость. Потому серверы делают быстрыми. Чтобы убрать оверхед от полноценных потоков, снова потребовались корутины. Новые версии языков: JavaScript, Rust, Kotlin, Python, Go, C++ и т. д. — пытаются выделиться их поддержкой.

В Lua корутины появились в версии 5.0 — она выпущена в 2003 году, до этого хайпа. Если понять, как они работают в этом языке, проще изучать аналогичные реализации в других. Поэтому приступим.

1. Итератор Фибоначчи

Начнём с наивного примера: обнаружив итеративный цикл for, вам почему-то захотелось создать итератор последовательности Фибоначчи.

Листинг 1.1. Итератор Фибоначчи. Самый простой вариант решения.
 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. Итератор Фибоначчи. Решение без лишнего мусора.
 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.3. Фибоначчи на корутинах.
 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. Принцип работы корутин

Корутина — надстройка над функцией, в которой можно вернуть значения несколько раз. Вот как они работают:

  1. Создаём корутину.

  2. Запускаем корутину, передаём аргументы.

  3. Корутина запускается, обрабатывает аргументы, возвращает какие-то значения.

  4. Значения снаружи получаем и снова запускаем корутину, передавая уже другие значения.

  5. Корутина принимает их и продолжает работу с момента остановки.

Затем она так же может приостановить исполнение. Продолжается так, пока корутина не завершится насовсем. Или можно её не вызвать в очередной раз.

Перенесём всё это в код.

  1. Создаёт корутину coroutine.create — ей нужна функция, которая станет кодом корутины.

    1
    2
    3
    4
    local co = coroutine.create(function(a, b)
      print(a, b)
      ...
    end)
    
  2. Запускаем через coroutine.resume, передавая корутину и аргументы.

    1
    2
    3
    4
    5
    6
    local co = coroutine.create(function(a, b)
      print(a, b)
      ...
    end)
    
    coroutine.resume(co, 42, 24)
    
  3. Пока корутина работает, как обычная функция. Получает 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)
    
  4. Теперь мы снаружи. 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)
    
  5. Корутина приняла sumc) и 12d) и желает завершиться насовсем. Делает она это 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)
    
  6. 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 ?
yield across c
Рисунок 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.

    • Проще в понимании.

    • Применяют в языках, где в основном корутины — итераторы.

    asymmetric hierarchy
    Рисунок 2. Иерархия асимметричных корутин.
  • Симметричный: иерархии корутин нет.

    • Корутины могут выбрать, куда передать значение.

    • Сделать просто yield, не указывая корутины, они не могут.

    • resume и yield — одна операция: корутина приостанавливает себя и запускает другую.

    • Управлять ими гораздо сложнее.

    • Обычно присутствуют в языках, которые реализуют через них многопоточность.

    symmetric hierarchy
    Рисунок 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
    
    • 4 FPS

Итак, корутины в Луа асимметричные, являются объектами первого класса и имеют стэк вызовов. Дальше будем использовать это.

5. Преобразования

Корутины в Lua используются редко, ибо часто можно обойтись без них. Но если знать, как переписать код без корутин, станет понятно, когда делать обратное.

5.1. Преобразование в симметричную корутину

Чтобы реализовать симметричный механизм передачи управления, придумаем функцию transfer, которая сочетает в себе yield работающей корутины и resume другой.

Первое сделать просто: вызвать coroutine.yield. Второе — проблема: если корутина останавливает себя, то кому запускать другую корутину? Поэтому нужен "оркестратор": он запускает все корутины, и поэтому к нему они возвращаются при yield. Так мы минимизируем высоту иерархии.

sym impl hierarchy
Рисунок 4. Иерархия корутин в нашей реализации.
Листинг 5.1.1. Симметричные корутины в Lua.
 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 в таком случае.

Листинг 5.1.2. Симметричные корутины. Обёртка вокруг 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. Поэтому кидаем ошибку.

Воспользуемся симметричными корутинами для построчного копирования файла.

Конкретно потребности в симметричных тут нет (на асимметричных даже удобнее), но сойдёт как первый пример в этом гайде, который делает что-то полезное.
Листинг 5.1.3. Копирование файлов на симметричных корутинах.
 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()
  • 4 FPS

5.2. Переписывание без корутин

В большинстве случаев от корутин можно избавиться в принципе. Если можно переписать содержимое главной функции, то во всех. Один такой пример я уже показывал — смотрите секцию про итератор. Идея состоит в том, чтобы вынести весь стейт в нелокальные переменные, а сам код превратить в замыкание. Например, из цикла for i = …​ вынести переменную i и в функции самому увеличивать счётчик.

Ещё вариант. Если делается coroutine.yield посреди функции, то её можно разделить на две части: в первой всё, что до yield, во второй то, что после.

Листинг 5.2.1. Переписывание без корутин: деление функции. С корутинами.
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
  • 4 FPS
Листинг 5.2.2. Переписывание без корутин: деление функции. Без корутин.
 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
  • 4 FPS

Без корутин получилось страшнее, не так ли?

Третий способ избавиться от корутин — поменяться местами между генератором и обработчиком. То есть сделать так, чтобы не обработчик вызвал генератор, а наоборот. Например, передать обработчик как коллбэк.

Листинг 5.2.3. Обход дерева с корутинами.
 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.
  • 4 FPS
Листинг 5.2.4. Обход дерева с обработчиком.
 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)
  • 4 FPS

Без корутин кажется проще. Однако я бы выбрал вариант первый:

  • Сам алгоритм (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.

Листинг 6.1.1. Пример пайпинга на корутинах.
 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 Теперь можно всё сложить в однострочник. Красота!
  • 4 FPS
piping hierarchy
Рисунок 5. Иерархия корутин в примере с пайпингом.

Конкретно эта программа вам может и не понадобиться. Но пайпинг полезен не только для такого. В коде выше мы реализовали три вида функций:

  • executeRead — итератор. Это функция, которая каждый раз возвращает очередное значение. Её можно также уместить в цикл for.

  • head — адаптер. Адаптер принимает один итератор (или несколько) и возвращает другой. Этот отдаёт первые n значений.

  • executeWrite — потребитель (обработчик). Потребляет значения из итератора и завершает цепочку.

В следующем примере придумаем ещё несколько похожих функций, которые встречаются в других языках программирования.

Листинг 6.1.2. Некоторые функции для работы с итераторами.
  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

Продолжим тему итераторов. На корутинах легко сделать стримы — бесконечные итераторы. Бесконечные они, конечно, только в теории, используют же ограниченное количество значений.

Листинг 6.1.3. Стрим натуральных чисел.
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.

Листинг 6.1.4. Пример запуска 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

Сам по себе такой стрим удивительно бесполезен, но с функциями из примера выше он сияет. Вот как прицепить номер итерации:

Листинг 6.1.5. Использование 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
  • 4 FPS

Итератор — жутко универсальная вещь. Позволяет удобно работать со структурами данных, файлами, различными объектами. Если они грамотно сделаны, разработчики рады использовать итераторы в своих программах. Скрасьте жизнь и вы.

6.2. Многопоточность

На корутинах можно запилить многопоточность. Она бывает двух видов:

  • вытесняющей — между потоками переключается планировщик;

  • кооперативной — тогда потоки сами отдают исполнение.

Разумеется, если делать многопоточность на корутинах, то получится кооперативная. Тогда если один поток зависнет, то заглохнут и все остальные. Зачем же они такие нужны тогда?

  • Для разделения программ. Корутина — это подпрограмма, как и функция (а функция — это подмножество корутин). Функции используют, чтобы поделить функциональность на независимые кусочки. То же делается и с корутинами.

  • Для работы с асинхронными данными без километровых цепей коллбэков и промисов.

В асинхронных программах ключевой элемент — event loop. Ивент луп — это цикл в программе, который ждёт событий и вызывает обработчиков. Эта конструкция есть в большинстве UI-библиотек. Ещё используют в серверах, которые занимаются обработкой запросов по сети, ибо сеть асинхронна. И так далее.

Плюс корутины в том, что она умеет останавливаться несколько раз.

С корутинами

Ивент луп получил событие A и вызвал корутину-обработчик. Корутина же отправила HTTP-запрос и уснула. Теперь ивент луп её разбудит, когда получит событие B, что соединение установлено. И корутина продолжит работу с того момента в коде, как уснула, что очень удобно. А пока она спит, могут работать другие корутины.

Без корутин

Ивент луп запускает корутину, а она сделала HTTP-запрос. Теперь все остальные корутины работать не будут, пока запрос не завершится и корутина его не обработает.

Преобразованием можно избавиться от корутин: нацепить коллбэков или вместо yield делать return с именем следующего ивента и функцией-обработчиком его. Однако это только усложнит код (попробуйте переписать и сравнить).

Ещё корутины легковесны. В Lua они кушают памяти, как 2–3 функции. А переключение между ними не влияет существенно на производительность. Отказываться от них ради оптимизации смысла не имеет.

Поэтому сделаем на корутинах:

Листинг 6.2.1. Event loop на корутинах.
 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 Иначе переставляем её на другой ивент.
  • 4 FPS

Мы предполагаем, что sendRequest не блокирует программу, а waitForEvent проверяет статус соединения. Такое справедливо в большинстве случаев. Если это не так, обычно есть опция специальная. Но если и опции нет, то смысла в таком дизайне немного. "Тяжёлые" функции должны быть асинхронными, чтобы схема выше работала.

6.3. Конечные автоматы

Объяснить, что такое конечный автомат, можно тремя способами:

  1. формально;

  2. корректно;

  3. и по-простому.

Первые два объяснения можно найти, например, на Википедии. Здесь попробуем простой вариант.

Есть дверь.

  • У неё 2 состояния: открыта, закрыта.

  • С ней можно проделать 3 действия: пройти, открыть, закрыть.

  • Когда она закрыта, нельзя пройти и нельзя закрыть её. Зато её можно открыть — тогда дверь становится открытой.

  • Когда она открыта, нельзя открыть её. Но можно пройти. Ещё её можно закрыть — дверь становится закрытой.

Во-первых, оказывается, что дверь — это сложный механизм. Во-вторых, это конечный автомат. Не знаю, какой из этих фактов удивительнее, но докажу второй.

Конечный автомат — это штука, у которой есть определённое число состояний, и она пребывает в одном из них. На вход автомату подаются какие-то действия. И в зависимости от действия и текущего состояния автомат переходит в новое состояние.

В примере с дверью я говорил, что какие-то действия сделать нельзя. Например, нельзя закрыть закрытую дверь. Иначе можно сказать, что действие закрыть, когда дверь закрыта, меняет состояние на закрытое. Звучит бредово, зато понятно, почему дверь — конечный автомат.

Конечным же он называется только потому, что конечно число состояний. В английском языке прямо так называют — finite-state machine.

Понятие это применяют не только к двери, разумеется.

  • Автомат с напитками — конечный автомат.

    Число его состояний определяется числом видов напитков и максимальной вместимостью автомата. Помножим одно число на другое, а потом ещё на два: когда монетка вставлена и когда не вставлена. Получим, что число состояний определено и конечно; автомат пребывает только в одном из них.

    Возможные действия: вставить монетку и нажать на одну из кнопок выбора напитка.

  • Автомат оружейный — конечный автомат.

    Число его состояний определяется вместимостью магазина — по одному состоянию на каждое число патронов.

    Возможные действия: стрелять и перезарядить.

  • И ещё огромная куча других вещей.

Вернёмся, впрочем, к программированию. Конечный автомат (и его более фичастые родственники) используется для моделирования:

  • сетевых протоколов;

  • компиляторов, в частности лексеров;

  • графических интерфейсов;

  • и т. д.

Эти вещи очень удобно реализовывать с помощью корутин. Текущее состояние хранится как явно (переменные), так и неявно (стэк вызовов и исполняемая операция).

Рассмотрим сетевой протокол FTP. Типичный сценарий:

  1. Подключиться к серверу. Подождать ответа.

  2. Послать юзернейм. Подождать ответа.

  3. Отослать пароль. Получить подтверждение входа.

  4. Попросить его открыть порт для передачи данных. Получить подтверждение.

  5. Подключиться на этот порт.

  6. Отправить запрос на получение файла. Получить подтверждение.

  7. Считать файл.

  8. Завершить подключение.

Состояние описывается текущим этапом подключения. То есть позицией в коде. Поэтому легко реализовать клиент на корутинах.

Листинг 6.3.1. Очень абстрактная версия 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
  • 4 FPS

Чтобы показать, как близко транслируется протокол в код, я расставил номера шагов.

Если доделать 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.

Приложение B: Корутины в дикой природе

По ссылкам — код, который использует корутины. Для каждого примера есть причина, почему там корутины к месту. Если нечем заняться, предлагаю её найти и понять, как работает код.

Корутины используются довольно редко, что печалит. Но список выше должен состоять явно не из 3 пунктов. Если знаете программу на Lua, которая использует корутины для забавных вещей (например, из этого списка), расскажите мне о ней в IRC.

Приложение C: Видяхи с интерпретацией

Сгенерировал своей программой. Ссылка на неё: crateriform.

Там же — код примеров, который использовался для рендера видео.

Приложение D: Сырцы и лицензия

Исходный код документа и сопровождающий контент доступен в репозитории.

Контент доступен по лицензии Creative Commons Attribution 4.0 International. См. LICENSE в репозитории.