Flexible Iterators

2013/01/31 · by · in Comp*, Ideas, Language

Java has some odd quirks which make it far more inflexible than it needs to be. For example, many programs have data structures which need to be iterated both forwards and backwards, and some algorithms require treating the first or last element differently than the others. My goal here is to find a tweak to the Java language that would permit use of the foreach loop in all of these cases. To achieve that, it would be nice if the data structure in question could return different iterators appropriate to the task at hand.

Let’s first review the laborious, multi-step process of gifting a class to support the foreach syntactic sugar.

  1. Declare the class with so that it implements Iterable<Data>.
  2. Define a method Iterator<Data> iterator().
  3. Implement an appropriate class DataIterator extends Iterator<Data>
  4. Define methods supported by all Iterators: next(), hasNext(), and remove().

The foreach loop, which looks like:

for(Data d : collection) {
  // do something with d
}

desugars into

Iterator it = collection.iterator();
while (it.hasNext()) {
  Data d = it.next();
  // do something with d
}

Knowing this implementation, I can achieve my stated desire in one of two ways 1. a syntax change or 2. a language change. I shall first present the syntax change because it’s such a horrible idea.

Syntax Modification

We first observe that the foreach loop desugars into a call to iterator() passing no arguments. This constraint forces each class into a box where it can only implement one kind of iteration. Immediately, my object oriented (damaged) brain thought to alleviate this constraint by overloading of the iterator() method with versions accepting different arguments. For example, a DataIterator which allowed slicing might be called with three arguments: start, end, and stride. The foreach loop syntax can be extended to perform this lookup, by a small tweak to the desugaring:

for(Data d : collection)(start, end, stride) {
  // do something with d
}

The syntactic change can even be made backwards compatible with the use of varargs.

Semantic Modification

Change the semantics of the foreach desugarer so that it can handle both Iteratables and Iterators.
This is by far the easiest change, because I find it comparatively easy to gift my class with many well-named methods which each return an Iterator.
The same example reads much better now:

for (Data d : collection.slice(start, end, stride)) {
  // do something with d
}

Instead of slice I could also implement reverse or any other kind of iteration.

I wondered why the Java implementors did not already put in the ability to handle both Iteratables and Iterators.
An answer on StackOverflow, of course, held the standard objection:

The reason for-each loops require an iterable is to allow the same object to be traversed multiple times (so that you can use multiple for-each loops over the same object without surprising behaviour), whereas an iterator only allows one traversal. If for-each allowed iterators to be used, the behaviour would be surprising to programmers who didn’t realise that their iterators would be exhausted after the loop is run.

Closing Remarks

My postdoc Per pointed out that Python programmers obviously have an easier time. Because Python has dynamic lookup mechanisms that allow the for-in loop to accept any iterator, it supports much more composition, allowing filters, generators, and iterators.

Tags: , , ,