Wandering Thoughts

Why we're not running the current version of Django

We have a small web app that uses Django (or is based on Django, depending on your perspective). As I write this, the latest version of Django is 1.11.2, and the 1.11 series of releases started back in April. We're running Django 1.10.7 (I'm actually surprised we're that current) and we're probably going to keep on doing that for a while.

(Now that I'm looking at this, I see that Django 1.10 will get security fixes through December (per here), so we'll probably stick with it until the fall. Summer is when new graduate students show up, which means that it's when the app is most important and most heavily used.)

On the one hand, you might ask what's the problem with this. On the other hand, you might ask why we haven't updated. As it turns out, both questions wind up in the same place. The reason I don't like being behind on significant Django version updates is that the further behind we get, the more work we have to do all at once to catch up with Django changes (not all of which are clear and well documented, and some of which are annoying). And the reason we're behind is exactly that Django keeps changing APIs from version to version (including implicit APIs).

The net result is that Django version updates are not drop in things. Generally each of them is a not insignificant amount of work and time. At a minimum I have to read a chunk of the release notes very carefully (important things are often mentioned in passing, if at all), frequently I need code changes, and sometimes Django deprecates an API in a way that leaves me doing a bunch of research and programming to figure out what to replace it with (my notes say that this is the case for 1.11). Our small web app otherwise needs basically no attention, so Django version updates are a real pain point.

At the same time, I've found out the hard way that if I start delaying this pain for multiple version updates, it gets much worse. For a start, I fast-forward through any opportunity to get deprecation warnings; instead a feature or an API can go straight from working (in our current version) to turned off. I also have to absorb and understand all of the changes and updates across multiple versions at once, rather than getting to space them out bit by bit. So on the whole it goes better to go through every Django version.

I don't expect this to ever change. I don't think the Django developers have any sort of policy about how easy it should be to move from, say, one Django long term support release to another. And in general I don't expect them to ever get such a policy that would significantly slow them down. The Django developers clearly like the freedom to change their APIs relatively fast, and the overall Django community seems to be fine with it. We're outliers.

(This issue is one reason to not stick with the version of Django that's supplied by Ubuntu. Even Ubuntu 16.04 only packages Django 1.8. I really don't want to think about what it would be like to jump forward four years in Django versions when we do our typical 'every second Ubuntu LTS release' update of the web server where our Django app runs. Even Ubuntu 14.04 to Ubuntu 16.04 is a jump from Django 1.6 to Django 1.8 all at once.)

The Python Gilectomy project's performance problem

After my recent entries on (C)Python's Global Interpreter Lock (GIL), Kevin Lyda asked me on Twitter if I'd read the latest update on Progress on the Gilectomy. For those of us who either haven't heard of this before or have forgotten about it, the 'Gilectomy' is Larry Hastings' ongoing project to remove the GIL from CPython. As summarized in the LWN article, his goals are:

[Larry Hastings] wants to be able to run existing multi-threaded Python programs on multiple cores. He wants to break as little of the existing C API as possible. And he will have achieved his goal if those programs run faster than they do with CPython and the GIL—as measured by wall time.

With a certain amount of hand waving, these are worthwhile goals for multi-threaded Python code and I don't think anyone would object. The project is also technically neat and interesting, although it appears to be more interesting from an engineering perspective (taking existing research and applying it to Python) than from a research perspective (coming up with new GC approaches). There's nothing wrong with this, of course; computer science stands on the shoulders of plenty of giants, so it's to our benefit to look down on a regular basis. If Larry Hastings can deliver his goals in a modified version of CPython that is solidly implemented, he'll have done something pretty impressive.

However, I agree with Guido van Rossum's view (as reported in LWN's 2016 Gilectomy article) that this should not become part of regular CPython unless existing single-threaded Python programs still run at full speed, as fast as they do now. This may seem harsh, given that a successful Gilectomy would definitely speed up multi-threaded programs, but here is where theory runs up against the reality of backwards compatibility.

