Разбираемся с coroutine в Kotlin — 2
Введение
Первое упоминание корутин дано в статье 1963 года (1) и о ней первая часть. После прочтения статьи, сказать честно, я не очень понял идею корутин и искал дополнительную информацию. Понадобилось четыре статьи: статья Конвея, глава из книги Дональда Кнута (2) и две статьи Саймона Тэтхема (3, 4) и некоторое время, чтобы глубже понять идею. После прочтения статьи Конвея и до прочтения Кнута казалось, что разница между вариантом программа-подпрограмма и две корутины почти косметическая. Казалось, что программы отличаются реализацией. Однако разница более существенная, нужно отказаться от идеи писать программы, в которых есть подпрограммы, а представлять программу как набор независимых модулей, которые могут обмениваться данными. Кнут предлагает вообще не думать о программе в контексте вызывающий (caler) и вызываемый (callee), а думать о подпрограммах как об отдельных независимых сопрограммах, которые передают друг другу данные при этом умеют сохранять свое состояние перед выходом из сопрограммы и восстанавливать состояние после вызова.
Итак, Конвей работал над компилятором ALGOL и ему приходилось считывать данные с перфокарт и записывать их на магнитную ленту. Насколько я понял, если вначале считать все данные с перфокарты и потом записать считанные данные на ленту, то это отнимет меньше времени, чем если считать часть данных с карты, а потом часть данных записать на ленту. То есть в первом случае делаем один проход считывания и один проход записи, а во втором гораздо больше. Считывание и запись данных за один проход оказывается выгоднее по времени, чем переключение между считал/записал. Собственно программа, точнее программы, которые он реализовал названы корутинами и по своей сути являются двумя независимыми программами, которые передавали управление друг другу.
После прочтения главы из книги Кнута понимаешь, что разница между программа-подпрограмма и сопрограммы не косметическая, а скорее структурная. После некоторых поисков я нашел статьи Саймона Тэтхэма. Собственно статья Конвея, глава из Кнута и статьи Саймона Тэтхема в конечном итоге и стали основной для написания этой статьи. Статья будет введением в корутины, в основном опирающаяся на практику и реализацию корутин на языке Си из статьи Тэтхэма.
Рассмотрим функцию в самой обычной программе. Какие действия можно выполнить над функцией? Можно вызвать функцию, из нее можно вернуться. Вызов функции это приостановка одной функции, создание стекового фрейма и активация другой. Возврат из функции это уничтожение стекового фрейма и возвращение управления/результата обратно. То есть функцию можно приостановить, активировать, завершить и вернуть результат. Вызывая функцию ничего неизвестно о состоянии до вызова: нужно инициализировать переменные, выполнить код, вернуть результат. Но, что если придумать некий механизм, который позволяет помнить, что было на предыдущем вызове и начинать не с чистого листа, а из предыдущего состояния. О реализации этой идеи пойдет речь дальше и статья Саймона Тэтхема нам в этом поможет.
Идея и реализация
Сразу перейдем к идее сохранить состояние функции и восстановить его при очередном вызове. Нам нужна такая фишка, чтобы каждый раз когда мы вызываем функцию начинать не с чистого листа, а из состояния, которое было на момент предыдущего вызова.
int function(void) {
int i;
for (i = 0; i < 10; i++)
return i; /* работать не будет, но это примерно то, чего я хочу */
}
function() // 0
function() // 1
…
function() // 9
Как вообще такое можно провернуть? Вот один из примеров.
int function(void) {
static int i, state = 0;
switch (state) {
case 0: goto LABEL0;
case 1: goto LABEL1;
}
LABEL0: /* start of function */
for (i = 0; i < 10; i++) {
state = 1;
return i;
LABEL1:;
}
}
Этот с виду странный код с оператором goto позволяет осуществить задуманное. Переменные state и i объявлены как static поэтому сохранят свое значение между вызовами. Первый вызов это инкремент i, state = 1 и return i. Все последующие вызовы goto LABEL1, снова инкремент i, далее state = 1 и return i. Неудобство здесь в том, что для каждого state надо создавать отдельный LABEL. Можно переписать код на что-то подобное
int function(void) {
static int i, state = 0;
switch (state) {
case 0: /* стартуем */
for (i = 0; i < 10; i++) {
state = 1; /* при следующем вызове стартуем уже с case1 */
return i;
case 1:; /* возвращаем управление сразу после возврата */
}
}
}
Этот код эквивалентен предыдущему, только без goto и LABEL и теперь мы можем написать макрос, который спрячет реализацию и дальше использовать его в коде.
#define crBegin static int state=0; switch(state) { case 0:
#define crReturn(i,x) do { state=i; return x; case i:; } while (0)
#define crFinish }
int function(void) {
static int i;
crBegin;
for (i = 0; i < 10; i++)
crReturn(1, i);
crFinish;
}
В макросе тот же самый недочет, что и в варианте с LABEL, так как нужно добавлять новый label на каждый case. Но это можно исправить с помощью специального макроса LINE. Таким образом мы решили и эту проблему.
#define crReturn(x) do { state=__LINE__; return x; \
case __LINE__:; } while (0)
Не вдаваясь в технические детали и отдавая себе отчет в том, что этой реализации недостаточно для полноценной работы корутин мы уже можем написать программу, состоящую из нескольких сопрограмм. Более того можно взять программу и с небольшими изменениями заменить все подпрограммы на сопрограммы. Для этого код каждой подпрограммы нужно обернуть в crBegin, crFinish и return заменить на crReturn.
function () {
crBegin()
while(1) {
// some code
if (condition) {
crReturn(x)
}
}
crFinish()
}
Каждая из этих сопрограмм будет работать независимо и в каждый момент времени находится в определенном состоянии. Особенно хочу отметить, что подпрограмму можно обернуть в некоторую обертку и превратить ее в корутину — программу, которая умеет «засыпать» и «просыпаться». У корутины нет классического return, она всегда возвращает управление, сохраняя состояние. После прочтения статьи Саймона Тэтхема стало понятнее как устроены корутины под капотом, но не совсем понятно как это использовать и главное в чем преимущества перед другими способами. С этими и другими вопросами я буду разбираться в следующей статье.
Список литературы:
1.Design of a Separable Transition-diagram Compiler
2. Дональд Кнут — Искусство программирования — Том 1 — Сопрограммы — стр. 229.
3.С. Тэтхем — Статья — философия корутин
4.С. Тэтхем — Статья — корутины на языке Си
5.Дмитрий Калугин-Балашов — Видео — Как устроены корутины?
6.Александр Нозик — Видео Мастер-класс — Кое-что о корутинах
7.Константин Владимиров — Лекция 10 — Корутины
8.Gor Nishanov — Видео — Await 2.0: Stackless Resumable Functions
