Les générateurs sont essentiellement semi-coroutines avec quelques limitations gênantes. Donc, évidemment, vous pouvez les implémenter en utilisant des semi-coroutines (et des coroutines complètes, bien sûr).
Si vous n'avez pas de coroutines, vous pouvez utiliser n'importe quelle autre structure de flux de contrôle universel. Il y a beaucoup de constructions de flux de contrôle qui sont «universelles» dans le sens où chaque construction de flux de contrôle (y compris toutes les autres constructions de flux de contrôle universel), y compris les coroutines et donc les générateurs peuvent être transformés trivialement en seulement cette construction universelle.
Le plus connu d'entre eux est probablement GOTO
. Avec juste GOTO
, vous pouvez construire toute autre construction de flux de contrôle: IF-THEN-ELSE
, WHILE
, FOR
, REPEAT-UNTIL
, FOREACH
, exceptions, fils, appels de sous-programme, les appels de méthode, les appels de fonction et ainsi de suite, et bien sûr aussi coroutines et générateurs.
Presque tous les processeurs prennent en charge GOTO
(bien que dans un processeur, ils l'appellent généralement jmp
). En fait, dans beaucoup de processeurs, est le seul construction de flux de contrôle, bien qu'aujourd'hui support natif pour au moins des appels de sous-programme (call
) et peut-être une forme primitive de gestion des exceptions et/ou primitive de concurrence (compare-and-swap) généralement également incorporé.
Une autre primitive d'écoulement de contrôle bien connue est les continuations. Les prolongations sont fondamentalement une variante plus structurée, mieux gérable et moins mauvaise de GOTO
, particulièrement populaire dans les langages fonctionnels. Mais il existe aussi des langages de bas niveau qui basent leurs flux de contrôle sur les continuations, par exemple la machine virtuelle Parrot utilise des suites pour le contrôle du flux et je crois qu'il y a même des CPU basés sur la continuation dans un laboratoire de recherche quelque part. C a une forme de continuations "merdiques" (setjmp
et longjmp
), beaucoup moins puissantes et moins faciles à utiliser que les "vraies" suites, mais elles sont assez puissantes pour implémenter des générateurs (et dans fait, peut être utilisé pour implémenter des continuations complètes). Sur une plate-forme Unix, setcontext
peut être utilisé comme une alternative plus puissante et de niveau supérieur à setjmp
/longjmp
.
Une autre construction de flux de contrôle bien connue, mais qui ne vient probablement pas à l'esprit en tant que construction de substrat de faible niveau autres constructions de flux de contrôle sont des exceptions. Il y a un article qui montre que les exceptions peuvent être plus puissantes que les continuations, faisant ainsi des exceptions essentiellement équivalentes à GOTO
et donc universellement puissantes. Et, en fait, les exceptions sont parfois utilisées comme constructions de flux de contrôle universel: le projet Microsoft Volta, qui a compilé .NET bytecode à JavaScript, a utilisé des exceptions JavaScript pour implémenter des threads et des générateurs .NET.
Pas assez universel, mais probablement puissant pour mettre en œuvre des générateurs est tout simplement l'optimisation des appels de queue. (Je peux me tromper, cependant, je n'ai malheureusement pas de preuve.) pense que vous pouvez transformer un générateur en un ensemble de fonctions réciproquement en queue. Je sais que les machines d'état peuvent être implémentées en utilisant des appels de queue, donc je suis assez sûr que les générateurs peuvent aussi, puisque, après tout, C# implémente des générateurs comme des machines d'état. (Enfin, je pense que cela fonctionne particulièrement bien avec l'évaluation paresseuse.)
Enfin et surtout, dans un langage avec une pile d'appels réifiée (comme la plupart des Smalltalks par exemple), vous pouvez construire à peu près n'importe quel type de flux de contrôle vous construit vouloir. (En fait, une pile d'appels réifiée est fondamentalement l'équivalent procédural de bas niveau équivalent à la continuation fonctionnelle de haut niveau.)
Alors, à quoi ressemble autres implémentations de générateurs?
Lua ne pas générateurs en soi, mais il a plein coroutines asymétriques. L'implémentation C principale utilise setjmp
/longjmp
pour les implémenter.
Ruby n'a pas non plus générateurs en soi, mais il a Enumerator
s, qui peuvent être utilisés en tant que générateurs. Enumerator
s ne font pas partie de la langue, ils sont une caractéristique de la bibliothèque. MRI implémente Enumerator
s en utilisant des continuations, qui à leur tour sont implémentées en utilisant setjmp
/longjmp
. YARV implémente Enumerator
s en utilisant Fiber
s (ce qui correspond à la façon dont Ruby orthographie les "coroutines"), et ceux sont implémentés en utilisant setjmp
/longjmp
. Je crois que JRuby implémente actuellement Enumerator
s en utilisant des threads, mais ils veulent passer à quelque chose de mieux dès que la JVM gagne de meilleures constructions de flux de contrôle.
Python a des générateurs qui sont en fait plus ou moins coroutines épanouies. CPython les implémente en utilisant setjmp
/longjmp
.
S'il y a un soutien pour les premiers continuations de classe dans votre langue, la mise en œuvre des générateurs au-dessus de ce genre de choses ne devrait pas être un problème. Sinon, vous devrez transformer votre code (et, honnêtement, je ne peux pas imaginer une langue dans laquelle vous ne pouvez pas le faire). –