Генераторы в основном полу-сопрограммы с некоторыми раздражающими ограничениями. Таким образом, очевидно, что вы можете реализовать их, используя полу-сопрограммы (и полные сопрограммы, конечно).
Если у вас нет сопрограмм, вы можете использовать любые другие универсальные конструкции потока управления. Существует множество конструкций потока управления, которые являются «универсальными» в том смысле, что каждая конструкция потока управления (включая все другие универсальные конструкции потока управления), включая сопрограммы и, следовательно, генераторы, может быть (более или менее) тривиально превращается только в эту универсальную конструкцию.
Наиболее известным из них, вероятно, является GOTO. С помощью GOTO вы можете создать любую другую конструкцию потока управления: IF-THEN-ELSE, WHILE, FOR, REPEAT-UNTIL, FOREACH, исключения, потоки, вызовы подпрограмм, вызовы методов , вызовы функций и так далее, а также сопрограммы и генераторы.
Почти все процессоры поддерживают GOTO (хотя в процессорах они обычно называют его jmp). Фактически, во многих процессорах GOTO - это конструкция потока управления only , хотя сегодня собственная поддержка по крайней мере вызовов подпрограмм (call) и, возможно, некоторая примитивная форма обработки исключений и / или примитив параллелизма (Сравнение и замена) обычно также встроены.
Другим известным примитивом потока управления являются продолжения. Продолжения - это в основном более структурированный, более управляемый и менее злой вариант GOTO, особенно популярный в функциональных языках. Но есть также некоторые низкоуровневые языки, которые основывают свой поток управления на продолжениях, например, виртуальная машина Parrot использует продолжения для потока управления, и я полагаю, что в какой-то исследовательской лаборатории даже есть некоторые ЦП на основе продолжений.
C имеет своего рода «дрянную» форму продолжений (setjmp и longjmp), которые гораздо менее мощны и менее просты в использовании, чем «настоящие» продолжения, но они достаточно мощны для реализации генераторов (и фактически может использоваться для реализации полных продолжений).
На платформе Unix setcontext может использоваться как более мощная и более высокоуровневая альтернатива setjmp / longjmp.
Другая конструкция потока управления, которая хорошо известна, но, вероятно, не приходит на ум в качестве низкоуровневой сборки субстрата. другие конструкции потока сверху являются исключениями. Есть статья, в которой показано, что исключения могут быть более мощными, чем продолжения, что делает исключения по существу эквивалентными GOTO и, следовательно, универсально мощными. И, действительно, исключения иногда используются в качестве универсальных конструкций потока управления: проект Microsoft Volta, который скомпилировал байт-код .NET в JavaScript, использовал исключения JavaScript для реализации потоков и генераторов .NET.
Не универсальный, но, вероятно, достаточно мощный для реализации генераторов - это просто оптимизация хвостового вызова. (Хотя я могу ошибаться. У меня, к сожалению, нет доказательств.) Я думаю, вы можете преобразовать генератор в набор взаимно рекурсивных функций. Я знаю, что конечные автоматы могут быть реализованы с использованием хвостовых вызовов, поэтому я вполне уверен, что генераторы тоже могут, поскольку, в конце концов, C # реализует генераторы как конечные автоматы. (Я думаю, что это работает особенно хорошо вместе с ленивой оценкой.)
И последнее, но не менее важное: в языке с расширенным стеком вызовов (как, например, большинство Smalltalks) вы можете создавать практически любые конструкции потоков управления, какие пожелаете. (Фактически, усовершенствованный стек вызовов в основном является процедурным низкоуровневым эквивалентом функционального продолжения высокого уровня.)
Итак, как же делают другие реализации генераторов?
У Lua нет генераторов как таковых, но у него полно асимметричных сопрограмм. Основная реализация C использует setjmp / longjmp для их реализации.
В Ruby также нет генераторов как таковых, но есть Enumerator с, которые можно использовать в качестве генераторов. Enumerator s не являются частью языка, они являются функцией библиотеки. MRI реализует Enumerator с использованием продолжений, которые, в свою очередь, реализуются с использованием setjmp / longjmp. YARV реализует Enumerator s, используя Fiber s (именно так Ruby произносит "сопрограммы"), а эти реализуются с использованием setjmp / longjmp. Я полагаю, что в настоящее время JRuby реализует Enumerator с использованием потоков, но они хотят переключиться на что-то лучшее, как только JVM получит более совершенные конструкции потока управления.
В Python есть генераторы, которые на самом деле являются более или менее полноценными сопрограммами. CPython реализует их, используя setjmp / longjmp.