Neopythonic

Compare-And-Set in Memcache

2011-08-25T09:59:00.000-07:00

With the most recent release (1.5.3, last week) App Engine's Python API for Memcache has added a new feature, Compare-And-Set. This feature (with a different API) was already available in Java; it has also been available in the non-App-Engine pure-Python memcache client. In fact, I designed the App Engine Python API for this feature to be compatible with the latter, since most of the rest of the App Engine Python API also strives to be at least a superset of that package.

But what is it? There seems to be little information on how to use Compare-And-Set with memcache. It is also sometimes (incorrectly) referred to as Compare-And-Swap -- incorrect, because the cas() operation does not actually "swap" anything. The first response when we closed the bug requesting this feature was "Some examples of usage are appreciated." So here goes.

The basic use case for Compare-And-Set is when multiple requests that are being handled concurrently need to update the same memcache key in an atomic fashion. Let's assume you are managing a counter in memcache. (Actually, you could use the incr() and decr() operations to update 64-bit integer counters atomically, but just for argument's sake assume you cannot use those -- there are other data types for which the memcache service does not have built-in support.)

The naive code to update a counter would be something like this:

def init_counter(key):
. memcache.set(key, 0)

def bump_counter(key):
. counter = memcache.get(key)
. assert counter is not None, 'Uninitialized counter'
. memcache.set(key, counter+1)

(Aside: I don't want to have to think about how to get blogger to properly format Python code. I really don't. So just bear with the dots I use for indentation. Okay? Comments pointing me to solutions will be DELETED.)

(Aside 2: The assert is kind of naive; in practice you'll have to somehow deal with counter initialization. You also should implement a backup for your counter using the App Engine datastore, so that it can survive eviction by the memcache service. However interesting these details are on their own, I leave them for another time.)

Hopefully you can spot the problem in this version of bump_counter(): if two requests execute concurrently (on different instances of the same app), the sequence of operations might be as follows, labeling the two requests as A and B:

A: counter = memcache.get(key) # Reads 42
B: counter = memcache.get(key) # Reads 42
A: memcache.set(key, counter+1) # Writes 43
B: memcache.set(key, counter+1) # Writes 43

So even though two requests were executed, the counter only gets incremented by one. This is called a race condition. Various interlacings of these lines can have the same effect; a race condition occurs whenever B reads the counter before A has written it (or vice versa).

You could try to guard against this by reading the counter value back and checking that it was incremented by one; however this solution still has a race condition (see if you can figure it out for yourself). There are other solutions possible involving a separate "lock" variable, managed using the add() and delete() operations. However these in general require more server roundtrips, and it is pretty hard to manufacture a decent lock out of the basic memcache operations (try for yourself -- think about what would happen if your request was somehow aborted after acquiring the lock, without having a chance of releasing it).

Using the Compare-And-Set operation, writing a reliable bump_counter() function is a cinch:

def bump_counter(key):
. client = memcache.Client()
. while True: # Retry loop
. . counter = client.gets(key)
. . assert counter is not None, 'Uninitialized counter'
. . if client.cas(key, counter+1):
. . . break

I've highlighted the changes from the previous version. There are several essential differences:

The use of a memcache Client object instead of memcache functions
The use of a retry loop
The use of gets() and cas() instead of get() and set()

The Client object is required because the gets() operation actually squirrels away some hidden information that is used by the subsequent cas() operation. Because the memcache functions are stateless (meaning they don't alter any global values), these operations are only available as methods on the Client object, not as functions in the memcache module. (Apart from these two, the methods on the Client object are exactly the same as the functions in the module, as you can tell by comparing the documentation.)

The retry loop is necessary because this code doesn't actually avoid race conditions -- it just detects them! The memcache service guarantees that when used in the pattern shown here (i.e. using gets() instead of get() and cas() instead of set()), if two (or more) different client instances happen to be involved a race condition like I showed earlier, only the first one to execute the cas() operation will succeed (return True), while the second one (and later ones) will fail (return False). Let's spell out the events that happen when a race condition occurs:

A: counter = memcache.gets(key) # Reads 42
B: counter = memcache.gets(key) # Reads 42
A: memcache.cas(key, counter+1) # Writes 43, returns True
B: memcache.cas(key, counter+1) # Returns False
B: counter = memcache.gets(key) # Reads 43
B: memcache.cas(key, counter+1) # Writes 44, returns True

Another refinement I've left out here for brevity is to set a limit on the number of retries, to avoid an infinite loop in worst-case scenarios where there is a lot of contention for the same counter (meaning more requests are trying to update the counter than the memcache service can process in real time). You can figure out how to code this for yourself. (UPDATE: see comments #1 and #2 for a note about busy-waiting.)

Now let me explain roughly how this actually works. For some people that helps understanding how to use it: this is often the case for me when I am trying to understand some new concept.

The gets() operation internally receives two values from the memcache service: the value stored for the key (in our example the counter value), and a timestamp (also known as the cas_id). The timestamp is an opaque number; only the memcache service knows what it means. The important thing is that each time the value associated with a memcache key is updated, the associated timestamp is changed. The gets() operation stores this timestamp in a Python dict on the Client object, using the key passed to gets() as the dict key.

The cas() operation internally adds the timestamp to the request it sends to the memcache service. The service then compares the timestamp received with a cas() operation to the timestamp currently associated with the key. If they match, it updates the value and the timestamp, and returns success. If they don't match, it leaves the value and timestamp alone, and returns failure. (By the way, it does not send the new timestamp back with a successful response. The only way to retrieve the timestamp is to call gets().)

Of course, there's one more important ingredient: the App Engine memcache service itself behaves atomically. That is, when two concurrent requests (for the same app id) use memcache, they will go to the same memcache service instance (for historic reasons called a shard), and the memcache service has enough internal locking so that concurrent requests for the same key are properly serialized. In particular this means that two cas() requests for the same key do not actually run in parallel -- the service handles the first request that came in until completion (i.e., updating the value and timestamp) before it starts handling the second request.

And that's Compare-And-Set in a nutshell. If you have questions please don't hesitate to ask!

(UPDATE: The memcache API defines batch versions of most of its APIs. For example, to get multiple keys in a single call, there is get_multi(); to set multiple keys, there is set_multi(). Corresponding to cas(), there is cas_multi(). But there is no gets_multi(): instead, you can use get_multi(keys, for_cas=True). Finally, there's cas_reset(), which clears the dict used to store timestamps. But I haven't figured out what to do with it yet. :-)

Before Python

2011-07-25T11:17:00.000-07:00

This morning I had a chat with the students at Google's CAPE program. Since I wrote up what I wanted to say I figured I might as well blog it here. Warning: this is pretty unedited (or else it would never be published :-). I'm posting it in my "personal" blog instead of the "Python history" blog because it mostly touches on my career before Python. Here goes.

Have you ever written a computer program? Using which language?

HTML
Javascript
Java
Python
C++
C
Other - which?

[It turned out the students had used a mixture of Scratch, App Inventor, and Processing. A few students had also used Python or Java.]

Have you ever invented a programming language? :-)

If you have programmed, you know some of the problems with programming languages. Have you ever thought about why programming isn't easier? Would it help if you could just talk to your computer? Have you tried speech recognition software? I have. It doesn't work very well yet. :-)

How do you think programmers will write software 10 years from now? Or 30? 50?

Do you know how programmers worked 30 years ago?

I do.

I was born in Holland in 1956. Things were different.

I didn't know what a computer was until I was 18. However, I tinkered with electronics. I built a digital clock. My dream was to build my own calculator.

Then I went to university in Amsterdam to study mathematics and they had a computer that was free for students to use! (Not unlimited though. We were allowed to use something like one second of CPU time per day. :-)

I had to learn how to use punch cards. There were machines to create them that had a keyboard. The machines were as big as a desk and made a terrible noise when you hit a key: a small hole was punched in the card with a huge force and great precision. If you made a mistake you had to start over.

I didn't get to see the actual computer for several more years. What we had in the basement of the math department was just an end point for a network that ran across the city. There were card readers and line printers and operators who controlled them. But the actual computer was elsewhere.

It was a huge, busy place, where programmers got together and discussed their problems, and I loved to hang out there. In fact, I loved it so much I nearly dropped out of university. But eventually I graduated.

Aside: Punch cards weren't invented for computers; they were invented for sorting census data and the like before WW2. [UPDATE: actually much earlier, though the IBM 80-column format I used did originate in 1928.] There were large mechanical machines for sorting stacks of cards. But punch cards are the reason that some software still limits you (or just defaults) to 80 characters per line.

My first program was a kind of "hello world" program written in Algol-60. That language was only popular in Europe, I believe. After another student gave me a few hints I learned the rest of the language straight from the official definition of the language, the "Revised Report on the Algorithmic Language Algol-60." That was not an easy report to read! The language was a bit cumbersome, but I didn't mind, I learned the basics of programming anyway: variables, expressions, functions, input/output.

Then a professor mentioned that there was a new programming language named Pascal. There was a Pascal compiler on our mainframe so I decided to learn it. I borrowed the book on Pascal from the departmental library (there was only one book, and only one copy, and I couldn't afford my own). After skimming it, I decided that the only thing I really needed were the "railroad diagrams" at the end of the book that summarized the language's syntax. I made photocopies of those and returned the book to the library.

Aside: Pascal really had only one new feature compared to Algol-60, pointers. These baffled me for the longest time. Eventually I learned assembly programming, which explained the memory model of a computer for the first time. I realized that a pointer was just an address. Then I finally understood them.

I guess this is how I got interested in programming languages. I learned the other languages of the day along the way: Fortran, Lisp, Basic, Cobol. With all this knowledge of programming, I managed to get a plum part-time job at the data center maintaining the mainframe's operating system. It was the most coveted job among programmers. It gave me access to unlimited computer time, the fastest terminals (still 80 x 24 though :-), and most important, a stimulating environment where I got to learn from other programmers. I also got access to a Unix system, learned C and shell programming, and at some point we had an Apple II (mostly remembered for hours of playing space invaders). I even got to implement a new (but very crummy) programming language!

All this time, programming was one of the most fun things in my life. I thought of ideas for new programs to write all the time. But interestingly, I wasn't very interested in using computers for practical stuff! Nor even to solve mathematical puzzles (except that I invented a clever way of programming Conway's Game of Life that came from my understanding of using logic gates to build a binary addition circuit).

What I liked most though was write programs to make the life of programmers better. One of my early creations was a text editor that was better than the system's standard text editor (which wasn't very hard :-). I also wrote an archive program that helped conserve disk space; it was so popular and useful that the data center offered it to all its customers. I liked sharing programs, and my own principles for sharing were very similar to what later would become Open Source (except I didn't care about licenses -- still don't :-).

As a term project I wrote a static analyzer for Pascal programs with another student. Looking back I think it was a horrible program, but our professor thought it was brilliant and we both got an A+. That's where I learned about parsers and such, and that you can do more with a parser than write a compiler.

