About me

Mozillian. Open Source enthusiast. Loves Programming Languages.

Content

Stop. Iteration time!

You have probably already heard of generators and iterators coming to a browser near you. They have been available in Firefox for a long time and are used extensively all over the Mozilla code base. The V8 team will implement iterators and generators once ES6 has been finalized.

This post describes the current implementation in SpiderMonkey and tries to include the current state of the ES6 draft and discussions.

A simple generator

Let us take a look at a simple example of a generator function that represents an infinite sequence containing all the numbers from 0 to Number.MAX_VALUE. Once it reaches MAX_VALUE it will not increase any further but always return the same number.

function myInfiniteGenerator() {
  var i = 0;
  while (true) {
    yield i++;
  }
}

var iter = myInfiniteGenerator();

while (true) {
  console.log(iter.next());
}

Any object of the following shape is an iterator:

{ next: function() -> any }

The next() method simply returns the item next in the sequence.

Finite sequences

As you surely noticed the generator of the first example produces iterators that will never run out of items. The next example shows an iterator representing a finite sequence:

function MyFiniteIterator(max) {
  this.cur = 0;
  this.max = max;
}

MyFiniteIterator.prototype.next = function () {
  if (this.cur < this.max) {
    return this.cur++;
  }

  throw StopIteration;
};

The given code implements a custom iterator without writing a generator function. Note that it throws StopIteration as soon as it reaches the maximum value to signal that the sequence is exhausted. It is a lot more elegant to implement the same sequence using a generator function:

function myFiniteGenerator(max) {
  var i = 0;
  while (i < max) {
    yield i++;
  }
}

Generator functions will automatically throw StopIteration when terminating. So how should one consume iterators with finite sequences?

Consuming sequences

In Java for example, you would check iter.hasNext() and stop when it returns false. In JavaScript however you need to use a try…catch statement to catch StopIteration when it is being thrown.

var iter = myFiniteGenerator(10);

while (true) {
  try {
    console.log(iter.next());
  } catch (e if e === StopIteration) {
    break;
  }
}

You might wonder if there is a better way to do this and indeed there is. Using for…in or for…of you do not have to catch StopIteration yourself, the JavaScript engine will do it for you. As soon as the sequence is exhausted the loop will terminate normally without the exception being propagated:

var iter = myFiniteGenerator(10);

for (var i in iter) {
  console.log(i);
}

StopIteration is special

StopIteration actually is a standard variable that is bound to an object of class StopIteration. It is an ordinary object with no properties of its own and it is not a constructor function.

try {
  throw StopIteration;
} catch (e if e instanceof StopIteration) {
  // This works because:
  StopIteration instanceof StopIteration === true;
}

As StopIteration is a singleton of type StopIteration you can also catch it by checking for equality:

try {
  throw StopIteration;
} catch (e if e === StopIteration) {
  // ... handle exception
}

StopIteration is mutable

You should be aware that StopIteration is a mutable global. Just like undefined it can be modified to hold any other value. If you write a library and want to shield against modifications from outside you can use this neat little trick I found on Dave Herman’s blog:

(function(){try{(function(){true||(yield)})().next()}catch(e){return e}})()

The inner function is a generator that terminates immediately and therefore will throw a StopIteration. The outer function simply catches and returns it.

StopIteration may become a constructor

The current iterator strawman states that StopIteration will become a constructor to maintain compatibility with generator functions returning values.

Iter.prototype.next = function () {
  if (this.cur < this.max) {
    return this.cur++;
  }

  var stop = new StopIteration();
  stop.value = "sequence exhausted";
  throw stop;
};

The equality check from above would not work anymore so it might be better to just use instanceof.

StopIteration may not be part of ES6

The Python way of throwing to denote the end of a sequence is backwards compatible with old ECMAScript versions but there seem to be people not happy with the current proposal. While I can’t tell whether StopIteration is really to be removed a couple of alternative suggestions have been made:

Introduce a keyword to end a frame

To not misuse exceptions for normal control flow ES6 could introduce a stopiteration or endframe keyword that would end the current frame with an optional return value. The obvious downside is that it is probably not backwards compatible.

Iter.prototype.next = function () {
  if (this.cur < this.max) {
    return this.cur++;
  }

  stopiteration [reason];
  // or endframe [reason];
};

Add an iterator.hasNext() method

Just like Java the iterator API could consist of the two methods next() and hasNext(). The client would then need to check hasNext() every time before calling next().

Iter.prototype = {
  hasNext: function () {
    return this.cur < this.max;
  },

  next: function () {
    if (this.hasNext()) {
      return this.cur++;
    }

    throw new Error("sequence exhausted");
  }
};

Let next() always return an object

Custom iterators would be required to implement a single method but would not need to throw. Instead they would return an object with the property done set to true to indicate that the sequence has ended. The value property would be used to store values passed to yield or return in a generator function.

{
  next() -> { done: false , value: any }
          | { done: true[, value: any] }
}

Food for thought

This is in no way a complete list of possibilities or proposals that were brought up on es-discuss so please make up your own mind about the current iterators implementation and the suggested improvements.

The future is bright

Whether or not StopIteration will end up in ES6, generators and iterators are great and you should make sure to be prepared when they become available in modern browsers as well as on Node.js.

I concentrated particularly on StopIteration but there are lots of great posts out there that go way more into depth about generators and their usage. Make sure to also take a look at libraries like Task.js that combines generators with promises to cooperative tasks.

Feedback

Recent posts

Disclaimer

The opinions expressed here are my own and do not necessarily represent those of current or past employers.