?

Log in

No account? Create an account

fanf

Inverting iterators

« previous entry | next entry »
10th Nov 2006 | 23:23

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.

| Leave a comment | Share

Comments {9}

Nicolai The Hand Grenade of Courteous Debate

from: _nicolai_
date: 11th Nov 2006 00:23 (UTC)

You Perlish functionalist, you!

Reply | Thread

Inverting iterators

from: anonymous
date: 12th Nov 2006 21:17 (UTC)

another obvious problem is where to preserve local variables inside the loop.

Reply | Thread

from: anonymous
date: 23rd Nov 2006 18:16 (UTC)

Why not use Smalltalk/Ruby like syntax?
arglist do: [:varlist | statements]

Reply | Thread

from: anonymous
date: 23rd Nov 2006 19:59 (UTC)

This is basically Haskell's map function.

Reply | Thread

from: fusiongyro
date: 24th Nov 2006 00:18 (UTC)

In OCaml, there's List.iter and also List.map. The map accumulates the result from each application, but iter doesn't. I think iter is closer to what's being described here, because it depends on side effects or other state being preserved within the closure that's being passed to the "inverted iterator."

Reply | Parent | Thread

Tony Finch

from: fanf
date: 24th Nov 2006 00:30 (UTC)

Right. Also, I'm partly wondering about the utility of building something like zipWith into the language...

Reply | Parent | Thread

from: fusiongyro
date: 24th Nov 2006 02:52 (UTC)

I've used it. It's pretty handy... in OCaml, it's called map2, I think.

I never have a problem with people including more stuff in the standard library, given that it will ever be used again and is named usefully. The naming thing tends to be the problem with Haskell, IMO.

Reply | Parent | Thread

I think you mean iterate

from: anonymous
date: 24th Nov 2006 01:12 (UTC)

I think you mean iterate:
http://www.haskell.org/ghc/docs/latest/html/libraries/base/Data-List.html#v%3Aiterate

The problem is though, does 'statements' perform any updates? Certainly not in a pure FP language like Haskell, but the example could be modified to resemble the correction :)

Reply | Parent | Thread

let the compiler do that...

from: jp107
date: 29th Nov 2006 19:37 (UTC)

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...

Reply | Thread