Разбираемся с 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