Python Generators in Depth

The talk from David Mertz on Co-routines: https://www.youtube.com/watch?v=b7R3-_ViNxk

Imagine you're a barista. You clock in and start doing barista things. You have three responsibilities. You have to take orders from customers and you have to pour coffee. When there are not customers you have to clean the shop.

The rules:

- You must take at least two orders if there is a line, but no more before you start pouring coffee. You should never have more than two outstanding orders at a time.

- If you have no customers in line and no coffee to pour, you must clean the shop.

Lets do it with generators (again pseudo code):

  function day_of_work() {
    generator take_orders() {
        orders = array()

        while(during_shift()) {
           while(customers_in_line()) {
             if(length(orders) >= 2) {
                yield orders
             } else {
               orders.push(take_customer_order())
             }
           }

           yield orders
        }

    generator clean_shop() {
        unpack_coffee()
        yield
        
        clean_espresso_machine()
        yield

        take_out_trash()
        yield
    }
 
    while(orders = take_orders.next()) {
        if(length(orders) > 0) {
          pour_coffee(orders.pop())
        } else {
          clean_shop.next()
        }
    }

First notice that these generators not only have variable state, but they also have control flow state and THAT is why they're different. Notice that take_orders will yield control if more than two orders exist in the queue. It will also yield control if no more customers are in line. So our main program loop is really simple. It gets the current set of orders from "take_orders". Once the order queue is full it starts pouring coffee.

Notice what happens when no orders are present. Clean shop is executed once per iteration. It first unpacks the coffee, and then yields control. Now we go back and check for more orders, if we find them we fill them until we don't have any more again. Then it's back to cleaning shop, but we pick back up RIGHT WHERE WE LEFT OFF! So we just start cleaning the espresso machine... this goes on and on until the work day ends at which point take_orders cleanly exists and orders is null. Then we pack up and go home.

Now you might go: Well I can implement that in Javascript! You'd be right! Closures + callbacks make it totally possible. Lets take a stab at it:

  orders = [];
  current_task = -1;

  while(during_work_day()) {
       take_orders(
            orders,
            function(order) { pour_coffee(order); },
            function() { current_task++; clean_shop(current_task); }
       );
  }

  function take_orders(orders, orders_full_callback, no_orders_callback) {
      if(customers_in_line()) {
          if(orders.length > 2) {
              orders_full_callback(orders.pop());
          } else {
              orders.push(take_customer_order());
          }
      } else {
          no_orders_callback();
      }
  }

  function clean_shop(current_task) {
      switch(current_task) {
        case 0:
            unpack_coffee()
            break
        case 1:
            clean_espresso_machine()
            break
        case 2:
            take_out_trash()
            break
        default:
            do_nothing()
      }
  }

Notice that our callbacks are closures. However, the callbacks do not have execution state. This means we have to manage state externally in the form of current_task.

Now for a trivial example like this, that might not be a big deal. However, imagine that we had a whole list of things to do when there weren't customers. Lets make it even harder, and have those tasks depend on state.

For instance what if we actually had a bunch of separate tasks we had to do:

- unload the truck

- draw something cool on the chalkboard

- clean the shop

What if the order those should be done in depended on state?

Before 1:00 PM the priority is:

#1 draw something cool

#2 unload the truck

#3 clean the shop

After 1:00PM the priority changes:

#1 unload the truck

#2 draw something cool

#3 clean the shop

After 3:00PM the priority changes again!

#1 clean the shop

#2 unload the truck

#3 draw something cool

Now think about how hard this is going to be in Javascript. You're going to have to maintain state for three separate jobs (where am I in that job), but also deal with making sure you're working on them in the right order.

What makes generators so damn handy is that the state is internalized. I only need to change the order I invoke the generators. As long as I keep calling next() until there aren't any items left...they'll just keep churning through whatever they're doing in the first place. They become more expressive as the complexity of the state they are managing increases. Things that are hard to do in languages that don't support them, are often pretty easy with generators. Do some work, yield, do some more work, yield... becomes a very simple pattern to reason about while not having to manage all of the state you have to do in other languages.

I hope that helps clear it up a bit:)

From a conceptual point of view, I think the main difference is where the perceived 'driver' of the action is. At least when I use generators I think of them as streaming building blocks for another, more complex, step being built (and driven) on top of the stream. In other words, I think from the bottom up. It allows me to forget about keeping important state, because that step is going to be taken care "above me". Let me give you a simple example.

Let's say you want to write an interpreter for a simple language. The base building block for the parser will be reading characters from a file ('input'). After that step, comes breaking that stream into tokens (say, at the first whitespace), and after that comes parsing the grammar by identifying what tokens are being returned by the tokenizer. If the tokenizer returns 'exit', then we should exit. You can think of the parser as a function composition like this:

exit_status = interpreter . tokenizer . char_reader (input)

The beauty of this is that the responsibility for each step is clearly defined by the level you are in, and 'input' could be infinite for all we care, the interpreter will still work (think streaming, persistent-connection protocols like XMPP.)

If you go the other way around and write this as an Interpreter class encapsulating a Tokenizer, which in turn encapsulates a CharReader, then each class has to keep more state (the 'input' has to be passed down) and know a lot more about each other. Interpreter needs to tell Tokenizer what to tokenize, and Tokenizer needs to ask CharReader to read.

Well, at least in my mind. Obviously it is completely subjective at this point. At least I like when I can drive all the logic or my (possibly infinite) loop from a single loop statement :)

But here's an example where you need to do a lot of extra work with a closure. It reads a file with '#' style comments, separates comment from non-comment strings, and keeps track of a few counters which a caller in the same file can access as global variables (technically "module-level" variables in Python).

    comments = 0
    uncommented_lines = 0
    commented_lines = 0

    def tokenize_comments(src):
        # Point A
        for line in src:
            p = line.find('#')
            if p < 0:
                yield line
                #Point B
                uncommented_lines += 1
            else:
                yield line[:p]
                #Point C
                comments += 1
                yield line[p:]
                #Point D
                commented_lines += 1
            #Point E
        return

The API could be much improved, for example, we might want to wrap this in a class to get rid of those global variables. But that's not the point. The point is that rewriting functionally equivalent code will require you to keep track of whether the code is at Point A, B, C, or D.

I purposely included the counters in this example to make it impossible to unify different control paths, which would make a closure-based implementation a lot easier. For example, if it wasn't for the counters, points B, D, and E would be identical.

Your code as is isn't bad in terms of readability/complexity...but it'd be cleaner as a generator. Then consider how much more complicated it would be if instead your generator needed to alternately return total/count and count/total (or whatever). You'd have to duplicate the two lines that increment total and count (or factor them out), have another send function, and then have code to start swapping @send to the appropriate function...or have some boolean flag to figure out which to do..etc. It gets messy if you introduce even more. Instead with generators you could write something like:

    function mySillyGenerator (c) {
        var count = c || 0;
        var total = 0;
        while (true) {
            count = yield count/total;
            count = yield total/cound
        }
    }

The same conversion for the later examples with multiple yield statements, try: except: or try: finally: will be much hairier, though.

[0] http://www.python.org/dev/peps/pep-3156/#coroutines-and-the-...

Seriously though, not being able to define a serialization method can be a limitation. However, it is always possible to turn a generator into an iterator class with whatever methods you like, but the code may end up looking totally different.