Lazy Evaluation of Generators in ES6

In a previous post I introduced generators in ES6.

Generators in most languages do the least amount of work possible, and generators in JavaScript are no different. When a program invokes a normal function, you can imagine the program jumping into the function and executing code inside the function until the function completes. But, the behavior of a generator function is entirely different from the behavior of a non-generator function.

As an example, let’s use the following generator function.

let random = function*() {

    while(true) {
        console.log("make random")
        yield Math.random();
    }
}

The random function looks like it will burn CPU cycles in an infinite loop. However, if we invoke the function and look for output in the console – there will be no output!

When you invoke a generator function, you can think of the runtime setting up a data structure or a state machine behind the scenes. The state machine knows how to take the code inside the generator function and allow pieces to execute on demand.

What creates the demand?

Since generators produce iterators, then each call to the next method of the iterator will force the state machine to execute just enough code to produce the next value – and no more. For example, if we execute the following code:

let iterator = random();
iterator.next();

Then we will see “make random” appear exactly once in the console. Asking the iterator for the next value forced the state machine to execute the code inside the function until a yield statement manufactured another value. Each time there is a call to next on the iterator, the flow of the program jumps back into the generator function at the point the program last left the function, and execution continues until the program reaches another yield.

In computer science terminology, a generator function offers what we call lazy evaluation. In order to make the function perform real work, we need to pull values out of the function by asking for those values through the iterator API. The random function will only create an infinite loop if we ask for an infinite number of values.

Let’s imagine we wanted a finite number of random numbers, and we only want random numbers less than 0.5. First, we could write a filtering function that will take an iterable object and a predicate function as arguments. The filtering function will only produce the items for which the predicate function returns true.

let filter = function*(items, predicate) {
    for(let item of items){
        console.log("filter", item);
        if(predicate(item)){
            yield item;
        }
    }
};

To make sure we ask for a finite number of items, we can also write a take function, to take a specific number of items.

let take = function*(items, number) {
    let count = 0;
    if(number < 1) return;

    for(let item of items){
        console.log("take", item);
        yield item;
        
        count += 1;
        if(count >= number) {
            return;
        }
    }
};

Note how we can stop iteration using a return statement in the take function.

With the above functions, all of which are generators, we can create two random numbers less than 0.5 with the following code.

let result = take(filter(random(), n => n < 0.5), 2);

Except, we have not created any numbers with the above code! All we’ve created is an iterator, and no output will appear on the console. We could force the functions to execute code using a for of loop, or use Array.from, which is a new API we can use to convert any iterable object to a concrete array.

expect(Array.from(result).length).toBe(2);

Console output of the above code might look like the following.

make random

filter 0.24152887403033674

take 0.24152887403033674

make random

filter 0.6618692250922322

make random

filter 0.49661534116603434

take 0.49661534116603434

Notice how the execution of the different functions interleave. You can imagine the iterators pulling values from each function on an as-needed basis.

Lazy evaluation allows for all sorts of interesting scenarios with control flow and data structures. We’ll look at some of these scenarios in a future post, but coming next: delegating generators.