Корутины: компоненты и особенности реализации

Введение

Компьютерные компоненты программного обеспечения

Корутины — это компоненты компьютерных программ, которые позволяют приостанавливать и возобновлять выполнение, обобщая подпрограммы для кооперативной многозадачности. Корутины хорошо подходят для реализации знакомых компонентов программы, таких как кооперативные задачи, исключения, циклы событий, итераторы, бесконечные списки и каналы. Их описывают как «функции, выполнение которых можно приостановить». Мелвин Конвей ввел термин «корутина» в 1958 году, применив его к построению ассемблерной программы. В данной статье обобщены две общепризнанные фундаментальные характеристики корутины:

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

механизм передачи управления. Асимметричные корутины обычно предоставляют ключевые слова, такие как `yield` и `resume`. Программисты не могут свободно выбирать, какой фрейм использовать для приостановки. Среда выполнения передает управление только ближайшему вызывающему элементу текущей корутины. С другой стороны, в симметричных корутинах программисты должны указывать пункт назначения для `yield`. Предоставляются ли корутины в языке как объекты первого класса, которыми программист может свободно манипулировать, или как ограниченные конструкции;
может ли корутина приостановить свое выполнение из вложенных вызовов функций. Такая корутина называется стековой корутиной. Противоположностью ей являются бесстековые корутины, где обычная функция не может использовать ключевое слово `yield`, если явно не объявлена как корутина. В статье Revisiting Coroutines, опубликованной в 2009 году, был предложен термин «полная корутина» для обозначения корутины, поддерживающей корутины первого класса и являющейся стековой. Полные корутины заслуживают собственного названия, поскольку обладают той же выразительной силой, что и одношаговые и ограниченные продолжения. Полные корутины могут быть как симметричными, так и асимметричными. Важно отметить, что симметричность или асимметричность корутины не влияет на ее выразительность, поскольку они одинаково выразительны, хотя полные корутины более выразительны, чем неполные. Несмотря на одинаковую выразительную силу, асимметричные корутины больше похожи на структуры управления, основанные на подпрограммах, в том смысле, что управление всегда возвращается вызывающему элементу, что может быть более привычным для программистов.

Реализация

По состоянию на 2003 год многие из наиболее популярных языков программирования, включая C и его производные, не имеют встроенной поддержки коррутин в самом языке или в их стандартных библиотеках. Это во многом связано с ограничениями реализации подпрограмм на основе стека. Исключением является библиотека Boost для C++. Context, являющаяся частью библиотек Boost, поддерживает переключение контекста на архитектурах ARM, MIPS, PowerPC, SPARC и x86 в операционных системах POSIX, Mac OS X и Windows. Коррутины можно построить на основе Boost.Context. В ситуациях, когда коррутина была бы естественной реализацией механизма, но недоступна, типичным решением является использование замыкания – подпрограммы с переменными состояния (статическими переменными, часто булевыми флагами) для сохранения внутреннего состояния между вызовами и передачи управления в нужную точку. Условные операторы в коде приводят к выполнению различных ветвей кода при последовательных вызовах, в зависимости от значений переменных состояния. Другим распространенным подходом является реализация явного конечного автомата в виде большого и сложного оператора switch или с помощью оператора goto, особенно вычисляемого goto. Такие реализации считаются сложными для понимания и поддержки, что является мотивацией для добавления встроенной поддержки коррутин. Потоки, и в меньшей степени волокна, являются альтернативой коррутинам в современных средах программирования. Потоки предоставляют средства для управления кооперативным взаимодействием одновременно выполняющихся фрагментов кода в реальном времени. Потоки широко доступны в средах, поддерживающих C (и поддерживаются нативно во многих других современных языках), знакомы многим программистам и обычно хорошо реализованы, документированы и поддерживаются. Однако, поскольку они решают сложную задачу, они включают в себя множество мощных и сложных средств и, соответственно, имеют крутую кривую обучения. Поэтому, когда требуется только коррутина, использование потока может быть избыточным. Важное отличие между потоками и коррутинами заключается в том, что потоки обычно планируются вытесняюще (preemptively), а коррутины – кооперативно. Поскольку потоки могут быть перепланированы в любой момент и могут выполняться параллельно, программы, использующие потоки, должны тщательно следить за блокировками. В отличие от этого, поскольку коррутины могут быть перепланированы только в определенных точках программы и не выполняются параллельно, программы, использующие коррутины, часто могут полностью избежать использования блокировок. Это свойство также называют преимуществом событийного или асинхронного программирования. Поскольку волокна планируются кооперативно, они предоставляют идеальную основу для реализации коррутин поверх них. Однако системная поддержка волокон часто ограничена по сравнению с поддержкой потоков.

