Coroutine vs Continuation vs Generator

147

¿Cuál es la diferencia entre una corutina y una continuación y un generador?

Mehdi Asgari
fuente
2
Me pregunto si las corutinas y las continuaciones son efectivamente equivalentes. Sé que es posible modelar corutinas con continuaciones, pero ¿es posible modelar continuaciones con corutinas o no porque las continuaciones son estrictamente más poderosas?
nalply

Respuestas:

127

Comenzaré con los generadores, ya que son el caso más simple. Como mencionó @zvolkov, son funciones / objetos a los que se puede llamar repetidamente sin volver, pero cuando se les llama devolverá (producirá) un valor y luego suspenderá su ejecución. Cuando se les llame nuevamente, comenzarán desde donde suspendieron la ejecución por última vez y harán lo suyo nuevamente.

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

Es un poco difícil encontrar un ejemplo trivial de dónde usarías corutinas, pero este es mi mejor intento. Tome este código Python (inventado) 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 dónde se usan las corutinas son lexers y parsers. Sin las rutinas en el lenguaje o emuladas de alguna manera, el código lexing y parsing debe mezclarse, aunque en realidad son dos preocupaciones separadas. Pero utilizando una rutina, puede separar el código lexing y el análisis.

(Voy a pasar por alto la diferencia entre corutinas simétricas y asimétricas. Baste decir que son equivalentes, puede convertir de una a otra, y las corutinas asimétricas, que son los generadores más parecidos) más fácil de entender. Estaba esbozando cómo uno podría implementar corutinas asimétricas en Python).

Las continuaciones son en realidad bestias bastante simples. Todas ellas son funciones que representan otro punto en el programa que, si lo llama, hará que la ejecución cambie automáticamente al punto que representa la función. Utiliza 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. Le daré un ejemplo de pseudocódigo basado en Python de una continuación.

Digamos que Python tenía una función llamada callcc(), y esta función tomó dos argumentos, el primero era una función y el segundo era una lista de argumentos para llamarlo. La única restricción sobre 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

Lo que sucedería es que callcc()a su vez llamaría foo()con la continuación actual ( cc), es decir, una referencia al punto del programa en el que callcc()se llamó. Cuando foo()llama a la continuación actual, es esencialmente lo mismo que decirle callcc()que regrese con el valor con el que está llamando a la continuación actual, y cuando lo hace, revierte la pila al lugar donde se creó la continuación actual, es decir, cuando llamó callcc().

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

Espero que eso ayude, ¡y estoy seguro de que mi explicación puede mejorarse bastante!

Keith Gaughan
fuente
66
Una cosa: las continuaciones delimitadas son funciones, pero las continuaciones no delimitadas no lo son: okmij.org/ftp/continuations/undelimited.html#delim-vs-undelim
Frank Shearar
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. Introducir los otros tipos de continuaciones habría enturbiado la explicación.
Keith Gaughan el
1
Las continuaciones no son funciones, aunque pueden reificarse 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 he conocido tal uso. También dio un ejemplo para una continuación no delimitada, utilizando call / cc. Los operadores para continuaciones delimitadas son generalmente "reset" y "shift" (pueden tener otros nombres).
Ivancho
3
Comencemos con el hecho de que han pasado cinco años desde que escribí esto. Llegas un poco tarde a la fiesta. En segundo lugar, que las continuaciones no delimitadas no son funciones, pero usted trata de explicar cómo funcionan sin referirse a ellas como tales y al mismo tiempo mantener el lenguaje directo. Desde el punto de vista del programador promedio, el hecho de que una continuación no delimitada no regrese solo lo convierte en una función de un solo disparo, que no es correcta según la definición de qué es una función, pero al menos es comprensible .
Keith Gaughan
2
No llego tarde a la fiesta, ya que este es el primer resultado que obtengo en Google cuando busco "coroutine vs generator". Esperaba encontrar buena información sobre sus diferencias. De todos modos lo encontré en otro lado. Y no soy el primero en señalar que su explicación sobre las continuaciones es incorrecta. El problema es que alguien se equivocará y posiblemente se confundirá más tarde cuando conozca la misma palabra utilizada para algo diferente.
Ivancho
33

La rutina es uno de los varios procedimientos que se turnan para hacer su trabajo y luego hacen una pausa para dar control a las otras rutinas del grupo.

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

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

zvolkov
fuente
Me doy cuenta de que la respuesta puede no ser precisa, pero a este nivel de pregunta traté de mantenerla simple. Además, yo mismo no entiendo todo esto :)
zvolkov 03 de
Un generador en python es similar a la versión de C #, pero se implementa como una sintaxis especial para crear una instancia de un objeto iterador, que devuelve los valores devueltos por la definición de "función" que proporciona.
Benson el
2
Una pequeña corrección: "... incluyendo la pila de llamadas y todas las variables PERO NO SUS VALORES" (o simplemente descartar "todas las variables"). Las continuaciones no conservan los valores, solo contienen la pila de llamadas.
nalply
No, las continuaciones no son "puntero a una función". En la implementación más ingenua, contiene un puntero para funcionar y un entorno contiene las variables locales. Y nunca regresa a menos que use algo como call / cc para capturarlo con un valor de retorno.
NalaGinrut
9

En la versión más reciente de Python, puede enviar valores a los Generadores con generator.send(), lo que hace que los Generadores de python sean efectivamente rutinas.

La principal diferencia entre Python Generator y otro generador, digamos greenlet, es que en python, yield valuesolo puede volver a la persona que llama. Mientras está en greenlet, target.switch(value)puede llevarlo a una corutina objetivo específica y generar un valor en el targetque continuaría ejecutándose.

Yichuan Wang
fuente
3
Pero en Python, todas las yieldllamadas deben estar en la misma función, que se llama "Generador". No se puede yielddesde una subfunción, razón por la cual las Python se llaman semi-corutinas , mientras que Lua tiene corutinas asimétricas . (Hay propuestas para propagar los rendimientos, pero creo que esas solo enturbian las aguas.)
cdunn2001
77
@ cdunn2001: (comentario de Winston) Python3.3 introdujo la expresión "rendimiento desde" que le permite rendir desde el subgenerador.
Linus Caldwell el