On Readability

Programs must be written for people to read, and only incidentally for machines to execute. — Abelson & Sussman, Structure and Interpretation of Computer Programs

Code readability gets talked about a lot these days. I haven't yet heard from anyone who's opposed to it. Unfortunately, learning to read code is a skill rarely discussed and even more rarely taught. As the SICP quote above points out, readability is perhaps the most important quality to aim for when writing. But what is code readability, exactly?

I propose there are three essential levels of code readability:

• "What is this code about?"
• "What is this code supposed to do?"
• "What does this code do?"

The first level is important when you're skimming code, trying to develop a picture of its overall structure. Good organization into modules tends to help a lot with this; if you have modules named util then this is harder than it has to be. Supporting docs describing architecture and organization can assist with this as well, along with usage examples if the code you're reading is a library.

The second level is what you encounter once you've found some code and you want to use or modify it. Maybe it's a library with weak or missing documentation and you're trying to discover how a function wants to be called or which methods to override in a class you need to inherit from. Good style, good class/function names, docstrings, and comments can all be very helpful in making your code readable for this case. There's been some research which associates poor quality identifier names and obvious bugs, so even if your code works well, poor naming can make it look like code that doesn't.

However, neither of these are the most important sense in which readability matters. They're more about communicating intent, so that later readers of your code can figure out what you were thinking. Sometimes it's a way to share hard-won insight that leaves indelible scars. But the final level is what matters most and matters longest.

To understand a program you must become both the machine and the program. — Alan Perlis, Epigrams In Programming #23

The most important level of readability is being able to look at code and understand what it actually does when run. All the factors discussed above — naming, style, documentation — cannot help with this task at all. In fact, they can be actively harmful to this. Even if the comment accurately described the code when it was written, there's no reason it has to now. The most obvious time you'll need to engage in this level of code reading is debugging — when the code looks like it does the right thing, but actually doesn't.

Language design plays a big role in supporting or detracting from the creation of readable code. As the link above shows, C provides a myriad of features that either fight against or outright destroy readability. So when picking a language, include readability as a factor in your decision making — and not just how the syntax looks. Mark Miller provides some excellent thoughts on how to design a language for readability in his notes on The Power of Irrelevance. There are also several people studying how to build tools to help us read code more effectively; Clarity In Code touches on some of the issues being considered in that field.

But given the constraints of the language you're currently using, what can we do to improve readability in our code? The key is promoting local reasoning. The absolute worst case for readability occurs when you have to understand all the code to understand any of the code. So we want to preserve as many barriers between portions of the program as are needed to prevent this.

Since local reasoning is good, global state is bad. The more code that can affect the behavior of the function or class you're looking at right now, the more work it takes to actually discern what it'll do, and when. Similarly, threads (and coroutines) destroy readability. since they destroy the ability to understand control flow locally in a single piece of code. Other forms of "magic" like call stack inspection, adding behavior to a class from other modules, metaclass shenanigans, preprocessor hacks, or macros all detract from local reasoning as well.

Since this perspective on programming is so little discussed or taught, it leads to a communications gap between inexperienced and veteran programmers. Once an experienced programmer has spent enough time picking apart badly designed code, it can become the dominant factor in his assessment of all the code he sees. I've experienced this myself fairly often: code that could be easily made a little more readable makes me itch; code that can't easily be fixed that was written with no thought for readability can be quite upsetting. But writing readable code is extra work, so people who haven't spent dozens of hours staring at a debugger prompt are sometimes baffled by the strong emotions these situations inspire. Why is it such a big deal to make that variable global? It works, after all.

Every program has at least one bug and can be shortened by at least one instruction — from which, by induction, it is evident that every program can be reduced to one instruction that does not work. — Ken Arnold

When considering how to write readable code, choice of audience matters a lot. Who's going to read what you're writing? When? For writing prose, we do this all the time. We use quite different style in a chat message or email than in a blog post, and a different style again in a formal letter or article. The wider your audience and the longer the duration you expect the message to be relevant, the more work you put into style, clarity, and readability. The same applies to code. Are you writing a one-off script that's only a few dozen lines long? Using global variables and one-letter identifiers is probably not going to hurt you, because you will most likely delete the code rather than read it again. Writing a library for use in more than one program? Be very careful about using any global state at all. (Also pay special attention to the names you give your classes/modules/functions; they may be very difficult to change later.) If new programmers were taught this idea as well as they're taught how to, e.g., override methods in a class or invoke standard libraries, it would be a lot easier for both new programmers and those mentoring them to relax.

So when you do set out to write readable code, consider your audience. There are some obvious parties to consider. If you're writing a library, your users will certainly read some of your code, even if it's just examples of how to use your library. Anyone who wants to modify your code later will need to read it. If your code is packaged by an OS distribution or other software collection, the packager will often need to read parts of your code to see how it interacts with other elements of the system. Security auditors will want to read your code to know how it handles the authority it's granted or the secrets it protects. And not least, you're writing for your future self! So even if those other people don't exist or don't matter to you — make life easier on that last guy. He'll thank you for it.

Coroutines reduce readability

A recent email thread was brought to my attention which suggested adding greenlet-style coroutines to the Python standard library. I felt like this would be a good time to go into why coroutines are a bad idea.

"Readability counts."

Many keyboards have been worn out debating how to make code more readable, and what affects readability. One of the reasons I've enjoyed using Python so much is that it doesn't fight (much) my efforts to write code that's easy to read. Proponents of coroutines, as used in libraries such as gevent, have claimed that a major advantage is that they make networking code easier to read, compared to other concurrency mechanisms such as generators or callbacks. I am going to argue instead that coroutines make code harder to read. Before I get into that, I'm going to propose this definition of readability:

A program is readable when you can look at its code and understand what it does.

Note particularly that this is different from looking at code and understanding what the author intended the program to do. Readability counts most when you're reading code that doesn't work (such as when debugging) or code that might not work the way it should (such as when doing a security audit). Designing for readability means designing for adversarial review of code.