as of 2003, many of the most popular programming languages, including C and its derivatives, do not have built in support for coroutines within the language or their standard libraries. This is, in large part, due to the limitations of stack based subroutine implementation. An exception is the C++ library Boost. Context, part of boost libraries, which supports context swapping on ARM, MIPS, PowerPC, SPARC and x86 on POSIX, Mac OS X and Windows. Coroutines can be built upon Boost. Context. In situations where a coroutine would be the natural implementation of a mechanism, but is not available, the typical response is to use a closurea subroutine with state variables (static variables, often boolean flags) to maintain an internal state between calls, and to transfer control to the correct point. Conditionals within the code result in the execution of different code paths on successive calls, based on the values of the state variables. Another typical response is to implement an explicit state machine in the form of a large and complex switch statement or via a goto statement, particularly a computed goto. Such implementations are considered difficult to understand and maintain, and a motivation for coroutine support. Threads, and to a lesser extent fibers, are an alternative to coroutines in mainstream programming environments today. Threads provide facilities for managing the real time cooperative interaction of simultaneously executing pieces of code. Threads are widely available in environments that support C (and are supported natively in many other modern languages), are familiar to many programmers, and are usually well implemented, well documented and well supported. However, as they solve a large and difficult problem they include many powerful and complex facilities and have a correspondingly difficult learning curve. As such, when a coroutine is all that is needed, using a thread can be overkill. One important difference between threads and coroutines is that threads are typically preemptively scheduled while coroutines are not. Because threads can be rescheduled at any instant and can execute concurrently, programs using threads must be careful about locking. In contrast, because coroutines can only be rescheduled at specific points in the program and do not execute concurrently, programs using coroutines can often avoid locking entirely. This property is also cited as a benefit of event driven or asynchronous programming. Since fibers are cooperatively scheduled, they provide an ideal base for implementing coroutines above. However, system support for fibers is often lacking compared to that for threads.

Язык

C# 2.0 добавил функциональность полу-коррутин (генераторов) посредством шаблона итератора и ключевого слова `yield`. C# 5.0 включает поддержку синтаксиса `await`. Помимо этого:

Фреймворк MindTouch Dream REST предоставляет реализацию коррутин на основе шаблона итератора C# 2.0. Фреймворк Caliburn для WPF использует итераторы C# 2.0 для упрощения программирования пользовательского интерфейса, особенно в асинхронных сценариях. Библиотека Power Threading Library от Джеффри Рихтера реализует AsyncEnumerator, который обеспечивает упрощенную модель асинхронного программирования с использованием коррутин на основе итераторов. Игровой движок Unity реализует коррутины. Проект Servelat Pieces от Евгения Боброва обеспечивает прозрачную асинхронность для сервисов Silverlight WCF и возможность асинхронного вызова любого синхронного метода. Реализация основана на итераторе Coroutines из Caliburn и блоках итератора C#. StreamThreads – это библиотека сопрограмм на C# с открытым исходным кодом, основанная на методах расширения итератора. Она поддерживает обработку ошибок и возвращает значения.

Замыкание

Cloroutine — это сторонняя библиотека, обеспечивающая поддержку стековых корутин в Clojure. Она реализована в виде макроса, который статически разбивает произвольный блок кода по произвольным вызовам переменных и генерирует корутину в виде функции с состоянием.

Д.

D реализует сопрограммы как стандартный библиотечный класс Fiber. Генератор позволяет легко представить функцию сопрограммы как диапазон, обеспечивая совместимость любой сопрограммы с существующими алгоритмами для диапазонов.

Иди .

Go имеет встроенную концепцию "горутин", которые представляют собой легковесные, независимые процессы, управляемые средой выполнения Go. Новую горутину можно запустить с помощью ключевого слова "go". Каждая горутина имеет стек переменного размера, который может расширяться по мере необходимости. Горутины обычно взаимодействуют друг с другом, используя встроенные каналы Go.

