Реализация поддержки "Генератор" на пользовательском языке

Question

У меня есть немного фетиша для языкового дизайна, и в настоящее время я играю с моим собственным языком хобби. ( http://rogeralsing.com/2010/04/14/playing-with-plastic/)

Одна вещь, которая действительно заставляет меня кровоточить, это "генераторы" и ключевое слово "yield". Я знаю, что C# использует преобразование AST для преобразования методов перечислителя в машины состояний.

Но как это работает на других языках? Есть ли способ получить поддержку генератора в языке без преобразования AST? Например, используют ли такие языки, как Python или Ruby, преобразования AST, чтобы решить эту проблему?

(Вопрос в том, как генераторы реализованы под капотом на разных языках, а не в том, как написать генератор на одном из них)

Answer 1

Генераторы - это в основном полу-сопрограммы с некоторыми раздражающими ограничениями. Таким образом, очевидно, что вы можете реализовать их, используя полу-сопрограммы (и полные сопрограммы, конечно).

Если у вас нет сопрограмм, вы можете использовать любые другие универсальные конструкции потока управления. Существует множество конструкций потока управления, которые являются "универсальными" в том смысле, что каждая конструкция потока управления (включая все другие конструкции универсального потока управления), включая сопрограммы и, таким образом, генераторы, может (более или менее) быть тривиально преобразована в только эту универсальную построить.

Наиболее известным из них является, вероятно, GOTO, С просто GOTO Вы можете построить любую другую конструкцию потока управления: IF-THEN-ELSE, WHILE, FOR, REPEAT-UNTIL, FOREACH исключения, потоки, вызовы подпрограмм, вызовы методов, вызовы функций и т. д., и, конечно, сопрограммы и генераторы.

Почти все процессоры поддерживают GOTO (хотя в CPU они обычно называют это jmp). На самом деле, во многих процессорах, GOTO является единственной конструкцией потока управления, хотя сегодня собственная поддержка по крайней мере вызовов подпрограмм (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 Они не являются частью языка, они являются функцией библиотеки. МРТ реализует Enumerator с использованием продолжений, которые, в свою очередь, реализуются с использованием setjmp / longjmp, YARV реализует Enumerator с помощью Fiber s (то, как Ruby произносит "сопрограммы"), и те, которые реализуются с помощью setjmp / longjmp, Я считаю, что JRuby в настоящее время реализует Enumerator с использованием потоков, но они хотят переключиться на что-то лучшее, как только JVM получит более совершенные конструкции потока управления.

У Python есть генераторы, которые на самом деле являются более или менее полноценными сопрограммами. CPython реализует их, используя setjmp / longjmp,