2009-04-03 14 views
120

¿Cuál es la diferencia entre una coroutine y una continuación y un generador?Coroutine vs Continuation vs Generator

+1

Me pregunto si las corutinas y las continuaciones son efectivamente equivalentes. Sé que es posible modelar corutinas con continuaciones, pero ¿es posible modelar las continuaciones con corrutinas o no porque las continuaciones son estrictamente más potentes? – nalply

Respuesta

102

Comenzaré con los generadores, ya que son el caso más simple. Como se mencionó en @zvolkov, son funciones/objetos que pueden repetirse repetidamente sin devolver, pero al llamar devolverán (cederán) un valor y luego suspenderán su ejecución. Cuando vuelvan a llamar, comenzarán desde donde suspendieron la ejecución por última vez y volverán a hacer lo suyo.

Un generador es esencialmente una corutina cortada (asimétrica). La diferencia entre una coroutine y un generador es que una coroutine puede aceptar argumentos después de haber sido llamada inicialmente, mientras que un generador no puede.

Es un poco difícil para algunos con un ejemplo trivial de dónde usarías corutinas, pero esta es mi mejor opción. Tome este código (compuesto) de Python como ejemplo.

def my_coroutine_body(*args): 
    while True: 
     # Do some funky stuff 
     *args = yield value_im_returning 
     # Do some more funky stuff 

my_coro = make_coroutine(my_coroutine_body) 

x = 0 
while True: 
    # The coroutine does some funky stuff to x, and returns a new value. 
    x = my_coro(x) 
    print x 

Un ejemplo de donde se utilizan corrutinas es lexers y analizadores. Sin corutinas en el lenguaje o emulado de alguna manera, el código léxico y de análisis debe mezclarse, aunque en realidad son dos preocupaciones distintas. Pero si usa una coroutine, puede separar el código lexing y de análisis.

(Voy a analizar la diferencia entre corutinas simétricas y asimétricas. Baste decir que son equivalentes, se puede convertir de una a la otra, y corutinas asimétricas, que son las que más se parecen a las generadoras --son los más fáciles de entender. Yo estaba delineando cómo se podrían implementar corotines asimétricas en Python.)

Las continuas son en realidad bestias bastante simples. Todas son funciones que representan otro punto del programa que, si lo llamas, hará que la ejecución cambie automáticamente al punto que representa la función. Usas versiones muy restringidas de ellos todos los días sin siquiera darte cuenta. Las excepciones, por ejemplo, pueden considerarse como una especie de continuación de adentro hacia afuera. Te daré un ejemplo de pseudocódigo basado en Python de una continuación.

Say Python tenía una función llamada callcc(), y esta función tomaba dos argumentos, el primero era una función, y el segundo era una lista de argumentos para invocarlo. La única restricción en esa función sería que el último argumento que tome será una función (que será nuestra continuación actual).

def foo(x, y, cc): 
    cc(max(x, y)) 

biggest = callcc(foo, [23, 42]) 
print biggest 

¿Qué pasaría es que callcc() a su vez llamada foo() con la continuación actual (cc), es decir, una referencia al punto en el programa en el cual se llamaba callcc(). Cuando foo() llama a la continuación actual, es esencialmente lo mismo que decirle al callcc() que regrese con el valor que está llamando a la continuación actual, y cuando lo hace, revierte la pila hasta donde se creó la continuación actual, es decir, cuando llamaste al callcc().

El resultado de todo esto sería que nuestra variante hipotética de Python imprimirá '42'.

Espero que eso ayude, ¡y estoy seguro de que mi explicación se puede mejorar un poco!

+6

Una nit: _delimited_continuaciones son funciones, pero _undelimited_continuaciones no son: http://okmij.org/ftp/continuations/undelimited.html#delim-vs-undelim –

+2

Ese es un buen punto. Dicho esto, en la mayoría de las aplicaciones prácticas, cuando las personas dicen 'continuación', están hablando de continuaciones parciales/delimitadas. Traer los otros tipos de continuaciones habría enturbiado la explicación de alguna manera. –

+1

Las continuas no son funciones, aunque se pueden reificar en funciones. "Dicho esto, en la mayoría de las aplicaciones prácticas, cuando la gente dice 'continuación', están hablando de continuaciones parciales/delimitadas". ¿Señalarías tal uso del término "continuación"? Nunca me he encontrado con tal uso. También dio un ejemplo para una continuación no delimitada, mediante el uso de call/cc. Los operadores para continuaciones delimitadas generalmente son "restablecer" y "cambiar" (pueden tener otros nombres). – Ivancho

28

Coroutine es uno de varios procedimientos que se turnan para hacer su trabajo y luego hacer una pausa para dar control a las otras corutinas del grupo.

La continuación es un "puntero a una función" que pasa a algún procedimiento, para ser ejecutado ("continúa con") cuando se realiza ese procedimiento.

Generator (en .NET) es una construcción de lenguaje que puede escupir un valor, "pausa" la ejecución del método y luego proceder desde el mismo punto cuando se le solicita el siguiente valor.

+0

Me doy cuenta de que la respuesta puede no ser precisa, pero a este nivel de pregunta intenté mantenerlo simple. Además, realmente no entiendo todo esto por mí mismo :) – zvolkov

+0

Un generador en python es similar a la versión C#, pero se implementa como una sintaxis especial para crear una instancia de un objeto iterador, que devuelve los valores devueltos por la "función "definición que proporciona. – Benson

+2

Una pequeña corrección: "... incluida la pila de llamadas y todas las variables, PERO NO SUS VALORES" (o simplemente suelte "todas las variables"). Las continuas no conservan los valores, solo contienen la pila de llamadas. – nalply

7

En la versión más nueva de Python, puede enviar valores a Generadores con generator.send(), lo que hace que los generadores de pitones sean corutinas de manera efectiva.

La principal diferencia entre Python Generator y otro generador, por ejemplo, greenlet, es que en python, su yield value solo puede regresar a la persona que llama. Mientras está en el área verde, target.switch(value) puede llevarlo a una corutina de destino específica y obtener un valor donde el target continuará ejecutándose.

+3

Pero en Python, todas las llamadas 'yield' deben estar en la misma función, que se llama el" Generador ". No se puede "ceder" desde una subfunción, por lo que las Python se llaman * semi-coroutines *, mientras que Lua tiene * corutinas asimétricas *. (Hay propuestas para propagar los rendimientos, pero creo que eso solo enturbia las aguas.) – cdunn2001

+4

@ cdunn2001: (comentario de Winston) Python3.3 introdujo la expresión "yield from" que le permite ceder desde el sub-generador. –

Cuestiones relacionadas