Older blog entries for kr (starting at number 11)

Asynchronous Programming in Python

Twisted is pretty good. It sits as one of the top networking libraries in Python, and with good reason. It is properly asynchronous, flexible, and mature. But it also has some pretty serious flaws that make it harder than necessary for programmers to use.

This hinders adoption of Twisted, and (worse) it hinders adoption of asynchronous programming in general. Unfortunately, fixing most of these flaws in the context of Twisted would cause massive compatibility problems. This makes me think the world could use a new, Pythonic, asynchronous programming library. Perhaps it should be a fork of Twisted; perhaps it should be a brand-new project. Either way, it would make life much nicer for programmers like you and me in the future.

Toward A Better Event Library

Here is what Twisted gets right:

  • Pervasive asynchrony.
  • The “reactor” pattern.
  • Each asynchronous function does not take callbacks as parameters; it just returns a promise (which Twisted calls a “deferred”).
  • Able to use modern select()-replacements like kqueue, epoll, etc.
  • Integrates with the GTK+ event loop. Same for other GUI toolkits.

These things are all absolutely crucial and Twisted nails them. This is what makes Twisted so great.

Here is what I would do differently:

  • Limited scope – This project has no need to include dozens of incomplete and neglected protocols. Instead, such things can easily (and should) be maintained as separate projects. For example, we don’t need two-and-a-half half-assed HTTP modules, but what if we had one excellent asynchronous HTTP library, which incidentally achieves asynchrony by means of this event library. It might start off as a port of httplib2, which is well designed even if it lacks asynchrony. This would leave the maintainers of the core event system more time to focus on making a really coherent, “as-simple-as-possible-but-no-simpler”, useful tool.
  • User-focused design – A good library, like a good language, should make simple things simple and hard things possible. Twisted makes simple things possible and hard things possible. Most users don’t particularly want to extend base classes to implement derived Factories and Protocols and Clients, they just want to fetch the document at a URL (asynchronously!). Achieving this ease of use is not terribly hard, but it requires conscious effort. You must start by designing the ideal top-level interface, then work downward and make it operate correctly. Twisted’s web modules (I don’t mean to pick only on HTTP here; these are just examples) look to me as if they started from the basic building blocks and added on pieces until HTTP was achieved. We are left with whatever interface happened to come out at the end. Further, they look like they were written by former C++ and Java programmers who haven’t yet fully realized that Python code doesn’t have to be so complicated.
  • Arbitrary events – Promises should let you send more than just “success” and “failure”. You should be able to emit arbitrarily-named events. For example, suppose you make an HTTP request. In the simple case, you just want the complete document when it is fully received. But what if you also want to update a progress bar for the transfer? You shouldn’t have to start digging through the HTTP library’s low-level unbuffered innards. Instead, the promise that eventually delivers you the HTTP response should also emit progress signals that you may observe if you wish.
  • Simple promises – Do not implicitly “chain” callbacks.

Simple Promises

This last problem deserves special attention. The rest are mere annoyances and could be suffered through, if not for implicit chaining. It is a fundamental design flaw, and I wouldn’t be surprised to learn that it’s responsible for more bugs in Twisted-using programs than any other single factor.

Let me first spell out exactly what I mean here by “implicitly chained” callbacks and “simple” promises. In Twisted, you can write:

  deferred = background_job()
deferred.addCallback(cb_1)
deferred.addCallback(cb_2)
deferred.addCallback(cb_3)

Each callback here will be given the return value of the previous callback. I’ll refer to that as implicit chaining.

Instead I advocate having the promise give each callback simply the same value – the original result of the background job. So I’ll call this a simple promise. (In these examples, I’ll use deferred for objects with implicit chaining and promise for simple promises.)

  promise = background_job()
promise.addCallback(cb_a)
promise.addCallback(cb_b)
promise.addCallback(cb_c)

In this example, each callback will get the exact same value. Nothing that any one of them does can affect the others.

Simple promises are more general. The key is to have addCallback and its friends return a new promise for the result of the callback. With this feature, you can still chain callbacks, but you must do it explicitly. That is a good thing. Consider a deferred with implicit chaining:

  def add4(n):
  return n + 4