The reality is that most current Python programs are single-threaded programs or ones that are at most using threading for what the GIL makes it good for. This is a chicken and egg issue, of course; the GIL made Python only good for this, so this is mostly how people wrote Python programs. You have to be at least somewhat perverse to write multi-threaded code knowing that multi-threading isn't really helping you; unsurprisingly, not many people are perverse and so probably not much of this code exists. If a new version of CPython sped up this uncommon 'perverse' code at the expense of slowing down common single-threaded code, most people would probably have their Python code slow down and would consider the new version a bad change.

I further believe that this holds not just for wall clock time but also for CPU usage. A version of CPython that required extra cores to keep existing programs running just as fast in wall clock time is a version that has slowed down in practice, because not all systems actually have those extra cores sitting idle, waiting to be used.

(There are also pragmatic issues with the CPython API for C extensions. For a start, you had better make it completely impossible for existing C extensions to create multi-threaded races if they are just recompiled for the new CPython. This may require deliberately dropping certain existing APIs because they cannot be made multi-thread safe and forcing extensions to be updated to new ones, which will inevitably result in a bunch of existing extensions never getting updated and users of them never updating either.)

On the whole I'm not optimistic for a Gilectomy to arrive before a hypothetical 'Python 4' that can break many things, including user expectations (although I'd love to be surprised by a Gilectomy that keeps single-threaded performance fully intact). I further suspect that Python's developers don't have much of an appetite for going through a Python 3 experience all over again, at least not any time soon. It's possible that a Gilectomy'd CPython could be maintained in parallel to the current regular CPython, which would at least give users a choice.

(Years ago I wrote an entry in praise of the GIL and I still basically stand by those views even in this increasingly multi-core world. Shared memory multi-threaded programming is still a bad programming model, even if CPython guarantees that your program will never dump core. But at this point it's probably too late to add a different model to multi-threaded (C)Python.)

Exploiting Python's Global Interpreter Lock for atomic operations is fun

Yesterday I wrote a sober and respectable article on how using the GIL safely has various tricky traps and you probably shouldn't try to do it. This is indeed the sensible, pragmatic approach to exploiting what the GIL protects for threaded Python code; you probably don't need that much performance and so you should use some form of explicit locking instead of trying to be clever.

The honest truth is that I've exploited the GIL this way before and I'll probably write more Python code that does it in the future. This isn't because it's necessarily a good idea; it's because the GIL is fun. Like many other complicated parts of CPython, the GIL is simply neat all by itself (at least if you're the kind of person who likes to peer behind the curtain and know how things work). And in general it's an important part of threaded CPython, with a lot of complexity that is important to understand if you want to write well-performing threaded Python code. You can't avoid learning something about the GIL's technicalities if you care about this area.

Once you have learned enough about the GIL, you have a Turing tarpit style puzzle of figuring out how to map your problem onto Python operations that are what I'll call GIL atomic, things that will never have races because the GIL is held across them. This sort of thing is like catnip for me and many programmers, especially since it requires deep domain knowledge. It make us feel smart, we're solving tough problems creatively and with real benefits (after all, this is the high performance option), and it means all of our domain knowledge gets put to nominally good use. It's simply fun to make CPython do what I want here, without the overhead and typing and work of setting up mutexes or managing locks or similar measures. It's magic; you do ordinary operations and things just work because you designed everything right.