As Mark Miller and Dave Herman have pointed out, when first learning to program in a language like Python, there are some basic assumptions we make about control flow. The main one I want to talk about here is that it's possible to understand what happens when you call a function by reading the code of the function.

Consider this trivial example.

self._foo.a = self._foo.b
self._foo.b = baz()

Suppose you want to determine whether any code can see self or self._foo while its internal attributes are disarranged — in this case, the time during which its a and b attributes are set to the same value. Normally in Python we'd be able to answer this question by reading the source for baz. However, in the presence of coroutines this isn't sufficient! If baz, or anything it calls, invokes something that causes the current coroutine to suspend, then any other code can be invoked at that point, thus making it impossible to keep this internal mutation from being exposed.

"In the face of ambiguity, refuse the temptation to guess."

There's many different situations where this sort of problem arises. In general, any kind of imperative code needs to be able to preserve invariants for its data structures, while still being able to do work that might temporarily violate those invariants. This is why Python has the with and try/finally structures; being able to express some level of transaction-like behaviour is useful, so you can worry about cleanup and invariants at a single place.

These are only useful for operations that aren't extended in time, however. When using coroutines, it's possible to write code where finally blocks don't get a chance to run before something in another coroutine interferes. More distressingly, the finally block may not run at all! When a coroutine is suspended, there's no guarantee it will be resumed before the program terminates.

If this sounds a lot like using threads, it's because it is. Coroutines are a form of threads; they're the foundation for what are called "green threads" in some language runtimes, such as early versions of Java and Ruby. The problems with threads are well documented, and various tools developed to deal with the problems they introduce, such as mutexes, locks, and queues. Not all coroutine libraries provide these tools, and the ones that do don't encourage their pervasive use. The only salient difference in behavior is that OS-provided threads can be interrupted at more points. On the other hand, OS threads can be scheduled on multiple processors at once, providing parallelism. So, in conclusion: coroutines are strictly worse than threads, because they have the same kinds of problems (non-determinism, loss of code readability) and do not offer any unique advantages.

Superior options for concurrency are use of Deferreds to manage callbacks, or generators. The primary historical objection to callbacks is the "pyramid of doom", where functions get nested to ridiculous depths. Deferreds make callback-invoking code composable, and help flatten out the functions used, as David Reid has ably shown. Use of callbacks/Deferreds lets you keep all your normal assumptions about control flow. Invoking a function can return a Deferred, but it can't do anything to suspend your code calling it. Once a function is exited, it can't be re-entered without calling it again. So in a very useful sense, Deferreds make concurrent code much more readable.

Generators let you keep most of your assumptions, but they add an extra rule: a function can be suspended and (maybe) later re-entered when a yield keyword is encountered. This provides the same amount of information as callbacks, but does enable some cases that require a good bit more squinting and head-scratching to figure out.

I believe that better syntax can provide the convenience of generators and the clarity benefits of Deferreds. More about that in a future post.

Exocet: A Second Look

So what I didn't really talk about last time is that more than just letting you directly express module loading, Exocet also implements:

Parameterized Modules

In Python, classes and functions take parameters, but modules don't. When you load a module, you don't have any opportunity to tell it what you want, or what context it's being loaded in. A lot of times, this matters.

For example, some code has optional dependencies. This idiom can be seen a lot in some parts of Twisted:

try:
    from OpenSSL import SSL
except ImportError:
    SSL = None

Code following this checks if 'SSL' is None to decide whether to define methods and classes that provide support for SSL connections in Twisted.


Other code can depend on one of multiple providers of an interface. Here's the famous example from the docs for the magnificent lxml library:

try:
  from lxml import etree
  print("running with lxml.etree")
except ImportError:
  try:
    # Python 2.5
    import xml.etree.cElementTree as etree
    print("running with cElementTree on Python 2.5+")
  except ImportError:
    try:
      # Python 2.5
      import xml.etree.ElementTree as etree
      print("running with ElementTree on Python 2.5+")
    except ImportError:
      try:
        # normal cElementTree install
        import cElementTree as etree
        print("running with cElementTree")
      except ImportError:
        try:
          # normal ElementTree install
          import elementtree.ElementTree as etree
          print("running with ElementTree")
        except ImportError:
          print("Failed to import ElementTree from any known place")

The effect of this code is to try to import, in order, one of:

1. lxml
   
2. cElementTree from the stdlib
   
3. ElementTree from the stdlib
   
4. ElementTree installed separately
   
5. cElementTree installed separately
   

I don't think it's a stretch to say this is rather silly. How would you feel if you saw a function that tried to access five different global variables in a row in order to decide what to do?

And though all of these modules implement the same interface, they're still different code, and you might hit some edge case where their behaviour differs. How do you test your code using each possible ElementTree implementation? As Glyph points out, it's always sunny in Python, and every piece of bad code can be worked around by writing worse code; you could have your unit tests fool around with sys.modules. But can't there be something better?

Here's a different way of thinking about it entirely.

In languages that aren't as good as Python, dependency injection is a technique that gets used to deal with this. Dependency injection has many forms and can be rather complicated, but the general idea is code declares the thing it needs, and something else (unfortunately, often an XML file!) describes what objects to provide to satisfy those dependencies.


With Exocet, we hijack the import statement to describe named parameters, indicating the dependencies our code has.

from exocet.parameters import etree

x = etree.parse(open("mydata.xml"))

Now, if you look in the Exocet tarball, you won't find a parameters.py file. This name doesn't correspond to anything on the filesystem.

So how does this help us? Well, it means you can load your ElementTree-using module like this:

m = exocet.pep302Mapper.withOverrides({"exocet.parameters.etree",
                                       xml.etree.cElementTree})
my_etree_using_module = exocet.loadNamed("my_etree_using_module", m)

Or this:

m = exocet.pep302Mapper.withOverrides({"exocet.parameters.etree",
                                        lxml.etree})
my_etree_using_module = exocet.loadNamed("my_etree_using_module", m)