deferred = background_job()
deferred.addCallback(add4)
deferred.addCallback(log)

Supposing background_job supplies a value of 3, this example will log 7. We can just as easily do that without implicit chaining:

  def add4(n):
  return n + 4

promise = background_job()
promise2 = promise.addCallback(add4)
promise2.addCallback(log)

This also logs 7. Now let’s look at an example starting with a simple promise:

  promise = background_job()
promise.addCallback(log)
promise.addCallback(log)

This logs 3, twice. But try doing this with implicit chaining. It can’t be expressed. (Yes, you could achieve the same output in many different ways, but here I’m concerned with the structure of control flow.)

More importantly, implicitly chained callbacks are confusing. You must pay careful attention to the order in which you add callbacks. They require complicated diagrams to explain how they behave. If you want to insert a new callback somewhere, you have to be extra careful when you do it, to ensure it goes in the right place in the chain. By contrast, if you want to insert a new callback somewhere with simple promises, you have only to stick it on the correct promise.

Further, implicit chaining makes you do extra work to propagate return values and errors, even when your callback properly doesn’t care about such things. Let’s say you have the following snippet (which is the same for either a promise or a deferred):

  either = background_job()
either.addCallbacks(my_result, my_error_handler)

You just want some basic logging to check what’s going on. With a simple promise, that’s easy:

  promise = background_job()
promise.addCallback(log)
promise.addCallbacks(my_result, my_error_handler)

With implicit chaining, it’s more work:

  def safe_identity_log(x):
  try:
    log(x)

  # If log raises an exception, we still
  # want our real callback to fire, so we
  # have to catch everything here, even
  # though that has nothing to do with the
  # function of this callback.
  except:
    pass

  # Likewise, we must take care to return
  # the original value, or else the
  # callback will just get None.
  return x

deferred = background_job()
deferred.addCallback(safe_identity_log)
deferred.addCallbacks(my_result, my_error_handler)

This Post is Too Long

Anyway. That’s all I got. I really want to see this exist. So badly, I might actually do it myself. But it will have to wait a bit.

Addendum: Coroutines and Continuations

Writing good code in most asynchronous systems (including Twisted, node.js, and even E) feels inside-out. Your results are passed in as parameters; they don’t come out as return values like they normally would. Same for exceptions. This results in more verbosity, and it just feels weird.

My earlier post The Wormhole describes a transformation that turns things right-side out again. (It’s built out of continuations, but it could just as well be done with coroutines, say in Python.) It makes writing correct asynchronous code almost as easy as writing correct synchronous code. However, it can only be done correctly if your promises are of the simple variety. I’ve since learned that Twisted has attempted this trick. That implementation is useful, but it has several sharp corners. For example, this will not do what you would hope:

  background_deferred = None
can_background_job_complete = False

@deferred.inlineCallbacks
def f():
  global background_deferred
  background_deferred = background_job()
  value = yield background_deferred
  returnValue(value + 4)

final_deferred = f()
background_deferred.addCallback(log)
final_deferred.addCallback(log)
can_background_job_complete = True

Supposing background_job supplies 3, what will this log? In real life: None, then 7. If these were simple promises, it would log 3, then 7.

Syndicated 2009-12-10 08:00:00 from Keith Rarick

Projects I Want

Some software I’d love to see get made, but that I don’t have time to write myself.

CouchDB URL Wrapper

CouchDB’s interface is almost good enough to expose directly to the public, but its URLs are ugly and crufty. See “URL as UI” and “Cool URIs don’t change” for some philosophy.

I’d like to see a thin wrapper that lets you design arbitrary clean URLs for CouchDB. It needn’t do anything else.

Face Detection in Javascript

When I upload photos to Facebook, why to I have to locate the faces by hand? Why doesn’t Facebook do it for me? Javascript (in modern browsers) is now fast enough to do real face detection.

Many other web sites could benefit from this, too. There should be a free, high-quality Javascript library for face detection. At vasc.ri.cmu.edu/NNFaceDetector/ you can find papers describing a pretty good algorithm.

