Eventlet is Awesome!

by Aaron

Eventlet is an asynchronous networking library for Python which uses coroutines to allow you to write non-blocking code without needing to perform the normal mental gymnastics that usually go along with asynchronous programming. There are a bunch of async/event-driven networking framworks (eventmachine, node.js, tornado, and twisted to name a few), and their defining characteristic is that they use select/epolll/kqueue/etc. to do I/O asynchronously. Asynchronous I/O is cool because when done correctly it allows your server to handle a much greater number of concurrent clients than the one-OS-thread-per-connection approach. Furthermore, since you're using co-operative rather than preemptive multitasking, you can safely update shared data structures without locks, which makes it a lot easier to write correct code.

Anyway, eventlet is pretty cool. If you like Python and you're interested in async programming, you should check it out. After all, anything that reduces the incidence of Heisenbugs is worth a look ;)

Proxymachine in 55 Lines

Since they're so specialized, playing with this kind of library requires a specific kind of project. Consequently, I decided to put together a "Hello Word!" version of Proxymachine. Proxymachine is a proxy built on eventmachine that lets you configure it's routing logic using Ruby. Don't get me wrong, Proxymachine is awesome and way more production ready than this. That being said, it's still friggin' cool that I could put togther a pale imitation of Proxymachine in less than 100 lines thanks to eventlet:

import functools
import eventlet

CHUNK_SIZE = 32384

class Router(object):
    def route(self, addr, data):
        raise NotImplemented

def merge(*dicts):
    result = {}
    for d in dicts:
        result.update(d)
    return result

def forward(source, dest):
    while True:
        d = source.recv(CHUNK_SIZE)
        if d == '':
            break
        dest.sendall(d)

def route(router, client, addr):
    blocks = []
    while True:
        block = client.recv(CHUNK_SIZE)
        if block == '':
            raise Exception('Failed to route request: "{0}"'.format("".join(blocks)))

        blocks.append(block)

        route = router.route(addr, "".join(blocks))
        if route is not None:
            print "Forwarded connection from {0} to {1}".format(addr, route)

            server = eventlet.connect(route)
            for block in blocks:
                server.sendall(block)

            eventlet.spawn_n(forward, server, client)
            forward(client, server)
            return


def start(router, **kwargs):
    defaults = {
        "listen": ('localhost', 8080),
    }

    config = merge(defaults, kwargs)
    print "Listening on:", config['listen']

    eventlet.serve(
        eventlet.listen(config['listen']),
            functools.partial(route, router())
    )

Roulette: A router in ten lines

The logic here is laughable, route inbound connections to either localhost:9998 or localhost:9999 depending on whether the remote port is divisible by two, but the point is that the routing logic could be anything. We're writing Python here. We could look stuff up in a database, or check the phase of the moon or y'know, do something useful.

import roulette

class Router(roulette.Router):
    def route(self, addr, data):
        if addr[1] % 2 == 0:
            return ("localhost", 9999)
        return ("localhost", 9998)

roulette.start(Router,
    listen = ("localhost", 80)
)

Grayvatar 2.0

by Aaron

In my post about Grayvatar, I warned everybody away from actually using it for anything as it was a complete toy. The major reason I cited was that it did not make any attempt to respect cache headers. Enter Grayvatar 2.0, which is slightly less of a toy as it, at least, makes a half-hearted attempt to respect cache headers.

The key addition was httplib2, which maintains it's own cache, so that we're not hitting Gravatar's servers for every single request we receive. The other big change was to copy cache headers from the client to the server and vice-versa. This means that we'll pass a long the cache-control: max-age=300 that we get from Gravatar or the cache-control: max-age=0 we get from the client. All of this adds about 20 lines on top of the existing implementation. You still shouldn't use it for anything, it's still a toy, but at least it's slightly less naive one.

import StringIO
import tempfile
import urllib, urllib2

import cherrypy
import httplib2
import Image

from paver.easy import path

URL = "http://www.gravatar.com/avatar/%s?%s"
cache_headers = ("cache-control",)


