At OpenVis Conf 2017, Mike Bostock introduced d3.express, an integrated discovery environment with a goal of making coding (and not just coding visualizations) more transparent and interactive.

One feature he uses in this system, namely generator functions, stood out to me as something I wanted to know more about. Mike introduced them in the context of constructing dynamic variables within the data/execution graph that drives a program in d3.express. Generators are used for a number of things in d3.express so I was curious to learn more about them. So, what are they?

function*

Generator functions are a feature of JavaScript that became part of the standard in ES6/ES2015. While we typically expect a function to run its course to the end once we have invoked it, generator functions allow us to transfer control flow from one portion of our program to another and then come back later.

We can effectively pause execution of a function and yield control to another part of the code and later resume execution of that function from the point that we left off as if nothing had happened. Lets look at an example to get some of the terminology down.

// This is our generator function. the * after the function keyword
// is what makes it a generator
function* gen() {
  // Yield will cause the function to pause after this statement,
  // it will also pass the value 1 out.
  yield 1;

  // When we next resume this function we will define a constant and 
  // yield that value
  const num = 2;
  yield num;

  // Generators can still return things.
  return 1 + 2 + num
}

// When we call our generator function, we get a "generator object" 
// or "iterator". Here we assign this to the variable g.
const g = gen();

// Start the functions actual execution
g.next()  // {value: 1, done: false}

// Control is returned here, we can do something else or just call
// next() to resume the function.
g.next()  // {value: 2, done: false}

// Resume the function and get the final value
g.next()  // {value: 5, done: true} | the return value of the function

Hopefully that gives you a quick sense of how control flow moves from the generator function to the calling context and back. Note that in addition to passing control, we can also pass values along to a calling context.

Let's look at a few examples of what we can do with this approach to control flow.

Introspection

With the ability to pause function execution as well as send values to another part of the program, we can capture the intermediate states of an algorithm's progression and visualize it. Let's use sorting as an example. Here is an implementation of insertion sort as a generator function.

// Adapted from https://en.wikipedia.org/wiki/Insertion_sort#Algorithm_for_insertion_sort
function* insertionSort(arr, comparator) {
  for (let i = 1; i < arr.length; i++) {
    let j = i;
    while (j > 0 && arr[j-1] > arr[j]) {
      let temp = arr[j];
      arr[j] = arr[j-1];
      arr[j-1] = temp;
      j = j - 1;
      yield arr; // This is the main addition
    }
  }
  return arr;
}

Note that in the inner while loop, after every swap, we will yield the current state of the array. This allows the calling code to access that intermediate state and we can generate the following visualization of the progression of an insertion sort.

For this particular algorithm it is nice that we can add a very small amount to code to the regular function in order to extract this information.

See the full code here. Also see Mike Bostock's Visualizing Algorithms if you are interested in seeing where this path leads.

History

If we were to capture all the intermediate state received in the example above, we can add a control to our visualization to enable a scrub-able history of the progress of the algorithm. Try it out below, run the sort, wait for it to finish and then drag the slider, it will allow you to rewind to any intermediate state of the algorithms progress.

Also keep in mind that we don't have to yield just one value, here we yielded the state of the whole array, but we could also pass information about the last swap that occurred and include that in the visualization.

See the full code here. Also, if this has caught your eye, and you haven't already read Bret Victor's Up and Down the Ladder of Abstraction, I highly recommend it. It gives a much fuller vision of what these concepts could mean in the context of our computing environments.

Builds/Steppers

Another use case that comes to mind is that of building steppers (or scrollers, or really any sequenced progression). In a stepper we want to allow fine grained progression through a sequence, often building up an image or revealing more information and usually in the control of the reader. There are lots of ways to achieve this, but if your sequence fits nicely into a function, then a generator may be helpful. Take a look at this toy example I made from a geoJSON file of Boston neighborhoods.

function* drawMap(collection) {
  const projection = d3.geoAlbers()
    .fitSize([width, height], collection);
  const pathGen = d3.geoPath()
    .projection(projection);
  const neighborhoods = _.sortBy(collection.features, d => d.properties.Acres);

  for (let neighborhood of neighborhoods) {
    let path = g.append("path")
      .datum(neighborhood)
      .attr('id', d => toId(d.properties.Name))
      .attr('fill', 'none')
      .attr('stroke', 'black')
      .attr('stroke-width', 1)
      .attr('d', pathGen);

    yield neighborhood; // This is the addition!

    path
      .transition()
      .attr('fill', '#D3D3D3');
  }

  // When we are all done, color them green.
  g.selectAll('path')
    .transition()
    .duration(500)
      .attr('fill', '#83C670');
}

Note that in our for loop to draw all the neighborhoods, we simply yield control (as well as some information) to something else. In this case we have another piece of code that does the following:

function showCaption(item, counter) {
  if (item === undefined) {
    // Once all the items are done show a summary caption
    d3.select('#caption')
      .text(`Here are Boston's ${counter} neighborhoods`);
  } else {
    const name = item.properties.Name;
    const size = item.properties.SqMiles;

    g.selectAll(`path#${toId(name)}`)
      .transition()
      .attr('fill', 'tomato');
    d3.select('#caption')
      .text(`"${name}" is a Boston neighborhood that is ${size} sq miles large.`);
  }
}

The showCaption function will turn the fill color of the neighborhood that was just drawn red, as well as change the caption below the visualization. Once we are done, the original loop in drawMap can continue the process of drawing (including turning the fill color to grey). Here is the code that controls that back and forth between drawing the map and showing the caption.

function run(data) {
  let counter = 0;
  const drawer = drawMap(data);
  d3.select('#next-button')
    .on('click', () => {
      const current = drawer.next();
      showCaption(current.value, counter);
      if (current.done) {
        d3.select('#next-button').attr('disabled', true);
      } else {
        counter += 1;
      }
    })
}

On each click of the button, the code above allows the drawing function to resume and draw its next thing, after which control is delegated to the behavior that we want to perform after each thing is drawn. We have full control of when and under which conditions we would want to resume drawing.

Note that this concept can extend to any sequence or incremental build that you would like. It also reduces the amount of code needed to 'slow-down' a sequence or build it up incrementally.

See the full code for this example here.

Conclusion

Certainly there are ways to achieve these tasks without generator functions, and I think one would want to be quite careful when considering using a control flow option like this one, for the same reasons one should be careful about GOTOs. However they can be a powerful tool in the toolbox.

There is also a lot more that could be done with generators and their associated machinery. For example, the ability to pause and resume means that we can write a function that never actually terminates, yet doesn't consume infinite CPU resources; it yields values when requested, yet otherwise remains quiet as if frozen in carbonite. In any case, I hope this has piqued your interest in this feature of JavaScript!