How can you implement a compiler that recognizes iterators?

Question

I have been using iterators for a while, and I love them.

But although I was thinking about it, I could not understand, "as a compiler that recognizes iterators." I also researched about this, but could not find any resource explaining the situation in the context of compiler design.

To clarify, most articles about Iterators imply that there is some kind of “magic” that implements the desired behavior. They suggest that the compiler support the state machine to keep track of where the execution is being performed (where the last "return profitability" is visible). I am particularly interested in this property of Iterators, which allows lazy evaluation.

By the way, I know what state-owned machines are, have already taken a compiler design course, and studied the Dragon book. But, apparently, I can not connect what I learned with the "magic" csc.

Any knowledge or differential thoughts are appreciated.

Answer 1

This is easier than it sounds. The compiler can decompose the iterator function into separate pieces; fragments are divided by yield .

The final computer just has to keep track of which piece we are currently in, and the next time the iterator is called, it jumps directly to that piece. We also need to track all local variables (of course).

Then we need to consider several special cases, in particular, loops containing yield s. Fortunately, IL (but not C # itself) allows goto to jump into loops and resume them.

Note that there are some very complex cases of cross, for example. C # does not allow yield in finally blocks, because it would be very difficult (impossible?) To leave the function after yield , and then resume the function, perform a cleanup, throw any exception again and save the stack trace.

Eric Lipper has published a detailed description of the process. (read the articles he related to, too!)

Answer 2

One thing I would try is to write a short example in C #, compile it, and then use a Reflector on it. I think that this “return profitability” is just syntactic sugar, so you should be able to see how the compiler processes it at the output of the disassembler.

But, well, I really don't know much about these things, so maybe I'm completely wrong.