(Then I can make myself feel even more clever by writing a long comment about how and why what I'm doing is perfectly safe.)

So that's my awkward confession about exploiting the GIL. It would be completely sensible to avoid doing so, but I'm probably not going to. Either I'll justify it on the grounds that this is a personal project and I'm allowed to have fun, or I'll justify it on the grounds of performance, but the truth is that I want to do it because it's neat and fun.

(If it was boring and tedious and took more work to arrange to exploit the GIL this way, you can bet that I'd be using mutexes and locks all the time.)

Safely using Python's Global Interpreter Lock is quite tricky and subtle

Recently I ran across Grok the GIL: How to write fast and thread-safe Python (via), by A. Jesse Jiryu Davis. In the original version of the article, A. Jesse wrote:

Even though the line lst.sort() takes several steps, the sort call itself is a single bytecode, and thus there is no opportunity for the thread to have the GIL seized from it during the call. We could conclude that we don't need to lock around sort().

In comments on that article, Ben Darnell pointed out that this is not necessarily true. The fundamental issue is that Python objects are allowed to customize how they are compared for sorting, hashed for things like dictionary insertions, and so on. These operations necessarily require running Python code, and the moment you start running Python code the GIL may be seized from you.

The version of the article on A. Jesse's personal site has been updated to note some qualifications:

[...] so long as we haven’t provided a Python callback for the key parameter, or added any objects with custom __cmp__ methods. [...]

If you guessed that these qualifications are not quite complete, you would be correct; they're missing the rich comparison operations, which may be defined instead of __cmp__ (and in Python 3, they're the only way to customize comparisons and ordering).

This may seem like nit-picking and in a sense it is. But what I really want to illustrate here is just how tricky it is to safely use the GIL without locking. In CPython there is a huge number of special cases where Python code can start running in what appear to be simple atomic C-level operations like lst.sort(). Knowing these special cases requires a great deal of up to date Python knowledge (so you know all the various ways things can be customized), then finding out if they're going to affect any particular operation you want to do may require deep dives into the source code you're dealing with. This is especially the case if the code uses things like metaclasses or class decorators.

In practice things get worse, because what you've looked at is a single point in time of your codebase; you only know that it's safe today. Nothing fundamentally prevents someone coming along later to helpfully add some rich comparison operators to a class that invalidate your assumptions that lst.sort() will be an atomic operation as far as the GIL is concerned and so you don't need to do any locking around it.

(If everyone involved is lucky, the class comments document that other code depends on the class not having rich comparison operators or whatever else you need it to not have.)

So what I've wound up feeling is that GIL safety is generally too complicated and tricky to use. Or perhaps it would be better to say that it's too fragile, since there are a vast number of ways to accidentally destroy it without realizing what you've done. If you actively want to use GIL safety to avoid explicit locking, it's probably going to be one of the trickier portions of your code and you should be very careful to document everything about it and to keep it as simple as possible (for example, using only primitive C-level types even if this requires contortions).

It's unfortunate that the GIL is this way, but it is (at least for now in CPython and thus probably for the future).

(In theory CPython could be augmented so that operations like lst.sort() explicitly held the GIL for their entire duration so that people wouldn't get surprised this way. But I suspect that the CPython developers want people to use explicit locking, mutexes, and so on, and not rely on hard to explain GIL guarantees that constrain their implementation choices.)

What I mostly care about for speeding up our Python programs

There are any number of efforts and technologies around these days that try to speed up Python, starting with the obvious PyPy and going on to things like Cython and grumpy. Every so often I think about trying to apply one of them to the Python code I deal with, and after doing this a few times (and even making some old experiments with PyPy) I've come to a view of what's important to me in this area.

(This has come to be more and more on my thoughts because these days we run at least one Python program for every incoming email from the outside world. Sometimes we run more than that.)

What I've come around to caring about most is reducing the overall resource usage of short running programs that mostly use the Python standard library and additional pure-Python modules. By 'resource usage' I mean a combination of both CPU usage and memory usage; in our situation it's not exactly great if I make a program run twice as fast but use four times as much memory. In fact for some programs I probably care more about memory usage than CPU, because in practice our Python-based milter system probably spends most of its time waiting for our commercial anti-spam system to digest the email message and give it a verdict.

(Meanwhile, our attachment logger program is probably very close to being CPU bound. Yes, it has to read things off disk, but in most cases those files have just been written to disk so they're going to be in the OS's disk cache.)

I'm also interested in making DWiki (the code behind Wandering Thoughts) faster, but again I actually want it to be less resource-intensive on the systems it runs on, which includes its memory usage too. And while DWiki can run in a somewhat long-running mode, most of the time it runs as a short-lived CGI that just serves a single request. DWiki's long-running daemon mode also has some features that might make it play badly with PyPy, for example that it's a preforking network server and thus that PyPy is probably going to wind up doing a lot of duplicate JIT translation.

I think that all of this biases me towards up-front approaches like Cython and grumpy over on the fly ones such as PyPy. Up-front translation is probably going to work better for short running programs (partly because I pay the translation overhead only once, and in advance), and the results are at least reasonably testable; I can build a translated version and see in advance whether the result is probably worth it. I think this is a pity because PyPy is likely to be both the easiest to use and the most powerful accelerator, but it's not really aimed at my usage case.

(PyPy's choice here is perfectly sensible; bigger, long-running programs that are actively CPU intensive for significant periods of time are where there's the most payoff for speeding things up.)

PS: With all of this said, if I was serious here I would build the latest version of PyPy by hand and actually test it. My last look and the views I formed back then were enough years ago that I'm sure PyPy has changed significantly since then.

Why modules raising core exceptions mostly hurts, not helps, your users

A while back I wrote an entry about how modules should never raise core Python exceptions. Recently via my Referer logs I found out that some people aren't convinced by my entry, so I feel like taking another run at this topic, this time approaching it from the perspective of someone using your module.

If I'm invoking some function or method from your module and want to trap errors, I need to write code like this:

import yourmod

def fred():
  try:
    res = yourmod.some_thing(10, 20)
  except SOMETHING as e:
    ...

In order to fill in that SOMETHING with the right exception, I need to consult your module's documentation. Given that I have to look this up, reusing a general exception saves me essentially nothing; at most I type a little less, and yourmod.Error versus RuntimeError is not exactly a compelling savings. If I just want to catch your explicitly raised errors, using RuntimeError (or a subclass of it) is not saving me any real effort.

In practice, only catching explicitly raised errors is almost always what people using your module want to do, because of the various dangers of over-broad tries that I mentioned in my original entry and elsewhere. And if I really do want to catch all errors that come out of your code, I can already do that explicitly:

try:
  res = yourmod.some_thing(10, 20)
except Exception as e:
  ...

Notice that raising RuntimeError instead of your own error doesn't actually help me here. If I want to catch all possible errors that can happen during your module's execution, I need to go much broader than merely RuntimeError.

(There are valid cases for doing this broad catching, generally in top-level code that wants to insure that no uncaught exceptions ever surface to the user.)

Which brings me around to the one case where it is sensible to raise standard errors, which is when you're writing code that stands in for standard Python code that raises these errors. This is the one case where using a standard error saves me from looking things up; in fact, using a standard error is generally essential. If you're writing a class that will get used instead of a standard dictionary, raising KeyError and so on is absolutely essential, because that makes your objects transparent substitutes for real dictionaries.

(This is in a sense a matter of API compatibility, where the exceptions that get raised are part of the API. Sometimes this can be explicit, as in the case of KeyError, but sometimes this is more implicit, in cases where raising and catching errors is more uncommon.)

Sidebar: my view on subclassing RuntimeError

I don't think you should do this because I don't think it's useful. If someone is catching RuntimeError today they probably intend to catch significant internal issues inside Python, not errors that your module happens to raise. Sweeping your module's errors into their except clauses is probably not helpful and may even be harmful.

For better or worse, I think that there is (or should be) a strong separation between 'internal' Python errors raised by the CPython interpreter and core Python modules, and module-specific errors raised by modules (yours, third party modules, and non-core modules in the standard library). These two sorts of errors don't really live in the same taxonomy and so putting one under the other is generally not going to help anyone.

Part of why Python 3.5's await and async have some odd usage restrictions

Python 3.5 added a new system for coroutines and asynchronous programming, based around new async and await keywords (which have the technical details written up at length in PEP 492). Roughly speaking, in terms of coroutines implemented with yield from, await replaces 'yield from' (and is more powerful). So what's async for? Well, it marks a function that can use await. If you use await outside an async function, you'll get a syntax error. Functions marked async have some odd restrictions, too, such as that you can't use yield or yield from in them.

When I described doing coroutines with yield from here, I noted that it was potentially error prone because in order to make everything work you had to have an unbroken chain of yield from from top to bottom. Break the chain or use yield instead of yield from, and things wouldn't work. And because both yield from and yield are used for regular generators as well as coroutines, it's possible to slip up in various ways. Well, when you introduce new syntax you can fix issues like that, and that's part of why async and await have their odd rules.

A function marked async is a (native) coroutine. await can only be applied to coroutines, which means that you can't accidentally treat a generator like a coroutine the way you can with yield from. Simplifying slightly, coroutines can only be invoked through await; you can't call one or use them as a generator, for example as 'for something in coroutine(...):'. As part of not being generators, coroutines can't use 'yield' or 'yield from'.

(And there's only await, so you avoid the whole 'yield' verus 'yield from' confusion.)

In other words, coroutines can only be invoked from coroutines and they must be invoked using the exact mechanism that makes coroutines work (and that mechanism isn't and can't be used for or by anything else). The entire system is designed so that you're more or less forced to create that unbroken chain of awaits that makes it all go. Although Python itself won't error out on import time if you try to call a async function without await (it just won't work at runtime), there's probably Python static checkers that look for this. And in general it's an easy rule to keep track of; if it's async, you have to await it, and this status is marked right there in the function definition.

(Unfortunately it's not in the type of the function, which means that you can't tell by just importing the module interactively and then doing 'type(mod.func)'.)

Sidebar: The other reason you can only use await in async functions

Before Python 3.5, the following was completely valid code:

def somefunc(a1, b2):
   ...
   await = interval(a1, 10)
   otherfunc(b2, await)
   ...

In other words, await was not a reserved keyword and so could be legally used as the name of a local variable, or for that matter a function argument or a global.

Had Python 3.5 made await a keyword in all contexts, all such code would immediately have broken. That's not acceptable for a minor release, so Python needed some sort of workaround. So it's not that you can't use await outside of functions marked async; it's that it's not a keyword outside of async functions. Since it's not a keyword, writing something like 'await func(arg)' is a syntax error, just as 'abcdef func(arg)' would be.

The same is true of async, by the way:

def somefunc(a, b, async = False):
  if b == 10:
     async = True
  ....

Thus why it's a syntax error to use 'async for' or 'async with' outside of an async function; outside of such functions async isn't even a keyword so 'async for' is treated the same as 'abcdef for'.

(I'm sure this makes Python's parser that much more fun.)

How we can use yield from to implement coroutines

Give my new understanding of generator functions and yield from, we can now see how to use yield from to implement coroutines and an event loop. Consider a three level stack of functions, where on the top layer you have an event loop, in the middle you have the processing code you write, and on the bottom are event functions like wait_read() or sleep().

Let's start with an example processing function or two:

def countdown(n):
   while n:
      print("T-minus", n)
      n -= 1
      yield from sleep(1)

def launch(what, nsecs):
   print("counting down for", what)
   yield from countdown(nsecs)
   print("launching", what)

To start a launch, we call something like 'coro.start(launch("fred", 10))', which looks a bit peculiar since it sort of seems like coro.start() should get control only after the launch. However, we already know that calling a generator function doesn't do exactly what it looks like. What coro.start() gets when we do this is an unstarted generator object (which handily encapsulates those arguments to launch(), so we don't have to do it by hand).

When the coroutine scheduler starts the launch() generator object, we wind up with a chain of yield froms that bottoms out at sleep(). What sleep() yields is passed back up to the coroutine scheduler and the entire call chain is suspended; this is no different that what I did by calling .send() by hand yesterday. What sleep() returns to the scheduler is an object (call it an event object) that tells the coroutine scheduler under what conditions this coroutine should be resumed. When the scheduler reaches the point that the coroutine should be run again, the scheduler will once again call .send(), which will resume execution in sleep(), which will then return back to countdown(), and so on. The scheduler may use this .send() to pass information back to sleep(), such as how long it took before the coroutine was restarted.

Here yield and yield from are being used for two things. First, they create a communication channel between the coroutine scheduler and the low-level event functions like sleep(). Our launch() and countdown() functions are oblivious to this since they don't touch either the value sleep() yields up to the scheduler or the value that the scheduler injects to sleep() with .send(). Second, the chain of yield from and the final yield neatly suspend the entire call stack.

In order for this to work reliably, there are two rules that our user-written processing functions have to follow. First, they must never accidentally attempt to do anything with the sleep() generator function. It is okay but unclear for a non-generator function to call sleep() and return the result:

def sleep_minutes(n):
   return sleep(n * 60)

def long_countdown(n):
   while n:
      print("T-minus", n, "minutes")
      yield from sleep_minutes(1)
      n -= 1

This is ultimately because 'yield from func()' is equivalent to 't = func(); yield from t'. We don't care just how the generator object got to us so we can yield from it, we just care that it did.

However, at no stage in our processing functions can we attempt to look at the results of iterating sleep()'s generator object, either directly or indirectly by writing, say, 'for i in countdown(10):'. This rules out certain patterns for writing processing functions, for instance this one:

def label_each_sec(label, n):
   for _ in tick_once_per_sec(n):
      print(label)

This leads to the second rule, which is that we must have an unbroken chain of yield froms from the top to the bottom of our processing functions, right down to where you use an event function such as sleep(). Each function must 'call' the next using the 'yield from func()' idiom. In effect we don't have calls from one processing function to another; instead we're passing control from one function to the next. In my example, launch() passes control to countdown() until the countdown expires (and countdown() passes control to sleep()). If we actually call a processing function normally or accidentally use 'yield' instead of 'yield from', the entire collection explodes into various sorts of errors without getting off the launch pad and you will not go to space today.

As you might imagine, this is a little bit open to errors. Under normal circumstances you'll catch the errors fairly fast (when your main code doesn't work). However, since errors can only be caught at runtime when a non-yield from code path is reached, you may have mistakes that lurk in rarely executed code paths. Perhaps you have a rarely invoked last moment launch abort:

def launch(what, nsecs):
   print("counting down for", what)
   yield from countdown(nsecs)
   if launch_abort:
      print("Aborting launch! Clear the launch pad for", what)
      yield sleep(1)
      print("Flooding fire suppression ...")
   else:
      print("launching", what)

It might be a while before you discovered that mistake (I'm doing a certain amount of hand-waving about early aborts in countdown()).

(See also my somewhat related attempt at understanding this sort of thing in a Javascript context in Understanding how generators help asynchronous programming. Note that you can't use my particular approach from that entry in Python with 'yield from' for reasons beyond the scope of this entry.)

Sorting out Python generator functions and yield from in my head

Through a chain of reading, I wound up at How the heck does async/await work in Python 3.5? (via the Trio tutorial). As has happened before when I started reading about Python 3's new async and await stuff, my head started hurting when I hit the somewhat breezy discussion of yield from and I felt the need to slow down and try to solidly understand this, which I haven't really before.

Generator functions are functions that contain a yield statement:

def fred(a):
   r = yield 10
   print("fred got:", r)
   yield a

A straightforward generator function is there to produce a whole series of values without having to ever materialize all of them at once in a list or the like.

Calling a generator function does not return its result. Instead, it returns a generator object, which is a form of iterator:

>>> fred(10)
<generator object fred at 0x7f52a75ea1a8>

This generator object is in part a closure that captures the argument fred() was called with (and in general will preserve fred()'s state while it is repeatedly iterated). Note that fred()'s code doesn't start executing until you try to get the first value from the iterator.

One common pattern with a stack of generator functions (including needing to modify or filter part of a generator's results) was that you would have one generator function that wanted to call another one for a while. In the beginning this was done with explicit for loops and the like, but then Python added yield from. yield from takes a generator or iterator and exhausts it for you, repeatedly yield'ing the result.

def barney(a):
   yield from fred(a)

(You can intermix yield and yield from and use both of them more than once in a function.)

Because generator functions actually return generators, not any sort of result, 'yield from func()' is essentially syntactic sugar for calling the function, getting a generator object back, and then calling yield from on the generator object. There is no special magic involved in that:

def barney(a):
   gen = fred(a)
   yield from gen

Because generator objects are ordinary objects, they can be returned through functions that are not generators themselves, provided that intermediate functions don't really attempt to manipulate them and simply return them as-is:

def jim(a):
   return fred(a)

def bob(a):
   yield from jim(a)

(If jim() actually iterated through fred()'s results, things would quietly go sideways in ways that might or might not be visible.)

When yield started out, it was a statement; however, that got revised so that it was an expression and could thus have a value, as we see in fred() where the value of one yield is assigned to r and then used later. You (the holder of the generator object) inject that value by calling .send() on the generator:

>>> g = fred(2)
>>> _ = g.send(None); _ = g.send("a")
fred got: a

(The first .send() starts the generator running and must be made with a None argument.)

As part of adding yield from, Python arranged it so that if you had a stack of yield from invocations and you called .send() on the outer generator object, the value you sent did not go to the outer generator object; instead it goes all the way down to the eventual generator object that is doing a yield instead of a yield from.

def level3(a):
   # three levels of yield from
   # and we pass through a normal
   # functions too
   yield from bob(a)

>>> g = level3(10)
>>> _ = g.send(None); _ = g.send("down there")
fred got: down there

This means that if you have a stack of functions that all relay things back up using 'yield from', you have a direct path from your top level code (here that's our interactive code where we called level3()) all the way down to the core generator function at the bottom of the call stack (here, the fred() function). You and it can communicate with each other through the values it yields and the values you send() to it without any function in the middle having to understand anything about this; it's entirely transparent to them.

(Don't accidentally write 'yield' instead of 'yield from', though. The good news about that mistake is that you'll catch it fast.)

Hopefully writing this has anchored yield from's full behavior and the logic behind it sufficiently solidly in my head that it will actually stick this time around.

Sidebar: yield from versus yield of a generator

Suppose that we have a little mistake:

def barney2(a):
   yield fred(a)

What happens? Basically what you'd expect:

>>> list(barney(20))
fred got: None
[10, 20]
>>> list(barney2(20))
[<generator object fred at 0x7f0fdf4b9258>]

When we used yield instead of yield from, we returned a value instead of iterating through the generator. The value here is what we get as the result of calling fred(), which is a generator object.

By the way, a corollary to strings being iterable is that accidentally calling 'yield from' instead of 'yield' on a string won't fail the way that eg 'yield from 10' does but will instead give you a sequence of single characters. You'll probably notice that error fairly fast, though.

This behavior of yield from is pretty much a feature, because it means that you can yield from another function without having to care about whether it's an actual generator function or it merely returns an iterable object of some sort; either will work.

In Python, strings are infinitely recursively iterable

Yesterday I posed the side question of what happened when you called the following code with flatten2(["abcdef",]):

def flatten2(inlst):
    olst = []
    for i in inlst:
        try:
            it = iter(i)
        except TypeError:
            it = None
        if it is None:
            olst.append(i)
        else:
            olst.extend(flatten2(i))
    return olst

The intent of this code is to recursively flatten iterable things. What I had expected to get when I called it with a string was ['a', 'b', 'c', 'd', 'e', 'f'], ie that it flattened the string instead of leaving it alone (because strings are iterable). What I actually got (and what you can get) is a RecursionError of 'maximum recursion depth exceeded'. So why did this recurse endlessly?

The answer is that strings are not just iterable, they are infinitely recursively iterable. With normal iterable containers, iterating the container yields non-iterable items unless you've explicitly put in iterable ones (such as a list inside another list); assuming that you have not cleverly embedded a cycle in your container, our recursive flattening will eventually bottom out and finish. This is not the case for Python strings. When you iterate a multi-character string like "abcdef", you get a sequence of single-character strings, "a" "b" "c" "d" "e" "f". However, these are still strings and so they are still iterable; when you iterate the "a" string, you get back another single-character string "a", which is also iterable. And so flatten2() chases down an infinite recursion of trying to unpack single-character strings into non-iterable items, which it will never succeed at.

Fixing this without side effects is a bit annoying. It's not enough to immediately check that inlst is length 1 and just return it if so, because this fails on flatten2([[1,]]) (and flatten2(["abcdef",]) too, for that matter). I think you have to check explicitly for length 1 strings (and bytes) and just return them, which of course leaves you exposed to any other infinitely recursively iterable types (should there be any other out there).

(I was about to gripe about repr()'s representation of single character strings but then I tested and it uses single quotes for all strings, not just single-character ones. I need to remember that in Python there is no 'character' type that's different from strings, unlike in other languages such as Go, and so single quotes still mean 'string'.)

Sidebar: It's trivially possible to create containers with cycles

>>> a = [1, 2, 3]
>>> a.append(a)
>>> print(a)
[1, 2, 3, [...]]

More involved versions are left as an exercise for the reader.

Without contemplating it too hard, I think that you can only create cycles with mutable containers, and then only with some of them. Sets are mutable, for example, but they can only contain hashable items, which are generally immutable.

How recursively flattening a list raises a Python type question

Today I wound up reading Why it's hard for programmers to write a program to flatten a list? (via), where the quiz challenge put forward is to turn an input like [1,[2,3], [4, [5,6]]] into [1,2,3,4,5,6]. My immediate reaction was that I'd do this in Python rather than in any statically typed language I know, because all of them make the input type here hard to represent. But then I realized that doing this in Python raises another type-related question.

If we stick exactly to the specification (and directly implement it), the result is pretty simple and straightforward:

def flatten(inlst):
    olst = []
    for i in inlst:
        if isinstance(i, int):
            olst.append(i)
        elif isinstance(i, list):
            olst.extend(flatten(i))
        else:
            raise ValueError("invalid element in list")
    return olst

(You can optimize this by having a _flatten internal function that gets passed the output list, so you don't have to keep building lists and then merging them into other lists as you work down and then back up the recursion stack. Also, I'm explicitly opting to return an actual list instead of making this a (recursive) generator.)

However, this code is not very Pythonic because it is so very narrowly typed. We can relax it slightly by checking for isinstance(i, (int, float)), but even then most people would say that flatten() should definitely accept tuples in place of lists and probably even sets.

If we're thinking about being Pythonic and general, the obvious thing to do is check if the object is iterable. So we write some simple and general code:

def flatten2(inlst):
    olst = []
    for i in inlst:
        try:
            it = iter(i)
        except TypeError:
            it = None
        if it is None:
            olst.append(i)
        else:
            olst.extend(flatten2(i))
    return olst

This should flatten any type (or mixture of types) that contains elements, as denoted by the fact that it's iterable. It looks good and passes initial tests. Then some joker calls our code with flatten2(["abcdef",]) and suddenly we have a problem. Then another joker calls our code with flatten2([somedict,]) and files a bug that our code only flattens the keys of their dictionary, not the keys and values.

(As an exercise, can you predict in advance, without trying it, what our problem is with flatten2(["abcdef",]), and why it happens? I got this wrong when I was writing and testing this code in Python 3 and had to scratch my head for a bit before the penny dropped.)

The problem here is that 'is iterable' is not exactly what we want. Some things, such as strings, are iterable but should probably be treated as indivisible by flatten2(). Other things, such as dicts, are iterable but the default iteration result does not fully represent their contents. Really, not only is Python lacking a simple condition for what we want, it's arguably not clear just what we want to do if we're generalizing flatten() (and what making it 'Pythonic' really means).

One valid answer is that we will explicitly check for container types that are close enough to what we want, and otherwise mostly return things as-is. Here we would write a version of flatten() that looked like this:

def flatten3(inlst):
    olst = []
    for i in inlst:
        if isinstance(i, (list, tuple, set)):
            olst.extend(flatten3(i))
        elif isinstance(i, dict):
            raise ValueError("dict not valid in list")
        else:
            olst.append(i)
    return olst

We could treat dicts as single elements and just return them, but that is probably not what the caller intended. Still, this check feels dubious, which is a warning sign.

As a minimum, it would be nice to have a Python abstract type or trait that represented 'this is a container object and iterating it returns a full copy of its contents'; you could call this the property of being list-like. This would be true for lists, tuples, and sets, but false for dicts, which would give us a starting point. It would also be true for strings, but you can't win them all; when dealing with iterable things, we'll probably always have to special-case strings.

(I'd go so far as arguing that making strings iterable by default was a Python mistake. It's one of those neat features that winds up getting in the way in practice.)

I don't have an answer here, by the way. If I was in this situation I might either write and carefully document a version of flatten2() (specifying 'recursively flattens any iterable thing using its default iterator; this will probably not do what you want for dicts'), or go with some version of flatten3() that specifically restricted iteration to things that I felt were sufficiently list-like.

(I'd worry about missing some new popular type over time, though. Ten years ago I might not have put set in the list, and who knows what I'm missing today that's going to be popular in Python in the future. Queues? Trees? Efficient numerical arrays?)