This way, you can test your code without having to resort to sys.modules hackery, and you can better factor your applications by separating configuration and environment concerns from the rest of your code.

As you may recall from last time, pep302Mapper provides the default Python implementation of module loading. In this case, we've just added another name that can be imported, exocet.parameters.etree.

Being able to provide parameters to modules opens up the possibility to eliminate all use of global objects from your code, and pass objects only to the code that needs them. I believe that with experimentation and refinement of these tools, this technique is going to enable a lot of simpler methods for organizing complex applications and reduce a lot of complications people have to deal with in Python now.

Introducing Exocet

Last time I talked about the deficiencies of Python's module system. Now I'd like to talk about a solution to them.

There are two questions related to Python's module system that come up repeatedly on #python, and don't have obviously good answers.

1. How do I reload a module?


2. How do I create a plugin system?

Exocet was written primarily to answer these questions.

Download Exocet 0.5

What is Exocet?

Exocet is a new way to load Python modules. It separates the act of naming a dependency from the act of creating a module object. As a result, more than one instance of a module can be created from the same source file. Also, when creating a module object, precise control can be exerted over what it's allowed to import.

Let's start with a code example.

>>> import exocet, httplib 
>>> urllib = exocet.loadNamed("urllib", exocet.pep302Mapper) 
 
>>> def HTTP_Ex(host): 
...     print "making HTTP connection to", host 
...     return httplib.HTTP(host) 
... 
 
>>> class _ModuleProxy(object): 
...     def __getattribute__(self, name): 
...           if name == 'HTTP': 
...               return HTTP_Ex 
...           else: 
...               return getattr(httplib, name) 
 
>>> httplib_plus = _ModuleProxy() 
>>> overriddenMap = exocet.pep302Mapper.withOverrides({"httplib": httplib_plus}) 
>>> urllib_plus = exocet.loadNamed("urllib", overriddenMap) 
 
>>> print urllib.urlopen("http://python.org").read(121) 
<!DOCTYPE html PUBLIC "-//W3C//DTD XHTML 1.0 Transitional//EN" "http://www.w3.org/TR/xhtml1/DTD/xhtml1-transitional.dtd"> 
 
>>> print urllib_plus.urlopen("http://python.org").read(121) 
making HTTP connection to python.org 
<!DOCTYPE html PUBLIC "-//W3C//DTD XHTML 1.0 Transitional//EN" "http://www.w3.org/TR/xhtml1/DTD/xhtml1-transitional.dtd"> 

Quick breakdown of what's going on here: loadNamed takes a module name and a mapper object, and returns a new module object. Note that this is very different from what import does; each invocation of loadNamed returns a new module object, unrelated to any previous ones.

The mapper object is responsible for intercepting all import calls made by the module being loaded. The pep302Mapper object used here just invokes Python's normal importing behaviour, caching loaded modules in sys.modules. But its withOverrides method creates a new mapper, one that looks in a dict first. The urllib_plus module is almost like the urllib module in this example, with one difference: the latter got the real httplib module when it executed the statement import httplib; urllib_plus got the httplib_plus module when it ran that statement. The other mapper that Exocet includes by default is emptyMapper, in which all import statements will fail. You can construct your own, providing any object under any name to be available to import statements in modules you load.

So after constructing these two modules, they're usable as normal. The only difference is that urllib_plus invokes our wrapper function when it calls httplib.HTTP(), producing the printed line before proceeding with its work.

So, how does this behaviour answer the questions I mentioned earlier?

Module reloading

As we saw last time, reload isn't suitable for real-world use; it changes things around too much in some places, not enough in others. With Exocet, you don't have to reload modules because you can just load them. When you want a new module with updated code, you just load it and have a new module object. All the old objects still exist as long as you want them to; there's no orphaned-instance problem. If you need new versions of the module's dependencies you can load them first and put them in the mapper so that they're visible to your new module. Old instances, classes, and modules can be removed in the normal way — by Python's garbage collection, when nothing uses them any longer.

Plugin systems

The normal use of Python packages and modules involves importing specific ones by name. However, sometimes you want to load a bunch of modules and call something in each. Since Exocet borrows code from twisted.python.modules, it's possible to iterate over a package and load each module in it:

>>> import exocet 
>>> [exocet.load(x, exocet.pep302Mapper) for x in 
...  exocet.getModule("twisted.plugins").iterModules()] 
[<module 'twisted.plugins.cred_anonymous' from '/home/washort/Projects/Twisted/trunk/twisted/plugins/cred_anonymous.py'>, 
 <module 'twisted.plugins.cred_file' from '/home/washort/Projects/Twisted/trunk/twisted/plugins/cred_file.py'>, 
<module 'twisted.plugins.cred_memory' from '/home/washort/Projects/Twisted/trunk/twisted/plugins/cred_memory.py'>, 
<module 'twisted.plugins.cred_unix' from '/home/washort/Projects/Twisted/trunk/twisted/plugins/cred_unix.py'>, 
<module 'twisted.plugins.twisted_conch' from '/home/washort/Projects/Twisted/trunk/twisted/plugins/twisted_conch.py'>, 
<module 'twisted.plugins.twisted_ftp' from '/home/washort/Projects/Twisted/trunk/twisted/plugins/twisted_ftp.py'>, 
<module 'twisted.plugins.twisted_inet' from '/home/washort/Projects/Twisted/trunk/twisted/plugins/twisted_inet.py'>, 
<module 'twisted.plugins.twisted_lore' from '/home/washort/Projects/Twisted/trunk/twisted/plugins/twisted_lore.py'>, 
<module 'twisted.plugins.twisted_mail' from '/home/washort/Projects/Twisted/trunk/twisted/plugins/twisted_mail.py'>, 
<module 'twisted.plugins.twisted_manhole' from '/home/washort/Projects/Twisted/trunk/twisted/plugins/twisted_manhole.py'>, 
<module 'twisted.plugins.twisted_names' from '/home/washort/Projects/Twisted/trunk/twisted/plugins/twisted_names.py'>, 
<module 'twisted.plugins.twisted_news' from '/home/washort/Projects/Twisted/trunk/twisted/plugins/twisted_news.py'>, 
<module 'twisted.plugins.twisted_portforward' from '/home/washort/Projects/Twisted/trunk/twisted/plugins/twisted_portforward.py'>, 
<module 'twisted.plugins.twisted_qtstub' from '/home/washort/Projects/Twisted/trunk/twisted/plugins/twisted_qtstub.py'>, 
<module 'twisted.plugins.twisted_reactors' from '/home/washort/Projects/Twisted/trunk/twisted/plugins/twisted_reactors.py'>, 
<module 'twisted.plugins.twisted_runner' from '/home/washort/Projects/Twisted/trunk/twisted/plugins/twisted_runner.py'>, 
<module 'twisted.plugins.twisted_socks' from '/home/washort/Projects/Twisted/trunk/twisted/plugins/twisted_socks.py'>, 
<module 'twisted.plugins.twisted_telnet' from '/home/washort/Projects/Twisted/trunk/twisted/plugins/twisted_telnet.py'>, 
<module 'twisted.plugins.twisted_trial' from '/home/washort/Projects/Twisted/trunk/twisted/plugins/twisted_trial.py'>, 
<module 'twisted.plugins.twisted_web' from '/home/washort/Projects/Twisted/trunk/twisted/plugins/twisted_web.py'>, 
<module 'twisted.plugins.twisted_web2' from '/home/washort/Projects/Twisted/trunk/twisted/plugins/twisted_web2.py'>, 
<module 'twisted.plugins.twisted_words' from '/home/washort/Projects/Twisted/trunk/twisted/plugins/twisted_words.py'>] 

