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

Question

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

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

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

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

Любые знания или различные мысли приветствуются.

Answer 1

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

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

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

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

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

Answer 2

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

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