Inverting iterators

[fanf]

Iterators are used in some programming languages to generalise the for loop. They were introduced by CLU in the 1970s and have been adopted by Python and Lua, amongst others. They are traditionally a special kind of function that has yield statements that return successive values in the iteration. This function is called at the start of the loop, and when it yields, the loop body is run. Each time round the loop the function is resumed until it yields again.

The iterator's activation frame is typically on top of the stack. This seems a bit backwards to me, because it leads to contortions to maintain the iterator's state between yields, e.g. using an auxiliary object or first-class closures. (See the first example here.)

I think it's simpler to desugar a for loop like this:

    for varlist in iterator(arglist) do
        statements
    loop

into

    iterator(
        (varlist): do
            statements
        end,
        arglist)

That is, you turn the loop body into an anonymous function which is passed to the iterator function. Instead of yielding, the iterator just calls the body function. The iterator can then be written as a normal loop without contortions to keep state between yields. (Pretty much like this, in fact.)

What makes this slightly interesting is how to desugar break, continue, and return statements inside the loop. A continue becomes just a return from the anonymous function, but the others have to escape from the iterator function as well as the anonymous function. This could be done with exceptions or continuation passing.

Comments

let the compiler do that...

[jp107.livejournal.com]

Part of the point of high-level languages is to make code more obvious (to the writers and readers), so if there is an obvious transformation of the iterator code into something which is more efficient to run but harder to follow then the compiler should spot that and do it automatically...

According to http://www.lcs.mit.edu/publications/pubs/pdf/MIT-LCS-TR-561.pdf
(page 16) the CLU implementation of iterators was done by essentially using coroutines:

    Iterators are related to coroutines; the iterator and the body of the
    for loop pass control back and forth.
    However, their use is limited so that CLU programs can make do
    with a single stack. They are inexpensive: a yield effectively
    calls the loop body, which returns to the iterator when it is
    finished. (Calls are very cheap in CLU.) Imposing the limitations
    on iterators was done to get the efficient, single stack
    implementation, albeit at the expense of some expressive power.
    For example, iterators cannot be used to compute whether two lists
    have the same elements, since to do this you need to iterate through
    the two lists side-by-side, and CLU only allows iterators to be
    nested.

Anyway what do you have against closures?

I'm now trying to remember if I actually own a copy of the CLU book or not...