In this case we used the default pep302Mapper since we wanted plugin modules to be able to import anything they wanted. However, a different mapper could be provided which provided different modules, limited them to only importing certain ones, or none at all.

Unit testing

Hardly anybody asks about this on #python, but they should. By loading the modules you test with Exocet, you can replace their dependencies with stubs without monkeypatching. Just provide overrides to the mapper object when loading the module, and you have a stubbed or mocked module to test without altering the behaviour of other tests.

Next steps

Exocet lets you load most existing Python modules, but in a way that gives much better control over what happens. This makes room for radically different ways of thinking about how to organize Python programs. Since this approach is so different, practice is needed to come up with new idioms for how to use it effectively. I've tried carefully to provide mechanism here with very little policy. There are a few kinks to still work out in how Exocet works in more complicated scenarios, but give it a try! It might be just the thing for your next IRC bot. ;-)

If you want to help with Exocet development, it happens here, on Launchpad. I look forward to your feedback.

Modules in Python: the Good, the Bad, and the Ugly

I've spent a lot of time living with Python's module system, both in my own
work and in helping people on Freenode's #python channel. A lot of Python's
power comes from its module system; however, it could be better. It can be
hard to think about how modules could be done differently, since it's so
central to the design of Python software, but it's worth the effort. Here's
some stuff I've been thinking about.

The Good

No global namespace for objects

This is the benefit of module systems in general and it's a big one. It's what I miss the most when writing in C, for example (And until very recently — Javascript!) Being able to treat a source file as an actual container for code instead of an arbitrary pile of functions and variables with no structure makes code much easier to comprehend and navigate.

Python modules are easy to write and to import

Particularly I'm comparing this to Scheme 48 and ML, which both have very well-designed and powerful module systems, but they're rather confusing to the newcomer because they require a good bit of up-front knowledge to construct a module that's useful to anyone else. In Python, you just stick some code in a file and then all the names in it are importable. My earliest Python memory was joining #python and asking "how do I import some code I wrote in one file into another"? I was told 'for a file named foo.py, use "import foo"'. My reaction was "Really? That's all?" Providing a low barrier to entry for creating and using modules is an extremely powerful advantage of Python.

The Bad

Modules are in a global namespace

Although modules contain classes, functions, etc., there's no containment hierarchy for module names themselves. Different modules can have functions and classes with the same name in them, but there's nothing that can contain multiple modules with the same name. This shows up as a problem when you want to write unit tests that use fake versions of some modules, for example. When faking a function or a class, one creates a new version. Modules generally have to be modified rather than replaced, since import looks up modules in the global module namespace.

PYTHONPATH is a rather inflexible way to organize modules

Organizing modules by location in the filesystem is a great way to get started, but it's not the only possible thing one might want. This deficiency has been addressed in recent Pythons via the PEP 302 import hooks. However...

PEP302 hooks help, but aren't enough by themselves

The canonical example of alternate module organization is putting them in a zip file, which Python supports via the standard import hooks now. Now you have extra problems, though. Python packages are a good way to organize modules, but they don't provide a way to enumerate their contents. To work around this, everybody looks at the filesystem layout to determine what's in a package. But if your modules aren't being loaded directly from the filesystem, this approach won't work.

The Really Bad

Modules are singletons (i.e., global mutable state)

This is the dark secret at the heart of any large-scale Python project. One can be very careful about organizing one's state into instances and so forth, but all modules are still visible and modifiable by any code at any time.

Still easy to write unreadable code via monkey-patching

It's easy and convenient to assign to module attributes any time you feel like it. The result is that any time you see "from foo import someObject", you can't every be sure about where that object was defined unless you read all the source code in the application. Even when it's desirable to change module contents (such as for tests), it's easy to fail to do so in a way that doesn't introduce dependencies or conflicts between tests. The classic example is calling some function that initializes module globals from a config file; if one test does it, it can cause tests run after it to fail or incorrectly succeed.

reload()

The reload function is a symptom of all the above problems. Its inspiration is obvious: loading code that's changed since the current Python process has started is an entirely sensible idea. However, Python's assumptions about how modules work makes this rather difficult to do in a sensible manner. It's common to create new lists rather than modify old ones when a new version of some data is wanted. This convention is reinforced by the ease by which list comprehensions can be used to do this job. The convention encouraged by the existence of reload is exactly opposite, though — instead of creating a new module object, the old one is emptied and refilled with fresh objects. The result is that instances of classes in that module are orphaned; the class they were instantiated from can't be reached by its name. Also, it only reloads a single module; no help is provided in updating modules that depend on it, or updating its own dependencies. Figuring out which modules to reload or not reload at any given time is often very tricky. Plenty of other corner cases exist, such as reinitialization of function default arguments, and so forth. Because of all this, the standard advice on #python is that "reload will not make you happy".

