Las corrutinas son componentes de programas informáticos que permiten suspender y reanudar la ejecución, generalizando subrutinas para la multitarea cooperativa . Las corrutinas son adecuadas para implementar componentes de programas familiares, como tareas cooperativas , excepciones , bucles de eventos , iteradores , listas infinitas y tuberías .
Se han descrito como "funciones cuya ejecución se puede pausar". [1]
Melvin Conway acuñó el término corrutina en 1958 cuando lo aplicó a la construcción de un programa ensamblador . [2] La primera explicación publicada de la corrutina apareció más tarde, en 1963. [3]
No existe una definición precisa de corrutina. En 1980, Christopher D. Marlin [4] resumió dos características fundamentales ampliamente reconocidas de una corrutina:
Además de eso, una implementación de corrutina tiene 3 características:
yieldy resume. Los programadores no pueden elegir libremente a qué marco ceder. El entorno de ejecución solo cede al llamador más cercano de la corrutina actual. Por otro lado, en las corrutinas simétricas , los programadores deben especificar un destino de rendimiento.yield.El artículo "Revisiting Coroutines" [5] publicado en 2009 propuso el término corrutina completa para denotar una que admita corrutinas de primera clase y sea apilable. Las corrutinas completas merecen su propio nombre ya que tienen el mismo poder expresivo que las continuaciones de una sola ejecución y las continuaciones delimitadas. Las corrutinas completas son simétricas o asimétricas. Es importante destacar que el hecho de que una corrutina sea simétrica o asimétrica no tiene relación con su expresividad, ya que son igualmente expresivas, aunque las corrutinas completas son más expresivas que las corrutinas no completas. Si bien su poder expresivo es el mismo, las corrutinas asimétricas se parecen más a las estructuras de control basadas en rutinas en el sentido de que el control siempre se devuelve al invocador, lo que puede resultar más familiar para los programadores.
Las subrutinas son casos especiales de corrutinas. [6] Cuando se invocan subrutinas, la ejecución comienza desde el principio y, una vez que una subrutina sale, termina; una instancia de una subrutina solo retorna una vez y no mantiene el estado entre invocaciones. Por el contrario, las corrutinas pueden salir llamando a otras corrutinas, que pueden volver más tarde al punto en el que fueron invocadas en la corrutina original; desde el punto de vista de la corrutina, no está saliendo sino llamando a otra corrutina. [6] Por lo tanto, una instancia de corrutina mantiene el estado y varía entre invocaciones; puede haber múltiples instancias de una corrutina dada a la vez. La diferencia entre llamar a otra corrutina mediante "cederle" y simplemente llamar a otra rutina (que, entonces, también, volvería al punto original), es que la relación entre dos corrutinas que ceden ante la otra no es la de llamador-llamado, sino simétrica.
Cualquier subrutina puede traducirse a una corrutina que no llame a yield . [7]
A continuación se muestra un ejemplo sencillo de cómo pueden resultar útiles las corrutinas. Supongamos que tiene una relación consumidor-productor en la que una rutina crea elementos y los añade a una cola y otra elimina elementos de la cola y los utiliza. Por razones de eficiencia, desea añadir y eliminar varios elementos a la vez. El código podría tener este aspecto:
var q := nueva colaLa corrutina produce un bucle mientras q no esté lleno Crea algunos elementos nuevos Añade los elementos a q ceder para consumirLa corrutina consume un bucle mientras q no esté vacío eliminar algunos elementos de q utiliza los articulos ceder para producirLlamar a producir
Luego, la cola se llena o se vacía por completo antes de ceder el control a la otra corrutina mediante el comando yield . Las llamadas a otras corrutinas comienzan justo después del comando yield , en el bucle de corrutina externo.
Aunque este ejemplo se utiliza a menudo como introducción al multihilo , no se necesitan dos hilos para esto: la declaración de rendimiento se puede implementar mediante un salto directo de una rutina a la otra.
Las corrutinas son muy similares a los hilos . Sin embargo, las corrutinas son multitarea cooperativa , mientras que los hilos son típicamente multitarea preventiva . Las corrutinas proporcionan concurrencia , porque permiten que las tareas se realicen fuera de orden o en un orden modificable, sin cambiar el resultado general, pero no proporcionan paralelismo , porque no ejecutan múltiples tareas simultáneamente. Las ventajas de las corrutinas sobre los hilos son que pueden usarse en un contexto de tiempo real estricto ( el cambio entre corrutinas no necesita involucrar ninguna llamada al sistema o ninguna llamada de bloqueo de ningún tipo), no hay necesidad de primitivas de sincronización como mutexes , semáforos, etc. para proteger secciones críticas , y no hay necesidad de soporte del sistema operativo.
Es posible implementar corrutinas usando subprocesos programados preventivamente, de una manera que sea transparente para el código que los llama, pero se perderán algunas de las ventajas (particularmente la idoneidad para operaciones en tiempo real estricto y la relativa economía de cambiar entre ellos).
Los generadores, también conocidos como semicorrutinas, [8] son un subconjunto de las corrutinas. Específicamente, si bien ambos pueden ceder varias veces, suspendiendo su ejecución y permitiendo el reingreso en múltiples puntos de entrada, difieren en la capacidad de las corrutinas para controlar dónde continúa la ejecución inmediatamente después de que ceden, mientras que los generadores no pueden, en su lugar transfieren el control nuevamente al llamador del generador. [9] Es decir, dado que los generadores se utilizan principalmente para simplificar la escritura de iteradores , la yielddeclaración en un generador no especifica una corrutina a la que saltar, sino que pasa un valor de regreso a una rutina padre.
Sin embargo, aún es posible implementar corrutinas sobre una función generadora, con la ayuda de una rutina despachadora de nivel superior (un trampolín , esencialmente) que pasa el control explícitamente a los generadores secundarios identificados por tokens que pasan de vuelta desde los generadores:
var q := nueva colaEl generador produce un bucle mientras q no esté lleno Crea algunos elementos nuevos Añade los elementos a q producirEl generador consume el bucle mientras q no esté vacío eliminar algunos elementos de q utiliza los articulos producirdespachador de subrutinas var d := new dictionary( generador → iterador ) d[producir] := iniciar consumir d[consumir] := iniciar producir var actual := producir bucle llamar actual actual := siguiente d[actual]despachador de llamadas
Varias implementaciones de corrutinas para lenguajes con soporte de generador pero sin corrutinas nativas (por ejemplo, Python [10] antes de 2.5) utilizan este modelo o uno similar.
El uso de corrutinas para máquinas de estado o concurrencia es similar al uso de recursión mutua con llamadas de cola , ya que en ambos casos el control cambia a una rutina diferente de un conjunto de rutinas. Sin embargo, las corrutinas son más flexibles y generalmente más eficientes. Dado que las corrutinas ceden en lugar de regresar, y luego reanudan la ejecución en lugar de reiniciar desde el principio, pueden mantener el estado, ambas variables (como en un cierre) y el punto de ejecución, y los rendimientos no se limitan a estar en la posición de cola; las subrutinas mutuamente recursivas deben usar variables compartidas o pasar el estado como parámetros. Además, cada llamada mutuamente recursiva de una subrutina requiere un nuevo marco de pila (a menos que se implemente la eliminación de llamadas de cola ), mientras que pasar el control entre corrutinas usa los contextos existentes y se puede implementar simplemente mediante un salto.
Las corrutinas son útiles para implementar lo siguiente:
Las corrutinas se originaron como un método de lenguaje ensamblador , pero son compatibles con algunos lenguajes de programación de alto nivel .
Dado que las continuaciones se pueden usar para implementar corrutinas, los lenguajes de programación que las admiten también pueden admitir corrutinas con bastante facilidad.
A partir de 2003 [actualizar], muchos de los lenguajes de programación más populares, incluido C y sus derivados, no tienen soporte integrado para corrutinas dentro del lenguaje o sus bibliotecas estándar. Esto se debe, en gran parte, a las limitaciones de la implementación de subrutinas basadas en pila . Una excepción es la biblioteca C++ Boost.Context, parte de las bibliotecas boost, que admite el intercambio de contexto en ARM, MIPS, PowerPC, SPARC y x86 en POSIX, Mac OS X y Windows. Las corrutinas se pueden crear sobre Boost.Context.
En situaciones en las que una corrutina sería la implementación natural de un mecanismo, pero no está disponible, la respuesta típica es utilizar un cierre , una subrutina con variables de estado ( variables estáticas , a menudo indicadores booleanos) para mantener un estado interno entre llamadas y transferir el control al punto correcto. Los condicionales dentro del código dan como resultado la ejecución de diferentes rutas de código en llamadas sucesivas, según los valores de las variables de estado. Otra respuesta típica es implementar una máquina de estado explícita en forma de una declaración switch grande y compleja o mediante una declaración goto , particularmente un goto calculado . Tales implementaciones se consideran difíciles de entender y mantener, y una motivación para el soporte de corrutinas.
Los subprocesos y, en menor medida, las fibras , son una alternativa a las corrutinas en los entornos de programación convencionales de la actualidad. Los subprocesos proporcionan facilidades para gestionar la interacción cooperativa en tiempo real de fragmentos de código que se ejecutan simultáneamente . Los subprocesos están ampliamente disponibles en entornos que admiten C (y son compatibles de forma nativa en muchos otros lenguajes modernos), son familiares para muchos programadores y, por lo general, están bien implementados, bien documentados y bien respaldados. Sin embargo, como resuelven un problema grande y difícil, incluyen muchas facilidades potentes y complejas y tienen una curva de aprendizaje correspondientemente difícil. Como tal, cuando una corrutina es todo lo que se necesita, usar un subproceso puede ser excesivo.
Una diferencia importante entre subprocesos y corrutinas es que los subprocesos suelen programarse de forma preventiva, mientras que las corrutinas no. Debido a que los subprocesos se pueden reprogramar en cualquier momento y se pueden ejecutar simultáneamente, los programas que utilizan subprocesos deben tener cuidado con el bloqueo . Por el contrario, debido a que las corrutinas solo se pueden reprogramar en puntos específicos del programa y no se ejecutan simultáneamente, los programas que utilizan corrutinas a menudo pueden evitar el bloqueo por completo. Esta propiedad también se cita como un beneficio de la programación asincrónica o basada en eventos .
Dado que las fibras están programadas de forma cooperativa, proporcionan una base ideal para implementar las corrutinas anteriores. [23] Sin embargo, el soporte del sistema para fibras suele ser deficiente en comparación con el de los subprocesos.
Para implementar corrutinas de propósito general, se debe obtener una segunda pila de llamadas , que es una característica que no es compatible directamente con el lenguaje C. Una forma confiable (aunque específica de la plataforma) de lograr esto es usar una pequeña cantidad de ensamblaje en línea para manipular explícitamente el puntero de pila durante la creación inicial de la corrutina. Este es el enfoque recomendado por Tom Duff en una discusión sobre sus méritos relativos frente al método utilizado por Protothreads . [24] [ fuente no primaria necesaria ] En plataformas que proporcionan la llamada al sistema POSIX sigaltstack, se puede obtener una segunda pila de llamadas llamando a una función springboard desde dentro de un manejador de señales [25] [26] para lograr el mismo objetivo en C portable, al costo de cierta complejidad adicional. Las bibliotecas C que cumplen con POSIX o la Especificación Única de Unix (SUSv3) proporcionaron rutinas como getcontext, setcontext, makecontext y swapcontext , pero estas funciones se declararon obsoletas en POSIX 1.2008. [27]
Una vez que se ha obtenido una segunda pila de llamadas con uno de los métodos enumerados anteriormente, las funciones setjmp y longjmp en la biblioteca estándar de C se pueden utilizar para implementar los cambios entre corrutinas. Estas funciones guardan y restauran, respectivamente, el puntero de pila , el contador de programa , los registros guardados por el usuario llamado y cualquier otro estado interno según lo requiera la ABI , de modo que al regresar a una corrutina después de haber dado un rendimiento se restaura todo el estado que se restauraría al regresar de una llamada de función. Las implementaciones minimalistas, que no se apoyan en las funciones setjmp y longjmp, pueden lograr el mismo resultado a través de un pequeño bloque de ensamblaje en línea que intercambia simplemente el puntero de pila y el contador de programa, y bloquea todos los demás registros. Esto puede ser significativamente más rápido, ya que setjmp y longjmp deben almacenar de manera conservadora todos los registros que pueden estar en uso de acuerdo con la ABI, mientras que el método clobber permite al compilador almacenar (al volcar a la pila) solo lo que sabe que realmente está en uso.
Debido a la falta de soporte directo del lenguaje, muchos autores han escrito sus propias bibliotecas para corrutinas que ocultan los detalles anteriores. La biblioteca libtask de Russ Cox [28] es un buen ejemplo de este género. Utiliza las funciones de contexto si las proporciona la biblioteca nativa de C; de lo contrario, proporciona sus propias implementaciones para ARM, PowerPC, Sparc y x86. Otras implementaciones notables incluyen libpcl, [29] coro, [30] lthread, [31] libCoroutine, [32] libconcurrency, [33] libcoro, [34] ribs2, [35] libdill., [36] libaco, [37] y libco. [26]
Además del enfoque general anterior, se han realizado varios intentos de aproximar corrutinas en C con combinaciones de subrutinas y macros. La contribución de Simon Tatham , [38] basada en el dispositivo de Duff , es un ejemplo notable del género y es la base para Protothreads e implementaciones similares. [39] Además de las objeciones de Duff, [24] los propios comentarios de Tatham proporcionan una evaluación franca de las limitaciones de este enfoque: "Hasta donde yo sé, esta es la peor pieza de hackery de C jamás vista en código de producción serio". [38] Las principales deficiencias de esta aproximación son que, al no mantener un marco de pila separado para cada corrutina, las variables locales no se conservan en todos los rendimientos de la función, no es posible tener múltiples entradas a la función y el control solo puede obtenerse desde la rutina de nivel superior. [24]
C# 2.0 agregó la funcionalidad de semicorrutina ( generador ) a través del patrón iterador y yieldla palabra clave. [44] [45] C# 5.0 incluye soporte para la sintaxis await . Además:
Cloroutine es una biblioteca de terceros que brinda soporte para corrutinas sin pila en Clojure . Se implementa como una macro, que divide estáticamente un bloque de código arbitrario en llamadas var arbitrarias y emite la corrutina como una función con estado.
D implementa corrutinas como su clase de biblioteca estándar. Un generador de fibra hace que sea trivial exponer una función de fibra como un rango de entrada , lo que hace que cualquier fibra sea compatible con los algoritmos de rango existentes.
Go tiene un concepto integrado de " goroutines ", que son procesos ligeros e independientes gestionados por el entorno de ejecución de Go. Se puede iniciar un nuevo goroutine utilizando la palabra clave "go". Cada goroutine tiene una pila de tamaño variable que se puede ampliar según sea necesario. Las goroutines generalmente se comunican utilizando los canales integrados de Go. [46] [47] [48] [49]
Existen varias implementaciones de corrutinas en Java . A pesar de las restricciones impuestas por las abstracciones de Java, la JVM no excluye esta posibilidad. [50] Se utilizan cuatro métodos generales, pero dos rompen la portabilidad del código de bytes entre las JVM compatibles con los estándares.
Kotlin implementa corrutinas como parte de una biblioteca propia.
Lua ha soportado corrutinas asimétricas apilables de primera clase desde la versión 5.0 (2003), [52] en la biblioteca estándar coroutine . [53] [54]
Modula-2, tal como lo define Wirth, implementa corrutinas como parte de la biblioteca SYSTEM estándar.
El procedimiento NEWPROCESS() rellena un contexto dado un bloque de código y espacio para una pila como parámetros, y el procedimiento TRANSFER() transfiere el control a una corrutina dado el contexto de la corrutina como su parámetro.
Mono Common Language Runtime tiene soporte para continuaciones, [55] a partir de las cuales se pueden construir corrutinas.
Durante el desarrollo de .NET Framework 2.0, Microsoft amplió el diseño de las API de hospedaje de Common Language Runtime (CLR) para manejar la programación basada en fibra con miras a su uso en modo de fibra para SQL Server. [56] Antes del lanzamiento, se eliminó la compatibilidad con el gancho de conmutación de tareas ICLRTask::SwitchOut debido a limitaciones de tiempo. [57] En consecuencia, el uso de la API de fibra para cambiar tareas actualmente no es una opción viable en .NET Framework. [ necesita actualización ]
OCaml admite corrutinas a través de su Threadmódulo. [58] Estas corrutinas proporcionan concurrencia sin paralelismo y se programan de manera preventiva en un único hilo del sistema operativo. Desde OCaml 5.0, también están disponibles los hilos verdes , proporcionados por diferentes módulos.
Las corrutinas se implementan de forma nativa en todos los backends de Raku . [59]
Racket ofrece continuaciones nativas, con una implementación trivial de corrutinas proporcionada en el catálogo oficial de paquetes. Implementación de S. De Gabrielle
Dado que Scheme proporciona soporte completo para continuaciones, la implementación de corrutinas es casi trivial y solo requiere que se mantenga una cola de continuaciones.
Dado que, en la mayoría de los entornos Smalltalk , la pila de ejecución es un ciudadano de primera clase, las corrutinas se pueden implementar sin necesidad de biblioteca adicional o soporte de VM.
Desde la versión 8.6, el lenguaje de comandos de herramientas admite corrutinas en el lenguaje principal. [62]
Vala implementa soporte nativo para corrutinas. Están diseñadas para usarse con un bucle principal de Gtk, pero se pueden usar solas si se tiene cuidado de garantizar que nunca sea necesario llamar a la devolución de llamada final antes de realizar, al menos, una operación de rendimiento.
Los lenguajes ensambladores dependientes de la máquina a menudo proporcionan métodos directos para la ejecución de corrutinas. Por ejemplo, en MACRO-11 , el lenguaje ensamblador de la familia de minicomputadoras PDP-11 , el cambio de corrutina "clásico" se efectúa mediante la instrucción "JSR PC,@(SP)+", que salta a la dirección extraída de la pila y empuja la dirección de instrucción actual ( es decir , la de la siguiente ) a la pila. En VAXen (en VAX MACRO ), la instrucción comparable es "JSB @(SP)+". Incluso en un Motorola 6809 existe la instrucción "JSR [,S++]"; note el "++", ya que se extraen 2 bytes (de dirección) de la pila. Esta instrucción se usa mucho en el 'monitor' (estándar) Assist 09.
6. La simetría es un concepto que reduce la complejidad (las co-rutinas incluyen subrutinas); búsquelo en todas partes