Разбираемся с Coroutine в Kotlin - часть вторая

Введение

Первое упоминание корутин дано в статье 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