Face Recognition in Javascript

As an extension of the above, try to identify the people whose faces have been detected. Recognition is less generally-applicable than detection, but certainly Facebook-like sites can benefit from this. They could completely automate the process of tagging photos. Leave humans to identify the missing faces and false matches.

Doctest-Style Tool for Network Protocols

I think doctest is pretty nice. I want a tool much like doctest, but for network conversations rather than python interpreter conversations.

So you could write something like:

  >>> GET / HTTP/1.1
>>> Server: localhost
>>>
HTTP/1.1 200 OK
Content-type: text/plain
Content-Length: 6

hello

and this tool will check that your new web server is working.

Syndicated 2009-11-18 08:00:00 from Keith Rarick

File Management Ideas

In theory, Gnome Zetigeist makes me happy; kudos to the people working on it for daring to make something new. Its concept excites me, but its design specifics leave me wanting. I think we can do better, and here are some concrete design ideas to back up my claim.

First I want to recognize that the iTunes-style (or Rhythmbox-style or Banshee-style) interface is successful at mitigating the complexity of a huge collection of files. There are just a few salient aspects of such an interface: a list of “data sources” on the left (including “playlists” and “smart playlists”) and a data display on the right. The data display is usually, but not always, a scrolling table with sortable columns. It is also searchable and the results update instantly (sub-250ms or, ideally, before the next frame).

This interface should be applied to all user files, not just media. I don’t advocate an auto-generated interface. Rather each data source (each item in the blue side bar) must be thoughtfully designed. Here are a few examples.

Media

For the Music, Movies, and TV Shows, start with an exact copy of iTunes. It’s pretty good. Then go ahead and make changes if you wish, but your changes must actually be better, not merely different.

Documents

The Documents, Spreadsheets, and Presentations items would simply give appropriately-filtered lists of files.

Downloads

I’m staring at three windows. The first one is drawn by Firefox; it shows a list of files I am currently downloading. The second is drawn by Nautilus; it shows a list of files I have recently downloaded. The third is drawn by Transmission; it shows a list of files I am currently downloading with BitTorrent.

Most of the time I do not care about these distinctions. I simply want to get the file I just downloaded. If it hasn’t finished yet, tell me so. I do not know, a priori, if it has finished downloading – that’s part of why I want to see it.

The Downloads item should present a list of files that have been or are being downloaded (in reverse chronological order by default). It should handle HTTP, FTP, BitTorrent, and all other things (hello, plugins…) that conceptually allow you to “download” a file.

Bookmarks

Firefox lets me make bookmarks of web pages. Gnome lets me make bookmarks of things on my computer. Again, I mostly do not care about this distinction. Any open window that represents a file should let me make a bookmark. The window could be showing a spreadsheet, video, web page, mail message, or something else. I don’t care. Just give me a little star button like in Gmail. The star should probably be in the window title bar. (I think this would require an EWMH extension.)

The Bookmarks item should then present a list of things I have starred.

It should also understand Delicious, Weave, and similar things (hello, plugins…).

History

Gnome keeps a list of recently opened files. Firefox keeps a list of recently visited web pages. You guessed it; I don’t often care about that distinction. The actual data display should be at least as useful as what you get in a modern web browser.

Trash

Trash is relatively prosaic, but I’ll go out on a limb and suggest that items in the Trash should be deleted automatically after 30 days, or when space is needed. I should not have to empty the Trash myself.

Photos

This one is interesting because it probably makes most sense to show thumbnail images rather than a table of text. Sort of like F-Spot.

Preferences & Applications

These aren’t in my mockup, but might make sense to include.

Syndicated 2009-09-23 07:00:00 from Keith Rarick

The Wormhole

I’m working on an experimental programming language called Sodium. Although I haven’t introduced the language yet, I must share a wonderful idea that recently occurred to me. These examples are written in Sodium, but I’ve avoided some unusual idioms; hopefully they will make sense to anyone with some programming background.

If I do a CPS transform, I can easily do exception-passing with continuations, exactly like return values. Every expression will have two continuations: success and failure (corresponding to return and raise). This implies call-with-current-continuations, plural. And that means I can write the following mind-blowing function:

  def (wormhole promise):
  call/ccs (fn (success failure)
              (promise.on-success success)
              (promise.on-failure failure)
              (escape.))