What Now?

So with these problems identified in how Python handles modules, can anything be done?
Well, that's why I wrote Exocet. More about that next time.

Unicode in Python, and how to prevent it

[UPDATE 16 Aug 2011] Armin Ronacher has written a nice module called unicode-nazi that provides the Unicode warnings I discuss at the end of this article.

Though I can't use Python 3 for any of my projects, it does have a few nice things. One particular behaviour where it improves on Python 2 is forbidding implicit conversions between byte strings and Unicode strings. For example:

Python 3.1.2 (release31-maint, Sep 17 2010, 20:34:23)

[GCC 4.4.5] on linux2

Type "help", "copyright", "credits" or "license" for more information.

>>> 'foo' + b'baz'

Traceback (most recent call last):

  File "<stdin>", line 1, in <module>

TypeError: Can't convert 'bytes' object to str implicitly

If you do this in Python 2, it invokes the default encoding to convert between bytes and unicode, leading to manifold unhappinesses. So in Python 2, the above example looks like:

Python 2.6.6 (r266:84292, Sep 15 2010, 15:52:39)

[GCC 4.4.5] on linux2

Type "help", "copyright", "credits" or "license" for more information.

>>> u'foo' + b'baz'

u'foobaz'

This looks OK, but problems lurk just below the surface. The default encoding used in nearly all circumstances is ASCII, and this conversion will blow up if non-ASCII bytes are involved.

>>> u'foo' + b'\xe2\x98\x83'

Traceback (most recent call last):

  File "<stdin>", line 1, in <module>

UnicodeDecodeError: 'ascii' codec can't decode byte 0xe2 in position 0: ordinal not in range(128)

This is only a 3, at best 3.5 on the Russell scale of API misusability. Even worse, this conversion is done for any function implemented in C that expects unicode or bytes and receives the other type. For example, unicode() converts byte strings to unicode strings, and if not given an explicit encoding argument, uses the default encoding.

>>> unicode('bob')

u'bob'

>>> unicode('\xe2\x98\x83')

Traceback (most recent call last):

  File "<stdin>, line 1, in 

UnicodeDecodeError: 'ascii' codec can't decode byte 0xe2 in position 0: ordinal not in range(128)

The right way to do it is call .decode() on the byte string.

>>> '\xe2\x98\x83'.decode('utf8')

u'\u2603'

Just be sure you don't call it on a unicode string by mistake, or you'll get very confused:

>>> u'foo'.decode('utf8')

u'foo'

>>> u'\u2603'.decode('utf8')

Traceback (most recent call last):

  File "<stdin>", line 1, in ?

  File "/usr/lib/python2.4/encodings/utf_8.py", line 16, in decode

    return codecs.utf_8_decode(input, errors, True)

UnicodeEncodeError: 'ascii' codec can't encode character u'\u2603' in position 0: ordinal not in range(128)

Hey! That error says "encode", but we asked for it to decode!

It turns out that since the utf8 decoder expects bytes as input, but we gave it unicode... Python helpfully tries to convert the unicode characters into bytes, using the default encoding! This is why the first decode call succeeds - all the characters in it can be converted to ASCII bytes.

Is there any hope?

Since Unicode was added to Python in 2.1, there's been a way to get Python 3's behavior. The site module in the Python standard library sets Python's default encoding on startup. If edited to use "undefined" instead of "ascii", the above examples all fail instead of converting:

>>> u'foo' + baz



Traceback (most recent call last):

  File "<stdin>", line 1, in 

  File "/usr/lib/python2.6/encodings/undefined.py", line 22, in decode

    raise UnicodeError("undefined encoding")

UnicodeError: undefined encoding

So why can't we switch to this today? Well, for one thing, lots and lots of code depends on this implicit encoding/decoding. Even code in the standard library:

Traceback (most recent call last):

  File "<stdin>", line 1, in <module>

  File "/usr/lib/python2.6/re.py", line 190, in compile

    return _compile(pattern, flags)

  File "/usr/lib/python2.6/re.py", line 243, in _compile

    p = sre_compile.compile(pattern, flags)

  File "/usr/lib/python2.6/sre_compile.py", line 506, in compile

    p = sre_parse.parse(p, flags)

  File "/usr/lib/python2.6/sre_parse.py", line 672, in parse

    source = Tokenizer(str)

  File "/usr/lib/python2.6/sre_parse.py", line 187, in __init__

    self.__next()

  File "/usr/lib/python2.6/sre_parse.py", line 193, in __next

    if char[0] == "\\":

  File "/usr/lib/python2.6/encodings/undefined.py", line 22, in decode

    raise UnicodeError("undefined encoding")

UnicodeError: undefined encoding

Not to mention loads of existing third-party apps and libraries. So what can we do? Fortunately, Python allows registering new codecs. I've written a slight variation on the ASCII codec, ascii_with_complaints, which preserves the default Python behaviour, but also produces warnings.

>>> import re

>>> re.compile(u'\N{SNOWMAN}+')

/usr/lib/python2.6/sre_parse.py:193: UnicodeWarning: Implicit conversion of str to unicode

  if char[0] == "\\":

/usr/lib/python2.6/sre_parse.py:418: UnicodeWarning: Implicit conversion of str to unicode

  if this and this[0] not in SPECIAL_CHARS:

/usr/lib/python2.6/sre_parse.py:421: UnicodeWarning: Implicit conversion of str to unicode

  elif this == "[":

/usr/lib/python2.6/sre_parse.py:478: UnicodeWarning: Implicit conversion of str to unicode

  elif this and this[0] in REPEAT_CHARS:

/usr/lib/python2.6/sre_parse.py:480: UnicodeWarning: Implicit conversion of str to unicode

  if this == "?":

/usr/lib/python2.6/sre_parse.py:482: UnicodeWarning: Implicit conversion of str to unicode

  elif this == "*":

/usr/lib/python2.6/sre_parse.py:485: UnicodeWarning: Implicit conversion of str to unicode

  elif this == "+":

<_sre.SRE_Pattern object at 0xb76d6f80>

Hopefully this will be useful as a tool for ferreting out those Unicode bugs waiting to break your application, as well.

The true blue fate with an artificial calendar

In case you were wondering, here's what I've been busy with lately.

I haven't given up on Python yet. Stay tuned, big stuff on the way.

Two-thirds slow, one-third amazing

My evident neglect of this site was not intentional. Moving across the country and starting a new job tend to reduce one's available time for open source work, and mine hasn't resulted in anything really worth announcing for the past year (or more). But today that changes!

Download PyMeta 0.4.0

Since the last release of Ecru I have been trying to get rid of its dependency on Python, by porting the E parser to E. In the process of doing so, I realized it was probably a bad idea to try to use a parser whose only form of error reporting was the string "Parse error". Since I'm still more familiar with Python than E, I started implementing error reporting in PyMeta. (Also, Python has a debugger.) This resulted in some significant rewrites of the internals.

So what's different in PyMeta 0.4?

Comments!

With its new space-age technology, PyMeta 0.4 will treat '#' as a comment character, just like Python. (Yes, this was rather overdue.)

Reorganized code generator

Previously, code for grammars was generated by the grammar parser calling methods on a builder object that directly emitted Python code as strings. Now the grammar parser builds a tree, which is then consumed by a code generator. If you want to generate something other than Python (or change how Python code gets generated), it should be a lot simpler now. Look at pymeta.builder.PythonWriter for specifics, specifically the generate_ methods.

Error tracking and reporting

This is the big one. Previously, PyMeta expressions returned a value or raised an error. Now, each expression evaluated by the parser now returns a value and an error, even if a successful parse was found. If parse failure occurs, an error still gets raised. Combining expressions with "|" returns the error from furthest into the input and combines ties.

So the result of this is that you can now get nicely formatted output telling you where stuff went wrong and how. Here's an example, based on the old TinyHTML parser:


When you mismatch tags, the parser notices:


Notice here that the information in ParseError is structured so that future tools can figure out stuff about what failed and how.

If there's more than one possible valid input at the point of failure, the parser will tell you:

Plans for the Future

There are a few directions I'd like to take PyMeta in the future. A really nice thing would be to have a way to generate grammars ahead of time easily, writing out a Python module. This release includes bin/generate_parser which does a rather naive version of this. The problem is figuring out how to make grammars that are subclasses of something other than just OMetaBase.
Also, with the new code generator setup, it'd be fairly easy to generate Cython instead of Python, resulting in grammars that can be compiled as extension modules, hopefully resulting in much faster parse times. PyMeta isn't meant to be blazingly fast -- PEG parsers aren't known to be the most efficient -- but it'd be nice to squeeze all we can out of it.

Other people have asked for event based parsing and incremental output. Seems like a neat idea... I'd just have to figure out what that means. :-)

Special thanks to Marien Zwart and Cory Dodt for their contributions and encouragement for this release.

Ecru 0.2.0

It's been a bit longer for this release.



The major new additions are message buffering on eventual references and the Ref.whenResolved and Ref.whenBroken methods, as well as the __whenMoreResolved Miranda method. Along with eventual sends and the vat support from the previous release, this is enough to provide support for the when syntax sugar. The Python interface now can control the E event loop: ecru.api.iterate runs a single item in the queue of the vat exposed to Python, and ecru.api.incrementalEval queues an E expression to be run, returning a promise to Python immediately. There's an example IRC-bot REPL in doc/examples/ircbot.py.

Special shout-out to Eric Mangold (aka teratorn) for bugfixes and testing. Thanks Eric!

Ecru 0.1.3

Time for another Ecru release. This release should be a lot more stable: ctypes is no longer used for the Python interface. The major behaviour change I've added is support for Selfless objects, allowing for value equality: for example, Map objects with the same contents now compare equal. The rest of the work has been in code reorganization and preparation for concurrency support; vats are implemented now, and the REPL executes code by putting it into the vat's event queue. Eventual sends work now (i.e., "foo <- doStuff(x, y)"). Goals for the next couple releases are actual multi-vat execution, support for the 'when' expression, and portability to other OSes.

Ecru, A C Runtime For E

I'm happy to announce Ecru, a new implementation of the E language.



E is a language designed both for security and safe and efficient concurrency. Twisted borrowed the idea of Deferreds from E, where they are much better integrated into the language than in Python, owing to the syntax and library support E provides. E's design is based around capability security, even to the level of allowing mutually untrusting programs to run in the same process. Due to its consistent focus on security, it's possible to write secure programs without having to do much more than stick to good object-oriented style.

My goals with Ecru development are, initially, to develop an environment suitable for restricted execution of the type that my esteemed colleague has been looking for, allowing safe scripting of server-hosted applications. A wider goal is to provide an effective replacement to the C implementation of Python for development of network software; a successor to Twisted, as it were. Furthermore, E's semantics lend themselves to more efficient implementation than Python's. Although Ecru has received essentially no optimization work thus far, I believe it may be possible to make it faster than Python for many tasks, without being any more difficult to work with.



Right now Ecru depends on Python, since I'm using PyMeta for its parser. Ecru only implements enough of E to run the compiler; I plan to soon implement OMeta in E, so that Ecru can also be used standalone. There's a simple REPL in Python, so you can download Ecru and try it out right now. Currently I'm focusing on cleaning up the code (bootstraps are usually messy affairs) and replacing some of the standard-library object stubs I wrote in C with the versions implemented in E in use by the existing Java version.

PyMeta 0.3.0 Released