I combined pleasure with a good cause when I helped out a small left-wing political party in Holland automate their membership database. This was until then maintained by hand as a collection of metal plates plates into which letters were stamped using an antiquated machine not unlike a steam hammer :-). In the end the project was not a great success, but my contributions (including an emulation of Unix's venerable "ed" editor program written in Cobol) piqued the attention of another volunteer, whose day job was as computer science researcher at the Mathematical Center. (Now CWI.)

This was Lambert Meertens. It so happened that he was designing his own programming language, named B (later ABC), and when I graduated he offered me a job on his team of programmers who were implementing an interpreter for the language (what we would now call a virtual machine).

The rest I have written up earlier in my Python history blog.

The depth and breadth of Python

2011-06-03T09:17:00.001-07:00

As of late I'm noticing a trend: I'm spending more time having in-person in-depth conversations, and less time coding. While I regret the latter, I really enjoy the former. Certainly more than weekly meetings, code reviews, or bikeshedding email threads. (I'm not all that excited about blogging either, as you may have guessed; but some things just don't fit in 140 characters.)

Two conversations with visitors I particularly enjoyed this week were both with very happy Python users, and yet they couldn't be more different. This to me is a confirmation of Python's enduring depth and breadth: it is as far away of a one-trick language as you can imagine.

My first visitor was Annie Liu, a professor of computer science (with a tendency to theory :-) at Stony Brook University in New York State. During an animated conversation that lasted nearly three hours (and still she had more to say :-) she explained to me the gist of her research, which appears to be writing small Python programs that implement fundamental algorithms using set comprehensions, and then optimizing the heck out of it using an automated approach she summarized as the three I's: Iterate, incrementalize, and implement. While her academic colleagues laugh at her for her choice of such a non-theoretical language like Python, her students love it, and she seems to be having the last laugh, obtaining publication-worthy results that don't require advanced LaTeX skills, nor writing in a dead language like SETL (of which she is also a great fan, and which, via ABC, had some influence on Python -- see also below).

Annie told me an amusing anecdote about an inscrutable security standard produced by NiST a decade ago, with a fifty-page specification written in Z. She took a 12-page portion of it and translated it into a 120-line Python program, which was much more readable than the original, and in the process she uncovered some bugs in the spec!

Another anecdote she recounted had reached me before, but somehow I had forgotten about it until she reminded me. It concerns the origins of Python's use of indentation. The anecdote takes place long before Python was created. At an IFIP working group meeting in a hotel, one night the delegates could not agree about the best delimiters to use for code blocks. On the table were the venerable BEGIN ... END, the newcomers { ... }, and some oddities like IF ... FI and indentation. In desperation someone said the decision had to be made by a non-programmer. The only person available was apparently Robert Dewar's wife, who in those days traveled with her husband to these events. Despite the late hour, she was called down from her hotel room and asked for her independent judgement. Immediately she decided that structuring by pure indentation was the winner. Now, I've probably got all the details wrong here, but apparently Lambert Meertens was present, who went on to design Python's predecessor, ABC, though at the time he called it B (the italics meant that B was not the name of the language, but the name of the variable containing the name of the language). I checked my personal archives, and the first time I heard this was from Prof. Paul Hilfinger at Berkeley, who recounted a similar story. In his version, it was just Lambert Meertens and Robert Dewar, and Robert Dewar's wife chose indentation because she wanted to go to bed. Either way it is a charming and powerful story. (UPDATE: indeed the real story was quite different.)

Of course Annie had some requests as well. I'll probably go over these in more detail on python-ideas, but here's a quick rundown (of what I could remember):

Quantifiers. She is really longing for the "SOME x IN xs HAS pred" notation from ABC (and its sibling "EACH x IN xs HAS pred"), which superficially resemble Python's any() and all() functions, but have the added semantics of making x available in the scope executed when the test succeeds (or fails, in the case of EACH -- then x represents a counterexample).
Type declarations. (Though I think she would be happy with Python 3 function annotations, possibly augmented with the attribute declarations seen in e.g. Django and App Engine's model classes.)
Pattern matching, a la Erlang. I have been eying these myself from time to time; it is hard to find a syntax that really shines, but it seems to be a useful feature.
Something she calls labels or yield points. It seems somewhat similar to yield statements in generators, but not quite.
She has only recently begun to look at distributed algorithms (she had some Leslie Lamport anecdotes as well) and might prefer sets to be immutable after all. Though that isn't so clear; her work so far has actually benefited from mutating sets to maintain some algorithmic invariant. (The "incrementalize" of the three I's actually refers to a form of "differentiation" of expressions that produce a new set for each input.)

The contrast with my visitor the next day couldn't be greater. Through a former colleague I got an introduction to Drew Houston, co-founder and CEO of the vastly successful start-up company Dropbox. Dropbox currently has 25 million users, stores petabytes of data on Amazon S3, is profitable, and is not for sale. Drew is an easygoing MIT graduate who is equally comfortable discussing custom memory allocators, the world of venture capitalism, and how to keep engineers happy; he likes hard problems and winning.

Python plays an important role in Dropbox's success: the Dropbox client, which runs on Windows, Mac and Linux (!), is written in Python. This is key to the portability: everything except the UI is cross-platform. (The UI uses a Python-ObjC bridge on Mac, and wxPython on the other platforms.) Performance has never been a problem -- understanding that a small number of critical pieces were written in C, including a custom memory allocator used for a certain type of objects whose pattern of allocation involves allocating 100,000s of them and then releasing all but a few. Before you jump in to open up the Dropbox distro and learn all about how it works, beware that the source code is not included and the bytecode is obfuscated. Drew's no fool. And he laughs at the poor competitors who are using Java.

Next Monday I'm having lunch with another high-tech enterpreneur, a Y-combinator start-up founder using (and contributing to) App Engine. Maybe I should just cancel all weekly meetings and sign off from all mailing lists and focus on two things: meeting Python users and coding. That's the life!

Asynchronous RPC in App Engine Today

2011-01-24T10:07:00.000-08:00

While I was laying the groundwork for a new datastore client library with support for asynchronous requests, I added some low-level support for asynchronous RPCs that you can use today. The only App Engine API with documented support for asynchronous RPCs is urlfetch, and it happens to be quite useful with that.

Suppose you want to fetch some data from a remote service. The remote service has two instances, both of which are slightly flaky. What you want to do is send off requests to both servers simultaneous (this is the easy part) and then wait for the first one to give you a result. The latter uses the new API that I'm about to describe here.


from google.appengine.api import urlfetch, apiproxy_stub_map

urls = ['http://service1.com', 'http://service2.com']  # Etc.

rpcs = []
for url in urls:
   rpc = urlfetch.create_rpc(deadline=1.0)
   urlfetch.make_fetch_call(rpc, url)
   rpcs.append(rpc)

rpc = apiproxy_stub_map.UserRPC.wait_any(rpcs)
# Now rpc is the first rpc that returned a result. Have at it!

That's all! If you're interested in learning more about this handy class method, just check out its docstring in the App Engine SDK. Note that technically you should loop until it doesn't return None.

You can also repeatedly call wait_any() to get subsequent result. Make sure to remove the rpc it returns (if any) from the list, since otherwise it will return the same rpc over and over again: the specification of wait_any() says it returns the first rpc in the given list that completes, regardless of whether you have seen it before.

Also note that there currently is no way to cancel the other RPCs, which is why I passed a low deadline to the create_rpc() call. The problem is that even if you completely ignore the other RPCs, the App Engine runtime still waits for them to finish or timeout.

Finally, there is also a similar class method UserRPC.wait_all(), which waits until all RPCs in the list you pass it are complete. (It doesn't return anything.)

PS. Don't look too closely at the implementation of these methods. It may change as we think of a better way to do it. But we're committed to the API.

A new App Engine datastore API

2011-01-07T12:20:00.000-08:00

This post is primarily intended for App Engine users (and of those, only Python users :-).

Over the past months I've been working on a new design for the Python datastore API, under the code name Datastore Plus. The new design is very ambitious, and changes a lot of things:

New, cleaner implementations of Key, Model, Property and Query classes
High-level asynchronous API using Python generators as coroutines (PEP 342)

The design is meant to eventually replace the existing db package in the App Engine runtime library, but for now, it is just an open source project which you have to download and copy into your application.

I am not at all finished with this design, but I believe in listening to users, so I am making a preliminary version of the new API available for review. Please send me your thoughts, either in this blog, or via private mail to guido (at) google.com. Note that the implementation works, but I cannot guarantee that it won't change.

Documentation is here: http://goo.gl/D6Onw

The project to check out is here: http://goo.gl/GapXI

You must use Mercurial to check out the project, but it's fine to check it out anonymously -- I don't require anybody to log in to look or comment. (If using Mercurial is too much of a burden, there's also a zipfile on the site, but I don't plan to update it frequently.)

I'm interested in receiving any kind of feedback at all. It would help me if you could clarify whether your feedback is about an issue with the documentation, an issue with the implementation, or an issue with the API design -- though I realize you can't always tell the difference. :-)

(You can also comment on the thread in the google-appengine-python group here: https://groups.google.com/group/google-appengine-python/browse_thread/thread/454cb81d49e759f2.)

While-you-type Searching

2009-12-11T13:45:00.001-08:00

Here's an idea that is just begging to be implemented as a Firefox extension.

You know how there's a while-you-type spell checker that's always on when you are editing text in a multi-line text box? There should be a feature that takes the last few words you're typing (or the entire current paragraph, or whatever works best), does a Google search, and presents snippets for the top few results in an unobtrusive pop-up window.

Sure, maybe you're thinking "It looks like you're writing a letter. Do you want me to write it for you?" (the Microsoft paperclip). But using web search instead of a fixed set of patterns could actually make this useful. Imagine the number of messages to customer support forums that will never have to be sent because this feature pops up the answer the user was looking for. And so on.

You might also think, "this already exists, it's called Google auto-suggest." But I specifically want it to work when I'm not (yet) actively searching, but just writing. (If it already existed, it might have stopped me from writing this blog post. :-) Twitter might also become a different place if users realized how many others have already entered the same item.

Of course there's a little privacy issue. But still, if this existed, I'd opt in! (In fact, I did half a dozen searches while I was typing this. How much easier it would be if I didn't have to select text, switch to a different tab, paste, and hit enter, losing my writing context each tim.)

Python in the Scientific World

2009-11-05T10:12:00.000-08:00

Yesterday I attended a biweekly meeting of an informal a UC Berkeley group devoted to Python in science (Py4Science), organized by Fernando Perez. The format (in honor of my visit) was a series of 4-minute lightning talks about various projects using Python in the scientific world (at Berkeley and elsewhere) followed by an hourlong Q&A session. This meant I didn't have to do a presentation and still got to interact with the audience for an hour -- my ideal format.

I was blown away by the wide variety of Python use for scientific work. It looks like Python (with extensions like numpy) is becoming a standard tool for many sciences that need to process large amounts of data, from neuroimaging to astronomy.

Here is a list of the topics presented (though not in the order presented). All these describing Python software; I've added names and affiliations insofar I managed to get them. (Thanks to Jarrod Millman for providing me with a complete list.) Most projects are easily found by Googling for them, so I have not included hyperlinks except in some cases where the slides emphasized them. (See also the blog comments.)

Fernando gave an overview of the core Python software used throughout scientific computing: NumPy, Matplotlib, IPython (by Fernando), Mayavi, Sympy (about which more later), Cython, and lots more.

On behalf of Andrew Straw (Caltech), Fernando showed a video of an experimental setup where a firefly is tracked in real time by 8 camaras spewing 100 images per second, using Python software.

Nitimes, a time-series analysis tool for neuroimaging, by Ariel Rokern (UCB).

A comparative genomics tool by Brent Pedersen of the Freeling Lab / Plant Biology (UCB).

Copperhead: Data-Parallel Python, by Bryan Catanzaro (working with Armando Fox) and others.

Nipype: Neuroimaging analysis pipeline and interfaces in Python, by Chris Burns (http://nipy.sourceforge.net/nipype/).

SymPy -- a library for symbolic mathematics in Pure Python, by Ondrej Certik (runs on Google App Engine: http://live.sympy.org).

Enthought Python Distribution -- a Python distro with scientific batteries inluded (some proprietary, many open source), supporting Windows, Mac, Linux and Solaris. (Travis Oliphant and Eric Jones, of Enthought.)

PySKI, by Erin Carson (working with Armando Fox) and others -- a tool for auto-tuning computational kernels on sparse matrices.

Rapid classification of astronomical time-series data, by Josh Bloom, UCB Astronomy Dept. One of the many tools using Python is GroupThink, which lets random people on the web help classify galaxies (more fun than watching porn :-).

The Hubble Space Telescope team in Baltimore has used Python for 10 years. They showed a tool for removing noise generated by cosmic rays from photos of galaxies. The future James Webb Space Telescope will also be using Python. (Perry Greenfield and Michael Droettboom, of STSCI.)

A $1B commitment by the Indian government to improve education in India includes a project by Prabhu Ramachandran of the Department of Aerospace Engineering at IIT Bombay for Python in Science and Engineering Education in India (see http://fossee.in/).

Wim Lavrijsen (LBL) presented work on Python usage in High Energy Physics.

William Stein (University of Washington) presented SAGE, a viable free open source alternative to Magma, Maple, Mathematica and Matlab.

All in all, the impression I got was of an incredible wealth of software, written and maintained by dedicated volunteers all over the scientific community.

During the Q&A session, we touched upon the usual topics, like Python 3 transition, the GIL (there was considerable interest in Antoine Pitrou's newgil work, which unfortunately I could not summarize adequately because I haven't studied it enough yet), Unladen Swallow, and the situation with distutils, setuptools and the future 'distribute' package (for which I unfortunately had to defer to the distutil-sig).

The folks maintaining NumPy have thought about Python 3 a lot, but haven't started planning the work. Like many other projects faced with the Python 3 porting task, they don't have enough people who actually know the code base well enough do embark upon such a project. They do have a plan for arriving at PEP 3118 compliance within the next 6 months.

Since NumPy is at the root of the dependency graph for much of the software packages presented here, getting NumPy ported to Python 3 is pretty important. We briefly discussed a possible way to obtain NumPy support for Python 3 sooner and with less effort: a smaller "core" of NumPy could be ported first, which would give the NumPy maintainers a manageable task, combined with the goal of selecting a smaller "core" which would give them the opportunity for a clean-up at the same time. (I presume this would mostly be a selection of subpackage to be ported, not an API-by-API cleanup of APIs; the latter would be a bad thing to do simultaneous with a big port.)

After the meeting, Fernando showed me a little about how NumPy is maintained. They have elaborate docstrings that are marked up with a (very light) variant of Sphynx, and they let the user community edit the docstrings through a structured wiki-like setup. Such changes are then presented to the developers for review, and can be incorporated into the code base with minimal effort.

An important aspect of this approach is that the users who edit the docstrings are often scientists who understand the computation being carried out in its scientific context, and who share their knowledge about the code and its background and limitations with other scientists who might be using the same code. This process, together with the facilities in IPython for quickly calling up the docstring for any object, really improves the value of the docstrings for the community. Maybe we could use something like this for the Python standard library; it might be a way that would allow non-programmers to help contribute to the Python project (one of the ideas also mentioned in the diversity discussions).

Lovely Python!

2009-09-17T09:48:00.000-07:00

I just heard from Bill Xu in China. His book "Lovely Python", an introduction to Python in Chinese, was just published and shot to the top-5 of china-pub.com's bestseller list (at some point it even was #2). I can't read Chinese, but I am very glad that there's a book on Python available for Chinese readers, and that's why I wrote a brief foreword for the book as well. (Also because I am one of the mentors of Zeuux.org.) Links:

This is the Lovely Python page on the book store:

http://www.china-pub.com/195771

This is the bestseller list:

http://www.china-pub.com/rank/?type=59&act=day&v=7

This is the cover (with front and back) of Lovely Python:

http://www.zeuux.org/pub/lovely-python-cover.jpg

This is my preface:

http://www.zeuux.org/science/zeuux-lovely-python-preface-by-guido.html (English)

http://www.zeuux.org/science/zeuux-lovely-python-preface-by-guido.cn.html (Chinese translation by Bill Xu)

Scientists Discover That Hidden Persuaders Are Real

2009-07-22T13:29:00.000-07:00

In yesterday's post I mentioned reading George Lakoff's book, The Political Mind. While I agree with the politics of the book in almost every instance, I was still disappointed. For one thing, the book "compresses well." (IOW it contains a lot of repetition. A Lot.) It also felt a bit like a classic bait-and-switch: the back flap touts "the science behind how our brains understand politics" but the contents are 90% political rhetoric, and I'm still in doubt about the science.

The author's premise is attractive enough as far as it goes: our brains don't make perfectly rational decisions, but are influenced by "framing"; and the Republicans have used this to their advantage while the Democrats with their belief in "pure reason" have not properly defended themselves by accepting the conservative framing (for example: "tax relief").

Well, there may be some recent scientific research that confirms that most people are not so good at rational decision making, but honestly, I thought that the importance of framing has been well known for a long time to all politicians -- and advertisers as well. As far as the recent scientific proof for this commonly-known fact, Jonah Lehrer's book "How We Decide" contains at least as much about the research, and the non-scientific parts of his book are better written and, I expect, more future-proof.

I'm also skeptical of the importance of Lakoff's discovery that frames are represented physically in the brain. That's about as insightful as saying that this blog entry exists physically in Google's computers (as magnetic fluctuations on a hard drive). Has he never heard of abstractions? He seems to argue that all of philosophy needs to be thrown away because it ignores this fact. I will gladly accept that we cannot treat the brain as a perfect mathematical machine, and using the embodyment of the mind will probably eventually help us understand consciousness (more likely than abstract reasoning like Douglas Hofstadter's approach, no matter how much I enjoy his puzzles and paradoxes).

But the important message to me is still about how the brain's software works. It's useful to know that frames are reinforced by trauma and repetition, and that it requires a lot of repetition of counteracting frames to override them once they're there. And yes, that the Bush government used this to its advantage is a great example. But I wanted to know more about the science, and less about the politics.

Lakoff's other point is that human beings are born to have emphathy with each other. But he doesn't mention much of the science behind this. That's because in the end he is a linguist, and linguists spend most of their time studying (and arguing about) human language, which was the result of a long evolutionary path and cannot necessarily explain it. And his oft-repeated use of the words America and American in connection to empathy is surely his own little joke, where he's trying to make the reader believe that American values are nurturing values by applying his own theory: say it over and over and the frame will be hard-wired (whether that's literally or figuratively :-) in the reader's mind. As a non-US-citizen I wished the emphasis was on human values, not American values.

Progressive vs. Conservative

2009-07-21T11:50:00.000-07:00

[Warning: loose thoughts ahead!]

Microsoft's Eric Meijer gave a talk at Google yesterday, and afterwards I had lunch with him. One of his remarks was (I paraphrase) that Microsoft users want to be told what to do, while the Java community is more vocal or argumentative. (He didn't discuss the Python community but in my experience it falls in the latter category.)

Now, while lying sick in bed with a hacking cough, I am reading George Lakoff's "The Political Mind". This book tries to model the distinction between conservative and progressive politics on the differences between two different ideal family models: the strict father (from which most conservative moral virtues flow according to Lakoff), and the nurturing family, from which the progressive moral virtues derived.

The parallel with Microsoft users vs. Java users seems to be all too obvious: Microsoft as the strict father: If you are loyal you will be rewarded, but if you stray you will be punished; whereas in the Java (or Python) community benefits and moral goodness flow from helping each other (which includes sharing open source software, and, apparently, bikeshedding :-).

What about other companies and communities? I can't help thinking of Oracle as the ultimate strict-father company, which makes me worry about the Sun takeover. Are Linus Torvalds and Richard Stallman strict fathers?

IronPython in Action and the Decline of Windows

2009-06-26T12:05:00.000-07:00

While CPython still rules on python-dev, especially with the excitement around Py3k, Python's alternative implementations are growing up: PyPy is now capable of running Django, Jython just released version 2.5, and IronPython has been releasing significant milestones like clockwork. I get a lot of satisfaction out of such milestones: they help establish Python as a language you can't ignore, no matter which platform you are using.

Seeing a book like IronPython in Action, by Michael Foord and Christian Muirhead, is another milestone for IronPython. This is a solid work in every aspect, and something nobody using IronPython on .NET should be without. The book is chock full of useful information, presented along with a series of running examples, and covers almost every aspect of IronPython use imaginable.

After reading the table of contents and the introduction by IronPython's creator Jim Hugunin, I couldn't help myself and skipped straight to appendix A, "A whirlwind tour of C#." This is a useful thing to have around for readers like myself who haven't really kept track of things in the .NET world. Maybe I'll comment more on C# another time. For now, let me just say that it seems a decent enough system programming language. The more relevant thing about C# is that you can't avoid learning it if you are developing on .NET, even when using IronPython. There just are too many issues where IronPython has to work around a limitation of C#. This happens often indirectly where a particular API was designed purely with C# in mind. And then there's the issue that Microsoft's API documentation focus on C#. (And VB.NET, I suppose, which after seeing some samples of in this book I have less desire to know than ever.)

There are some introductory chapters -- some fluff about .NET and the CLR, an introduction to Python, and an introduction to with .NET objects from IronPython. The Python introduction has a slight emphasis on differences between IronPython and CPython, though there aren't enough to fill a chapter. This is a good thing! The chapter does a pretty good job of teaching Python, assuming you already know programming. In general, the book is aimed solidly at professional software developers: unless you are paid to do it, why would anyone want to get intimate with Windows?

Yes, Windows programming is what this book is really about. I'm sure that doing Windows programming using IronPython is a much better proposition than Windows programming using C++; but it's still Windows programming. Fortunately the authors maintain a slightly ironic attitude about Windows. I can't help admiring their persistency in getting to the bottom of the many mysteries presented by Windows(and in some cases by IronPython's wrappers).

Many, many years ago -- so long ago that I can't even recall when -- I did some Windows programming myself, using Mark Hammond's Win32 extensions for CPython. That package maps the Win32 API pretty directly to Python. It lets you work with Windows in much the same way as you can in IronPython -- the main difference is that IronPython lives in the more modern .NET world, while Win32 is showing its age.

But is life with IronPython all that much better than in CPython+Win32? It still looks incredibly tedious to create the simplest of UI. Each button in the UI has to be tediously positioned and configured (width, height, padding, font size, etc.). The book maintains a running example throughout many of the chapters, and one of the earlier versions (with many features not yet developed) clicks in at a "mere" 258 lines. Fortunately, the source code for all examples can be downloaded from the book's website. While the downloaded zip file is a whopping 33 megabytes, there's actually only half a megabyte of source code in it (and much of it multiple versions of the same running example) -- the majority of the download is not source code but DLLs that are probably included by the authors because Microsoft scatters them around half a dozen or more different support websites. (Plus, there seem to be multiple copies of IronPython.dll and a few other DLLs included.)

This then, was the big eye-opener for me: that despite all the hype, Windows UI programming is as tedious today as it was in 1995. Sure, the new UI looks a lot better. But that's mostly glitz: 3D effects, color gradients, video, and so on. Sure, it's all object-oriented now. But it hasn't really gotten any less complex to create the simplest of simple UIs. And that's a shame. When is Microsoft going to learn the real lesson about simplicity of HTML? Instead, Microsoft is doing the same thing to HTML that it does to anything it touches: adding cruft to the point where the basic functionality is buried so deeply that most people can't even find it. You can't really blame the average Windows developer for focusing on eye candy instead of usability -- it's all mashed together in the APIs, and by the time you've got something that works at all, you're too exhausted to look at it from your users' perspective.

It's no wonder that users are switching to the web as the platform for everything that used to live on the desktop -- with all its flaws (which I will discuss another time), web development still feels like a breeze compared to Windows development. And that means less time to release, and hence more frequent releases, which in turn means more opportunities for developers to learn what their users actually do. Which as a user I really appreciate.

Highs and Lows of IEEE Computer Magazine

2009-06-16T18:47:00.000-07:00

I still read a few print publications, including IEEE Computer. Today's issue contained a high and a low:

Today's high point was a detailed history of the Conficker worm. Since we're a Macintosh family, and Google typically has its security stuff in order, I was barely aware of it. The sophistication of the worm's creators is almost admirable. (They probably use Python too. :-) An interesting table in the article included information about which countries contribute the most to the worm's population. China, Brazil and Russia top the list. You could have all sorts of theories on why this would be; personally I'm assuming it's a combination of sheer number of computers plus widespread use of bootlegged copies of Windows.

The low point was an article on "Software Engineering Ethics." Why a low point? Look at this table and think of how many bits of information it contains:

Using postphenomenology for software engineering ethics
Actions	Desirable	Undesirable
Amplify experiences that are	+	-
Reduce experiences that are	-	+
Invite actions that are	+	-
Inhibit actions that are	-	+

Ironically, this pointless table contains a redundant column, while the table I mentioned above was missing a column that would have been useful -- how many PCs are installed in each country. Oh well.

PS: Googling for "postphenomenology" gives this as the title of the first hit: "If phenomenology is an albatross, is postphenomenology possible?" The web knows best.

New App Engine Book

2009-06-15T09:20:00.000-07:00

At Google I/O I received a copy of Using Google App Engine by Charles Severance, published by O'Reilly. I haven't kept track, but this appears one of the first App Engine books to actually hit the stores -- an Amazon search for App Engine showed up one other book (Developing with Google App Engine by Eugene Ciara, published by APress) and many titles available for pre-order (including additional titles from the same publishers).

Severance's book is a quick read if you're already familiar with the basic premises of web programming. I think it would do well in an introductory course about the topic. (The author teaches at the University of Michigan so this is likely how he developed the material in the first place.) In fact, quite a bit of the book could well have come from a pre-existing earlier course: the chapters on HTML, CSS, Python and JavaScript barely mention App Engine.

Don't get me wrong, I think that's a good approach: in my experience quite a few App Engine users are new to web programming in general, or could at least use a refresher course. If you don't fall in this category, don't feel offended: you just probably aren't the intended audience for this book. On the other hand, if you've developed for the web but haven't used Python before, you could probably just skip the HTML/CSS chapter and dive right into Python and App Engine.

If you're a blank sheet where it comes to programming, don't expect to come out an experienced Python developer: the book only covers enough of the language so you can get started with App Engine without feeling you're just copying and pasting text. The same is actually true for any topic covered -- in many cases the book actually recommends that you study a topic more in-depth using other resources. But in each case the book's coverage is enough to get you started with the creation of dynamic web sites, and that's the important part. After all, you didn't learn your mother tongue by studying the rules of grammar either: you learned a few nouns, a few verbs, a few adjectives, and a few grammatical forms ("Daddy throw toy again") and you were on your way to communicating with others.

Actually, if you read this book from cover to cover, you might not be ready to create the Greate American Website, but you'll be well past the "Daddy throw toy" level. For example, you'll be creating App Engine datastore models with ease, tying them together with forms, and you'll even be able to use simple AJAX patterns. You will also have learned about the importance of caching, and you'll have more than a fleeting experience debugging problems using tracebacks and logs.

I also enjoyed some of the history bits that Severance presents (it makes me feel old to see 1990 referred to as ancient history :-). A downside is that sometimes the exercises given at the end of each chapter seem to be focused more on assessing that you were awake during class than that you actually have learned a useful skill (e.g. "Give a brief history of the major phases of the internet"). Teachers considering to use this book in the classroom might appreciate such questions; but for self-study, I would focus on the difference between the class= and id= attributes in HTML...

What's missing? The book doesn't touch Django (except for the templating facility built into App Engine's webapp package, which is based on Django). If our customer support traffic is any indication, Django is very popular with professional App Engine developers. The book also doesn't describe the various APIs offered by App Engine for things like sending mail, fetching other web resources by URL, or image processing. But arguably you can learn those directly from the App Engine docs. Oh, and the book doesn't touch on App Engine's Java support. I expect other books will fill that void.

So you want to learn Python?

2009-05-26T15:46:00.000-07:00

There's never a lack of books to use for learning Python. I occasionally receive books for review, but I don't have a particularly good yardstick to judge such books by: I find that they all contain some factual errors and some oddities of presentation, but I have no idea whether those matter for the readers. Even Knuth's books are full of errors: for example the errata for Vol. 1 (2nd ed.) are a staggering 80 pages, but I doubt anybody besides Knuth himself is bothered by this knowledge.

Recently I got a review copy of "Hello World", and a colleague kindly lent me his copy of "Practical Programming". I think it's interesting to compare the two a bit, since they both claim to be teaching Python programming to people who haven't programmed before. And yet their audiences are totally different!

"Hello World", published by Manning, is written by Warren Sande and his son Carter. The subtitle is "Computer programming for kids and other beginners", but I think if you're not a kid any more you might get annoyed by the rather popular writing style. If you are a kid, well, you will probably enjoy a book written with you in mind, and you will learn plenty. The only prerequisites are reading and typing skills, a computer that wasn't built in the stone age, and a desire to learn more about what goes on inside that computer. The book uses short chapters with lots of illustrations, often cartoons and jokes. There are lots of opportunities to try out the material and learn that way. Each chapter ends with a review section, some tests, and more experiments to try. The book pays plenty of attention to typical "gotchas", so that if you get stuck at some point, there probably is help nearby to get you unstuck.

"Practical Programming" is written by Jennifer Campbell, Paul Gries, Jason Montojo, and Greg Wilson. This a team composed of three university professors and a former student of theirs. Their purported goal is to teach Computer Science (with Capital Letters), and Python is merely a teaching vehicle. But they spend about half of the book on Python itself, covering roughly the same material as any introduction to Python, including "Hello World". Their intended audience is clearly more mature than that of the Sandes, and I would think that Carter Sande and his friends would have a hard time staying focused on the material as presented by Campbell et al. -- their illustrations and diagrams are more functional but a lot less fun.

Both books present a number of projects and running examples. Again, the difference in audience makes it likely that if you love one, you'll hate the other, and vice versa. "Hello World" uses examples from computer games. The games are extremely simple though: modern computer games are some of the most complex system around, and you can't expect to approach them using PyGame and a couple hundred lines of Python. "Practical Programming" takes its example frome scientific data processing with an environmental touch: for example, a numerical series is presented as whale sightings over the years and 2-dimensional data is taken from deforestation data. No doubt this is done in an attempt to appeal to a certain kind of student, though the number of potential applications is so large that some students might just as well be turned off by the specific set of choices.

In the end, "Hello World" will leave the reader with a fair amount of practical Python experience, enough to get them started on the long road to becoming a programmer if they are so inclined, or at least enough to give them some idea of what it is that programmers do. "Practical Programming" tries to go further: it presents some well-known algorithms (there's even a discussion of MergeSort), and it has introductory chapters on topics like object-oriented programming and databases. The overall focus is still on being able to use all this new knowledge in one's professional life, and I hesitate to agree with the authors' apparent view that it teaches "Computer Science". Calling it "Computer Use" would cover the contents better, I think, and that's more in line with the series title as well ("The Pragmatic Programmers", also the publisher).

So, how do you learn about Computer Science? Some would no doubt recommend "Structure and Interpretation of Computer Programs" by Abelson and Sussman here. (Someone sent me review copy of that book too.) But really, SICP (as it is often referred to) has its own agenda: convincing the reader that the most important thing computers can do is interpreting computer programs. This agenda has arguably caused the proliferation of Scheme implementations and indoctrinated many young minds with certain ideas about how to design and implement programming languages. But personally, I recommend you go straight to the source. After all these years, there is still no substitute for Knuth.

[UPDATE: fixed book titles as commenters pointed out my typos.]

Final Words on Tail Calls

2009-04-27T19:51:00.000-07:00

A lot of people remarked that in my post on Tail Recursion Elimination I confused tail self-recursion with other tail calls, which proper Tail Call Optimization (TCO) also eliminates. I now feel more educated: tail calls are not just about loops. I started my blog post when someone pointed out several recent posts by Pythonistas playing around with implementing tail self-recursion through decorators or bytecode hacks. In the eyes of the TCO proponents those were all amateurs, and perhaps that's so.

The one issue on which TCO advocates seem to agree with me is that TCO is a feature, not an optimization. (Even though in some compiled languages it really is provided by a compiler optimization.) We can argue over whether it is a desirable feature. Personally, I think it is a fine feature for some languages, but I don't think it fits Python: The elimination of stack traces for some calls but not others would certainly confuse many users, who have not been raised with tail call religion but might have learned about call semantics by tracing through a few calls in a debugger.

The main issue here is that I expect that in many cases tail calls are not of a recursive nature (neither direct nor indirect), so the elimination of stack frames doesn't do anything for the algorithmic complexity of the code, but it does make debugging harder. For example, if your have a function ending in something like this:

if x > y:
 return some_call(z)
else:
 return 42

and you end up in the debugger inside some_call() whereas you expected to have taken the other branch, with TCO as a feature your debugger can't tell you the value of x and y, because the stack frame has been eliminated.

(I'm sure at this point someone will bring up that the debugger should be smarter. Sure. I'm expecting your patch for CPython any minute now.)

The most interesting use case brought up for TCO is the implementation of algorithms involving state machines. The proponents of TCO claim that the only alternative to TCO is a loop with lots of state, which they consider ugly. Now, apart from the observation that since TCO essentially is a GOTO, you write spaghetti code using TCO just as easily, Ian Bicking gave a solution that is as simple as it is elegant. (I saw it in a comment to someone's blog that I can't find back right now; I'll add a link if someone adds it in a comment here.) Instead of this tail call:

return foo(args)

you write this:

return foo, (args,)

which doesn't call foo() but just returns it and an argument tuple, and embed everything in a "driver" loop like this:

func, args = ...initial func/args pair...
while True:
  func, args = func(*args)

If you need an exit condition you can use an exception, or you could invent some other protocol to signal the end of the loop (like returning None).

And here it ends. One other thing I learned is that some in the academic world scornfully refer to Python as "the Basic of the future". Personally, I rather see that as a badge of honor, and it gives me an opportunity to plug a book of interviews with language designers to which I contributed, side by side with the creators of Basic, C++, Perl, Java, and other academically scorned languages -- as well as those of ML and Haskell, I hasten to add. (Apparently the creators of Scheme were too busy arguing whether to say "tail call optimization" or "proper tail recursion." :-)

People Who Annoy Me

2009-04-25T09:04:00.000-07:00

It's Grumpy Saturday. If I didn't respond to your email or "friend" request, maybe you fall in one of the following categories.

1. People who have exchanged some email with me (or who once commented on my blog, or were once in the same line at a conference) and send me a Linkedin friend request with the default invite message.

2. People I've never heard from asking to become my friend on Facebook.

3. People who send me a long form letter inviting me to speak at their conference, without any kind of personal note at the top.

4. People who resend that form letter three times.

5. People who get all upset when I respond to the last identical copy of that form letter with "Please stop spamming me."

6. People who send me a long rambling email asking me a Python programming question.

7. People who send me a long rambling email proposing a change to the Python language.

8. People who collect pictures of famous people's desktops.

9. People who send me email asking if they can put their ads on my website.

10. People who create fake blogs with computer-generated pseudo-nonsense text that happens to include my name.

Tail Recursion Elimination

2009-04-22T13:06:00.000-07:00

I recently posted an entry in my Python History blog on the origins of Python's functional features. A side remark about not supporting tail recursion elimination (TRE) immediately sparked several comments about what a pity it is that Python doesn't do this, including links to recent blog entries by others trying to "prove" that TRE can be added to Python easily. So let me defend my position (which is that I don't want TRE in the language). If you want a short answer, it's simply unpythonic. Here's the long answer:

First, as one commenter remarked, TRE is incompatible with nice stack traces: when a tail recursion is eliminated, there's no stack frame left to use to print a traceback when something goes wrong later. This will confuse users who inadvertently wrote something recursive (the recursion isn't obvious in the stack trace printed), and makes debugging hard. Providing an option to disable TRE seems wrong to me: Python's default is and should always be to be maximally helpful for debugging. This also brings me to the next issue:

Second, the idea that TRE is merely an optimization, which each Python implementation can choose to implement or not, is wrong. Once tail recursion elimination exists, developers will start writing code that depends on it, and their code won't run on implementations that don't provide it: a typical Python implementation allows 1000 recursions, which is plenty for non-recursively written code and for code that recurses to traverse, for example, a typical parse tree, but not enough for a recursively written loop over a large list.

Third, I don't believe in recursion as the basis of all programming. This is a fundamental belief of certain computer scientists, especially those who love Scheme and like to teach programming by starting with a "cons" cell and recursion. But to me, seeing recursion as the basis of everything else is just a nice theoretical approach to fundamental mathematics (turtles all the way down), not a day-to-day tool.

For practical purposes, Python-style lists (which are flexible arrays, not linked lists), and sequences in general, are much more useful to start exploring the wonderful world of programming than recursion. They are some of the most important tools for experienced Python programmers, too. Using a linked list to represent a sequence of value is distinctly unpythonic, and in most cases very inefficient. Most of Python's library is written with sequences and iterators as fundamental building blocks (and dictionaries, of course), not linked lists, so you'd be locking yourself out of a lot of pre-defined functionality by not using lists or sequences.

Last, let's look at how we could implement tail recursion elimination. The first observation is that you can't do it at compile time. I've seen at least one blog entry that used a bytecode hack to replace a CALL opcode immediately before a RETURN opcode with a jump to the top of the function body. This may be a nice demo, but unfortunately Python's compiler cannot reliably determine whether any particular call is actually reference the current function, even if it appears to have the same name. Consider this simple example:

def f(x):
     if x > 0:
            return f(x-1)
    return 0

It looks like you could replace the body with something like this:

if x > 0:
    x = x-1
    <jump to top>
return 0

This seems simple enough, but now add this:

g = f
def f(x):
      return x
g(5)

The call to g(5) invokes the earlier f, but the "recursive" call no longer recurses! At run-time, the name 'f' is rebound to the later non-recursive definition, so the returned value is 4, not 0. While I agree that this particual example is bad style, it is a well-defined part of Python's semantics that has plenty of legitimate uses, and a compiler that made this replacement in the optimistic hope that f's definition will remain unchanged would introduce enough bugs in real-world code to cause an outrage.

Another blog post showed decorators that can be used to implement tail recursion using magical exceptions or return values. These can be written in plain Python (though that post shows an optimized Cython version that is claimed to be "only 10% slower", though it doesn't seem to be thread-safe). If this tickles your fancy I won't try to stop you, but I would strongly object against inclusion of something like this in the core distribution: there are many caveats to the use of such a decorator, since it has to assume that any recursive call (in the decorated function) is tail-recursive and can be eliminated. In the hands of less experienced users this could easily lead to disasters. For example, the common recursive definition of factorial is not tail-recursive:

def fact(n):
      if n > 1:
            return n * fact(n-1)
      return 1

There are also plenty of functions that contain a tail-recursive call and another recursive call that isn't tail-recursive; the decorators don't handle such cases. Another subtlety that those decorators don't handle is tail-recursive calls inside try blocks: these may look like they could be eliminated, but they can't, because TRE could remove the exception handling which is guaranteed by the language. For all these reasons I think the decorator approach is doomed, at least for a general audience.

Still, if someone was determined to add TRE to CPython, they could modify the compiler roughly as follows. First, determine "safe" tail-recursive call sites. This would be something like a CALL opcode immediately followed by a RETURN opcode, and completely outside any try blocks. (Note: I'm ignoring the different CALL_* opcodes, which should be easy enough to handle using the same approach.) Next, replace each such CALL-RETURN opcode pair with a single CALL_RETURN opcode. There's no need for the compiler to try and check if the name of the function being called is the same as the current function: the new opcode can represent savings for all CALL+RETURN combinations merely by saving the time to decode a second opcode. If at run time the determination is made that this particular call is not applicable for TRE, the usual actions for a CALL followed by a RETURN opcode are carried out. (I suppose you could add some kind of caching mechanism indexed by call site to speed up the run-time determination.)

In the determination of wheter TRE can be applied, there are several levels of aggressiveness that you could apply. The least aggressive, "vanilla" approach would only optimize the call if the object being called is the function that is already running in the current stack frame. All we have to do at this point is clear the locals out of the current stack frame (and other hidden state like active loops), set the arguments from the evaluation stack, and jump to the top. (Subtlety: the new arguments are, by definition, in the current stack frame. It's probably just a matter of copying them first. More subtleties are caused by the presence of keyword arguments, variable length argument lists, and default argument values. It's all a simple matter of programming though.)

A more aggressive version would also recognize the situation where a method is tail recursive (i.e. the object being called is a bound method whose underlying function is the same as the one in the current stack frame). This just requires a bit more programming; the CPython interpreter code (ceval.c) already has an optimization for method calls. ( I don't know how useful this would be though: I expect the tail recursive style to be popular with programmers who like to use a functional programming style overall, and would probably not be using classes that much. :-)

In theory, you could even optimize all cases where the object being called is a function or method written in Python, as long as the number of local variables needed for the new call can be accommodated in the current stack frame object. (Frame objects in CPython are allocated on the heap and have a variable allocation size based on the required space for the locals; there is already machinery for reusing frame objects.) This would optimize mutually tail-recursive functions, which otherwise wouldn't be optimized. Alas, it would also disable stack traces in most cases, so it would probably not be a good idea.

A more benign variant would be to create Python-level stack frames objects just like before, but reuse the C stack frame. This would create an approximation of Stackless Python, though it would still be easy enough to run out of C stack by recursing through a built-in function or method.

Of course, none of this does anything to address my first three arguments. Is it really such a big deal to rewrite your function to use a loop? (After all TRE only addresses recursion that can easily be replaced by a loop. :-)

Italia Here I Come!

2009-04-07T10:44:00.001-07:00

That is: PyCon Italia, here I come! It's still a month away (May 8-10), but I'm already looking forward to my vacation in the historic city of Florence and on the beautiful west coast of Italy. The organizers of PyCon Italia kindly invited me to give a keynote at their annual conference, making me an offer I couldn't refuse.

Kidding aside, it looks like it will be a very exciting conference, with Googlers Fredrik Lundh and Alex Martelli also coming to speak, as well as Python core developer Raymond Hettinger. And even though much of the program will be in Italian, real-time translations will be available for the main track. Personally, I'm most looking forward to a mysterious late-night event labeled PyBirra, where the locals will try to drink me under the table. Salute!

Capabilities for Python?

2009-03-06T11:49:00.001-08:00

I received an email recently from Mark Miller, quoting a post from Zooko to the cap-talk mailing list (which I do not read). Mark asked me to clarify my position about capabilities (in Python, presumably). Since the last thing I need is another mailing list subscription, I'm posting my clarification here. I'm sure that through the magic of search engines it will find its way to the relevant places.

In his post, Zooko seems to believe that I am hostile to the very idea of capabilities, and seems to draw a link between this assumed attitude and my experience with the use of password-based capabilities in Amoeba. This is odd for several reasons. First, the way I remember it, Amoeba's capabilities weren't based on passwords, but on one-way functions and random numbers (and secure Ethernet wall-sockets, which is perhaps why the idea didn't catch on :-). Second, I don't believe my experience with capabilities in Amoeba made a difference in how I think about capabilities being offered by some modern programming languages like E, or about the various proposals over the years to add capabilities to Python, perhaps starting with an old proposal by Ka-Ping Yee and Ben Laurie. (It would be better to think of this as a subtraction rather than an addition, since such proposals invariably end up limiting the user to a substantially reduced subset of Python. More about that below.)

But the biggest surprise to me is that people are reading so much in my words. I'm not the Pope! I'm a hacker who likes to think aloud about design problems. Often enough I get it wrong. If you think you disagree with me, or have a question about what I said, just respond in the forum where I post (e.g. python-dev or python-ideas, or this blog), but please don't go forwarding my messages to lists I don't read and speculate about them.

With that off my mind, and with the caveat that this entire post is thinking alound, let me try to expose some of my current thoughts about capabilities and Python.

Note that I'm trying to limit myself to Python. Languages specifically written to support capabilities exist (e.g. E) and may well become successful, though I expect they will have a hard time gaining popularity until they also sprout some other highly attractive features: most developers see security as a necessary evil.

This attitude, of course, is the reason why the idea of adding security features to an existing language keeps coming back: it's assumed to be much more likely to convince the "unwashed masses" to switch to a slightly different version of a language they already know, than to get them to even try (let alone adopt) a wholly new language. This argument not limited to security zealots of course. The same reasoning is common in the larger world of "language marketing": C++ made compatibility with C a principle overruling all others, Java chose to resemble C or C++ for ease of adoption, and it is well known that Larry Wall picked many of Perl's syntactic quirks because the initial target audience was already using sed and sh.

I'll be the first to admit that wasn't completely free of this attitude for Python's design, although I didn't do it with the intent of gaining popularity: whenever I borrowed from another language, I did so either because I recognized a good idea, or because I didn't think I had anything to add to current practice, but not because I was concerned about market share. (If I had been, I wouldn't have used indentation for grouping. :-)

Anyway, regardless of the merits of this idea, it keeps coming back. A recent incarnation is Mark Seaborn's CapPython. Skimming through this wiki page it seems that Mark is well aware of the limitations: the section labeled "problem areas" takes up more than half of the page. And the most recent discussion (which also triggered Zooko's post I believe) started with a blog post by Tav where he proposes (with my encouragement) some modest additions to CPython's existing restricted execution mode and challenges the world to break into it. In a follow-up post, Tav provides a better history of this topic than I could provide myself.

And yet, I remain extremely skeptical of this whole area. The various attacks on Tav's supervisor code show how incredibly subtle it is to write a secure supervisor. CPython's restricted execution model lets sandboxed (= untrusted) code call into the supervisor, where the supervisor's Python code runs with full permissions. In Tav's version, the sandbox is given access to the supervisor only through a small collection of function objects which the supervisor passes into the sandbox. Tav's proposed changes remove some introspection attributes from function and class objects that would otherwise give the sandboxed code access to data or functions that the supervisor is trying to hide from the sandbox. This basic idea works well and nobody has yet found a way to break out of the sandbox directly -- so far it looks like no other attributes need to be removed in order to secure the sandbox.

However, several attacks found non-obvious weaknesses in Tav's supervisor code itself: it is deceptively easy to trick the supervisor into calling seemingly safe built-in functions with arguments carefully crafted by the code inside the sandbox so as to make it reveal a secret. This uses an approach that was devised years ago by Samuele Pedroni to dispell doubt that restricted execution was unsafe in Python 2.2 and beyond.

Samuele's approach combines two properties of (C)Python: built-ins invoked by the supervisor run with the supervisor's permissions, and there are many places in Python where implicit conversions attempt to call various specially-named attributes on objects given to them. The sandboxed exploit defines a class with one of these "magic" attributes set to some built-in, and voila, the built-in is called with the supervisor's permissions. It takes some added cleverness to pass an interesting argument to the built-in and to get the result back, but it can be done: for details, see Tav's blog.

My worry about this approach is that a supervisor that provides a reasonably large subset of Python will have to implement some pretty complex functionality: for example, you'll have to support a secure way to import modules. My confidence in the security of the supervisor goes down exponentially as the its complexity goes up. In other words, while Tav may be able to evolve the toy supervisor in "safelite.py" into an impenetrable bastion after enough iterations of exploit-and-patch, I don't think this approach will converge in a realistic timeframe (e.g. decades) for a more fully-featured supervisor.

This lets me segue into another, perhaps more generic, concern with the idea of providing a secure subset of Python, whether it's based on restricted execution, capabilities, or restricting attribute references (like CapPython and Zope's RestrictedPython). Python's claim to fame comes largely from its standard library. People's proficiency with the language is not just measured by how well they can construct efficient algorithm implementations using lists and dicts: to a large extent it depends on how much of the standard library they master as well. Python's standard library is large compared to many other languages. Only Java seems to have more stuff that's assumed to be "always there" (except in certain embedded environments).

For a "secure" version of Python to succeed, it will need to support most of the standard library APIs. I'm distinguishing between the implementations and APIs here, for it is likely that many standard library modules use features of the language that aren't available by the secure subset under consideration. This doesn't have to be a show-stopper as long as an alternate implementation can be provided that uses only the secure subset.

Unfortunately, I expect that, due to a combination of factors, it will be impractical to provide a sufficiently large subset of the standard library for a sufficiently secure subset of Python. One problem is that Python, being a highly dynamic language, it supports introspection at many levels, including some implementation-specific levels, like access to bytecode in CPython, which has no equivalent in Jython, IronPython or other implementations. Because of the language's dynamic and introspective features, there is often no real distinction between a module's API and its implementation. While this is an occasional source of frustration for Python users (see e.g. the recent discussion about asyncore on python-dev), in most cases it works quite well, and often APIs can be simpler because of certain dynamic features of the language. For example, there are several ways that dynamic attribute lookup can enhance an API: automatic delegation is just one of the common patterns that it enables; command dispatch is another. All this leads me to think that a secure version of Python is unlikely to become complete enough to attract enough users to become viable. I'd be happy to be proven wrong, but it seems that the people most attracted to the idea are hoping that adding capabilities Python will somehow provide a shortcut to success. Unfortunately, I don't think it's a shortcut at all.

I should mention that I have some experience in this area: Google's App Engine (to which I currently contribute most of my time) provides a "secure" variant of Python that supports a subset of the standard library. I'm putting "secure" in scare quotes here, because App Engine's security needs are a bit different than those typically proposed by the capability community: an entire Python application is a single security domain, and security is provided by successively harder barriers at the C/Python boundary, the user/kernel boundary, and the virtual machine boundary. There is no support for secure communication between mutually distrusting processes, and the supervisor is implemented in C++ (crucial parts of it live in a different process).

In the App Engine case, the dialect of the Python language supported is completely identical to that implemented by CPython. The only differences are at the library level: you cannot write to the filesystem, you cannot create sockets or pipes, you cannot create threads or processes, and certain built-in modules that would support backdoors have been disabled (in a few cases, only the insecure APIs of a module have been disabled, retaining some useful APIs that are deemed safe). All these are eminently reasonable constraints given the goal of App Engine. And yet almost every one of these restrictions has caused severe pain for some of our users.

Securing App Engine has required a significant use of internal resources, and yet the result is still quite limiting. Now consider that App Engine's security model is much simpler than that preferred by capability enthusiasts: it's an all-or-nothing model that pretty much only protects Google from being attacked by rogue developers (though it also helps to prevent developers from attacking each other). Extrapolating, I expect that a serious capability-based Python would require much more effort to secure, and yet would place many more constraints on developers. It would have to have a very attractive "killer feature" to make developers want to use it...

Detecting Cycles in a Directed Graph

2009-01-29T12:54:00.001-08:00

I needed an algorithm for detecting cycles in a directed graph. I came up with the following. It's probably something straight from a textbook, but I couldn't find a textbook that had one, so I came up with this myself. I like the simplicity. I also like that there's a well-defined point in the algorithm where you can do any additional processing on each node for which you find that is not part of a cycle.

The function makes few assumptions about the representation of the graph; instead of a graph object, it takes in two function arguments that are called to describe the graph:

def NODES(): an iterable returning all nodes
def EDGES(node): an iterable returning all nodes reached via node's outgoing edges

In addition it takes a third function argument which is called once for each node:

def READY(node): called when we know node is not part of any cycles

The function returns None upon success, or a list containing the members of the first cycle found otherwise. Here's the algorithm:

def find_cycle(NODES, EDGES, READY):
  todo = set(NODES())
  while todo:
    node = todo.pop()
    stack = [node]
    while stack:
      top = stack[-1]
      for node in EDGES(top):
        if node in stack:
          return stack[stack.index(node):]
        if node in todo:
          stack.append(node)
          todo.remove(node)
          break
      else:
        node = stack.pop()
        READY(node)
  return None

Discussion: The EDGES() function may be called multiple times for the same node, and the for loop does some duplicate work in that case. A straightforward fix for this inefficiency is to maintain a parallel stack of iterators that is pushed and popped at the same times at the main stack, and at all times contains iter(node). I'll leave that version as an excercise.

Update: Fixed a typo in the algorithm (EDGES(top)) and renamed all to todo.

The History of Python - Introduction

2009-01-13T09:04:00.000-08:00

Python is 19 years old now. I started the design and implementation of the language on a cold Christmas break in Amsterdam, in late December 1989. It started out as a typical hobby project. Little did I know where it would all lead.

With Python's coming of age, I am going to look back on the history of the language, from the conception as a personal tool, through the the early years of community building, (If Guido was hit by a bus?), all the way through the release of Python 3000, almost 19 years later. It's been quite an adventure, for myself as well as for the users of the language.

This won't be an ordinary blog post -- it'll be an open-ended series. I may invite guest writers. I'll be touching upon many aspects of the language's history and evolution, both technical and social.

I'll start with the gradual publication of material I wrote a few years ago, when I was invited to contribute an article on Python to HOPL-III, the third installment of ACM's prestigious History of Programming Languages conference, held roughly every ten years. Unfortunately, the demands of the rather academically inclined reviewers were too much for my poor hacker's brain. Once I realized that with every round of review the amount of writing left to do seemed to increase rather than decrease, I withdrew my draft. Bless those who persevered, but I don't believe that the resulting collection of papers gives a representative overview of the developments in programming languages of the past decade.

The next destination of the draft was a book on Python to be published by Addison-Wesley. Again, the mountain of raw material that I had collected was too large and at the same time too incomplete to serve as a major section of the book, despite the editing help I received from David Beazley, a much better writer than I am.

As they tell prospective Ph.D. students, the best way to eat an elephant is one meal at a time. So today I am publishing the first bit of the elephant, perhaps still somewhat uncooked, but at least it's out there. Hopefully others who were there at the time can help clear up the inevitable omissions and mistakes. I have many more chapters, each still requiring some editing, and I expect this to be a long-running series. Therefore I am starting a separate blog title for this, unimaginatively called The History of Python. Follow the link and enjoy!

The Emperor's New Mind

2008-12-18T15:49:00.000-08:00

I recently re-read Roger Penrose's The Emperor's New Mind. I read it first in 1990, soon after it came out, and I still find it a stunning book, despite disagreeing with Penrose's speculations about consciousness somehow being boosted by quantum effect.

What makes the book so great in my view is that, in order to make his point, he has written an incredibly accessible textbook about a large number of topics in mathematics, physics and computer science. Penrose doesn't dumb down anything: he assumes the reader is an intelligent layperson, and explains each topic without compromise (though without getting into the technicalities of proofs).

Mathematical/computer topics include the theories of computability and algorithm complexity, Gödel's theorem, the Mandelbrot set, Turing machines (there's an appending with several pages of ones and zeros encoding a universal Turing machine -- I haven't checked it, but I'm sure that Penrose did), the Church-Turing thesis, and so on. In physics, he explains Maxwell's theory of electromagnetism (this was the first time I understood it), Phase space, special and general relativity, quantum theory, cosmology, black holes, space-time singularities and more. The table of contents reads like an overview of modern "hard" science. In the mean time Penrose also manages to explain Penrose tiling (the nonperiodic tiling of the plane, which he invented in the 1970s), the physics of nerve signals, Platonism, and important topics from the modern history of mathematics like Hilbert's program and Bertrand Russel's Principia Mathematica.

It's not surprising that Penrose shows prominently in the acknowledgments for Neil Stephenson's novel Anathem (in fact finding it there made me pick up my copy and start re-reading it).

Despite all this, I disagree with Penrose's claims about consciousness. Penrose does a good job separating his opinions on this topic from the science he presents, and in the end he cannot prove his hunches about consciousness any more than I can mine. Personally, I think that evolution is a perfectly fine explanation for our brains -- in other words, Richard Dawkins did a better job convincing me than Penrose. (I cannot recommend Dawkins' books enough -- you can skip The God Delusion though, just stick to his many excellent works about evolution and memes.)

In the Cloud or Not?

2008-12-08T14:37:00.001-08:00

Some people love the cloud. (As in cloud computing, e.g. Google App Engine, Amazon EC2, Microsoft Azure.) Others hate it. They gripe about lock-in, proprietary APIs and so on. (I would provide links to examples of both attitudes, but I don't have time right now, and you can fill those in yourself easily. :-)

I wonder if, apart from the field being young, the differences of opinion may be similar to the different attitude towards home ownership: some folks hate renting, citing landlord conflicts, noisy neighbors and so on. Others hate home ownership, due to the outsize financial commitment and risk (all too clear to many these days), the never-ending maintenance (new roof, new fence, new furnace, new bathroom, new kitchen, it never ends). I'm kind of in the middle myself, having had good landlords in the past, and disliking the maintenance effort/cost for my own home these days, but enjoying the independence.

Obviously cloud computing would be more similar to renting, while traditional datacenter ownership to home ownership (though without the aspect of building up wealth through ownership :-). Someone else can take the analogy further, and compare different styles of cloud services to different ways landlords can run their business. (E.g. with Google App Engine you get carpet and furniture as part of the deal, and meals delivered as an option, while Amazon EC2 rents out bare concrete units where you can do as you please. There's a market for both.)

If that's the case, we should expect that the love/hate posts will never stop, and we'll never convince all haters to love the cloud. But there will be plenty of business for the landlords from those who prefer not to own their own servers, and we might as well cater to them rather than be discouraged by the cloud haters.

Scala?

2008-11-21T09:53:00.001-08:00

I received a free copy of the Scala eBook by Martin Odersky, Lex Spoon, and Bill Venners. I tried to read it on my CalTrain commute, but ended up only skimming -- at 700+ pages it's a hefty tome. I'm also not in the primary target audience, as its focus seems to bounce between trying to entice Java programmers to try a better language, and an introduction to programming that happens to use Scala. I ended up going to the Scala website where I downloaded various other documents, such as a tutorial, a more technical overview paper, and the language reference.

Sad to say, I'm quite disappointed (in the language -- can't really say much about the quality of the eBook except that it's as big as the language). One of the first times I heard Scala mentioned it was a talk by Steve Yegge at Google I/O last May. Steve characterized Scala as "static typic's revenge" (I'm paraphrasing -- too lazy to watch the video to find that section) and went on to make fun of the incredible complexity of Scala's type system, which contains such esoteric concepts as type erasures, variance annotations, existential types, polymorphic method types, and many more (just scan the ToC of the language reference).

I have to agree with Steve -- if this is what it takes to have compile-time type-safety in a language, I'll take dynamic typing any day. There's got to be a better way -- perhaps Haskell? Haskell is a pure functional language with a fast implementation that seems to have solved the I/O problem of functional languages well -- while its Monads are truly deep and take real work to create, their use seems quite straightforeward.

Perhaps my biggest disappointment in Scala is that they have so many rules to make it possible to write code that looks straightforward, while being anything but -- these rules all seem to have innumerable exceptions, making it hard to know when writing simple code will work and when not. For example, the Scala book explains that you can use multiple 'if' qualifiers in its for-statement, but points out that you have to insert a semicolon in a position where you'd expect it to be inferred by the parser. To make matters even more mysterious, if you were to use curly braces instead of parentheses, you can omit the semicolon. All this is presented without any explanation. I found the explanation by combining two seemingly unrelated rules in the reference manual: first, the for-statement (technically called for-comprehension) allows both braces or parentheses with exactly the same semantics, but the rules for inferring semicolons are different inside braces than they are inside parentheses. Obvious, eh! :-)

Overheard

2008-11-14T14:00:00.001-08:00

"All you can do with a shell script is make it worse. But since this is Python, you can make it better."

Yes I am a sore loser

2008-11-10T07:30:00.000-08:00

I'm still devastated and baffled by the passing of California Proposition 8, the gay marriage ban.

What is the rationale behind a Yes vote? I cannot believe over half of Californians simply do what their pastor says. Actually, I cannot even believe that half the pastors in California are against gay marriage -- this is not a black and white issue even in religious circles, no matter what some claim the bible says. I'd like to hear from people who voted Yes and can explain their rationale. (So far the only pro-Prop-8 comments I've seen were slogans that fit on a bumper sticker but do not explain anything.)

And how is it possible that something called a state's constitution can be changed with a single, simple majority vote? In fact I would say it's not even a majority since a significant percentage of Californians eligible to vote didn't vote. Does this mean that in two years we can remove that amendment from the Californian constitution (or amend it out of existence) with a new referendum that is also approved by 50% plus one vote? That's not much of a constitution if you ask me! (In contrast, to change the Dutch constitution, both chambers of two successive parliaments must approve of the change, with a two-third majority.)

Cisco Developer Contest

2008-11-06T13:18:00.000-08:00

This hasn't had enough attention yet: Cisco is inviting application developers who "think outside the box", to innovate and promote the concept of the network as a platform. This is your opportunity to build exciting Linux based applications on the Cisco Application Extension Platform (AXP), and win a share of the total prize pool valued at US $100,000.

Read more at Cisco's contest site.

Bibles or computers -- it's the same thing

2008-11-03T09:51:00.000-08:00

This subject was on my list to blog eventually; but this clipping from the weekly OLPC mailing made it relevant:

Antonio Battro presented Pope Benedict XVI with an XO on Friday at the Vatican. The occasion was a papal audience for the Pontifical Academy of Sciences, of which Antonio is a member. They spoke about OLPC's philosophy and objectives in the developing world. Benedict seemed deeply pleased by our work.

I'm not surprised that the pope is pleased by the OLPC program. The mentality from which it springs is the same mentality which in past centuries created the missionary programs. The idea is that we, the west, know what's good for the rest of the world, and that we therefore must push our ideas onto the "third world" by means of the most advanced technology available. In past centuries, that was arguably the printing press, so we sent missionaries armed with stacks of bibles. These days, we have computers, so we send modern missionaries (of our western lifestyle, including consumerism, global warming, and credit default swaps) armed with computers.

It's the same thing, really.

Vote for Obama, No on California Prop 8

2008-10-30T09:35:00.000-07:00

I'm not a US citizen, so I can't vote in US elections (though I pay taxes like the best of them!), but my wife is. We have two signs in our front yard this week. One simply says "Obama", the other "No on Prop 8". I'd like to put up the equivalent of those signs in my blog.

If you're eligible to vote in the US, do me and the rest of the world a favor and vote for Obama. If you're voting in California, please help to reject Proposition 8, which is a blatant curtailing of freedom, equality and happiness for gay Californians. Defeating Prop 8 in California will pave the way for equal rights in other states and eventually all of the US. Don't make me ashamed of living here!

PS. If you think you have no time to vote, think again.

What makes me feel good

2008-10-29T13:27:00.001-07:00

Whenever I feel down, I look at the TIOBE programming community index, and it makes me feel better. :-)

Questions Answered

2008-10-27T11:07:00.000-07:00

I have now answered the top 20 questions in my section of "Ask a Google Engineer". Many of the remaining ones sound inappropriate or unanswerable, so I don't expect I'll be answering them, unless the popular vote really brings some of them to the top.

Why explicit self has to stay

2008-10-26T10:02:00.001-07:00

Bruce Eckel has blogged about a proposal to remove 'self' from the formal parameter list of methods. I'm going to explain why this proposal can't fly.

Bruce's Proposal

Bruce understands that we still need a way to distinguish references to instance variables from references to other variables, so he proposes to make 'self' a keyword instead. Consider a typical class with one method, for example:

class C:
   def meth(self, arg):
      self.val = arg
      return self.val

Under Bruce's proposal this would become:

class C:
   def meth(arg):  # Look ma, no self!
      self.val = arg
      return self.val

That's a saving of 6 characters per method. However, I don't believe Bruce proposes this so that he has to type less. I think he's more concerned about the time wasted by programmers (presumably coming from other languages) where the 'self' parameter doesn't need to be specified, and who occasionally forget it (even though they know better -- habit is a powerful force). It's true that omitting 'self' from the parameter list tends to lead to more obscure error messages than forgetting to type 'self.' in front of an instance variable or method reference. Perhaps even worse (as Bruce mentions) is the error message you get when the method is declared correctly but the call has the wrong number of arguments, like in this example given by Bruce:

Traceback (most recent call last):
File "classes.py", line 9, in
   obj.m2(1)
TypeError: m2() takes exactly 3 arguments (2 given)

I agree that this is confusing, but I would rather fix this error message without changing the language.

Why Bruce's Proposal Can't Work

Let me first bring up a few typical arguments that are brought in against Bruce's proposal.

There's a pretty good argument to make that requiring explicit 'self' in the parameter list reinforces the theoretical equivalency between these two ways of calling a method, given that 'foo' is an instance of 'C':

foo.meth(arg) == C.meth(foo, arg)

Another argument for keeping explicit 'self' in the parameter list is the ability to dynamically modify a class by poking a function into it, which creates a corresponding method. For example, we could create a class that is completely equivalent to 'C' above as follows:

# Define an empty class:
class C:
   pass

# Define a global function:
def meth(myself, arg):
   myself.val = arg
   return myself.val

# Poke the method into the class:
C.meth = meth

Note that I renamed the 'self' parameter to 'myself' to emphasize that (syntactically) we're not defining a method here. Now instances of C have a method with one argument named 'meth' that works exactly as before. It even works for instances of C that were created before the method was poked into the class.

I suppose that Bruce doesn't particularly care about the former equivalency. I agree that it's more of theoretical importance. The only exception I can think of is the old idiom for calling a super method. However, this idiom is pretty error-prone (exactly due to the requirement to explicitly pass 'self'), and that's why in Python 3000 I'm recommending the use of 'super()' in all cases.

Bruce can probably think of a way to make the second equivalency work -- there are some use cases where this is really important. I don't know how much time Bruce spent thinking about how to implement his proposal, but I suppose he is thinking along the lines of automatically adding an extra formal parameter named 'self' to all methods defined directly inside a class (I have to add 'directly' so that functions nested inside methods are exempted from this automatism). This way the first equivalency can be made to hold still.

However, there's one situation that I don't think Bruce can fix without adding some kind of ESP to the compiler: decorators. This I believe is the ultimate downfall of Bruce's proposal.

When a method definition is decorated, we don't know whether to automatically give it a 'self' parameter or not: the decorator could turn the function into a static method (which has no 'self'), or a class method (which has a funny kind of self that refers to a class instead of an instance), or it could do something completely different (it's trivial to write a decorator that implements '@classmethod' or '@staticmethod' in pure Python). There's no way without knowing what the decorator does whether to endow the method being defined with an implicit 'self' argument or not.

I reject hacks like special-casing '@classmethod' and '@staticmethod'. I also don't think it would be a good idea to automagically decide whether something is supposed to be a class method, instance method, or static method from inspection of the body alone (as someone proposed in the comments on Bruce's proposal): this makes it harder to tell how it should be called from the 'def' heading alone.

In the comments I saw some pretty extreme proposals to save Bruce's proposal, but generally at the cost of making the rules harder to follow, or requiring deeper changes elsewhere to the language -- making it infinitely harder to accept the proposal as something we could do in Python 3.1. For 3.1, by the way, the rule will be once again that new features are only acceptable if they remain backwards compatible.

The one proposal that has something going for it (and which can trivially be made backwards compatible) is to simply accept

def self.foo(arg): ...

inside a class as syntactic sugar for

def foo(self, arg): ...

I see no reason with this proposal to make 'self' a reserved word or to require that the prefix name be exactly 'self'. It would be easy enough to allow this for class methods as well:

@classmethod
def cls.foo(arg): ...

Now, I'm not saying that I like this better than the status quo. But I like it a lot better than Bruce's proposal or the more extreme proposals brought up in the comments to his blog, and it has the great advantage that it is backward compatible, and can be evolved into a PEP with a reference implementation without too much effort. (I think Bruce would have found out the flaws in his own proposal if he had actually gone through the effort of writing a solid PEP for it or trying to implement it.)

I could go on more, but it's a nice sunny Sunday morning, and I have other plans... :-)

Sorting a million 32-bit integers in 2MB of RAM using Python

2008-10-22T12:49:00.000-07:00

Someone jokingly asked me how I would sort a million 32-bit integers in 2 megabytes of RAM, using Python. Taking up the challenge, I leared something about buffered I/O.

Obviously this is a joke question -- the data alone would take up 4 megabytes, assuming binary encoding! But there's a possible interpretation: given a file containing a million 32-bit integers, how would you sort them with minimal memory usage? This would have to be some kind of merge sort, where small chunks of the data are sorted in memory and written to a temporary file, and then the temporary files are merged into the eventual output area.

Here is my solution. I'll annotate it in a minute.

NOTE: All my examples use Python 3.0. The main difference in this case is the use of file.buffer to access the binary stream underlying the text stream file.

#!/usr/bin/env python3.0
import sys, array, tempfile, heapq
assert array.array('i').itemsize == 4

def intsfromfile(f):
  while True:
     a = array.array('i')
     a.fromstring(f.read(4000))
     if not a:
         break
     for x in a:
         yield x

iters = []
while True:
  a = array.array('i')
  a.fromstring(sys.stdin.buffer.read(40000))
  if not a:
      break
  f = tempfile.TemporaryFile()
  array.array('i', sorted(a)).tofile(f)
  f.seek(0)
  iters.append(intsfromfile(f))

a = array.array('i')
for x in heapq.merge(*iters):
  a.append(x)
  if len(a) >= 1000:
      a.tofile(sys.stdout.buffer)
      del a[:]
if a:
  a.tofile(sys.stdout.buffer)

On my Google desktop (a 3 year old PC running a Googlified Linux, rating about 34000 Python 3.0 pystones) this took about 5.4 seconds to run, with an input file containing exactly 1,000,000 32-bit random integers. That's not so bad, given that a straightforward in-memory sort of the same input took about 2 seconds:

#!/usr/bin/env python3.0
import sys, array
a = array.array('i', sys.stdin.buffer.read())
a = list(a)
a.sort()
a = array.array('i', a)
a.tofile(sys.stdout.buffer)

Back to the merge-sort solution. The first three lines are obvious:

#!/usr/bin/env python3.0
import sys, array, tempfile, heapq
assert array.array('i').itemsize == 4

The first line says we're using Python 3.0. The second line imports the modules we're going to need. The third line here makes it break on those 64-bit systems where the 'i' typecode doesn't represent a 32-bit int; I am making no attempts to write this code portably.

Then we define a little helper that is a generator which reads integers from a file and yields them one at a time:

def intsfromfile(f):
  while True:
      a = array.array('i')
      a.fromstring(f.read(4000))
      if not a:
          break
      for x in a:
          yield x

This is where the performance tuning of the algorithm takes place: it reads up to 1000 integers at a time, and yields them one by one. I had originally written this without buffering -- it would just read 4 bytes from the file, convert them to an integer, and yield the result. But that ran about 4 times as slow! Note that we can't use a.fromfile(f, 1000) because the fromfile() method complains bitterly when there aren't enough values in the file, and I want the code to adapt automatically to however many integers are on the file. (It turns out we write about 10,000 integers to a typical temp file.)

Next we have the input loop. This repeatedly reads a chunk of 10,000 integers from the input file, sorts them in memory, and writes them to a temporary file. We then add an iterator over that temporary file, using the above intsfromfile() function, to a list of iterators that we'll use in the subsequent merge phase.

iters = []
while True:
  a = array.array('i')
  a.fromstring(sys.stdin.buffer.read(40000))
  if not a:
      break
  f = tempfile.TemporaryFile()
  array.array('i', sorted(a)).tofile(f)
  f.seek(0)
  iters.append(intsfromfile(f))

Note that for an input containing a million values, this creates 100 temporary files each containing 10,000 values.

Finally we merge all these files (each of which is sorted) together. The heapq module has a really nice function for this purpose: heapq.merge(iter1, iter2, ...) returns an iterator that yields the input values in order, assuming each input itself yields its values in order (as is the case here).

a = array.array('i')
for x in heapq.merge(*iters):
  a.append(x)
  if len(a) >= 1000:
      a.tofile(sys.stdout.buffer)
      del a[:]
if a:
  a.tofile(sys.stdout.buffer)

This is another place where buffered I/O turned out to be essential: Writing each individual value to a file as soon as it is available slows the algorithm down about twofold. Thus, by simply adding input and output buffering, we gained a tenfold speed-up!

And that's the main moral of the story.

Another lesson is praise for the heapq module, which contains the iterator merge functionality needed in the output phase. Also, let's not forget the utility of the array module for managing binary data.

And finally, let this example remind you that Python 3.0 is notso different from Python 2.5!

About This Blog

2008-10-10T12:14:00.000-07:00

You may wonder why I started a new blog, where I already have a perfectly fine blog on Artima. I am currently wondering too, since somehow my very first entry was flagged as spam by the helpful Blogger spam detection software, and now claims I have to request a manual review to prove I'm not a spammer. I'm guessing that I either used too many long, difficult words referring to schools of philosophy -- I've seen splogs containing long strings of text copied from philosophy textbooks. Or perhaps I quoted too many nonsense words from Anthem. Anyway, I've requested two reviews so far, but still nada. Fingers crossed.

As for the reason to start a new blog, the Artima blog is meant to be technical stuff about Python -- Artima in general is a site about OO programming, and I wanted to write about other stuff that interests me. I have a slew of topics lined up: other books I've read, more about my views on consciousness (with a lowercase 'c' :-), and a silly idea I call "planet of the nerds": what if Captain Kirk ran into a planet whose entire population was made up of nerds with IQs of 250 and no social skills? Would such a society even survive?

Anyway, this is just a test -- Blogger claims I cannot make new posts. Let's see if that's true!

Thoughts after reading Neal Stephenson's Anathem

2008-10-05T20:56:00.000-07:00

I just finished reading Neal Stephenson's new novel, Anathem. I don't know where to start: it's a fascinating story, if occasionally slow, but that seems unavoidable given the deep ideas Stephensons expose. I'm not an avid Science Fiction reader, though I don't avoid the genre. There's just so much else to read about! (And I'm a slow reader, especially in English, which is not my first language.) But I like Stephenson's work, which I first encountered with Cryptonomicon. I ate up the Baroque Cycle, and when Stephenson showed up at Google a few weeks ago to discuss Anathem, I tuned in from the SF office. Hearing him talk about his ideas made me want to read the book even more -- but I decided to do some "homework" first, and bought Snow Crash in the same Amazon order as Anathem, and read it first.

(Warning: mild spoilers may be ahead.)

Snow Crash is fascinating, but it rings a bit hollow -- in the end I felt like it was mostly a superbly crafted fantastic adventure story. The "deep ideas" in that book felt a bit fake: the technical details of how the Metaverse works make little sense from what I know about virtual reality systems (this was corroborated by a friend who worked in the game industry for 25 years), and the idea of an "ur-language" that is like the low-level software of our brains strikes me as nonsense from what I've read about the functioning of our brains (see note above :-). The idea of a virus or anti-virus that can be fed into our brains by appealing directly to this low-level software of hackers' brains then becomes rather bizarre, and the idea of feeding this same information into non-hackers' brains via the blood utter nonsense. So then we're left with a great, dark view of a possible future where many phenomena of modern society, from the mafia's code of honor to suburbs full of bored teenagers, have become fantastically exaggerated, and a lot of cool wish-it-could-be technology, from the Metaverse to skateboards and motorcycles with "smart wheels" (why doesn't the Wikipedia article mention those?). I find it hard to believe that there are many women who would enjoy this book, it's the ultimate testosterone fantasy.

Fast-forward to Anathem. Stephenson has gotten a lot better. It's more likely that women might appreciate this book (and not just because in the end the couple "get" each other and clearly will live happily ever after). As long as they're into philosophy and not afraid of long detailed explanations of space technology. Ok, so maybe it's still mostly a guy's thing (please prove me wrong!) but it's a lot less testosterone-laden, and the technology and "deep ideas" presented are a lot more realistic.

I find it interesting that in Snow Crash the (near) future has gotten completely out of hand, while in Anathem a world is depicted that develops more or less cyclically for thousands of years: after the high point of technology (roughly, today's age) things stay more or less the same, society and prosperity going down and up cyclically without much news being added. Stephenson's explanation for this is that most people prefer to deal with technology they can understand and tinker with, like internal combustion engines, rather than the more advanced space-age stuff that most Sci-Fi authors (including Stephenson, see Snow Crash) love to make up. Although nobody seems to object to the ubiquity of cell phones connected to the Internet -- they are apparently too useful (for society, or for the plot) to ban.

I loved the puzzles for the reader, small and large, that Stephenson spreads throughout the book. I recall that in Cryptonomicon he often starts a new chapter with a minute, detailed description of an everyday phenomenon from an unexpected vantage point or using precise scientific language, which often made me chuckle. There is some of that in Anathem, but the main class of puzzles is the introduction of new vocabulary (ostensibly because the world depicted is not Earth) for familiar things. E.g. ark for church, drummon, fetch and mobe for freight truck, pick-up truck and car, syntactic device or syndev for computer, praxis for engineering, Andrakhonic theorem for Pythagorean theorem, and Gardan’s Steelyard for Occam’s Razor. (I found one place where Stephenson apparently forgot to apply global substitution and used the word "computer-generated" instead of syndev-generated.) In general the new words are remarkably easy to remember once you've figured it out -- sometimes it helps to know Latin or French (for example fraa and suur are clearly from frère and soeur).

The only stuff that's hard is the names for the various philosophical schools -- probably because I'm not really all that well-schooled in this. I can recognize the references to Plato, but that's about it. There are probably tons of references to philosophic schools of the past two centuries, but I don't know my Nietzche from my Kant, and I'm not all that well-versed in interpretations of quantum mechanics. Except I did recognize the idea of consciousness as a quantum computer as originating with Roger Penrose -- I read his book long ago, and decided I simply disagreed. The whole idea of merging together world lines in such a way that the history of one world appears in the present of another sounds like a Sci-Fi device of the same nature as travel faster than light: useful as a plot device, but not realistic.

Yes, of course it's fiction! But Stephenson really does seem to try to make everything else realistic -- the ideas he presents have roots in real science, and so does much of the technology, from the "long now" clock to the electrodynamic tether propulsion device (both mentioned in the acknowledgements). So I guess at this point we (Stephenson and I) simply disagree on the correct interpretation of quantum mechanics, which is not something to be particularly worried about, as it's all highly speculative in the real scientific world too.

When we're talking about the nature of consciousness, I'm definitely in the camp of Douglas Hofstadter, who makes (what I think is) an eloquent point that it's just a bunch of extremely sophisticated software running on highly developed hardware, both evolved over a very long time, starting with the earliest animals that were capable of making decisions based on sensory input. I recently bought and read Hofstadter's I am a Strange Loop and loved most of it, although I had to skip some of the sentimental stuff; it made me pull out Gödel, Escher Bach and The Mind's I (both of which I'd read when I was about half my current age) and re-read much of them, enjoying them just as much as the first time (and probably understanding a lot more).

My only quibble with Hofstadter is his insistence on the importance of self-referentiality of consciousness. While I appreciate the relevance of introspection, and love the idea that the algorithms for searching our (various kinds of) memory are derived from the pattern matching algorithms originating in our sensory processing (which clearly was a precursor of consciousness), I don't believe that in order to be called "intelligent" a piece of software would necessarily have to have a concept of "I" that resembles that of a person. (And no, I don't think we're anywhere near developing such intelligent software yet -- we don't know enough about the most basic stuff like perception. For that matter, I think that the whole "Singularity" idea promoted by Ray Kurzweil is bulshytt, as the inhabitants of Stephenson's world would say.)

But I do agree with Hofstadter that there is no a priori reason why sufficiently complex (presumably layered) software couldn't be developed that has representations of real-world concepts that can be queried and updated and connected in ways very similar to the way this apparently happens in our brains. Personally, I think that one of the keys to the development of such software is better understanding of our preceptional mechanisms. Which is a long-winded segue into the work of Oliver Sacks, whose works I've also been reading recently. (I am about to dive into Musicophilia, his latest work.) Sacks writes yarns that are as accessible (or more) as Stephenson's, and almost as exciting (for me anyways), with the added value that they are science, not fiction.

I wish I could work in a reference to Richard Dawkins, whose ideals on evolution also seem highly relevant. (Even though to a 3rd generation atheist like myself his rant against organized religion seems a little over the top.) But I'll save that for later.