Ruby 2.0 Works Hard So You Can Be Lazy

Lazy enumeration isn’t magic; it’s just a matter of hard work

Ruby 2.0’s new lazy enumerator feature seems like magic. In case you haven’t tried it yet, it allows you to iterate over an infinite series of values and take just the values you want. It brings the functional programming concept of lazy evaluation to Ruby - at least for enumerations.

For example, in Ruby 1.9 and earlier you would run into an endless loop if you tried to iterate over an infinite range:

Here the call to collect starts an endless loop; the call to first never happens. However, if you upgrade to Ruby 2.0 and use the new Enumerable#lazy method, you can avoid the endless loop and get just the values you need:

But how does lazy evaluation actually work? How does Ruby know I only want ten values, in this example? All I have to do is make the simple call to the lazy method and it just works.

It seems like magic, but actually it’s just a matter of hard work. A lot happens inside of Ruby when you call lazy. To give you just the values you need, Ruby automatically creates and uses many different types of internal Ruby objects. Like heavy equipment at a work site, these objects work together to process the input values from my infinite range in just the right way. What are these objects? What do they do? How do they work together? Let’s find out!

The Enumerable module: many different ways of calling “each”

When I call collect on the range above I’m using Ruby’s Enumerable module. As you probably know, this module contains a series of methods, such as select, detect, any? and many more, that process lists of values in different ways. Internally, all of these methods work by calling each on the target object or receiver:

You can think of the Enumerable methods as a series of different types of machines that operate on data in different ways, all via the each method:

Enumerable is eager

Many of the Enumerable methods, including collect, return an array of values. Since the Array class also includes the Enumerable module and responds to each, you can chain different Enumerable methods together easily:

In my code example above, the Enumerable#first method calls each on the result of Enumerable#collect, an array which was generated in turn by another call to each on the input range.

One important detail to notice here is that both Enumerable#collect and Enumerable#first are eager: this means that they process all of the values returned by each before returning the new array value. So in my example, first collect processes all the values from the range and saves the results into the first array. Then in a second step first processes all the values from the first array, placing the results into the second array:

This is what leads to the endless loop for an infinite range; since Range#each will never stop returning values, Enumerable#collect will never finish, and Enumerable#first will never get a chance to stop the iteration.

The Enumerator object: deferred enumeration

One interesting trick you can use with the Enumerable module’s methods is to call them without providing a block. For example, suppose I call collect on my range, but I don’t provide a block:

Here Ruby has prepared an object you can use later to actually enumerate over the range, called an “Enumerator.” As you can see from the inspect string, Ruby has saved a reference to the receiver (1..10) along with the name of the enumerable method I want to use (collect) inside the enumerator object.

Later when I want to actually iterate through the range and collect the values in an array, I can just call each on the enumerator:

There are a few other ways of using enumerators, such as calling next repeatedly, which I don’t have time to discuss today.

Enumerator::Generator - generating new values for enumeration

In my previous examples I used a Range object to produce a series of values. However, the Enumerator class provides another more flexible way of generating a series of values using a block. Here’s an example:

Let’s take a look at what sort of enumerator this is:

As you can see, Ruby has created a new enumerator object that contains a reference to an internal object called Enumerator::Generator, and has setup to call the each method on that generator. Internally, the generator object converts the block I provided above into a Proc object and saves it away:

Now when I use the Enumerator object, Ruby will call the Proc saved inside the generator to get the values for the enumeration:

In other words, the Enumerator::Generator object is a source of data for an enumeration - it “generates” the values and passes them along.

Enumerator::Yielder - allowing one block to yield to another

If you take a close look at the code above, there’s something strange about it. I first created the Enumerator object using a block:

…which yields values to a second block I provide later when I call each:

In other words, the enumerator somehow allows you to yield values directly from one block to another:

But of course this isn’t how Ruby works. Blocks can’t pass values directly to each other like this. The trick to making this work is another internal object called the Enumerator::Yielder object, passed into the block with the y block parameter:

The y parameter is very easy to miss here. But if you re-read the block’s code, you’ll notice I’m not actually yielding values at all, I’m simply calling the yield method on the y object, which is an instance of the built in Enumerator::Yielder class. You can see and use this class for yourself in IRB as follows:

The yielder catches values I want the enumerator to generate, using the yield method, and then later actually yields them to the target block. As a Ruby developer, aside from calling yield I don’t normally ever need to interact with the generator or the yielder; they are used internally by the enumerator. When I call each on the enumerator, it uses these two objects to generate and yield the values I want:

Enumerators generate data; Enumerable methods consume it

Stepping back for a moment, the pattern we’ve seen so far with enumerations in Ruby is:

• Enumerator objects produce data.
• Enumerable methods consume data.

From right to left, the enumerable method calls each to request data; later from left to right the enumerator object provides the data by yielding it to a block.

Enumerator::Lazy - putting it all together

Ruby 2.0 implements lazy evaluation using an object called Enumerator::Lazy. What makes this special is that it plays both roles! It is an enumerator, and also contains a series of Enumerable methods. It calls each to obtain data from an enumeration source, and it yields data to the rest of an enumeration:

Since Enumerator::Lazy plays both roles, you can chain them up together to produce a single enumeration. This is what happens in my infinite range example:

The call to lazy produces one Enumerator::Lazy object. Then when I call collect on this first object, the Enumerator::Lazy#collect method returns a second one:

You can see here that the second Enumerator::Lazy, created by the call to Enumerator::Lazy#collect, also calls my block, the x*x code.

How does all of this work? How does Enumerator::Lazy do all of this? To serve both as a data producer and consumer, Enumerator::Lazy uses generator and yielder objects in a special way. The generator first calls each to obtain data, and then it passes each value it obtains immediately into a special block:

Let’s take a closer look at the block from the diagram - this block implements the Enumerator::Lazy#collect method. (The other lazy enumeration methods use slightly different blocks.) Ruby implements it internally using C code, but this is the equivalent Ruby code:

Reading the code, we can see the block takes a yielder and a value. Then it yields the value to another block - this is actually the block I provide to Enumerator::Lazy#collect or x*x in my example. Then the Enumerator::Lazy#collect block calls the yielder, passing the result of my block onto the rest of the enumeration.

This is the key to lazy evaluation in Ruby. Each value from the data source is yielded to my block, and then the result is immediately passed along down the enumeration chain. This enumeration is not eager - the Enumerator::Lazy#collect method does not collect the values into an array. Instead, each value is passed one at a time along the chain of Enumerator::Lazy objects, via repeated yields. If I had chained together a series of calls to collect or other Enumerator::Lazy methods, each value would be passed along the chain from one of my blocks to the next, one at a time:

Lazy evaluation: executing code backwards

Why is this chain lazy evaluation? Why does this allow Ruby to avoid an endless loop and provide me with just the values I need? The answer is that the code at the end of the enumeration chain, in my example the first(10) method call, controls how long the enumeration runs:

At the end of the enumeration chain the values are yielded to the Enumerable#first method:

After the Enumerable#first method receives enough values, 10 in my example, it stops the iteration by raising an exception.

In other words, the code at the right side of my enumeration chain, the code at the end, actually controls the execution flow. The Enumerable#first both starts the iteration by calling each on the lazy enumerators, and ends the iteration by raising an exception when it has enough values.

At the end of the day, this is the key idea behind lazy evaluation: the function or method at the end of a calculation chain starts the execution process, and the program’s flow works backwards through the chain of function calls until it obtains just the data inputs it needs. Ruby achieves this using a chain of Enumerator::Lazy objects, as we’ve seen above. However, functional languages such as Haskell implement this in a deeper, more fundamental way, that encompasses all execution and not just enumeration.