Originally when I was implementing PyMeta I was sure that the input stream implementation that the Javascript version used was inefficient. Rather than having a mutable object with methods for advancing and rewinding the stream, it has immutable objects with "head" and "tail" methods, which return the value at the current position and a new object representing the next position in the stream. All that allocation couldn't be healthy.

Turns out I was wrong. I misunderstood the requirements for OMeta's input stream. Various operations require the ability to save a particular point in the stream and go back to it. To further complicate matters, arguments to rules are passed on the stream by pushing them onto the front, and rules that take arguments read them off of the stream. This is very handy for certain types of pattern matching, but it totally destroys any hope of simply implementing the input as a list and an index into it, because there has to be a way to uniquely identify values pushed onto the stream. If a value gets pushed onto the stream, is read from it, then another one is pushed on, both of them have the same predecessor, but they don't have the same stream position. It becomes more like a tree than a sequence. JS-OMeta handled this by just creating a new stream object for each argument. I didn't give up soon enough on my clever idea when initially implementing PyMeta, and it grew more complicated with each feature I implemented, involving a bunch of lists for buffering things and a complicated mark/rewind scheme.

After writing a rather complicated grammar with PyMeta, I began to wonder if I could improve its speed. By this time I knew the JS version's algorithm was less complicated so I decided to try it out. It cut my grammar's unit tests' runtime from around 40 seconds to 4 seconds. Also, it fixed a bug.



Moral of the story: I'm not going to try to implement clever optimizations until I understand the original version any more. :)

I've released a version with this new input implementation. Get it in the usual place.

More Than Just Parsers

PyMeta is more than just a parsing framework, it's a general pattern matching language. Here's a parser for a tiny HTML-like language:

from pymeta.grammar import OMeta
from itertools import chain

tinyHTMLGrammar = """

name ::= <letterOrDigit>+:ls => ''.join(ls)

tag ::= ('<' <spaces> <name>:n <spaces> <attribute>*:attrs '>'
         <html>:c
         '<' '/' <token n> <spaces> '>'
             => [n.lower(), dict(attrs), c])

html ::= (<text> | <tag>)*

text ::= (~('<') <anything>)+:t => ''.join(t)

attribute ::= <spaces> <name>:k <token '='> <quotedString>:v => (k, v)

quotedString ::= (('"' | '\''):q (~<exactly q> <anything>)*:xs <exactly q>
                     => ''.join(xs))

"""
TinyHTML = OMeta.makeGrammar(tinyHTMLGrammar, globals(), name="TinyHTML")

This will parse an HTML-ish string into a tree structure.

