Decode Genrators

I’m not gonna talk about how to use generators or different ways of using it. This page talks about how generators works? and it’s internals.

Generators inherit their behaviour from iterators, they are lazy loaders. Each next value will be evaluated and returned only after asked for next. Iterators does required to maintain the state and it’s you need to take care of it. It becomes hard when you deal with a recursion at n stack depth.

Generators are good alternates for iterators, you don’t have to maintain the current state of evaluation. State becomes snapshoted between evaluations and retun the intended value to the caller.

Let’s take a deep look how this works…

A simple program to generate fibanocci series would be the below….

def fib():
    a, b = 0, 1
    while 1:
       yield b
       a, b = b, a+b

When fib() is first invoked, it sets a to 0 and b to 1, then yields b back to its caller. The caller sees 1. When fib is resumed, from its point of view the yield statement is really the same as, say, a print statement: fib continues after the yield with all local state intact. a and b then become 1 and 1, and fib loops back to the yield, yielding 1 to its invoker. And so on. From fib’s point of view it’s just delivering a sequence of results, as if via callback. But from its caller’s point of view, the fib invocation is an iterable object that can be resumed at will.

How is this happening?

Let’s see how feb function get’s intrepreted using the disassembled bytecode.

>>> import dis
>>> dis.dis(fib)
  2           0 LOAD_CONST               3 ((0, 1))
              2 UNPACK_SEQUENCE          2
              4 STORE_FAST               0 (a)
              6 STORE_FAST               1 (b)

  3           8 SETUP_LOOP              24 (to 34)

  4     >>   10 LOAD_FAST                1 (b)
             12 YIELD_VALUE
             14 POP_TOP

  5          16 LOAD_FAST                1 (b)
             18 LOAD_FAST                0 (a)
             20 LOAD_FAST                1 (b)
             22 BINARY_ADD
             24 ROT_TWO
             26 STORE_FAST               0 (a)
             28 STORE_FAST               1 (b)
             30 JUMP_ABSOLUTE           10
             32 POP_BLOCK
        >>   34 LOAD_CONST               0 (None)
             36 RETURN_VALUE

We don’t see anything abnormal in the interpreter flow, if we understand the bytecode properly there is a loop setup at bytecode index 8 3 8 SETUP_LOOP 24 (to 34) this would jump to bytecode index 34 (>> 34 LOAD_CONST 0 (None)) if the loop ends otherwise it will be running forver between bytecode index 10 and 30 (JUMP_ABSOLUTE moved bytecode stack pointer to the excat byteindex).

So, where is the generator magic happening here?

If we check the type of object we get with fib function is a generator object.

>>> f = fib()
>>> f
<generator object fib at 0x10ef104f8>

In the compilation phase the genrator objects are treated different, generators get additional properties and attributes to maintain it’s state, if you check the dir of generator object…

>>> dir(f)
['__class__', '__del__', '__delattr__', '__dir__', '__doc__', '__eq__', '__format__', '__ge__', '__getattribute__', '__gt__', '__hash__', '__init__', '__init_subclass__', '__iter__', '__le__', '__lt__', '__name__', '__ne__', '__new__', '__next__', '__qualname__', '__reduce__', '__reduce_ex__', '__repr__', '__setattr__', '__sizeof__', '__str__', '__subclasshook__', 'close', 'gi_code', 'gi_frame', 'gi_running', 'gi_yieldfrom', 'send', 'throw']

There are few interesting things attached to generators, I wouldn’t be surprised with gi_code as it is a code object, Here gi_frame and gi_running are interesting ones. Generally frame objects are interpreter level things, they wouldn’t be attached to a specific object.

This is where python does magic to maitain the generators state, The frame object gets directly attached to generator object so that it would load the frame back to stack instead using current stack top frame.

If you check a bit inside gi_frame….you can check more about frame object here

>>> f.gi_frame
<frame at 0x10ef95c18, file '<stdin>', line 1, code fib>

>>> dir(f.gi_frame)
['__class__', '__delattr__', '__dir__', '__doc__', '__eq__', '__format__', '__ge__', '__getattribute__', '__gt__', '__hash__', '__init__', '__init_subclass__', '__le__', '__lt__', '__ne__', '__new__', '__reduce__', '__reduce_ex__', '__repr__', '__setattr__', '__sizeof__', '__str__', '__subclasshook__', 'clear', 'f_back', 'f_builtins', 'f_code', 'f_globals', 'f_lasti', 'f_lineno', 'f_locals', 'f_trace', 'f_trace_lines', 'f_trace_opcodes']

