Advantages and disadvantages of different iterator protocols

A commonly-cited argument against Python's approach, where the StopIteration exception indicates that an iterator is exhausted, is that raising and catching an exception is typically slower than returning a value and checking it with an if statement. However, this is not true in CPython, since the CPython interpreter handles StopIteration as a special case in order to make iteration fast. So this is more of an implementation concern than a design concern.

Nonetheless, this approach does have a specific pitfall, which is that it allows for non-local control flow effects. This usually only happens by accident, but it's hard to reason about so it can cause bugs which are difficult to diagnose. The issue occurs when StopIteration is thrown indirectly by something a __next__ method calls, rather than intentionally by the __next__ method itself. In this case, the StopIteration exception bubbles up and is caught by whatever consumes the iterator; the consumer then thinks the iterator is exhausted when it isn't necessarily. An example of this occurring "in the wild" is given in this Stack Overflow Q&A.

The protocol could be changed slightly to prevent this: each iterator could have its own sentinel exception, provided by the consumer, so that the consumer knows it can only be thrown by that specific iterator. However, it would make the protocol more complicated to implement, which doesn't seem worth it to address a pitfall that only occurs very rarely.

The other approaches, which use the return value of the next or hasNext method to signal termination, don't have this problem because unlike exceptions, return values cannot have non-local control flow effects that automatically bubble up the stack.

1. The first Python syntax has the advantage that custom list-like objects become iterable automatically without the user thinking about it.
2. Conversely, the first Python syntax has the disadvantage that it's a heruistic that sometimes isn't correct - if you are implementing a custom dictionary-like object then it will have a __getitem__ and a __len__, but synthesizing them won't produce a useful iterator.
3. Obviously, the Java syntax supports a remove method that no other language does, which could be said to be an advantage, as removing elements from the list while iterating it is a common pain point. It also makes it clear that that operation may not be supported if it doesn't make sense.
4. The Java syntax has the disadvantage that it requires the iterator to know whether there is a next element without producing it, which may not be possible for some iterators (think a Python generator - you never know whether it will yield another value or return before running the code). While you can of course work around this by calculating the next value in hasNext, that's counterintuitive and confusing.

The iteration protocols in the question all rely on mutable iterators: Each iteration has a single iterator object on which a .next method is called for each step; the iterator must mutate its state between .next calls to advance.

An example that also allows immutable iterators is the Julia iterator interface. This is realised by each iteration step providing a state in addition to a value:

• iterate(iterable) starts iteration by producing a new state
• iterate(iterable, state) resumes iteration from the previous state

By passing the state into each iteration step and receiving the next state, state may be newly created on each step and thus be immutable.

There are some advantages to this:

• This protocol is still compatible with mutable iteration as iterate is free to mutate and pass back the state it got or to mutate iterable.
• For immutable iterable and state, the tuple of (iterable, state) clearly defines a point in the iteration. This makes it simple and safe to split one iterator into two or more at any point, or to safe an earlier state to roll back to it.
• The end-of-iteration can be clearly marked by returning the sentinel value nothing instead of a tuple. This makes it impossible to accidentally proceed with iteration past the end, yet allows the sentinel to still be a valid value as (nothing, state).

The added complexity of lugging around both iterable and state can be easily hidden by syntactic sugar. For example, a for item in iter loop desugars very similar to other languages:

next = iterate(iter)
while next !== nothing
    (item, state) = next
    # body
    next = iterate(iter, state)
end

Of course, instead of an imperative while loop it could also be desugarred in a functional style using recursion to go along with promoting immutability.

The language*¹ which has the best possible iterators is, in my opinion, C#. I will explain why.

1. The collection to be iterated does not have to implement any particular interface. All standard collections implement IEnumerable, but that is not necessary: if the collection has a IEnumerator<T> GetEnumerator() function, it is eligible for participation in a foreach loop.

2. If the IEnumerator returned by GetEnumerator() is disposable, then at the end of the foreach loop the disposable will be disposed. Contrast this with Java, where the programmer has to be aware of, and explicitly dispose, any Iterator that happens to be Closeable.

3. The functions offered by IEnumerator are bool HasNext(), void MoveNext(), and T Current (a property.) Thus, if you want access to the IEnumerator you can refrain from using a foreach loop, and you can use a regular for loop instead, where the initialization clause of the for loop creates the enumerator, the condition clause invokes HasNext(), the step clause invokes MoveNext(), and the current value is at any moment available via the Current property, which you can invoke multiple times in the same iteration if you need to.

4. This makes it very easy to create decorators of IEnumerator. (wikipedia) Contrast this to Java, where the functions offered by Iterator cannot easily be used in a regular for loop, and decorators are really hard to write. A filtering iterator cannot be implemented without cumbersome look-ahead logic, and then it is impossible to use it for removing items from the collection because looking ahead means that you are always past the item you want to delete.

*¹ I only consider strongly typed languages. Weakly typed languages like Javascript, Python, etc. receive nothing but scorn from me.

Multiple return

If a language supports returning multiple values in functions or methods, a somewhat better protocol is the generator to return (live: bool, ref data: T?), where live indicates that the enumerator reader should examine the data or keep running, and data is an Optional<T> that indicates if any data is produced in this iteration.

This protocol would cover both direct and async usage, and would further permit filter dropping or accumulating usage in direct code.

Ref return

The ref data instead of simple data is designed to reduce allocation of temporaries drastically in enumerations. To zero, in special.

Other protocols may cause unnecessary allocations by preserving the next data in a backing field, after running/returning of hasMext, and would otherwise impossibilite the creation of generators of "stack only" data types.

The language may offer composite, possible allocating IteratorResult<T> that conforms to Java/C# protocol, that buffers the results outside the generator, instead of forcing the existence of storage by design.

Normal syntax

With or without multiple returns, I also argue that a big step in easing the creation and usage of generators and iterations is to make their syntax simple, instead of special.

A generator is basically an async function that returns multiple times. The same with iterators.

A simple syntax for this wuuld be, for example, and taking note from languages that names the Optional<T> cases with None and Some<T>, to mark generator and/or iterator functions with returning Many<T>

public async Many<T> Filter( Predicate pred )
{ }