Generators and Ruby Blocks: Closures with a Twist

Consider the following Javascript code:

function printFibo(a, b) {
  while(true) {
    print(a);
    if (a > 1000) {
        break;
    }

    let next = a + b;
    a = b;
    b = next;
  }
}

printFibo(0, 1)

What if we want to create a separation of concerns that decouples (1) how we compute the Fibonacci numbers from (2) what we do with them (printing and conditionally stopping)?

OOP approach: Iterators

We could try this:

function printFibo(a, b, action) {
  while(true) {
    action(a);
    
    let next = a + b;
    a = b;
    b = next;
  }
}

printFibo(0, 1, () => {
  print(a);
  if (a > 1000) {
    break;
  }
})

…but it doesn’t work. Why? Because the break is no longer instead the while loop, and in Javascript (and most languages), break is lexically scoped.

Here’s an approach that uses OOP:

class Fibo extends Iterator {
  constructor() {
    super()
    this.a = 0;
    this.b = 1;
    this.done = false;
  }
  
  next() {
    let newVal = this.a + this.b;
    this.value = this.a;
    this.a = this.b;
    this.b = newVal;
    return this;
  }
}

let fiboIter = new Fibo();
while (true) {
  let n = fiboIter.value;
  print(n)
  if (n > 1000) {
    break;
  }
  fiboIter.next()
}

This does work! And Javascript has a bit of special language-level support for it: because we subclassed Iterator and implemented a next method and a done property, Javascript let us iterate over a Fibo object as if it were an array:

for (let n of new Fibo()) {
  print(n)
  if (n > 1000) {
    break;
  }
}

This for-each loop is syntactic sugar for the while loop above. (Java for-each loops do exactly the same thing!)

This OOP approach is still awfully verbose compared to the original, however. The reason that code gets messy is that this approach means we have one function that represents the start of the loop and a different function that represents each iteration of the loop.

Closure-adjacent approach: Generators

Javascript gives us a second option with a very different shape:

function* fibo(a, b) {
  while(true) {
    yield(a);
    
    let next = a + b;
    a = b;
    b = next;
  }
}

for (let a of fibo(0, 1)) {
  print(a);
  if (a > 1000) {
    break;
  }
}

The function* syntax means that fibo is not a normal function. When we call it, we don’t just get a single return value; we get something called a generator. It’s kind of like a closure, but we can call it over and over to get multiple sequential return values. Every time that fibo reaches the yield, it returns a value — but it remembers where it was. The next time we ask the generator for another value, fibo continues running from where it left off!

This means we can write fibo with the same simple syntax as the original version, but Javascript lets us loop over the generator with a for loop.

Python has generators too! The syntax is very similar:

def fibo(a, b):
  while True:
    yield a
    
    next = a + b
    a = b
    b = next

for n in fibo(0, 1):
  print(n)
  if n > 1000:
    break

Generators and lazy evaluation

Note there are two loops in the code above: a for loop and a while loop. The for loop is finite — it stops when when n > 1000 — but the while loop is infinite! However, that infinite loop does not cause the program to run forever: it’s inside the generator, the generator pauses every time it reaches the yield, and we eventually stop asking the generator for values.

Generators can thus be a form of lazy evaluation: computing results only when they’re needed (“lazily”) instead of computing them all in advance (“eagerly”). Python has some handy building blocks that let us take advantage of this.

Python provides the syntax:

expr for value in iterable

…which is a bit like .map in Ruby and Java: it means “create a new generator that evaluates expr for each value in iterable.” For example, this code:

(str + "!" for str in ["hi", "bye"])

…produces a generator that yields "hi!" and then "bye!". And you can apply that syntax to another generator:

Code		Result
`fibo(0, 1)`	→	0, 1, 1, 2, 3, 5, 8, …
`x > 1001 for x in fibo(0, 1)`	→	False, False, …, (eventually) True, True, …

The any function accepts a generator. It means “Are any values in this sequence true?” However, it does not check all of the values: If it ever receives a truthy value, it immediately stops and returns True. But if it doesn’t, it keeps asking for more values. And if the values run out, then it returns False. Pseudocode:

any(e)
  while not e.done
    if e.next
      return True
  return False

That means we can ask whether there are any Fibonacci numbers greater than 1001:

any(x > 1001 for x in fibo(0, 1))

…and it works! Because any stops as soon as x > 1001 is true, this program does not run forever — even though fibo yields an infinite sequence. Thanks, lazy evaluation! However, this program will run forever:

