Interruptible Iterators

Just completed reading Interruptible Iterators by Jed Liu, Aaron Kimball and Andrew C. Myers in POPL 2006.

Iterator is one of the design patterns which has enjoyed the maximum patronage of most language developers and implementors. Though it has been debated that the design of iterator objects in C++ and Java have been impaired by the lack of suitable control structures, we find abundance of iterator usage in both of them. But as the above paper by Liu et. al. aptly states, in the absence of higher order functions in these programming languages,

programmers commonly use iterators as clients, but usually avoid defining their own iteration abstractions, leading to interfaces that are less clean and simple than they could be.

Alternatively, functional languages like CLU, SML, Scheme, Sather and some of the modern day multiparadigm languages like C# 2.0 and Scala provide iterators through higher order functions, closures and generators as do Ruby and Python. All of them support convenient implementation of iterators with a structured coroutine mechanism in which iterator code can yield iterated values back to the loop, leading to a much cleaner syntax.

The paper in discussion, describes interruptible iterators, which handles element removal requests through an exception like semantics called interrupts. It says :

Like exceptions, interrupts are a nonlocal control mechanism; unlike exceptions, a handled interrupt results in resumption, and interrupts propagate logically downwards in the call stack rather than upward.

Interruptible Iterators differ from standard coroutine based iterators in the sense that the latter do not support imperative updates such as element removal during iteration. But interruptible iterators take an interrupt from the client code for element removal operations, performs the request and return control to the place where the interrupt was raised, typically within a loop body. The paper has lots of other details and speaks about its implementation in the JMatch language.

Oh! BTW, C++ iterators are also due for a facelift. The current C++ iterator categories bind together two orthogonal concepts: traversal and element access. Hence the Boost team has submitted a proposal for new style iterators.