It’s a frame object with few properties like f_back, f_code, f_lasti, f_lineno, f_trace etc..

>>> import dis
>>> dis.dis(fib)
  2           0 LOAD_CONST               3 ((0, 1))
              2 UNPACK_SEQUENCE          2
              4 STORE_FAST               0 (a)
              6 STORE_FAST               1 (b)

  3           8 SETUP_LOOP              24 (to 34)

  4     >>   10 LOAD_FAST                1 (b)
             12 YIELD_VALUE
             14 POP_TOP

  5          16 LOAD_FAST                1 (b)
             18 LOAD_FAST                0 (a)
             20 LOAD_FAST                1 (b)
             22 BINARY_ADD
             24 ROT_TWO
             26 STORE_FAST               0 (a)
             28 STORE_FAST               1 (b)
             30 JUMP_ABSOLUTE           10
             32 POP_BLOCK
        >>   34 LOAD_CONST               0 (None)
             36 RETURN_VALUE

As per the bytecode, YIELD_VALUE is at byteindex 12, so if the frame execution freeze happens the interpreter evaluation should stop at byteindex 12 and when it is resumed it should go on, Let’s see what’s happening with each iteration.

>>> next(f)
1
>>> f.gi_frame.f_lasti
12
>>> next(f)
1
>>> f.gi_frame.f_lasti
12
>>> next(f)
2
>>> f.gi_frame.f_lasti
12

If we see, the gi_frame.f_lasti is pointed to bytecode index 12, f_lasti is the last instruction where the stack pointed to, for each iteration we call next(f) the execution starts only from byteindex 12 then continute till byte index 30 where it is JUMP_ABSOLUTE to byte index 10 back and agin go to 12 and repat this infinitely.

Let’s take another simple generator for better understanding..

>>> def foo():
       yield 1
       print("After 1")
       yield 2
       print("After 2")
       yield 3
       print("After 3")

The correspondng bytecode for this is ..

>>> dis.dis(foo)
  2           0 LOAD_CONST               1 (1)
              2 YIELD_VALUE
              4 POP_TOP

  3           6 LOAD_GLOBAL              0 (print)
              8 LOAD_CONST               2 ('After 1')
             10 CALL_FUNCTION            1
             12 POP_TOP

  4          14 LOAD_CONST               3 (2)
             16 YIELD_VALUE
             18 POP_TOP

  5          20 LOAD_GLOBAL              0 (print)
             22 LOAD_CONST               4 ('After 2')
             24 CALL_FUNCTION            1
             26 POP_TOP

  6          28 LOAD_CONST               5 (3)
             30 YIELD_VALUE
             32 POP_TOP

  7          34 LOAD_GLOBAL              0 (print)
             36 LOAD_CONST               6 ('After 3')
             38 CALL_FUNCTION            1
             40 POP_TOP
             42 LOAD_CONST               0 (None)
             44 RETURN_VALUE 

Remember this we’ve YIELD_VALUE instrucrtions at byte index 2, 16, 30 as per the above bytecode.

Let’s start calling next value, iteration 1

>>> foo_test = foo()

Iteration 1..

>>> next(foo_test)
1
>>> foo_test.gi_frame.f_lasti
2

Iteration 2..

>>> next(foo_test)
2
>>> foo_test.gi_frame.f_lasti
16

Iteration 3..

>>> next(foo_test)
3
>>> foo_test.gi_frame.f_lasti
30

If we carefully observe the interpretation flow for generator objects, for the iteration one after yield which is byte index 2 in the bytecode, the frame objects f_lasti is freezed at 2 and then for iteration 2 when the generator resumed, the frame objects f_lasti is freezed at 16 and then for iteration 3 frame objects f_lasti is freezed at 30.

Like wise at each yield point the frame gets snapshotted and attached to the generator object for future evaluation.

We can also see all the local variables and global variables attached to the generator objects freezed frame.

For fibanocci generator object that we’ve created above the local variabes can be seen at frame objects f_locals

>>> f.gi_frame.f_locals
{'a': 2, 'b': 3}

If we go further iterations the local variables gets updated.

>>> next(f)
5
>>> f.gi_frame.f_locals
{'a': 3, 'b': 5}
>>> next(f)
8
>>> f.gi_frame.f_locals
{'a': 5, 'b': 8}
>>> next(f)
13
>>> f.gi_frame.f_locals
{'a': 8, 'b': 13}

This is how the generator works, I hope this helps. If you have any questions you can always fire me an email at gsb at gsb-eng.com.

Published: December 25 2018

  • category:
blog comments powered by Disqus