(Here, escape is just another continuation, saved at the beginning of the process, that pops back out to the main event loop.)

What does wormhole do? Consider the following snippet of typical asynchronous I/O code:

  site = "example.net"
path = "/robots.txt"
promise = (http.get site path)
promise.on-success (fn (robots-txt)
                      (spider site robots-txt))
promise.on-failure (fn (error)
                      (spider-all site))

This sort of thing can get pretty deeply nested and ugly, especially if you need to use lots of local variables.

Using wormhole, you can rewrite it:

  site = "example.net"
path = "/robots.txt"
try:
  robots-txt = (wormhole (http.get site path))
  spider site robots-txt
catch error:
  spider-all site

This new example is fully asynchronous, just like the first one, but it is much more readable (as long as you know what’s really going on under the hood).

The wormhole operator has pretty serious implications for any callers of your code who expect things to happen in the usual synchronous order. It’s not clear if the resulting code is really any better, on balance.

Certainly, anyone tempted to use this device should think hard first. At least until we understand it better and develop rules of thumb. I think this function should be discouraged for library code, but, in the right circumstances, it might do for top-level application code. The end result can be simple and pretty while still fully asynchronous.

Syndicated 2009-09-05 07:00:00 from Keith Rarick

Upset at Apple?

Steven Frank has a post about Apple’s iPhone app store policies (or lack thereof).

“I’m furious with Apple and AT&T right now, with regard to the iPhone.”

Really? Dude, what did you expect? It’s Apple.

“The boat may turn slowly, but nothing before has ever suggested to me that Apple are actively malicious.”

No, actually, Apple has a long history of active maliciousness.

But there is hope for the future. The Palm Pre (and to some extent, Android) is set to bring serious competition. When that happens, Apple will be forced to adopt rational policies or lose their developers, followed by their users.

Why expect this? Compared to the iPhone, the Pre currently has essentially three disadvantages, all of which will probably disappear over time, and one big advantage, which will never go away.

Pre’s Disadvantages:

  1. Inferior design. Debatable, and certainly fixable.
  2. Fewer (good) apps. Of course. iPhone has a two-year head start. But this will reverse, because of the advantage below.
  3. Worse network coverage. Sprint < AT&T; Verizon > AT&T. Just wait six months.

Pre’s Advantage:

  1. Javascript. Don’t underestimate the effect of millions of brilliant, hungry web programmers and designers who will never write a line of Objective-C in their lives.

    The iPhone can never overcome this without becoming a Pre clone, and Apple is too proud to do that. I think. Actually, I’m not so sure about this last statement. Apple will probably just copy the Pre and then pretend like they invented HTML-CSS-Javascript-based phone apps.

Syndicated 2009-07-31 07:00:00 from Keith Rarick

Places to Eat

Presenting a list of food places Tracy and I frequent. These all have four- or five-star food in our book. If you know of a great place that isn’t on here, we probably have never been there! Tell us about it.

Or see Tracy & Keith’s Food List in a larger map.

Syndicated 2009-07-29 07:00:00 from Keith Rarick

One-Click Cloning

Here’s an easy way to enable all those git:// URIs you see in the git repos.

First, save the following shell script somewhere in your path, name it “git-web-clone”, and make it executable.

Then, register a protocol handler in Firefox:

Visit about:config; right-click and select New → String, enter “network.protocol-handler.app.git” as the name, and “/path/to/git-web-clone” as the value.

Then right-click and select New → Boolean, enter “network.protocol-handler.external.git” as the name, and select true as the value.

For bonus points, let’s register a protocol handler for the rest of Gnome:

$ gconftool-2 --set --type=string /desktop/gnome/url-handlers/git/command '/path/to/git-web-clone "%s"'
$ gconftool-2 --set --type=bool /desktop/gnome/url-handlers/git/enabled true
$ gconftool-2 --set --type=bool /desktop/gnome/url-handlers/git/need-terminal false