Python 2.5.2 (r252:60911, Apr 8 2008, 21:49:41)
[GCC 4.2.3 (Ubuntu 4.2.3-2ubuntu7)] on linux2
Type "help", "copyright", "credits" or "license" for more information.
>>> import html
>>> x = html.TinyHTML("<html><title>Yes</title><body><h1>Man, HTML is
 <i>great</i>.</h1><p>How could you even <b>think</b> 
otherwise?</p><img src='HIPPO.JPG'></img><a 
href='http://twistedmatrix.com'>A Good Website</a></body></html>")

>>> tree = x.apply("html")

>>> import pprint

>>> pprint.pprint(tree)
[['html',
  {},
  [['title', {}, ['Yes']],
   ['body',
    {},
    [['h1', {}, ['Man, HTML is ', ['i', {}, ['great']], '.']],
     ['p',
      {},
      ['How could you even ', ['b', {}, ['think']], ' otherwise?']],
     ['img', {'src': 'HIPPO.JPG'}, []],
     ['a', {'href': 'http://twistedmatrix.com'}, ['A Good Website']]]]]]]

Suppose now that we want to turn this tree structure back into the HTMLish format we found it in. We can write an unparser:

def formatAttrs(attrs):
    """
    Format a dictionary as HTML-ish attributes.
    """
    return ''.join([" %s='%s'" % (k, v) for (k, v) in attrs.iteritems()])


unparserGrammar = """
contents ::= [<tag>*:t] => ''.join(t)
tag ::= ([:name :attrs <contents>:t]
            => "<%s%s>%s</%s>" % (name, formatAttrs(attrs), t, name)
         | <anything>)
"""

TinyHTMLUnparser = OMeta.makeGrammar(unparserGrammar, globals(), name="TinyHTMLUnparser")

Square brackets in a rule indicate that a list with the given contents should be matched. This way we can traverse a tree structure and produce a string.

>>> html.TinyHTMLUnparser([tree]).apply("contents")
"<html><title>Yes</title><body><h1>Man, HTML is 
<i>great</i>.</h1><p>How could you even <b>think</b> 
otherwise?</p><img src='HIPPO.JPG'></img>
;<a href='http://twistedmatrix.com'>A Good Website</a></body></html>"

Other sorts of transformations are possible, of course: here's an example that ignores everything but the 'src' attribute of IMG and the 'href' attribute of A:

linkExtractorGrammar = """
contents ::= [<tag>*:t] => list(chain(*t))
tag ::= ( ["a" :attrs ?('href' in attrs) <contents>:t] => ([attrs['href']] + t)
        | ["img" :attrs ?('src' in attrs) <contents>:t] => ([attrs['src']] + t)
        | [:name :attrs <contents>:t] => t
        | :text => [])
"""

LinkExtractor = OMeta.makeGrammar(linkExtractorGrammar, globals(), name="LinkExtractor")

>>> html.LinkExtractor([tree]).apply("contents")

['HIPPO.JPG', 'http://twistedmatrix.com']

And here's an example that produces another tree, without B or I elements:

boringifierGrammar = """
contents ::= [<tag>*:t] => list(chain(*t))
tag ::= ( ["b" <anything> <contents>:t] => t
        | ["i" <anything> <contents>:t] => t
        | [:name :attrs <contents>:t] => [[name, attrs, t]]
        | :text => [text])
"""

Boringifier = OMeta.makeGrammar(boringifierGrammar, globals(), name="Boringifier")

And once we have the new tree, we can treat it just like the original:

>>> tree2 = html.Boringifier([tree]).apply("contents")
>>> pprint.pprint(tree2)
[['html',
  {},
  [['title', {}, ['Yes']],
   ['body',
    {},
    [['h1', {}, ['Man, HTML is ', 'great', '.']],
     ['p', {}, ['How could you even ', 'think', ' otherwise?']],
     ['img', {'src': 'HIPPO.JPG'}, []],
     ['a', {'href': 'http://twistedmatrix.com'}, ['A Good Website']]]]]]]
>>> html.TinyHTMLUnparser([tree2]).apply("contents")
"<html><title>Yes</title><body><h1>Man, HTML is 
great.</h1><p>How could you even think otherwise?</p><img src='HIPPO.JPG'>
</img><a href='http://twistedmatrix.com'>A Good Website</a></body>
</html>"

As you can see, the final result shows the original string, but with <b> and <i>tags removed.

This kind of tree transformation is highly useful for implementing language tools, and might form a good basis for a refactoring library. Analysis can be done on the syntax tree produced by the parser, transformation can be done by other tools, and the unparser can then turn it back into valid source code.

PyMeta: How and Why

(Note: In the course of writing this post, I fixed a bug. Get PyMeta 0.1.1 here.)

Python already has a big pile of parsing frameworks, such as ANTLR, PLY, PyParsing, YAPPS2, ZAPPS, ZestyParser, and plenty others. Why did I write another one?

PyMeta Works Like Python

One of the main difficulties I've had using parser generators has been the difficulty of figuring out why a grammar didn't work. Fixing shift-reduce and reduce-reduce conflicts seemed like voodoo to me, and though I slightly understand better how to fix such things now it's still a different mode of thinking that I don't want to try to get into when I just want to parse something simple. PyMeta uses a variation on the Parsing Expression Grammar (PEG) approach to parsing. The chief consequence of this is there's no possibility of ambiguity in a parse: a successful parse will yield exactly one result, and you can trace the control flow through the grammar to figure out how it got there.

This is possible because the alternative operator ("|") works like Python's "or": it tries all the alternatives in order, returning the value of the first expression to succeed. Let's take on the example that's so problematic in the Bison doc I linked to:

>>> ifExample = """
ifStmt ::= ( <token 'if'> <expr> <token 'then'> <stmt> <token 'else'> <stmt>
           | <token 'if'> <expr> <token 'then'> <stmt>)

expr ::= <spaces> <letter>
stmt ::= <ifStmt> | <expr>
"""

(Rules can take arguments in PyMeta: "token" here is a built-in rule that consumes whitespace and matches all the characters in the string passed to it.) I've reversed the order in 'ifStmt' from the Bison example. This grammar isn't ambiguous: PyMeta will try to match the if/then/else form first, and if that fails, it rewinds back to before the 'if' and tries the if/then branch of the
alternative.

>>> Example = OMeta.makeGrammar(ifExample, {})
>>> g = Example("if x then y")
>>> g.apply("ifStmt")
'y'
>>> g2 = Example("if x then y else if a then b")
>>> g2.apply("ifStmt")
'b'

(Since I didn't specify explicit return values for any of the expressions, they simply return the value of the last expression in the sequence. In this case, "letter" returns the letter it parses, which is then passed up through "expr" and "stmt" and "ifStmt".)

An additional advantage is that you don't need a separate lexer pass: you can handle everything in a single grammar.

PyMeta Lets You Say It Quickly

So why not ZestyParser or PyParsing, which also don't have these problems? There's a couple reasons. First of all, neither of these offer a compact syntax for defining a parser. (Which arguably isn't desirable in all cases; I may add a pyparsing-like interface to PyMeta later.) Second, PyMeta fits Python's object-oriented abilities better -- each grammar is its own class, and can be subclassed in the usual way, as well as extended with new grammar rules.

>>> from pymeta.runtime import ParseError
>>> class Example2(Example):
...  def parseIt(self):
...    try:
...      return self.apply("ifStmt")
...    except ParseError:
...      return "No Good"
...
>>> Example2("if x then y").parseIt()
'y'
>>> Example2("bob's yer uncle").parseIt()
'No Good'
>>> extendedGrammar = """
number ::= <digit>+
expr ::= <super> | <spaces> <number>
"""
>>> Example3 = Example2.makeGrammar(extendedGrammar, {})
>>> Example3("if 1 then x").parseIt()
'x'

Notice here the use of the special rule "super": this calls the grammar rule of the same name as the current one in the superclass. (This uses Python's super() internally.) This way it's possible to try new extensions to a grammar without having to disturb existing code.

Introducing PyMeta

I've just upload the initial release of a Python implementation of Alessandro Warth's OMeta, an object-oriented pattern matching language. Get the tarball here (or simply bzr get lp:pymeta). It's an extremely handy tool for all kinds of parsing and filtering jobs. Here's a tiny example:

>>> exampleGrammar = """
word ::= <letter>+:chars => ''.join(chars)
greeting ::= <word>:x ',' <spaces> <word>:y '!' => (x, y)
"""

Here's a breakdown of the syntax in the first rule: as you can probably tell, "word ::=" defines a parsing rule. "<letter>" calls a builtin rule that matches a single letter. The "+" works similar to its use in regexes, executing the expression before it multiple times and collecting the results into a list. ":chars" binds the result to a local variable, "chars". "=>" is used to provide a Python expression as the result of a successful parse.

The second rule strings multiple expressions together in sequence -- after matching a word, it looks for a comma and then calls the builtin rule "spaces" which matches any amount of whitespace, then another word and finally an exclamation point. Once that's all matched it returns a tuple containing the two matched words.

Using this in a Python program is simple:

>>> from pymeta.grammar import OMeta
>>> GreetingParser = OMeta.makeGrammar(exampleGrammar, {})
>>> gp = GreetingParser("Hello, world!")
>>> gp.apply("greeting")
('Hello', 'world')

In my next few posts I'll be showing more examples of what PyMeta can do and how it's different from other Python parsing tools.