как можно реализовать компилятор, который распознает итераторы?

Я использую итераторы некоторое время, и я люблю их.

Но хотя я много думал об этом, я не мог понять, «как реализовать компилятор, который распознает итераторы». Я также исследовал это, но не смог найти ни одного ресурса, объясняющего ситуацию в контексте разработки компилятора.

Чтобы уточнить, большинство статей об итераторах подразумевают, что существует какая-то «магия», реализующая желаемое поведение. Они предполагают, что компилятор поддерживает конечный автомат, чтобы отслеживать, где находится выполнение (где виден последний «возврат урожая»). Меня особенно интересует это свойство итераторов, которое позволяет выполнять ленивые вычисления.

Кстати, я знаю, что такое конечные автоматы, уже прошел курс проектирования компиляторов, изучал Dragon Book. Но, по-видимому, я не могу связать то, что я изучил, с «магией» csc.

Любые знания или дифференцированные мысли приветствуются.


person tafa    schedule 13.07.2009    source источник
comment
Вы можете объяснить это немного больше? Например, с примером исходного кода, который, по вашему мнению, будет очень сложно распознать компилятору?   -  person Thilo    schedule 13.07.2009
comment
а также на каком языке вы говорите - что, например, делает yield?   -  person    schedule 13.07.2009
comment
C# имеет синтаксис возврата yield.   -  person Vilx-    schedule 13.07.2009
comment
Извините, мой справочный язык - c#.   -  person tafa    schedule 13.07.2009


Ответы (2)


Это проще, чем кажется. Компилятор может разложить функцию итератора на отдельные фрагменты; куски разделены операторами yield.

Конечный автомат просто должен отслеживать, в каком фрагменте мы сейчас находимся, и при следующем вызове итератора переходит прямо к этому фрагменту. Нам также нужно отслеживать все локальные переменные (конечно).

Затем нам нужно рассмотреть несколько особых случаев, в частности циклы, содержащие yields. К счастью, IL (но не сам C#) позволяет goto переходить в циклы и возобновлять их.

Обратите внимание, что есть некоторые очень сложные крайние случаи, например. C# не допускает yield в блоках finally, потому что было бы очень сложно (невозможно?) выйти из функции после yield, а затем возобновить функцию, выполнить очистку, повторно создать любое исключение и сохранить трассировку стека.

Эрик Липперт опубликовал подробное описание процесса. (Прочитайте также статьи, на которые он ссылается!)

person Konrad Rudolph    schedule 13.07.2009

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

Но, ну, я не особо разбираюсь в этих вещах, так что, возможно, я совершенно не прав.

person Vilx-    schedule 13.07.2009