Now, clicking on any git:// URI will clone the repo into your work directory. Nice!

Syndicated 2009-07-27 07:00:00 from Keith Rarick

Probability and “Anthropic” Arguments

At Accelerating Future, Michael Anissimov has a post aptly titled “More Anthropic Nonsense?”. In it, he asks why this argument is wrong:

The joke about this is that delays keep happening is because the LHD would kill us all if it worked and that it’s anthropically likely that we’d be born into a universe with a high population, one where human extinction keeps not happening for “mysterious” reasons.

Here’s a selection from The Meaning of It All, an excellent book of a set of three lectures by Richard Feynman:

I now turn to another kind of principle or idea, and that is that there is no sense in calculating the probability or the chance that something happens after it happens. A lot of scientists don’t even appreciate this. In fact, the first time I got into an argument over this was when I was a graduate student at Princeton, and there was a guy in the Psychology department who was running rat races. I mean, he has a T-shaped thing, and the rats go, and they go to the right, and the left, and so on. And it’s a general principle of psychologists that in these tests they arrange so that the odds that the things that happen happen by chance is small, in fact, less than one in twenty. That means that one in twenty of their laws is probably wrong. But the statistical ways of calculating the odds, like coin flipping if the rats were to go randomly right and left, are easy to work out. This man had designed and experiment which would show something which I do not remember, if the rats always went to the right, let’s say. I can’t remember exactly. He had to do a great number of tests, because, of course, they could go right accidentally, so to get it down to one in twenty by odds, he had to do a number of them. And it’s hard to do, and he did his number. Then he found that it didn’t work. They went to the right, and they went to the left, and so on. And then he noticed, most remarkably, that they alternated, first right, then left, then right, then left. And then he ran to me, and he said, “Calculate the probability for me that they should alternate, so that I can see if it is less than one in twenty.” I said, “It probably is less than one in twenty, but it doesn’t count.” He said, “Why?” I said, “Because it doesn’t make any sense to calculate after the event. You see, you found the peculiarity, and so you selected the peculiar case.”

For example, I had the most remarkable experience this evening. While coming in here, I saw license plate ANZ 912. Calculate for me, please, the odds that of all the license plates in the state of Washington I should happen to see ANZ 912. Well, it’s a ridiculous thing. And, in the same way, what he must do is this: The fact that the rat directions alternate suggests the possibility that rats alternate. If he wants to test this hypothesis, one in twenty, he cannot do it from the same data that gave him the clue. He must do another experiment all over again and then see if they alternate. He did, and it didn’t work.

The application of this principle to anthropic arguments is left as an excercise for the reader.

Syndicated 2009-07-23 07:00:00 from Keith Rarick

Two Resizing Features I’d Like to See

I have are two features I’d like to see done in a Firefox extension. The goal of each of them is to eliminate horizontal scrolling.

Shrink-Wrap

Provide a button, labelled “shrink-wrap”, that will resize the browser window so it’s just big enough to display the page with no horizontal scrollbars. Probably should have a reasonable minimum size (such as 640px) and maximum size (the width of the screen).

Fit Width

This is the same feature, but in the other direction. Rather than resizing the window to fit the content, resize the content to fit the window!

Probably works best when “Zoom Text Only” is unchecked.

I bet this sort of thing already exists in mobile phone browsers, but I want it on my desktop.

Syndicated 2009-07-15 07:00:00 from Keith Rarick

Polymorphism

I’ll never forget when I first discovered that Smalltalk has no special forms for conditionals. Smalltalk has no if statement. That moment changed the way I think about programming (as happens with any worthwhile language, according to Alan Perlis).

A conditional expression in Smalltalk is just a simple method call on a boolean object.

  (x > 3) ifTrue: [y process]

The square brackets form a lambda expression; ifTrue: is the name of a method. Here is the same structure translated into Python syntax.

  (x > 3).ifTrue(lambda: y.process())