Ява

Существует несколько реализаций корутин в Java. Несмотря на ограничения, накладываемые абстракциями Java, JVM не препятствует их использованию. Существует четыре основных метода, но два из них нарушают переносимость байт-кода между JVM, соответствующими стандартам. Модифицированные JVM. Возможно создание модифицированной JVM для более нативной поддержки корутин. Для JVM Da Vinci были разработаны патчи. Модифицированный байт-код. Функциональность корутин может быть реализована путем переписывания обычного байт-кода Java, либо в процессе выполнения, либо во время компиляции. К инструментам относятся Javaflow, Java Coroutines и Coroutines. Механизмы JNI, специфичные для платформы. Они используют методы JNI, реализованные в библиотеках операционной системы или на C, для предоставления функциональности JVM. Абстракции потоков. Корутинные библиотеки, реализованные с использованием потоков, могут быть ресурсоемкими, хотя производительность будет зависеть от реализации потоков в JVM.

Котлин

Kotlin реализует корутины как часть библиотеки, разработанной самой компанией Kotlin.

Луа

Lua поддерживает полноценные асимметричные корутины со стеком с версии 5.0 (2003) в стандартной библиотеке coroutine.

Модуль-2

Модуль 2, как определено Виртом, реализует сопрограммы как часть стандартной библиотеки SYSTEM. Процедура NEWPROCESS заполняет контекст, получая в качестве параметров блок кода и место для стека, а процедура TRANSFER передает управление сопрограмме, используя контекст сопрограммы в качестве параметра.

Моно

Mono Common Language Runtime поддерживает продолжения, на основе которых можно создавать сопрограммы.

.NET Framework (англ.) (англ.)

Во время разработки NET Framework 2.0 компания Microsoft расширила архитектуру API размещения среды выполнения общего языка (CLR) для поддержки планирования на основе волокон, с расчетом на их использование в режиме волокон для SQL Server. Перед выпуском поддержка механизма переключения задач ICLRTask::SwitchOut была удалена из-за нехватки времени. В результате, использование API волокон для переключения задач в настоящее время не представляется возможным в NET Framework.

ОКамм

OCaml поддерживает сопрограммы через свой модуль Thread. Эти сопрограммы обеспечивают конкурентность без параллелизма и планируются с вытеснением на одном потоке операционной системы. Начиная с OCaml 5.0, также доступны зелёные потоки, предоставляемые другими модулями.

Ракеты

Racket предоставляет собственные продолжения, а также тривиальную реализацию корутин, доступную в официальном каталоге пакетов. Реализация С. Де Габриэль.

Схема

Поскольку Scheme обеспечивает полную поддержку продолжений, реализация коррутин практически тривиальна и требует лишь ведения очереди продолжений.

- Небольшой разговор .

Поскольку в большинстве сред Smalltalk стек вызовов является полноценным объектом, корутины могут быть реализованы без дополнительной поддержки библиотек или виртуальной машины.

Язык команд инструмента (Tcl)

С версии 8.6, Tool Command Language поддерживает сопрограммы в основном языке.

Вала

Vala реализует встроенную поддержку сопрограмм. Они разработаны для использования с циклом обработки событий Gtk, но могут использоваться и самостоятельно, если обеспечить, чтобы конечный колбэк никогда не вызывался до выполнения хотя бы одной операции yield.

Языки сборки

Машинно-зависимые языки ассемблера часто предоставляют прямые методы для выполнения сопрограмм. Например, в MACRO 11, языке ассемблера семейства PDP 11 миникомпьютеров, "классическое" переключение сопрограмм осуществляется инструкцией "JSR PC,@(SP)+", которая переходит по адресу, извлеченному из стека, и помещает текущий (то есть адрес следующей) инструкции в стек. На VAXen (в VAX MACRO) соответствующая инструкция – "JSB @(SP)+". Даже на Motorola 6809 есть инструкция "JSR [,S++]"; обратите внимание на "++", так как из стека извлекается 2 байта (адреса). Эта инструкция широко используется в (стандартном) "мониторе" Assist 09.