Coroutine vs Continuation vs Generator

147

Quelle est la différence entre une coroutine et une suite et un générateur?

Mehdi Asgari
la source
2
Je me demande si les coroutines et les suites sont effectivement équivalentes. Je sais qu'il est possible de modéliser des coroutines avec des continuations, mais est-il possible de modéliser des suites avec des coroutines ou non parce que les suites sont strictement plus puissantes?
nalply le

Réponses:

127

Je vais commencer par les générateurs, car c'est le cas le plus simple. Comme @zvolkov l'a mentionné, ce sont des fonctions / objets qui peuvent être appelés à plusieurs reprises sans retour, mais lorsqu'ils sont appelés, ils renverront (produiront) une valeur et suspendront leur exécution. Lorsqu'ils sont appelés à nouveau, ils redémarreront à partir de l'endroit où ils ont suspendu l'exécution pour la dernière fois et recommenceront.

Un générateur est essentiellement une coroutine coupée (asymétrique). La différence entre une coroutine et un générateur est qu'une coroutine peut accepter des arguments après avoir été initialement appelée, alors qu'un générateur ne le peut pas.

C'est un peu difficile de trouver un exemple trivial où vous utiliseriez des coroutines, mais voici mon meilleur essai. Prenez ce code Python (inventé) comme exemple.

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

Les lexers et les analyseurs sont un exemple d'utilisation des coroutines. Sans coroutines dans le langage ou émulés d'une manière ou d'une autre, le lexing et le code d'analyse doivent être mélangés même s'il s'agit vraiment de deux préoccupations distinctes. Mais en utilisant une coroutine, vous pouvez séparer le code de lexing et d'analyse.

