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 canalizaciones .
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 de ensamblaje . [2] La primera explicación publicada de la corrutina apareció más tarde, en 1963. [3]
No existe una definición única y 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 rutina tiene 3 características:
yieldy resume. Los programadores no pueden elegir libremente a qué marco ceder. El tiempo de ejecución solo cede al llamante más cercano de la rutina actual. Por otro lado, en la rutina simétrica , los programadores deben especificar un destino de rendimiento.yield.Revisiting Coroutines [5] publicado en 2009 propuso el término Full Coroutine para denotar uno que admite corrutinas de primera clase y es acumulativo. Las corrutinas completas merecen su propio nombre porque tienen el mismo poder expresivo que las continuaciones one-shot 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 influye en cuán expresiva puede ser, ya que son igualmente expresivas, aunque las corrutinas completas son más expresivas que las 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 los programadores pueden encontrar más familiar.
Las subrutinas son casos especiales de corrutinas. [6] Cuando se invocan subrutinas, la ejecución comienza desde el principio y, una vez que sale una subrutina, finaliza; una instancia de una subrutina solo regresa una vez y no mantiene el estado entre invocaciones. Por el contrario, las corrutinas pueden salir llamando a otras corrutinas, que luego pueden regresar al punto donde fueron invocadas en la corrutina original; Desde el punto de vista de la corrutina, no se trata de salir sino de llamar a otra corrutina. [6] Por lo tanto, una instancia de rutina mantiene el estado y varía entre invocaciones; puede haber varias instancias de una rutina determinada a la vez. La diferencia entre llamar a otra corrutina mediante "ceder" a ella y simplemente llamar a otra rutina (que luego, también, volvería al punto original), es que la relación entre dos corrutinas que ceden entre sí no es la de llamante -callee, pero en cambio simétrico.
Cualquier subrutina se puede traducir a una corrutina que no llame a rendimiento . [7]
A continuación se muestra un ejemplo sencillo de cómo las corrutinas pueden resultar útiles. Suponga que tiene una relación consumidor-productor en la que una rutina crea elementos y los agrega a una cola y otra elimina elementos de la cola y los usa. Por razones de eficiencia, desea agregar y eliminar varios elementos a la vez. El código podría verse así:
var q := nueva colala rutina produce un bucle mientras q no está lleno crear algunos elementos nuevos agregar los elementos a q rendir para consumirbucle de consumo de rutina mientras q no está vacío eliminar algunos elementos de q usa los artículos rendimiento 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 de rendimiento . Las llamadas de corrutinas adicionales comienzan justo después del rendimiento , en el bucle de corrutina externo.
Aunque este ejemplo se utiliza a menudo como introducción al subproceso múltiple , no se necesitan dos subprocesos para esto: la declaración de rendimiento se puede implementar saltando directamente de una rutina a otra.
Las corrutinas son muy similares a los hilos . Sin embargo, las corrutinas realizan múltiples tareas de forma cooperativa , mientras que los subprocesos suelen realizar múltiples tareas de forma preventiva . Las corrutinas proporcionan concurrencia porque permiten que las tareas se realicen fuera de orden o en un orden variable, sin cambiar el resultado general, pero no proporcionan paralelismo porque no ejecutan múltiples tareas simultáneamente. Las ventajas de las corrutinas sobre los subprocesos son que pueden usarse en un contexto de tiempo real estricto ( el cambio entre corrutinas no necesita implicar llamadas al sistema ni llamadas de bloqueo de ningún tipo), no hay necesidad de primitivas de sincronización como mutexes , semáforos, etc. para proteger las secciones críticas y no hay necesidad de soporte del sistema operativo.
Es posible implementar corrutinas utilizando subprocesos programados de forma preventiva, de una manera que sea transparente para el código de llamada, pero se perderán algunas de las ventajas (particularmente la idoneidad para la operación en tiempo real y el relativo bajo costo de cambiar entre ellos).
Los generadores, también conocidos como semicorutinas, [8] son un subconjunto de 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 ceder, mientras que los generadores no pueden, sino que transfieren el control nuevamente a la persona que llama al 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 a una rutina principal.
Sin embargo, todavía es posible implementar corrutinas en la parte superior de una instalación de generador, con la ayuda de una rutina de despachador de nivel superior (un trampolín , esencialmente) que pasa el control explícitamente a los generadores secundarios identificados por tokens devueltos desde los generadores:
var q := nueva colaEl generador produce un bucle mientras q no está lleno. crear algunos elementos nuevos agregar los elementos a q producirEl generador consume bucle mientras q no está vacío. eliminar algunos elementos de q usa los artículos producirdespachador de subrutinas var d: = nuevo diccionario ( generador → iterador ) d[producir] := iniciar producir d[consumir] := iniciar consumir var actual := producir llamada de bucle actual actual := siguiente d[actual]llamar al despachador
Varias implementaciones de corrutinas para lenguajes con soporte de generador pero sin corrutinas nativas (por ejemplo, Python [10] anterior a 2.5) utilizan este modelo o uno similar.
Usar corrutinas para máquinas de estado o concurrencia es similar a usar recursividad mutua con llamadas de cola , ya que en ambos casos el control cambia a uno diferente de un conjunto de rutinas. Sin embargo, las corrutinas son más flexibles y, en general, más eficientes. Dado que las corrutinas rinden en lugar de regresar, y luego reanudan la ejecución en lugar de reiniciar desde el principio, pueden mantener el estado, tanto las variables (como en un cierre) como el punto de ejecución, y los rendimientos no se limitan a estar en la posición final; 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 rutinas utiliza 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 utilizar 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 para 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 . Estas implementaciones se consideran difíciles de comprender y mantener, y constituyen una motivación para el soporte rutinario.
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 la ejecución simultánea de fragmentos de código. Los subprocesos están ampliamente disponibles en entornos que soportan C (y son compatibles de forma nativa con muchos otros lenguajes modernos), son familiares para muchos programadores y, por lo general, están bien implementados, bien documentados y bien soportados. Sin embargo, como resuelven un problema grande y difícil, incluyen muchas funciones poderosas y complejas y, en consecuencia, tienen una curva de aprendizaje difícil. Como tal, cuando todo lo que se necesita es una corrutina, usar un subproceso puede resultar excesivo.
Una diferencia importante entre subprocesos y corrutinas es que los subprocesos normalmente se programan de forma preventiva, mientras que las corrutinas no. Debido a que los subprocesos se pueden reprogramar en cualquier instante y pueden ejecutarse 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 usan 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 se programan de forma cooperativa, proporcionan una base ideal para implementar las corrutinas anteriores. [23] Sin embargo, a menudo falta el soporte del sistema para las fibras en comparación con el de los hilos.
Para implementar rutinas de propósito general, se debe obtener una segunda pila de llamadas , que es una característica que el lenguaje C no admite directamente . Una forma confiable (aunque específica de la plataforma) de lograr esto es utilizar una pequeña cantidad de ensamblaje en línea para manipular explícitamente el puntero de la pila durante la creación inicial de la rutina. 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] [ se necesita fuente no principal ] En plataformas que proporcionan la llamada al sistema POSIX sigaltstack, se puede obtener una segunda pila de llamadas llamando a una función de trampolín desde un controlador de señales [25] [26] para lograr el mismo objetivo en portátil C, a costa de cierta complejidad adicional. Las bibliotecas C que cumplen con POSIX o la especificación única de Unix (SUSv3) proporcionan rutinas como getcontext, setcontext, makecontext y swapcontext , pero estas funciones fueron declaradas 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 C estándar se pueden usar para implementar los cambios entre rutinas. Estas funciones guardan y restauran, respectivamente, el puntero de la pila , el contador del programa , los registros guardados por el destinatario y cualquier otro estado interno requerido por la ABI , de modo que regresar a una corrutina después de haber cedido restaura todo el estado que se restauraría al regresar. de una llamada a función. Las implementaciones minimalistas, que no aprovechan 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 la pila y el contador del programa, y golpea todos los demás registros. Esto puede ser significativamente más rápido, ya que setjmp y longjmp deben almacenar de forma conservadora todos los registros que puedan estar en uso según la ABI, mientras que el método clobber permite al compilador almacenar (derramándolos en la pila) solo lo que sabe que está realmente 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 C nativa; 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 las 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 piratería en C jamás vista en un 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 rutina, las variables locales no se conservan en los rendimientos de la función, no es posible tener múltiples entradas a la función y el control solo puede ser obtenido de la rutina de nivel superior. [24]
C# 2.0 agregó funcionalidad de semicorutina ( generadoryield ) a través del patrón iterador y la palabra clave. [44] [45] C# 5.0 incluye soporte de sintaxis de espera . Además:
Cloroutine es una biblioteca de terceros que brinda soporte para corrutinas sin pila en Clojure . Se implementa como una macro, dividiendo estáticamente un bloque de código arbitrario en llamadas var arbitrarias y emitiendo la corrutina como una función con estado.
D implementa corrutinas como su clase de biblioteca estándar. El generador Fiber A 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 incorporado de " gorutinas ", que son procesos ligeros e independientes administrados por el tiempo de ejecución de Go. Se puede iniciar una nueva gorutina utilizando la palabra clave "go". Cada gorutina tiene una pila de tamaño variable que se puede ampliar según sea necesario. Las gorutinas generalmente se comunican mediante los canales integrados de Go. [46] [47] [48] [49]
Existen varias implementaciones de corrutinas en Java . A pesar de las limitaciones 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 que cumplen con los estándares.
Kotlin implementa corrutinas como parte de una biblioteca propia.
Lua ha admitido corrutinas asimétricas apilables de primera clase desde la versión 5.0 (2003), [52] en la biblioteca estándar de corrutina . [53] [54]
Modula-2 , tal como lo define Wirth , implementa corrutinas como parte de la biblioteca estándar del SISTEMA.
El procedimiento NEWPROCESS() completa 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 rutina dado el contexto de la rutina como 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 alojamiento Common Language Runtime (CLR) para manejar la programación basada en fibra con miras a su uso en modo de fibra para el servidor SQL. [56] Antes del lanzamiento, se eliminó la compatibilidad con el enlace de cambio de tareas ICLRTask::SwitchOut debido a limitaciones de tiempo. [57] En consecuencia, el uso de la API de fibra para cambiar de tarea 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 forma preventiva en un único subproceso del sistema operativo. Desde OCaml 5.0, los hilos verdes también están disponibles; proporcionado por diferentes módulos.
Las corrutinas se implementan de forma nativa en todos los backends de Raku . [59]
Racket proporciona continuaciones nativas, con una implementación trivial de corrutinas proporcionadas en el catálogo de paquetes oficial. Implementación por S. De Gabrielle
Dado que Scheme proporciona soporte total para continuaciones, implementar corrutinas es casi trivial y solo requiere que se mantenga una cola de continuaciones.
Dado que, en la mayoría de los entornos de Smalltalk , la pila de ejecución es un ciudadano de primera clase, las corrutinas se pueden implementar sin 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ñados para usarse con un Gtk Main Loop, pero se pueden usar solos si se tiene cuidado de garantizar que nunca sea necesario llamar a la devolución de llamada final antes de realizar, al menos, un rendimiento.
Los lenguajes ensambladores dependientes de la máquina a menudo proporcionan métodos directos para la ejecución de rutinas. Por ejemplo, en MACRO-11 , el lenguaje ensamblador de la familia de minicomputadoras PDP-11 , el cambio de rutina "clásico" se efectúa mediante la instrucción "JSR PC,@(SP)+", que salta a la dirección extraída del 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++]"; tenga en cuenta "++", ya que se extraen 2 bytes (de dirección) de la pila. Esta instrucción se utiliza mucho en el 'monitor' Assist 09 (estándar).
6. La simetría es un concepto que reduce la complejidad (las co-rutinas incluyen subrutinas);
búscalo en todas partes