Fiber

I've been talking a lot about Enumerator lately. While we're on the topic, I thought it might be fun to write our own implementation of Enumerator.

First, a super-quick review. Given a method that yields a series of names in turn, an Enumerator based on that method will have the following properties:

• It will return the next value yielded by the method every time it is sent the #next method.
• When the underlying method finishes, #next will raise a StopIteration exception.
• It exposes the series of yielded values as an Enumerable collection. It supports #each, #to_a, #detect, and all the other Enumerable goodies.
• It exposes a #with_index method which returns a new Enumerator that adds an index variable which counts up with each yield.

Let's see if we can duplicate this functionality ourselves.

We'll start by defining a MyEnumerator class which is initialized with an object, a method name, and a list of arguments to be passed to the method. It creates and saves a Fiber. A fiber is, in the words of the Ruby documentation, a "primitive for implementing lightweight concurrency in Ruby". They are a type of code block which can be paused and resumed. Rather than try to explain what that means, let's keep coding and see how it works in practice.

This fiber calls the given method with the provided arguments, and passes a block to it. Remember, enumerators only work for methods which take a block. Inside the block it calls Fiber.yield with whatever values the called method yielded into the block. We'll talk about what Fiber.yield means momentarily.

The only other method we define is #next. This method calls #resume on the fiber we defined earlier. Once this method is called, control of the program is handed over to the fiber block. The fiber will continue to execute until something in it calls Fiber.yield. At that point, control will be returned to the code that called #resume.

We create one of our hand-rolled enumerators for the #names method, and try calling #next on it. Each time we call #next, it returns the next name yielded by the method, exactly as the built-in Enumerator did. We're off to a good start!

def names
  yield "Ylva"
  yield "Brighid"
  yield "Shifra"
  yield "Yesamin"
end

class MyEnumerator
  def initialize(object, method_name, *args)
    @fiber = Fiber.new do
      object.send(method_name, *args) do |*yielded_values|
        Fiber.yield(*yielded_values)
      end
    end
  end

  def next
    @fiber.resume
  end
end

enum = MyEnumerator.new(self, :names)
enum.next                       # => "Ylva"
enum.next                       # => "Brighid"

As we continue to call #next, however, the behavior starts to diverge. It returns an extra nil at the end, and then raises a FiberError.

enum.next                       # => "Shifra"
enum.next                       # => "Yesamin"
enum.next                       # => nil
enum.next                       # => 
# ~> -:18:in `resume': dead fiber called (FiberError)
# ~>    from -:18:in `next'
# ~>    from -:28:in `<main>'

Ruby's Enumerator raises a StopIteration error when the enumerated method finishes. Let's mimic that behavior by adding our own StopIteration exception and raising it after the given method is done.

Now when we call #next one too many times, we get a StopIteration exception.

class MyEnumerator
  class StopIteration < RuntimeError
  end

  def initialize(object, method_name, *args)
    @fiber = Fiber.new do
      object.send(method_name, *args) do |*yielded_values|
        Fiber.yield(*yielded_values)
      end
      raise StopIteration
    end
  end

  def next
    @fiber.resume
  end
end

enum = MyEnumerator.new(self, :names)
enum.next                       # => "Ylva"
enum.next                       # => "Brighid"
enum.next                       # => "Shifra"
enum.next                       # => "Yesamin"
enum.next                       # => 
# ~> -:17:in `block in initialize': MyEnumerator::StopIteration (MyEnumerator::StopIteration)

Ruby's Enumerator also supported all of the methods provided by the Enumerable module. Let's make our enumerator class Enumerable as well. We include the Enumerable module, and then add the #each method that Enumerable depends on. This method simply enters an infinite loop, calling the #next method and then yielding whatever it returns to the given block. If the StopIteration exception is raised, the method returns.

This version of our homemade enumerator supports all of the comforts of Enumerable. We can convert it to an array; search through it with #detect; and so on.

class MyEnumerator
  include Enumerable

  class StopIteration < RuntimeError
  end

  def initialize(object, method_name, *args)
    method = object.method(method_name)
    @fiber = Fiber.new do
      method.call(*args) do |*yielded_values|
        Fiber.yield(*yielded_values)
      end
      raise StopIteration
    end
  end

  def next
    @fiber.resume
  end

  def each
    loop do
      yield self.next
    end
  rescue StopIteration
    # NOOP
  end
end

enum = MyEnumerator.new(self, :names)
enum.to_a                 # => ["Ylva", "Brighid", "Shifra", "Yesamin"]
enum = MyEnumerator.new(self, :names)
enum.detect{|n| n =~ /^S/} # => "Shifra"
enum = MyEnumerator.new(self, :names)

Let's add one last ability to this class: the #with_index modifier. For this, we extract out the block passed to the given method into a lambda we call DEFAULT_YIELD_HANDLER. We then add an optional block argument to the MyEnumerator constructor. If it is given, it will replace the DEFAULT_YIELD_HANDLER.

In the #with_index method we initialize an index count to 0. Then we build a new enumerator wrapped around the current one. But this time instead of relying onthe default yield handler, we explicitly supply a modified yield handler which adds the index to the yielded values, and then increments the index.

When we use this modifier, we can see that the auto-incrementing index is indeed added to the yielded values.

class MyEnumerator
  include Enumerable

  class StopIteration < RuntimeError
  end

  DEFAULT_YIELD_HANDLER = ->(*yielded_values) do
    Fiber.yield(*yielded_values)
  end

  def initialize(object, method_name, *args, &yield_handler)
    method = object.method(method_name)
    yield_handler ||= DEFAULT_YIELD_HANDLER
    @fiber = Fiber.new do
      method.call(*args, &yield_handler)
      raise StopIteration
    end
  end

  def next
    @fiber.resume
  end

  def each
    loop do
      yield self.next
    end
  rescue StopIteration
    # NOOP
  end

  def with_index
    index = 0
    self.class.new(self, :each) do |*yielded_values|
      Fiber.yield(*yielded_values, index)
      index += 1
    end
  end
end

enum = MyEnumerator.new(self, :names)
enum.with_index.each do |name, index|
  puts "#{index}: #{name}"
end
# >> 0: Ylva
# >> 1: Brighid
# >> 2: Shifra
# >> 3: Yesamin

With a few minor exceptions, we now have a class which mimics Ruby's built-in Enumerator. And we accomplished it all with a Fiber. By enabling us to pause a method after every yield, and then resume it later, the Fiber let us reproduce Enumerator's trick of turning a method "inside out" and driving it from the outside.

Hopefully this gives you a better idea of what fibers are all about. Happy hacking!