That all looks fine, if not particularly inspiring. The real “aha!” comes when you start to ask how such a method could possibly be implemented. If there’s no if statement, how can a boolean object decide whether or not to run the callback function? It can’t, but it doesn’t need to. Since there are two boolean objects, true and false (each of which is the only instance of a distinct class, True or False), each one can have its own behavior. So true’s ifTrue: method simply runs the callback, and false’s is even simpler.

  True>>ifTrue: consequent
  ^consequent value

False>>ifTrue: consequent
  ^nil

Again, here is a (ficticious) Python version of the same structure.

  class true(bool):
  def ifTrue(self, consequent):
    return consequent()

class false(bool):
  def ifTrue(self, consequent):
    return None

This is the definition of polymorphism – two objects can provide the same interface with different behavior.

If you understand this concept and apply it in your every-day programming, you code will turn out simpler, more concise, and easier to modify or extend. How? Let’s look at a practical example.

Example

Here’s a piece of Ruby code I found recently while browsing the Jekyll source code.

  class Hash
  # Merges self with another hash, recursively.
  # 
  # This code was lovingly stolen from some random gem:
  # http://gemjack.com/gems/tartan-0.1.1/classes/Hash.html
  # 
  # Thanks to whoever made it.
  def deep_merge(hash)
    target = dup
    
    hash.keys.each do |key|
      if hash[key].is_a? Hash and self[key].is_a? Hash
        target[key] = target[key].deep_merge(hash[key])
        next
      end
      
      target[key] = hash[key]
    end
    
    target
  end
end

This code defines a new binary operation, deep_merge, on Hash instances. It is like the existing Hash#merge except that it is defined recursively, so that when the left- and right-hand entries are both Hash instances, they are “deeply merged” instead of one replacing the other.

This code is quite useful and simple enough, but it can be improved. I tend to identify things to improve by the smell; though I don’t usually manage to identify smells consciously, that’s how my mind likes to work.

The first smell I notice here is a “copy, modify, replace” pattern common in imperative-style writing. Rather than copying and updating structures in-place, it’s usually clearer and more concise to generate the new structure directly, so let’s try to make this code more stylistically functional. In this case, we can simplify things a lot by writing deep_merge in terms of Hash#merge.

  class Hash
  def deep_merge(hash)
    merge(hash) do |key, lhs, rhs|
      if lhs.is_a? Hash and rhs.is_a? Hash
        lhs.deep_merge(rhs)
      else
        rhs
      end
    end
  end
end

The second (and more important) smell is use of the is_a? method. Often, is_a? can be replaced by polymorphism.

Because deep_merge is recursive, we can usefully revise our definition of deep_merge to apply to all objects, not just Hash instances. When we do so, most applications of deep_merge are degenerate – if the left-hand side is not a Hash, the left-hand object is simply replaced by the right-hand object.

  class Object
  def deep_merge(other)
    other
  end
end

The remaining cases can now be handled even more simply.

  class Hash
  def deep_merge(other)
    merge(other) do |key, lhs, rhs|
      lhs.deep_merge(rhs)
    end
  rescue TypeError
    super(other)
  end
end

(I’ve changed the parameter name here from hash to other because we are no longer assuming it is a Hash instance.)

Organizing things this way has benefits beyond clarity. Suppose we want to alter the meaning of deep_merge so that it concatenates arrays. All we need to do now is override deep_merge in the Array class.

  class Array
  def deep_merge(other)
    self + other
  rescue TypeError
    super(other)
  end
end

Or suppose instead that we want the elements of the arrays to be deeply merged.

  class Array
  def deep_merge(other)
    (0...[size, other.size].max).map do |i|
      if i < other.size
        self[i].deep_merge(other[i])
      else
        self[i]
      end
    end
  end
end

Though there’s some noise in this code to deal with arrays of uneven lengths, its structure is still straightforward. Further, we didn’t need to touch Hash#deep_merge to add this feature.

Syndicated 2009-02-13 08:00:00 from Keith Rarick

2 older entries...

New Advogato Features

New HTML Parser: The long-awaited libxml2 based HTML parser code is live. It needs further work but already handles most markup better than the original parser.

Keep up with the latest Advogato features by reading the Advogato status blog.

If you're a C programmer with some spare time, take a look at the mod_virgule project page and help us with one of the tasks on the ToDo list!