class Grayvatar(object):
    def __init__(self):
        tmp_dir = tempfile.mkdtemp(".cache")
        self.http = http = httplib2.Http(tmp_dir)

    @cherrypy.expose
    def default(self, *bits, **kwargs):
        if bits:
            cherrypy.response.headers["Content-Type"] = "image/png"
            url = URL % (bits[0], urllib.urlencode(kwargs))
            headers, img = self.get_img(url)

            for header in cache_headers:
                if header in headers:
                    cherrypy.response.headers[header] = headers[header]

            return img_as_str(img.convert("L"))

        pwd = path(__file__).abspath().parent
        return (pwd / "how_it_works.html").text()

    def get_img(self, url):
        headers, body = self.http.request(url,
            headers = project(cherrypy.request.headers, cache_headers)
        )
        return headers, Image.open(StringIO.StringIO(body))


def project(d, keys):
    return dict((k, d[k]) for k in keys if k in d)

def img_as_str(img):
    sock = StringIO.StringIO()
    img.save(sock, "png")
    return sock.getvalue()

if __name__ == "__main__":
    cherrypy.quickstart(Grayvatar())

Grayvatar

by Aaron
http://aaron.maenpaa.ca/grayvatar/634329486bd326c395c8b3539c035139?s=196&d=identicon&r=PG

The week before last I got to spend some time working on a prototype as part of a sekrit project at work. In order to give the prototype the air of not-quite-done, I did the whole thing in black and white. This worked great up until I added in Identicons to identify users, which added a bunch of brightly colored triangles and ruined the whole black-and-white aesthetic. I eventually ended up pulling a bunch of Identicons from Gravatar with wget and desaturated them with ImageMagik. It worked, but it was kind of gross.

Teh Codez

It occurred to me that it should be pretty straightforward to build a web app that implemented the Gravatar API and desaturate real Gravatars, so I took a crack at it:

import StringIO
import urllib, urllib2

import cherrypy
import Image

from paver.easy import path

URL = "http://www.gravatar.com/avatar/%s?%s"

class Grayvatar(object):
    @cherrypy.expose
    def default(self, *bits, **kwargs):
        if bits:
            cherrypy.response.headers["Content-Type"] = "image/png"
            url = URL % (bits[0], urllib.urlencode(kwargs))
            img = get_img(url).convert("L")
            return img_as_str(img)

        pwd = path(__file__).abspath().parent
        return (pwd / "how_it_works.html").text()

def get_img(url):
    sock = urllib2.urlopen(url)
    return Image.open(StringIO.StringIO(sock.read()))

def img_as_str(img):
    sock = StringIO.StringIO()
    img.save(sock, "png")
    return sock.getvalue()

if __name__ == "__main__":
    cherrypy.quickstart(Grayvatar())

I think it's awesome that, thanks to CherrPy and PIL, I could put together a web app that does all that 30 odd lines (including imports), but it's less awesome that so many of those lines are shuffling data in and out of a StringIO.

mod_wsgi

I set up an instance at: http://aaron.maenpaa.ca/grayvatar using Apache and mod_wsgi. I used a lightly adapted version of the the wsgi config from the CherryPy wiki.

import sys
sys.stdout = sys.stderr

import atexit
import threading
import cherrypy

sys.path = ['/home/aaron/code/grayvatar'] + sys.path

import grayvatar

cherrypy.config.update({
    'environment': 'embedded',
    'log.screen': True,
})

if cherrypy.__version__.startswith('3.0') and cherrypy.engine.state == 0:
    cherrypy.engine.start(blocking=False)
    atexit.register(cherrypy.engine.stop)

application = cherrypy.Application(grayvatar.Grayvatar(), script_name=None)

The most important change was adding 'log.screen': True to the config. This sends errors to stderr, which eventually makes it's way to /var/log/apache2/error.log which makes it possible to figure out what's going on when things don't go right.

How It Works

Just like Gravatar. The base URL is http://aaron.maenpaa.ca/grayvatar/. You calculate the MD5 hash of your email address, append it to the base URL and then add any query parameters that Gravatar supports. That gets you a URL like this: http://aaron.maenpaa.ca/grayvatar/634329486bd326c395c8b3539c035139?s=256&d=identicon&r=PG

It fetchs the appropriate Gravatar, desaturates and returns it. Keep in mind, this is a toy: It doesn't actually respect the cache headers Gravatar sends and worse, it doesn't even pass them along to the client.

Krypto and 24

by Aaron

Daily WTF inspired me to implement a Krypto and 24 solver:

import functools
import itertools
import operator

class Node:
        def evaluate(self): raise NotImplemted()
        def print(self): raise NotImplemted()

        def __add__(self, other): return Add(self, other)
        def __sub__(self, other): return Sub(self, other)
        def __mul__(self, other): return Mul(self, other)
        def __truediv__(self, other): return Div(self, other)

        def __str__(self):
                return "<Node: {}>".format(self.print())

        def __repr__(self):
                return str(self)

class Binary(Node):
        def __init__(self, left, right):
                self.left = left
                self.right = right

        def evaluate(self):
                try:
                        return self.op(
                                self.left.evaluate(),
                                self.right.evaluate(),
                        )
                except ZeroDivisionError:
                        return float("NaN")

        def print(self):
                return "({} {} {})".format(
                                self.left.print(),
                                self.symbol(),
                                self.right.print()
                )

        def op(self, left, rigth): raise NotImplemted()
        def symbol(self): raise NotImplemted()

class Unary(Node):
        def __init__(self, op, val):
                self.op = op
                self.val = val

        def evaluate(self):
                return self.op(self.val)

        def print(self):
                return str(self.evaluate())

def BinOp(op, symbol, commutative = True):
        class inner(Binary):
                def op(self, left, right):
                        return op(left, right)

                def symbol(self):
                        return symbol

                @classmethod
                def iscommutative(cls):
                        return commutative

        return inner

Add = BinOp(operator.add, "+")
Sub = BinOp(operator.sub, "-", commutative = False)
Mul = BinOp(operator.mul, "*")
Div = BinOp(operator.truediv, "/", commutative = False)
Lit = functools.partial(Unary, lambda x: x)

OPS = [Add, Sub, Mul, Div]

def generate_expressions(nodes):
        if len(nodes) == 1:
                yield first(nodes)

        for x, y, op in itertools.product(nodes, nodes, OPS):
                isnew = not op.iscommutative() or id(x) > id(y)
                if x is not y and isnew:
                        yield generate_expressions((nodes - set([x, y])) | set([op(x, y)]))

def flatten(xs):
        for x in xs:
                try:
                        for y in flatten(x):
                                yield y
                except TypeError:
                        yield x

def first(xs):
        for x in xs:
                return x

def krypto(nums, solution):
        def issolution(expr):
                return expr.evaluate() == solution

        nodes = set(map(Lit, nums))
        expr = first(filter(issolution, flatten(generate_expressions(nodes))))
        print(expr.print(), "=", expr.evaluate())

if __name__ == "__main__":
        import sys
        args = list(map(int, sys.argv[1:]))
        krypto(args[:-1], args[-1])

My favourite part is that the core of the algorithm is 6 lines:

def generate_expressions(nodes):
        if len(nodes) == 1:
                yield first(nodes)

        for x, y, op in itertools.product(nodes, nodes, OPS):
                isnew = not op.iscommutative() or id(x) > id(y)
                if x is not y and isnew:
                        yield generate_expressions((nodes - set([x, y])) | set([op(x, y)]))

The parametric classes are also a reminder of just how badass python is:

def BinOp(op, symbol, commutative = True):
        class inner(Binary):
                def op(self, left, right):
                        return op(left, right)

                def symbol(self):
                        return symbol

                @classmethod
                def iscommutative(cls):
                        return commutative

        return inner

Edit

2010-05-16: Apparently Python comes with an implementation of cross product.

Ford Circles

by Aaron

I picked up a copy of The Math Book after reading the review on John D. Cook's blog.

So far it has been pretty interesting and I've was plesently surprised with how much of the material I am familar with, despite the fact that I haven't studied math beyond the courses that are part of the engineering curriculum at my university.

The best part, though, has been the occasions when I find something that I can play with a little bit on my own. A good example is Ford Circles, which with a little time in NodeBox I had my own renderings:

Ford Circles

Here's the code:

from __future__ import division

scale(1000, 1000)

def circle(x, y, r):
    oval(x * 1000, y * 1000, 2 * r, 2 * r)

def ford(h, k):
    r = 1 / (2 * k**2)
    x, y = h/k, r
    print x, y, r
    circle(x, y, r)


for h in range(0, 200):
    for k in range(1, 200):
        ford(h, k)

... and here's a bigger rendering, if you're interested.