Возвращаясь к стилю передачи продолжений. Часть 3: размышления о сопрограммах
В прошлый раз я кратко описал, как можно реализовать интересную логику управления, такую как try-catch с помощью продолжений; как мы видели, реализация методов Try и Throw весьма примитивна при наличии CPS. Я уверен, что вы можете расширить эти идеи для реализации try-catch-finally. Другим базовым упражнением при изучении CPS является реализация сопрограмм (coroutines).
Что такое сопрограмма? Отличный вопрос!
Давайте вспомним старые деньки кооперативной многозадачности (cooperative multitasking) в Windows 3. Идея кооперативной многозадачности заключается в том, что операционная система позволяет выполняться процессу и процесс сам решает, когда приостановить свое выполнение и позволить выполняться другому процессу. Если процесс попадает в бесконечный цикл, то остальные процессы будут «голодать» и никогда не получат процессорного времени. Программы требовали тщательного конструировавния, чтобы они не расходовали слишком много процессорного времени до передачи управления обратно операционной системе, которая затем передаст управление очередному процессу.
Конечно, сегодня операционная система предоставляет некооперативную многозадачность, как на уровне процессов, так и на уровне потоков. Не процесс, а операционная система принимает решение о том, когда некоторый поток в некотором процессе приостановит свое исполнение. Это означает, что программы не нужно писать особым образом; они могут быть написаны без оглядки на то, что другим процессам может не достаться процессорного времени. Однако это означает, что операционная система должна уметь быстро получить состояние, важное для текущего потока, сохранить его и восстановить, чтобы поток продолжил выполнение с того же места, даже не зная о том, что он был прерван. (Фактически, операционная система сохраняет продолжение потока!)
Сопрограммы – это концепция языка программирования очень схожая с понятием кооперативной многозадачности уровня операционной системы. Сопрограмма – это метод, который выполняется некоторое время, затем решает приостановить свое выполнение, позволяя выполняться другой сопрограмме. Когда другая сопрограмма решает поступить аналогичным образом, первая сопрограмма продолжает выполнения с того места, где она была приостановлена. Можно представить себе множество систем, где могла бы применяться эта техника:
Stack<Pancakes> pancakes = new Stack<Pancakes>();
coroutine MakePancakes(Chef chef)
{
while(true)
{
while (chef.IsAwake)
pancakes.Push(chef.MakePancake());
yield;
}
}
coroutine EatPancakes(Child child)
{
while(true)
{
while (child.IsHungry && pancakes.Count != 0)
child.Eat(pancakes.Pop());
yield;
}
}
Это значительно лучше, нежели взаимная рекурсия. Вы явно не будете вызывать методы “MakePancakes()” и “EatPancakes()” по следующим причинам: (1) это приведет к бесконечной рекурсии и (2) может быть несколько шеф-поваров и несколько детей, которые могут быть доступны в разном порядке. Вы скорее скажете: «Я пока что завершил работу над этой задачей. Кто-то другой может продолжить, но я продолжу с того же самого места, когда придет моя очередь». Поскольку это кооперативная однопоточная многозадачность, две сопрограммы не могут выполняться в один момент времени и не могут быть приостановлены в середине своего выполнения. Здесь нет проблем «безопасности потоков» при использовании глобального стека блинов (pancake) двумя сопрограммами.
Однако сложность заключается в том, как добиться выполнения правила: «я продолжу с того же самого места, когда придет моя очередь». В Windows вы можете использовать волокна (fibers) для реализации сопрограмм, поскольку именно волокна и являются «легковестным» потоком, который самостоятельно решает, когда передать управление другому волокну, а не предоставляет решать это операционной системе. Но давайте пока забудем об этом. Предположим у нас нет волокон (*), но есть сопрограммы.
С теми знаниями, которые у вас есть о продолжениях, должно быть ясно, что сопрограммы могут быть очень просто реализованы на любых языках программирования, поддерживающих CPS. Все становится еще проще, если вы можете воспользоваться кодом, вызывающим следующее продолжение, но это не обязательно. Когда приходит время вернуть управление, достаточно просто сказать этому коду: «Я сопрограмма, которая возвращает управление. Вот мое текущее продолжение. Пожалуйста, положите его в конец очереди. И вызовите продолжение той сопрограммы, которое находится в начале очереди». Если все нормально сотрудничают, тогда каждая сопрограмма потихоньку выполняет свою работу и передает управление своему соседу. (И конечно, при завершении выполнения сопрограммы, если такое когда-нибудь происходит, сопрограмма просто не помещает продолжение в очередь и исчезает.) Поскольку «все что мне нужно сделать потом» – это именно то, чем является продолжение, то мы уже решили проблему восстановления управления с того места, где оно было приостановлено.
Как вы уже сейчас поняли, если не знали об этом раньше, то оператор “ yieldreturn ” в языке C# не что иное, как одна из разновидностей сопрограмм. При выполнении “yield return”, концептуально перечислитель (enumerator) сохраняет продолжение, т.е. достаточное количество информации, чтобы продолжить выполнение. Затем он возвращает управление вызывающему коду, который сам решает, когда опять вызвать метод MoveNext и восстановить выполнение с того места блока итератора, где она была прервана. Блок итератора и вызывающий код должны сотрудничать; блок итератора обязуется возвращать следующий элемент в определенное время, а вызывающий код обязуется вызывать либо метод MoveNext(), либо Dispose(), что позволит итератору либо выполнить очередной кусок работы, либо очистить за собой ресурсы.
Конечно, как я уже писал в прошлом году, блок итератора реализован не в «чистом» стиле передачи продолжений. Мы не преобразовываем метод целиком и каждый последующий вызов в CPS и не создаем лямбда-выражение «для всего, что еще осталось выполнить». Поскольку мы ограничили себя реализацией потока данных, похожего на сопрограммы, исключительно для реализации IEnumerator, мы не заявляли, что это CPS в чистом виде. Мы создали значительно более простую систему, конечный автомат, отслеживающий текущее положение, плюс замыкание, отслеживающее состояние всех локальных переменных. Но теоретически, мы могли реализовать блоки итераторов с помощью сопрограмм, которые, в свою очередь, реализовать на основе продолжений. Оператор “yield return” приводит к достаточно сложной логике управления, однако с помощью продолжений мы можем создавать логику любой сложности.
Сейчас, возможно, самое время прочитать статьи Реймонда о том, как итераторы на самом деле реализованы в языке C# и, возможно, оставшуюся часть моих статей о последствиях тех решений. Знакомство с этой темой вам вскоре очень пригодится. (Помните, что неопределенность является показателем качества блога.)
В следующий раз: если CPS такая классная штука, то почему мы не используем ее каждый день?
(*) Или мы не хотим платить за это миллионом байтов стека, резервируемых для каждого волокна. Волокна не настолько легковесны, как это может показаться.