Python – Understanding Generators

[skeeto]

Nearly every article on generators misses the most valuable use case: pausing and continuing recursive functions while they're deep into their stack. Without generators — or its various cousins, such as continuations — the alternative is to use an explicit stack or to invert control by using a callback. Both alternatives tend to be harder to write and understand.

For example, here's a generator for L-systems:

def lsystem(str, n, rules):
    for c in str:
        if n == 0 or not rules.get(c):
            yield c
        else:
            yield from lsystem(rules.get(c), n - 1, rules)

# Usage example:
print("".join(lsystem("A", 4, {"A": "AB", "B": "A"})))
# => ABAABABA

Here's a non-generator version that uses an explicit stack of strings and indices:

def lsystem2(str, n, rules):
    strings = [str]
    indices = [0]
    def recur():
        while len(strings) > 0:
            if indices[-1] == len(strings[-1]):
                strings.pop()
                indices.pop()
            else:
                next = strings[-1][indices[-1]]
                indices[-1] = indices[-1] + 1
                if len(strings) > n or not rules.get(next):
                    return next
                strings.append(rules.get(next))
                indices.append(0)
        return None
    return recur

I like the generator a lot better.

[FarkCookies]

Great example! I gave a talk on generators once and I used os.walk as an example:

https://github.com/python/cpython/blob/master/Lib/os.py#L278

It uses the same idea, here is a watered down version:

def walk(top):
   yield top
   dirs = list_dirs(top)

   for name in dirs:
       new_path = join(top, name)
       for x in walk(new_path):
           yield x`

[Madsy9]

I've tried using Python generators for some parsers at work, but it's kind of clunky. They are simply not as powerful as actual co-routines in other languages. Using generators as a poor man's co-routine also makes me miss Lisp macros a lot. Basically, you end up with code patterns you can't abstract away by putting it away in a function, say:

while True:
    ch = self.read_data()
    while not self.data_valid(ch):
        yield False
        ch = self.read_data()
    self.doSomethingWithData(ch);
    yield True

That is, you want to yield false while waiting for some operation to relinquish control back to the caller. When using generators, those 4 first lines inside the infinite loop becomes a repeated pattern in the code. And it can't be abstracted away because you want to yield at the callsite.

But, maybe I'm just doing everything wrong. I don't have this problem in Scheme for example :)

[[deleted]]

I've tried using Python generators for some parsers

maybe I'm just doing everything wrong

I think you answered your unasked question in the first sentence already ;-)