(Je vais passer en revue la différence entre les coroutines symétriques et asymétriques. Qu'il suffise de dire qu'elles sont équivalentes, vous pouvez convertir de l'une à l'autre, et les coroutines asymétriques - qui ressemblent le plus à des générateurs - sont les plus facile à comprendre. J'expliquais comment on pourrait implémenter des coroutines asymétriques en Python.)

Les suites sont en fait des bêtes assez simples. Tout ce qu'elles sont, ce sont des fonctions représentant un autre point du programme qui, si vous l'appelez, provoquera le basculement automatique de l'exécution vers le point représenté par la fonction. Vous en utilisez quotidiennement des versions très restreintes sans même vous en rendre compte. Les exceptions, par exemple, peuvent être considérées comme une sorte de continuation à l'envers. Je vais vous donner un exemple de pseudocode basé sur Python d'une suite.

Disons que Python avait une fonction appelée callcc(), et cette fonction a pris deux arguments, le premier étant une fonction et le second étant une liste d'arguments avec lesquels l'appeler. La seule restriction sur cette fonction serait que le dernier argument qu'elle prend sera une fonction (qui sera notre continuation actuelle).

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

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

Ce qui se passerait, c'est que cela callcc()appellerait à son tour foo()avec la continuation courante ( cc), c'est-à-dire une référence au point du programme auquel a callcc()été appelé. Lorsque vous foo()appelez la continuation actuelle, c'est essentiellement la même chose que de dire callcc()de retourner avec la valeur avec laquelle vous appelez la continuation actuelle, et quand il fait cela, il ramène la pile à l'endroit où la continuation actuelle a été créée, c'est-à-dire lorsque vous avez appelé callcc().

Le résultat de tout cela serait que notre variante hypothétique de Python s'imprimerait '42'.

J'espère que cela aide, et je suis sûr que mon explication peut être améliorée un peu!

Keith Gaughan
la source
6
Un nit: délimité continuations sont des fonctions, mais non délimitées continuations ne sont pas: okmij.org/ftp/continuations/undelimited.html#delim-vs-undelim
Frank Shearar
2
C'est un bon point. Cela dit, dans la plupart des applications pratiques, lorsque les gens disent «continuation», ils parlent de continuations partielles / délimitées. Apporter les divers autres types de continuations aurait quelque peu brouillé l'explication.
Keith Gaughan
1
Les suites ne sont pas des fonctions, bien qu'elles puissent être réifiées en fonctions. "Cela dit, dans la plupart des applications pratiques, quand les gens disent" continuation ", ils parlent de continuations partielles / délimitées." Souhaitez-vous signaler un tel usage du terme «continuation»? Je n'ai jamais rencontré un tel usage. Vous avez également donné un exemple pour une continuation non limitée, en utilisant call / cc. Les opérateurs pour les suites délimitées sont généralement "reset" et "shift" (ils peuvent avoir d'autres noms).
Ivancho
3
Commençons par le fait que cela fait cinq ans que j'ai écrit ceci. Vous êtes un peu en retard à la fête. Deuxièmement, je sais que les continuations non limitées ne sont pas des fonctions, mais vous essayez d'expliquer comment elles fonctionnent sans y faire référence en tant que telles tout en gardant le langage simple. Du point de vue du programmeur moyen, le fait qu'une continuation non limitée ne retourne pas en fait simplement une fonction à un coup, ce qui n'est pas correct selon la définition de ce qu'est une fonction, mais c'est au moins compréhensible .
Keith Gaughan
2
Je ne suis pas en retard pour la fête puisque c'est le premier résultat que j'obtiens sur google lorsque je recherche "coroutine vs générateur". J'espérais trouver de bonnes informations sur leurs différences. Bref je l'ai trouvé ailleurs. Et je ne suis pas le premier à signaler que votre explication sur les continuations est erronée. Le problème est que quelqu'un se trompera et sera peut-être confus plus tard quand il ou elle rencontrera le même mot utilisé pour quelque chose de différent.
Ivancho
33

Coroutine est l'une des nombreuses procédures qui font leur travail à tour de rôle, puis s'arrêtent pour donner le contrôle aux autres coroutines du groupe.

La continuation est un "pointeur vers une fonction" que vous passez à une procédure, à exécuter ("suite avec") lorsque cette procédure est terminée.

Generator (en .NET) est une construction de langage qui peut cracher une valeur, «mettre en pause» l'exécution de la méthode, puis procéder à partir du même point lorsqu'on lui demande la valeur suivante.

zvolkov
la source
Je me rends compte que la réponse n'est peut-être pas exacte, mais à ce niveau de question, j'ai essayé de la garder simple. D'ailleurs, je ne comprends pas vraiment tout cela moi-même :)
zvolkov
Un générateur en python est similaire à la version C #, mais il est implémenté comme une syntaxe spéciale pour créer une instance d'un objet itérateur, qui renvoie les valeurs renvoyées par la définition de «fonction» que vous fournissez.
Benson
2
Une petite correction: "... y compris la pile d'appels et toutes les variables MAIS PAS LEURS VALEURS" (ou simplement supprimer "toutes les variables"). Les suites ne conservent pas les valeurs, elles contiennent simplement la pile d'appels.
nalply le
Non, les suites ne sont pas des "pointeurs vers une fonction". Dans l'implémentation la plus naïve, il contient un pointeur sur la fonction et un environnement contient les variables locales. Et il ne revient jamais à moins que vous n'utilisiez quelque chose comme call / cc pour le capturer avec une valeur de retour.
NalaGinrut
9

Dans la nouvelle version de Python, vous pouvez envoyer des valeurs aux générateurs avec generator.send(), ce qui fait des générateurs python des coroutines efficaces.

La principale différence entre python Generator et un autre générateur, disons greenlet, est qu'en python, vous yield valuene pouvez revenir qu'à l'appelant. Dans le greenlet, target.switch(value)peut vous amener à une coroutine cible spécifique et générer une valeur où le targetcontinuerait à s'exécuter.

Yichuan Wang
la source
3
Mais en Python, tous les yieldappels doivent être dans la même fonction, qui s'appelle le "Générateur". Vous ne pouvez pas yieldpartir d'une sous-fonction, c'est pourquoi les Python sont appelés semi-coroutines , tandis que Lua a des coroutines asymétriques . (Il y a des propositions pour propager les rendements, mais je pense que celles-ci ne font que brouiller les eaux.)
cdunn2001
7
@ cdunn2001: (commentaire de Winston) Python3.3 a introduit l'expression "yield from" qui vous permet de générer du sous-générateur.
Linus Caldwell