any(x < 0 for x in fibo(0, 1))

…because there are no negative Fibonacci numbers, so nothing ever causes any to stop.

You’ve probably noticed the standard for-each syntax in Ruby doesn’t actually involve the word “for:”

items.each do |x|
  ...
end

Here we are calling the each method of items, and passing it…is that a closure??

Javascript has something very similar: there is a forEach method on arrays, and it takes a closure:

items.forEach((x) => {
  ...
})

However, Javascript programming tend to prefer the for (... of ...) syntax. One reason for that is that this code doesn’t work:

let items = ["fish", "hat", "badger"]

items.forEach((x) => {
  print(`Next item is ${x}`)
  if (item == "hat") {
    print("STOP FOR THE HAT");
    break;
  }
})

The programmer here clearly was trying to stop when the code reaches “hat,” but instead it gives an error. Why? Because the break statement is inside the closure, and it can’t reach out of the closure and break from the enclosing loop.

However, in Ruby, what appears to be exactly the same thing actually works!

items = ["fish", "hat", "badger"]

items.each do |x|
  puts "Next item is #{x}"
  if x == "hat"
    puts "STOP FOR THE HAT"
    break
  end
end

That do..end syntax is almost a closure, but not quite. It’s called a block in Ruby. It can use either the do...end syntax or curly braces. Ruby programmers mostly prefer do...end for multiline blocks and { } for single-line blocks:

items.each do |x|
  ...
end

items.each { |x| ... }

A block is like a closure in many ways: it’s code that’s passed to each, that can be called multiple times or not at all, and that can take a parameter every times it’s called. However, it’s different from a closure in three ways:

A block is not a full-fledged value in the language. A function can’t return a block or assign it to a variable. (There is a way to convert a block it into a full-fledged closure, but that’s an explicit step that changes what it is and how it behaves.)
Because of 1, a block doesn’t outlive its calling context. The do...end block we passed to each will go away before the each function returns. Ruby uses this limitation to keep the block’s local variables on the stack, whereas as values captured by a closure have to move to the heap. Ruby blocks are thus very efficient at runtime!
A break or return in a Ruby block can reach outside the block, up to the lexically closest enclosing loop (for break) or method (for return).

This makes it practical for the each method to be Ruby’s primary form of iteration over a collection.

Very few languages have a feature like this. Perhaps more should!

Writing a function that uses blocks

Much like a generator, a block can yield values:

def things
  yield "fish"
  yield "hat"
  yield "badger"
end

things do |item|
  puts "item is #{item}"
end

Notice, however, that we do not first call things and then loop over it with a for loop. Remember: blocks stay on the stack; when the things method is done, that block we passed to it goes away. (That’s different from a generator, which immediately becomes a normal value in the language once it’s created.)

We could use blocks to write from scratch something very much like Python’s any function:

def any(seq)
  seq.each do |value|
    if yield(value)
      return true
    end
  end
  return false
end

Now let’s do that same job of checking whether there is a Fibonacci number larger than 1001:

class Fibo
  def each
    a = 0
    b = 1
    loop do  # infinite loop
      yield a
      next_val = a + b
      a = b
      b = next_val
    end
  end
end

any(Fibo.new) do |x|  # not infinite!
  x > 1001
end

This looks very, very similar to a generator! It isn’t quite, but it’s close! Any Ruby does in fact provide a class called Enumerator that uses the language’s block and closure features to let us build a full-fledged generator:

def fibo(a, b)
  Enumerator.new do |yielder|
    loop do
      yielder.yield a
      next_val = a + b
      a = b
      b = next_val
    end
  end
end

…and Enumerator has a built-in any? method that works just like Python’s any function:

fibo(0, 1).any? { |x| x > 1001 }

Closures, generators, and Ruby blocks are all closely related riffs on related themes.

Generators and blocks are both limited examples of a more general family of language features called coroutines: functions that can arbitrarily pause, resume, and pass values to each other.

Coroutines in turn are a specialized version of a truly wild feature called continuations, which are values that represent an execution context: the execution point and the call stack all bundled into a single pause now, pick up here” value.

A study of continuations and coroutine-shaped features in various languages could be a good project topic.

Generators and Ruby Blocks: Closures with a Twist

Generators

OOP approach: Iterators

Closure-adjacent approach: Generators

Generators and lazy evaluation

Ruby Blocks

Writing a function that uses blocks

Further research