Valued Lessons

Message Passing Conccurrency (Actor Model) in Python

2008-06-27T13:43:00.000-07:00

As I wrote previously, I'm a fan of message-passing concurrency. But to use it in python, I had to write my own infrastructure. It's far from perfect, but it's working for me. I've simplified it a bit and prepared some code to share with you.

The basic idea of my framework is to be and simple and easy to use as possible. There's no Erlang-style pattern matching or process linking. There isn't even any built-in error handling. But, there's a lot of support for the typical "react loop" style of message handling.

The architecture is very simple. There's one thread per actor. An actor is just an object you can send a message to. The actor receives the messages in the order they were sent. You always know the sender of the message; it's built right in. There's also "Bridge" that allows you to interact with actors from non-actor code.

The only tricky thing you'll see is a "handles" decorator. This is used to help you identify how you want an actor to handle a given message type. It helps you avoid re-creating a message loop and dispatcher yourself for every actor.

I've included a little example of how to use the framework. It obviously quite simple, but keep in mind that I used little more for the foundation of a rather complex file synchronization application. A little bit goes a long way.

So, here it is. Cut, paste, and run.


from threading import Thread, Event
from Queue     import Queue, Empty

class IActor:
    pass
    # send(message, sender)

class HandlerRegistry(dict):
    # should be used as a decorator
    def __call__(self, typ):
        def register(func):
            self[typ] = func
            return func
        return register

OtherMessage = "Other Message"

class Stop(Exception):
    def __repr__(self):
        return "Stop()"

class Stopped:
    def __repr__(self):
        return "Stopped()"

class ActorNotStartedError(Exception):
    def __init__(self):
        Exception.__init__(self, "actor not started")

class Actor(IActor):
    @classmethod
    def spawn(cls, *args, **kargs):
        self = cls(*args, **kargs)
        self.mailbox = Mailbox()
        start_thread(target = self.act, as_daemon = True)
        return self

    def send(self, message, sender):
        if self.mailbox is None:
            raise ActorNotStartedError()
        else:
            self.mailbox.send(message, sender)

    def receive(self):
        if self.mailbox is None:
            raise ActorNotStartedError()
        else:
            return self.mailbox.receive()

    # override if necessary
    def act(self):
        self.handleMessages()



    handles = HandlerRegistry()

    @classmethod
    def makeHandles(*classes):
        return HandlerRegistry((typ, handler) for cls in classes for (typ, handler) in cls.handles.iteritems())

    def handleMessages(self):
        try:
            while True:
                message, sender = self.receive()
                self.handleMessageWithRegistry(message, sender)
        except Stop:
            pass

    def handleMessageWithRegistry(self, message, sender):
        registry = self.__class__.handles
        handler  = registry.get(message.__class__) or registry.get(OtherMessage)
        if handler is not None:
            handler(self, message, sender)

    @handles(OtherMessage)
    def onOther(self, message, sender):
        pass

    @handles(Stop)
    def onStop(self, message, sender):
        sender.send(Stopped(), self)
        raise message

def start_thread(target, as_daemon, name = None):
    thread = Thread(target = target)
    if name:
        thread.setName(name)
    thread.setDaemon(as_daemon) 
    thread.start()
    return thread

class Mailbox:
    def __init__(self):
        self.mailbox = Queue()

    def send(self, message, sender):
        self.mailbox.put((message, sender), block = False)

    def receive(self, timeout = None):
        return self.mailbox.get(block = True, timeout = timeout)

class Bridge(IActor):
    def __init__(self):
        self.mailbox = Mailbox()

    def send(self, message, sender):
        self.mailbox.send(message, sender)

    def call(self, target, request, timeout, default = None):
        self.sendRequest(target, request)
        return self.receiveResponse(timeout, default)

    # targeted_requests can be an iterator
    def multiCall(self, targeted_requests, timeout, default = None):
        count = 0
        for target, request in targeted_requests:
            self.sendRequest(target, request)
            count += 1
            
        for _ in xrange(count):
            yield self.receiveResponse(timeout, default)

    def stop(self, actors, timeout):
        stop = Stop()
        return list(self.multiCall(((actor, stop) for actor in actors), timeout, default = None))

    def sendRequest(self, target, request):
        target.send(request, self)

    def receiveResponse(self, timeout, default):
        try:
            message, sender = self.mailbox.receive(timeout = timeout)
            return message
        except Empty:
            return default
        

if __name__ == "__main__":
    import time

    class GetInventory:
        pass

    class Task:
        def __init__(self, input, destination):
            self.input       = input
            self.destination = destination

    class Worker(Actor):
        handles = Actor.makeHandles()

        def __init__(self, skill):
            self.skill = skill

        @handles(Task)
        def onTask(self, task, sender):
            output = self.skill(task.input)
            task.destination.send(output, self)

    class Warehouse(Actor):
        handles = Actor.makeHandles()

        def __init__(self):
            self.inventory = []

        @handles(GetInventory)
        def onGetInventory(self, message, sender):
            # copy the inventory to avoid anyone mutating it
            sender.send(list(self.inventory), self)
            
        @handles(OtherMessage)
        def onTaskResult(self, result, sender):
            self.inventory.append(result)

    worker    = Worker.spawn(lambda x : x * 2)
    positives = Warehouse.spawn()
    negatives = Warehouse.spawn()
    bridge    = Bridge()

    for val in [1, 2, 3, -2, -4, -6]:
        warehouse = positives if val >= 0 else negatives
        worker.send(Task(val, warehouse), sender = None)

    print bridge.call(positives, GetInventory(), 1.0) #should be [ 2,  4,   6]
    print bridge.call(negatives, GetInventory(), 1.0) #should be [-4, -8, -12]
    print bridge.stop([worker, positives, negatives], 1.0) #should be [Stopped(), Stopped(), Stopped()]

    
    class Start:
        def __init__(self, target):
            self.target = target

    class Ping:
        def __repr__(self):
            return "Ping()"

    class Pong:
        def __repr__(self):
            return "Pong()"

    class Pinger(Actor):
        handles = Actor.makeHandles()

        @handles(Start)
        def onStart(self, start, sender):
            start.target.send(Ping(), self)

        @handles(Pong)
        def onPong(self, pong, sender):
            print "-",
            sender.send(Ping(), self)
            
    class Ponger(Actor):
        handles = Actor.makeHandles()

        @handles(Ping)
        def onPing(self, ping, sender):
            print "+",
            sender.send(Pong(), self)

    # should print lots of +-+-+-
    pinger = Pinger.spawn()
    ponger = Ponger.spawn()
    pinger.send(Start(ponger), sender = None)
    time.sleep(0.1)
    bridge.stop([pinger, ponger], 1.0)

My Experience with Message Passing Concurrency

2008-06-27T12:43:00.001-07:00

I'm working on a peer-to-peer file synchronization program. It's really concurrent and distributed, and it's forced me to
learn a thing or two about the concurrency models that we use as programmers. Over the past few years, I've tried both the shared-state model common to C, C++, Java, C#, Python, etc, and the message-passing model unique to Erlang and Scala. In my experience, the message-passing model (aka Actor Model) is far superior to the shared-state model for writing distributed applications. After having used both extensively, I'd go so far as to say that for distributed programming, shared-state concurrency is upside down and backwards.

Here's my informal proof that message-passing concurrency is necessary in a distributed system:

Since the system in distributed, real shared state is impossible.

The only way for the distributed components of an application to
communicate is by sending a message from one to another.

Everything else is an abstraction on top of message passing.

HTTP is an abstraction on top of message-passing. AJAX is an abstraction on top of HTTP on top of message-passing. XML-RPC is an abstraction on top of HTTP on top of message-passing. SOAP is an abstraction on top of an abstraction on top of an abstraction on top of HTTP on top of message-passing. Any RPC mechanism is an abstraction on top of message-passing. SQL queries to a remote database are an abstraction on top of message-passing. CORBA is a nasty, tangled mess on top of a foundation of message-passing.

See a pattern?

Not only are all of these abstractions, but they are leaky abstractions. Just about all RPC (Remote Procedure Call) frameworks try to pretend that remote objects or local. But the facade is impossible to keep from leaking. Calls to a remote object might fail or take arbitrarily long. If you want to make the same call to two different remote nodes, those calls must be made synchronously and sequentially; in order to call them in parallel on the remote nodes, they most be called in parallel on the local node. If a call to a remote node triggers a call back to the local node, which may trigger a call to a third node, you end up with a huge spaghetti mess of calls and threads.

I've been down that road. It wasn't pretty. There is a better way.

I think AJAX has opened our eyes a bit. It's a lot closer to message-passing than it is to RPC. In a REST architecture, you "send" messages by POSTing to a URL and you "receive" messages by GETing a URL. All messages are clearly local copies that were serialized and deserialized from the remote data. There isn't any leaky abstraction of data or classes pretending to be in two places at once. Data, timeouts, and failures are in your face and you have to deal with them. So, AJAX is a lot less leaky.

But AJAX is far from perfect. I can't help but think of the Greenspun's Tenth Rule of Programming with a twist on distributed programming: "Any sufficiently complicated distributed platform contains an ad hoc, informally-specified, bug-ridden, slow implementation of half of a message-passing system (Erlang)". Once you get message-passing in your head, you can't help but think of AJAX in that way.

I've been down a better road. It was much more pleasant.

About six months ago, I rewrote major portions of our application with message-passing concurrency. I took a long time. It was tricky. It hurt my head. But it worked. It's a success. It's capable of things that the shared-state system could never do.

Having done it, I can emphatically say that if I could start all over, I would go with message-passing. Most of the work was building the infrastructure and wrapping my head around a new way of thinking. But now that I've done both of those, I've paid the costs and I'm reaping the rewards. We're moving the application in directions that would have been nearly in possible with the old concurrency model.

In my experience, message-passing concurrency is the best way to write distributed applications. But it isn't an easy road to go down. Support for it just isn't there in most programming languages and environments. So far, Erlang has been the pioneer. I would humbly agree that the way I've implemented message-passing in Python, compared to Erlang, looks like an ad-hoc, bug-ridden half-implementation. But for various reasons, I can't use Erlang. I'm hoping for someone to create Erlang++ or E# or Eython or something that combines the concurrency model of Erlang with a modern programming language. Until then, I'll just keep on cobbling together what I can onto the programming language I happen to be using.

More on that in another article.

Wii Fit From A Programmer's Perspective (after one day)

2008-05-23T18:01:00.000-07:00

I bought Wii Fit. It came in the mail yesterday and I had my first try at it last night and my first workout this morning. Although I haven't had a lot of time with it so far, I think I've had enough that I can share some observations.

I have read a lot about Wii Fit from a video game or fitness perspective, but I've never read about if from the perspective of a software developer. I think as software developers, we should have extra interest in it for three reasons:

Most software developers are physically weak.

The Wii Fit Balance Board is a new and unique user interface device.

There might be some money to be made!

Wii Fit as an antidote to programmer physical weakness

I talked myself into buying Wii Fit because of #1. As a programmer, I sit all day with little or no physical activity. Most of my life, in fact, has involved sitting with little or no physical activity. If you're reading this, I'm guessing that you probably don't get much physical activity either. Well guess what: that makes us weak!

I know not all programmers are weak. My good friend Wes is a programmer, and he's pretty buff. But I'm weak, and I'm sure I'm not the only one. I didn't understand how weak until I played Wii Fit the first time. Just about every activity (and there are many) involved a seldom-used muscle. After a short while, I realized that I have a lot of unused muscles.

Will Wii Fit make me strong? I don't know. I suppose that depends on how much I use it. But if it pushes me to use lots of muscles that I never did, then it can only make me stronger, right? In other words, if I keep using it, my strength will increase monotonically. Eventually it will plateau, and it's limit is probably lower than going to a gym. But I'm not going to a gym, and this is sure better than nothing.

Plus, it's surprisingly enjoyable! I enjoyed my first workout this morning so much that an hour sped by before I looked at the time. Part of that is novelty, I'm sure, but there's something more to it, and I'm optimistic that I'll keep it up. I'm already looking forward to my next round tomorrow.

Wow. Did you hear what I just said? I said I'm looking forward to getting up early to have time to excersize. Either I got hit in the head with a coconut or Wii Fit is really on to something.

Wii Fit Balance Board as a user interface device.

Although I bought for the exercise, I'm interested in the potential of the Balance Board that comes with Wii Fit. It's one of the most
unique user interface devices I've ever used.

Nintendo seems to be on a role with user interface devices. It's success at turning a gyroscope into sports simulation led to the huge success of the Wii. The availability of wiimotes led to an explosion of interesting
uses and interest in hacking it. It's certainly an interface device success story.

The big question is: how useful with the Balance Board be? In Wii Fit, there seem to be two kinds of uses:

A measuring device.

A control device.

As a measure device, I think it's very useful. By "measure", I mean that the board measures how well you do a task. For example, I was doing "lunges", and it noticed that I was bending my leg too far, and told me so. That's pretty impressive. When I doing push-ups, it had a rhythm to follow and it really helped to know that someone was "watching"; I couldn't wimp out. Even just standing on it let me know that my whole life I've been standing too much on my heals. How's that for some realization!

Just like Wii Sports was the perfect application for the Wiimote, I think Wii Fit is the perfect application for the Balance Board. I can't think of an activity better suited to it's strong point: measuring.

But what else can it do? When we think of a user interface device, we usually think of controlling something, whether it be a web browser or a game character. As a developer, this is the possibility I was most excited about. After having used it, how well does the Balance Board work as a controlling device? I'm not so sure.

Wii Fit comes with a couple of "balance games" showing various ways of using the board to control something. There's leaning left and right to ski, crouching and standing to ski jump, and leaning in all
directions to roll a ball into a hole. Some of them are actually quite impressive. But I still doubt the board's effectiveness for precise control.

The problem is I find it's really hard to control my balance. I'm not kidding. Just rolling a little ball down into the hole was
really hard. My first time on the ski slope was a disaster. I read that a skateboard game is going to support the board. That might end up being so realistic that I can't control it, just like in real life!

I think a big part of it is that controlling my balancing is something I've never really done before. Imagine handing someone who has never played video games an Xbox controller and watching them play Halo. It won't be pretty. Similarly, I remember when I was a kid and the mouse was a new input device. My teacher at school couldn't handle it. She'd never had to control anything like it. Like her, I am facing a new control device, and there's a learning curve.

Long story short: The Wii Fit Balance Board is hard to use for precise control, but maybe it's just me. Hopefully, my skill with it will improve, and we as software developers will think of
interesting ways of using it.

Profit

There's definetely some money to be made writing software for the Balance Board. How so?

Millions of households already have a Balance Board

Millions more will soon.

They will show it to everyone they know.

Many will want more beyond Wii Fit.

Even though it's only one player at a time, it a hilarious game to play in a group. Some family happened to be over last night, and they couldn't get enough of it. It was a surprisingly fun watching each other try and hula hoop and dodge shoes. The first decent, cheap party game featuring compatibility with the Balance Board is going to sell like hot cakes (which...sell fast, right?).

I'm not saying who is going to make a lot of money. Nintendo might make it all. But there's probably room for little guys too.
With WiiWare, games like LostWinds have shown that a small developer can take a simple idea for a new interface, add a little bit of style, and make a great game. If someone made a game like LostWinds for the Balance Board for $10, I
wouldn't hesitate to buy it.

I'd be excited just to have some Linux drivers and an interesting open source hack to control my computer somehow, even if it's something silly like that MacBook-turned-into-lightsaber trick. Someone might even think of way to really "surf the web". I don't think there's much many in that, though :).

So far, I'm glad I bought Wii Fit. I hope to keep it up and strengthen my muscles. It's a very fun party game, which should lead to widespread adoption and an opportunity to create interesting uses for the Balance Board. It's hard to control precisely, but I hope it will get easier as we learn to control our balance (something that some of us have never done before).

Events in Python

2008-04-28T15:10:00.000-07:00

I'm a huge fan of the Actor Model . I think that for most applications, it's the best way to do concurrency. As CPUs get more cores, concurrency becomes more important for programmers, and I think the Actor Model will become more important, too.

But, sometimes you need something more light-weight for handling "events". For example, imagine you have some code listening for file changes in a particular directory. What you'd like to do is make an "event" that is "fired" whenever a file change is detected. When fired, there may be a "handler" or "listener" which is notified of the event. That "handler" is ultimately just some code which is executed when the event occurs.

A while ago, I wanted an event system like this for Python. I didn't see anything builtin or any library available, so I decided to write my own. I'd like to share what I created with you.

But first, I want to follow an example through other programming languages to give you an idea of what I was trying to accomplish and how it compares with what's out there. After that, I'll give you my implemenation in Python. Our example will be listening for changes on the file system. We want to keep the "watcher" code decoupled from the rest of the code, so we use events.

The best implementation of events that I've used is in C#, so we'll start there. In C# 1.0, our file watcher would looks something like this:


public delegate void FileChangeHandler(string source_path);

class FileWatcher
{
    public event FileChangeHandler FileChanged;

    public void WatchForChanges()
    {
       ...
       if(FileChanged != null)
       {
          FileChanged(source_path);
       }
       ...
    }
}

class FileChangeLogger
{
    public void OnFileChanged(string source_path)
    {
        Console.WriteLine(String.Format("{0} changed.", source_path));
    }
}

watcher = FileWatcher();
logger  = FileChangeLogger();
watcher.FileChanged += new FileChangeHandler(logger.OnFileChanged);
watcher.WatchForChanges();

It's pretty nice. The best part is at the end, where you can write "watcher.FileChange += ...". But, you need to type the completely useless "new FileChangeHandler", and you also need to wrap it all in a separate FileChangeLogger class. Luckily, in C# 2.0, they added Anonymous Delegates, which makes this much nicer:


watcher.FileChanged += delegate(string source_path)
{
    Console.WriteLine(String.Format("{0} changed.", source_path));
}

And in C# 3.0, they've made it even nicer!


watcher.FileChanged += (source_path => Console.WriteLine(String.Format("{0} changed.", source_path)));

C# 3.0 has an event system that's downright slick, with type-inferencing and everything. I don't think it gets much better than that.

Actually, there is one thing. If there's no handler registered with the event, calling "FileChanged()" will blow up because it sees FileChanged == null until a handler is registered. This means that you have to write "if(Event != null){Event(...):}" every single time you fire the event. Every single time. If you forget, your code will seem to work fine until there's no handler, in which case it will blow up and you'll smack your forhead because you forgot that you have to repeat that line of code every single time you fire an event. I really mean every single time. It's by far the worst wart on an otherwise elgant system. I have no idea why the designers of C# thought this was a good idea. When would you ever want to fire and event and have it blow up in your face?

Anyway, let's try a different programming language, perhaps Java. It has the worst implementation of events I've ever seen. Here's our FileWatcher example:

...

...

Ok, nevermind, I don't have the heart. I can imagine the code full of IListeners, and implementations, and keeping an array of them, and iterating over them, etc, and I just can't do it. I got seriously upset at one useless line in C#. In Java, it's at least 10 times worse. If you really have the stomach for it, go look at http://java.sun.com/docs/books/tutorial/uiswing/events/index.html. To me, it appears that in Java, events are one giant hack around the lack of first-class functions. If Java had first-class functions, none of that nonsense would be necessary.

Now that we've seen a good implementation of events in C# and avoided a bad one in Java, let's make one for Python. I'd rather it be like the C# event system, so let's see what our example would look like:


from Event import Event

class FileWatcher:
    def __init__(self):
        self.fileChanged = Event()

    def watchFiles(self):
        ...
        self.fileChanged(source_path)
        ...

def log_file_change(source_path):
    print "%r changed." % (source_path,)

watcher              = FileWatcher()
watcher.fileChanged += log_file_change

I think that looks pretty good. So what does the implementation of Event look like?



class Event(IEvent):
    def __init__(self):
        self.handlers = set()

    def handle(self, handler):
        self.handler.add(handler)
        return self

    def unhandle(self, handler):
        try:
            self.handlers.remove(handler)
        except:
            raise ValueError("Handler is not handling this event, so cannot unhandle it.")
        return self

    def fire(self, *args, **kargs):
        for handler in self.handlers:
            handler(*args, **kargs)

    def getHandlerCount(self):
        return len(self.handlers)

    __iadd__ = handle
    __isub__ = unhandle
    __call__ = fire
    __len__  = getHandlerCount

Wow. That was pretty short. Actually, this is one of the reasons I love Python. If the language doesn't have a feature, we can probably add it. We just added one of C#'s best features to Python in 26 lines of code. More importantly, we now have a nice, light-weight, easy-to-use event system for Python.

For all of you how like full examples that you can cut and paste, here is one that you can run. Enjoy!



class Event:
    def __init__(self):
        self.handlers = set()

    def handle(self, handler):
        self.handlers.add(handler)
        return self

    def unhandle(self, handler):
        try:
            self.handlers.remove(handler)
        except:
            raise ValueError("Handler is not handling this event, so cannot unhandle it.")
        return self

    def fire(self, *args, **kargs):
        for handler in self.handlers:
            handler(*args, **kargs)

    def getHandlerCount(self):
        return len(self.handlers)

    __iadd__ = handle
    __isub__ = unhandle
    __call__ = fire
    __len__  = getHandlerCount

class MockFileWatcher:
    def __init__(self):
        self.fileChanged = Event()

    def watchFiles(self):
        source_path = "foo"
        self.fileChanged(source_path)

def log_file_change(source_path):
    print "%r changed." % (source_path,)

def log_file_change2(source_path):
    print "%r changed!" % (source_path,)

watcher              = MockFileWatcher()
watcher.fileChanged += log_file_change2
watcher.fileChanged += log_file_change
watcher.fileChanged -= log_file_change2
watcher.watchFiles()

Banana Cream Pie Shake in 30 Seconds

2008-04-02T17:16:00.000-07:00

I don't intend this blog to be purely about programming matters. I intend it to be about anything I've learned and would like to share. Today I'd like to share with you an incredibly delicious and easy desert recipe that I've never seen before recently but stumbled upon. You'll love it. But if you are really only interested in programming topics, then I suggest you change your bookmark to a programming-label-only link or your feed reader to a programming-label-only feed to enjoy just my posts about programming (at least I hope you enjoy them :).

No about that recipe... If you like banana cream pie or a banana shake, this recipe is right up your alley. It's a banana cream pie shake. It tastes exactly like a banana cream pie, except that you can drink it, it's healthy for you, and it only takes 30 seconds. Here's the recipe:

2 frozen bananas (I chop them a bit to blend easier)
1 cup of liquid (I use soy milk)
blend until smooth

I'm still astounded that something that costs so little (clearly less than $1) and takes so little time (a few minutes if you are slow) is so delicious and healthy.

Finally, a little FAQ:

Q: Does it really only takes 30 seconds?

A: It only takes 30 seconds to blend, but obviously bananas take a few hours to freeze, and you may spend a minute or two cutting, pouring, and cleaning up. Not counting the freezing, the whole process is just a few minutes.

Q: What kind of blender do I need?

I have a Blendtec TotalBlender. Have you seen them blend an iPhone? That's my blender. I'll hopefully review it for you someday; it really is that good. It's some of the best $400 I've ever spent. Frozen bananas are no challenge for it.

If you have a lesser blender and it doesn't work at first, I'd recommend that you let the bananas thaw for a little while.

Q: Does it really taste that good?

Yes. It's so good I'm about to stop writing this to make some more. I drank the last one so fast it didn't even make it through this whole post.

Q: Is it really healthy?

If the ingredients are healthy, it's healthy. Bananas are healthy. Just use healthy liquid. You can even toss in extra healthy ingredients like flax seed and make it even healthier without altering the taste much. Adding chocolate might make it more tasty, but it will also make it less healthy. I prefer it without chocolate anyway.

Q: I tried it and it's too thick and creamy.

A: Add ice. It dilutes it while keeping it cold and smooth.

Enjoy!

Update: I made it again with a different batch of bananas, and it tasted different. It appears that the ripeness of the bananas makes a big difference. More ripe is more tasty. So, wait until the bananas are very ripe before freezing them.

Update 2: I sprinkled on a little cinnamon, and it tastes like a mix between a shake, banana bread, and even egg nog. It's delicious!

You Could Have Invented Monadic Parsing

2008-04-01T21:37:00.000-07:00

Even though Pysec (and functional programming in python in general) turned out to be 2-3x slower, monadic parsing is still great for certain tasks. After I wrote about Pysec the first time, I received comments regarding pyparsing, which is a great parsing library that looks very similar. Today, I'd like to show you a very simple example where monadic parsing really shines above all other parsing techniques, including pyparsing. This is a real-world need that I had, not just an academic thought-experiment.

The situation is that I'm writing a peer-to-peer file synchronizer and I need to serialize binary data in an efficient way. I've choosen to use what I call "sized binary", which is basically netstrings without the comma or bencode's byte string. The byte-string "ABC", for example, would be encoded as "3:ABC", or "Hello World!" would be "12:Hello World!". This is very efficient because "ABC" or "Hello World!" can be any bytes \x00-\xFF, without any sort of encoding or decoding like uuencode.

Stop and think for a minute how you would define a grammer to parse "3:ABC". It's so simple, right? Well, try and write a grammar for it. Try using BNF, EBNF, yacc/bison, pyparsing, SimpleParse, or any parsing libarary you know of, in any programming language. If you manage, please write me an email and let me know how you did it, because I'm not so sure it's even possible. Maybe it is in the Perl6 grammars; they're throwing the kitchen sink into that thing :). The best I've seen is that the creator of pyparsing hacked a grammar object to change how it parses the "ABC" part after a different object parsed the "3" part. This basically uses the grammar object as a global variable. It works in a single-core world, but it won't work in the many-core world we're headed for.

But now you're getting bored with me because it's silly ringing my hands over such a simple format. I bet you could parse this format in just 4 lines of code:


def parse_sized_binary(stream):
    size_bytes, stream = stream.readUntil(":")
    size               = int(size_bytes)
    bytes, stream      = stream.read(size)
    return bytes, stream

You're right, it's really simple, at least until you have to embed this little "sized binary language" inside of a bigger language. Perhaps, like me, you need to embed binary data inside of a bigger data structure, and so you need to define a serialization for things like ints, floats, lists, and hash tables. For that stuff, you can define a grammer for a language like JSON or YAML and hand it over to a grammar-based parser library. But now you need a way to tell the library, "OK, when you see my binary data, hand control over to my four lines of code, and then I'll hand control back". You might even say "You know, why don't you just let me hand you any function of the form stream -> (value, stream) and let me control the parsing for a while".

Congratulations, you just invented monadic parsing. The function you wrote, parse_sized_binary, of the form stream -> (bytes, stream), is a Parser Monad. Monadic parsing is just combining lots of these little parsers together. And so, it's incredibly easy to insert arbitrary parsing code, like parse_sized_binary, into any parser.

As a complete example, using Pysec, here's a full parser for a language just like bencode but with support for floats and unicode. Notice that our parse_size_binary is renamed to bencode_sized and is given a more functional definition.


from Pysec import Stub, until, lift, read, many_until, branch

bencode_any     = Stub()
bencode_sized   = until(":") >> lift(int) >> read
bencode_unsized = until("e")
bencode_list    = many_until(bencode_any, "e")
bencode_any.set(branch({"s" : bencode_sized,
                        "u" : bencode_sized >> lift(lambda bytes : bytes.decode("utf8")),
                        "i" : bencode_unsized >> lift(int),
                        "f" : bencode_unsized >> lift(float),
                        "l" : bencode_list,
                        "d" : bencode_list >> lift(dict)}))

I think this is sort of like Greenspun's Tenth Rule. Any implementation of netstrings/sized-binary-data probably has an ad-hoc implementation of monadic parsing in it. Even my own non-monadic version of this parser (which I use for performance reasons) has an ad-hoc implementation of monadic parsing. I'm convinced that if you write a parser for a similar format, you'll implement/invent monadic parsing as well, even if you don't know it.

Why are my monads so slow?

2008-03-19T14:10:00.000-07:00

If you've read the last few posts, you know that I choose to use monadic parsing for some application code I am writing. At an abstract level, it turned out beautifully. I was able to write the parser very elgantly and compactly despite the serialization format having some unique requirements. But at a practical level, it failed pretty miserably. It was horribly slow. With a deadline looming, I had to abandon my monadic parser and go back to using an older serialization format. But not content to give up so easily, I decided to figure out why are my monads so slow? I hope that my investigation may be of help to you if you choose to use similar techniques in your code.

First, I tried running a profiler like cProfile. While such profilers normally work quite well, they don't work so well with lots of first-class functions. And since monadic code is full of first-class functions, the profiler didn't give much valuable information.

So, I had to do optimizing the "old fashioned" way. I wrote a benchmark and ran both of my serializers against it. To start, I had two data points: one in traditional imperitave code and one in fully monadic code, and this is what I got:


imperative: 0.465 seconds
monadic:    3.893 seconds

Monadic code was 8x slower! But why? To narrow it down, I added some more data points by implementing the serializer in gradually more monadic ways. For example, I wrote a serializer in a functional/immutable style that passes around a "stream" rather than a string, and then another that passed around "state" in a very monadic way, but withoug using the monad class that I used in Pysec. Then I got this:


imperative:                0.465 seconds
functional with stream:    1.018 seconds
almost monadic with state: 2.450 seconds
monadic:                   3.893 seconds

This gave some answers. One answer it gave was that passing around an immutable "stream" object is twice as expensive as merely passing around a string. Also, passing around a state object on top of that is even more expensive. With these clues, I was able to optimize in certain ways and reduce it to this:


imperative:                0.465 seconds
functional with stream:    1.018 seconds
almost monadic with state: 1.098 seconds
monadic:                   1.283 seconds

That's a nice 3x improvement. What things were I able to do? By far the biggest cost that I was able to eliminate was object creation. I flattened two layers of abstraction into one, and thus split the number of objects created in half. The second thing I did was I created a "read until" operation that could be used more efficiently in the "grammar" of the parser. This is a form of pushing performance-critical code down the layers of abstraction. Finally, I didn't used decorators, for some often-called functions.

In the end, it looks like monadic code is about 2-3x slower in Python. Almost all of that is actually the result of just doing things in a functional/immutable way. In particular, creating data structures appears to be the main bottleneck. In functional languagues, these types of operations are very common and optimized heavily, and so are typically very fast. It looks like it's not the same in Python. Just like you have to avoid recursion because there's no tail recursion, it looks like you have to avoid a functional/immutable coding style if you care about performance because object creation is so slow. On the other hand, if you don't mind the peformance hit, it makes the code much more elegant, just like recursion usually does.

One thing of interest is that there is essentially no performance penatly for using monads over using a functional/immutable code style. The 20% penatly seen between "almost monadic" and "monadic" is only because I'm wrapping the monad in a Parser class which allows nice operator overloading.

Here's a summary of what you can do to speed up any functional/immutable-style code, including monadic code when writing in Python:

Make object creation as fast as possible. Don't do anything fancy in __init__.

Use as few layers of abstraction as possible, especially when there is an object created in each layer.

Push common or expensive operations down the layers of abstaction, especially if it avoids creating objects.

Avoid using decorators for heavily used functions.

Don't use wrapper classes if you don't have to.

As a final thought, I'd like to mention that while there's currently a substantial performance penalty for using immutable data structures, that style is going to become increasingly important as we enter the many-core era. No matter what style of concurrency you like, immutable data is always easier to work with when concurrency is involved. Concurrency and mutable data are just a bad combo. I think that it's going to be very important for language designers to address this when working on the peformance of their languages. I certainly hope future versions Python are much faster with immutable data. If they are, then the peformance penatly of using Monads will almost disappear.

Pysec: Monadic Combinatoric Parsing in Python (aka Parsec in Python)

2008-02-12T13:51:00.001-08:00

Update: It turns out that there's a similar technique being used by pyparsing. I hadn't seen it before and when I first saw it I thought had reinvted the wheel and wasted my time. But upon further inspection, Pysec does a few things a much better than pyparsing, which happen to be the exact things that I need. There's no coincedence, of course, that Pysec matches my needs well. I'll be covering this in more detail in a future article.

Update 2: I got @do syntax to work! Again, stay tuned for another article on how.

I've talked about monads in the past, but I never really covered what purpose they serve. I covered the "how" in Python and Ruby, but I doubt I'll ever full cover the "why" because it's simply too big of a subject. But today, I'd like to share with you one example of how monads are useful. In fact, it's the example that motivated me to do all of the monad stuff in the first place: parsing.

Parsing is a topic that's been around pretty much forever in computer science and most people thing it's pretty much "solved". My experience is that we've still got a long way to go. Specifically, I'm writing an application with lots of distributed concurrency, which requires lots of data serialization and deserialization (aka parsing). There are very few good serialization libraries out there, and I've been through three or four versions of various techniques. Finally, I think I have found a parsing technique that works well: monadic combinatoric parsing. And it's in Python.

What the heck does that mean? "monadic" means we're using monads. "combinatoric" means we can take monad parsers and combine them to make new monad parsers, which is extremly powerful. I call it Pysec. The design is a copy of Parsec brought to Python. Notice how I said "design"; I didn't bother looking at any of their code; The design described on their web page was good enough guidance for me. But, I'm sure that their implementation is WAY better than mine. If you want to see real monadic parsing, look at Parsec. If you're interested in monadic parsing for Python, keep reading.

Here's an example of Pysec for parsing a subset of JSON:


from Pysec import Parser, choice, quoted_chars, group_chars, option_chars, digits, between, pair, spaces, match, quoted_collection

# json_choices is a hack to get around mutual recursion 
# a json is value is one of text, number, mapping, and collection
# text is any characters between quotes
# a number is like the regular expression -?[0-9]+(\.[0-9]+)?
# "parser >> Parser.lift(func)" means "pass the parsed value into func and return a new Parser"
# quoted_collection(start, space, inner, joiner, end)
#   means "a list of inner separated by joiner surrounded by start and end"
# we have to put a lot of "spaces" in since JSON allows lot of optional whitespace

json_choices = []
json         = choice(json_choices)
text         = quoted_chars("'", "'")
number       = group_chars([option_chars(["-"]), digits, option_chars([".", digits])]) >> Parser.lift(float)
joiner       = between(spaces, match(","), spaces)
mapping_pair = pair(text, spaces & match(":") & spaces & json)
collection   = quoted_collection("[", spaces, json,         joiner, "]") >> Parser.lift(list)
mapping      = quoted_collection("{", spaces, mapping_pair, joiner, "}") >> Parser.lift(dict)
json_choices.extend([text, number, mapping, collection])

print json.parseString("{'a' : -1.0, 'b' : 2.0, 'z' : {'c' : [1.0, [2.0, [3.0]]]}}")

Like most monadic or functional code, it's pretty dense, so don't feel bad if you go cross-eyed looking at it the first time. Realize that most of the code is building a Parser monad called "json", which parses the test string at the end. I tried to comment each individual part to explain what's going on.

You may be thinking "why would I want to write code like this?". One response is to look at the code: it's the bulk of JSON parsing in 15 lines that look like a grammar definition! Another response I can give is a challange: go write a parser to parse that string and then compare your code to this code. Which is shorter? Which is easier to read? Which is more elegant? While in college, I had a team project to write a compiler for a subset of Pascal. We were smart enough to use Python, but dumb enough to use Yacc and Flex. I'm sure the parser portion was pretty fast, but it was incredibly painful to get it right. Once we did, we dared not touch it for fear of breaking it. I really wish I had Parse/Pysec back then (ok, Parsec was around back then, but I hadn't even heard of Haskell or monads).

But monadic combinatoric parsing isn't just about making your code look like a grammar definition. It makes it possible to combine parsers in incredibly flexible ways. For example, let's say that on a differnt project, you wrote a simplified CSV parser for numbers like this one:


def line(cell):
    return sep_end_by(cell, match(","))

def csv(cell):
    return sep_end_by(line(cell), match("\n"))

print csv(number).parseString("1,2,3\n4,5,6")

And now you realize you'd really like to put whole JSON values in your simplified CSV. In other words, you want to combine the CVS and JSON parsers. I think that you'll find that doing so really isn't as easy as it sounds. Imagine trying to combine two Yacc grammars. It hurts just thinking about that. Luckily, monadic combinatoric parsers make this incredibly easy:


print csv(json).parseString("{'a' : 'A'},[1, 2, 3],'zzz'\n-1.0,2.0,-3.0")

While this is a slighly contrived example, you must understand that with this technique you can combine any two parsers in a similar fasion. I don't know about you, but that really feels right to me. I haven't seen any parsing techniques as elegant as that.

Everything it's perfect of course, especially since making this work in Python is a bit of a hack. Here are some downsides to this approach:

It's hard to debug when you do something wrong.

It's annoying to import so many things from Pysec.

You have to hack around mutual recursion of values in a strict language like python.

There's probably a performance hit.

Most of these can be either fixed or worked around, though, so I think long-term monadic parsing is good bet. I'd like to see what you can do with it or to make it better.

I know how much you all like a working example, so here's some code that you can just cut, paste, and run (in Python 2.5; older versions of Python may require some tweaking). Please ignore the top half. It's mostly stuff I've covered in other articles, like Immutable Records and monad base classes. The meat starts where it says "Parser Monad".

I'd like to talk about it in more detail, but I'll save that for another article. For now, please play around with it and see what you think.


##### Base Libraries included here for convenience ###########

def Record(*props):
    class cls(RecordBase):
        pass

    cls.setProps(props)

    return cls

class RecordBase(tuple):
    PROPS = ()

    def __new__(cls, *values):
        if cls.prepare != RecordBase.prepare:
            values = cls.prepare(*values)
        return cls.fromValues(values)

    @classmethod
    def fromValues(cls, values):
        return tuple.__new__(cls, values)

    def __repr__(self):
        return self.__class__.__name__ + tuple.__repr__(self)

    ## overridable
    @classmethod
    def prepare(cls, *args):
        return args

    ## setting up getters and setters
    @classmethod
    def setProps(cls, props):
        for index, prop in enumerate(props):
            cls.setProp(index, prop)
        cls.PROPS = props

    @classmethod
    def setProp(cls, index, prop):
        getter_name = prop
        setter_name = "set" + prop[0].upper() + prop[1:]

        setattr(cls, getter_name, cls.makeGetter(index, prop))
        setattr(cls, setter_name, cls.makeSetter(index, prop))

    @classmethod
    def makeGetter(cls, index, prop):
        return property(fget = lambda self : self[index])

    @classmethod
    def makeSetter(cls, index, prop):
        def setter(self, value):
            values = (value if current_index == index
                            else current_value
                      for current_index, current_value
                      in enumerate(self))
            return self.fromValues(values)
        return setter

class ByteStream(Record("bytes", "index")):
    @classmethod
    def prepare(cls, bytes, index = 0):
        return (bytes, index)

    def get(self, count):
        start = self.index
        end   = start + count
        bytes = self.bytes[start : end]
        return bytes, (self.setIndex(end) if bytes else self)

def make_decorator(func, *dec_args):
    def decorator(undecorated):
        def decorated(*args, **kargs):
            return func(undecorated, args, kargs, *dec_args) 
        
        decorated.__name__ = undecorated.__name__
        return decorated
    
    decorator.__name__ = func.__name__
    return decorator

decorator = make_decorator

class Monad:
    ## Must be overridden
    def bind(self, func):
        raise NotImplementedError

    @classmethod
    def unit(cls, val):
        raise NotImplementedError

    @classmethod
    def lift(cls, func):
        return (lambda val : cls.unit(func(val)))

    ## useful defaults that should probably NOT be overridden
    def __rshift__(self, bindee):
        return self.bind(bindee)

    def __and__(self, monad):
        return self.shove(monad)
        
    ## could be overridden if useful or if more efficient
    def shove(self, monad):
        return self.bind(lambda _ : monad)

class StateChanger(Record("changer", "bindees"), Monad):
    @classmethod
    def prepare(cls, changer, bindees = ()):
        return (changer, bindees)

    # binding can be slow since it happens at bind time rather than at run time
    def bind(self, bindee):
        return self.setBindees(self.bindees + (bindee,))

    def __call__(self, state):
        return self.run(state)

    def run(self, state0):
        value, state = self.changer(state0) if callable(self.changer) else self.changer
        state        = state0 if state is None else state

        for bindee in self.bindees:
            value, state = bindee(value).run(state)
        return (value, state)

    @classmethod
    def unit(cls, value):
        return cls((value, None))

######## Parser Monad ###########

class ParserState(Record("stream", "position")):
    @classmethod
    def prepare(cls, stream, position = 0):
        return (stream, position)

    def read(self, count):
        collection, stream = self.stream.get(count)
        return collection, self.fromValues((stream, self.position + count))

class Parser(StateChanger):
    def parseString(self, bytes):
        return self.parseStream(ByteStream(bytes))
        
    def parseStream(self, stream):
        state = ParserState(stream)
        value, state = self.run(state)
        return value

class ParseFailed(Exception):
    def __init__(self, message, state):
        self.message = message
        self.state   = state
        Exception.__init__(self, message)

@decorator
def parser(func, func_args, func_kargs):
    def changer(state):
        return func(state, *func_args, **func_kargs)
    changer.__name__ = func.__name__
    return Parser(changer)

##### combinatoric functions #########

@parser
def tokens(state0, count, process):
    tokens, state1 = state0.read(count)

    passed, value = process(tokens)
    if passed:
        return (value, state1)
    else:
        raise ParseFailed(value, state0)
    
def read(count):
    return tokens(count, lambda values : (True, values))

@parser
def skip(state0, parser):
    value, state1 = parser(state0)
    return (None, state1)

@parser
def option(state, default_value, parser):
    try:
        return parser(state)
    except ParseFailed, failure:
        if failure.state == state:
            return (default_value, state)
        else:
            raise
        
@parser
def choice(state, parsers):
    for parser in parsers:
        try:
            return parser(state)
        except ParseFailed, failure:
            if failure.state != state:
                raise failure
    raise ParseFailed("no choices were found", state)

@parser
def match(state0, expected):
    actual, state1 = read(len(expected))(state0)
    if actual == expected:
        return actual, state1
    else:
        raise ParseFailed("expected %r" % (expected,), state0)

def between(before, inner, after):
    return before & inner >> (lambda value : after & Parser.unit(value))

def quoted(before, inner, after):
    return between(match(before), inner, match(after))

def quoted_collection(start, space, inner, joiner, end):
    return quoted(start, space & sep_end_by(inner, joiner), end)

@parser
def many(state, parser, min_count = 0):
    values = []

    try:
        while True:
            value, state = parser(state)
            values.append(value)
    except ParseFailed:
        if len(values) < min_count:
            raise

    return values, state
    
@parser
def group(state, parsers):
    values = []

    for parser in parsers:
        value, state = parser(state)
        values.append(value)

    return values, state

def pair(parser1, parser2):
    # return group((parser1, parser2))
    return parser1 >> (lambda value1 : parser2 >> (lambda value2 : Parser.unit((value1, value2))))

@parser
def skip_many(state, parser):
    try:
        while True:
            value, state = parser(state)
    except ParseFailed:
        return (None, state)

def skip_before(before, parser):
    return skip(before) & parser

@parser
def skip_after(state0, parser, after):
    value, state1 = parser(state0)
    _,     state2 = after(state1)
    return value, state2

@parser
def option_many(state0, first, repeated, min_count = 0):
    try:
        first_value, state1 = first(state0)
    except ParseFailed:
        if min_count > 0:
            raise
        else:
            return [], state0
    else:
        values, state2 = many(repeated, min_count-1)(state1)
        values.insert(0, first_value)
        return values, state2

# parser separated and ended by sep
def end_by(parser, sep_parser, min_count = 0):
    return many(skip_after(parser, sep_parser), min_count)

# parser separated by sep
def sep_by(parser, sep_parser, min_count = 0):
    return option_many(parser, skip_before(sep_parser, parser), min_count)
    
# parser separated and optionally ended by sep
def sep_end_by(parser, sep_parser, min_count = 0):
    return skip_after(sep_by(parser, sep_parser, min_count), option(None, sep_parser))

##### char-specific parsing ###########

def satisfy(name, passes):
    return tokens(1, lambda char : (True, char) if passes(char) else (False, "not " + name))

def one_of(chars):
    char_set = frozenset(chars)
    return satisfy("one of %r" % chars, lambda char : char in char_set)

def none_of(chars):
    char_set = frozenset(chars)
    return satisfy("not one of %r" % chars, lambda char : char and char not in char_set)

def maybe_match_parser(parser):
    return match(parser) if isinstance(parser, str) else parser

def maybe_match_parsers(parsers):
    return tuple(maybe_match_parser(parser) for parser in parsers)

def many_chars(parser, min_count = 0):
    return join_chars(many(parser, min_count))

def option_chars(parsers):
    return option("", group_chars(parsers))

def group_chars(parsers):
    return join_chars(group(maybe_match_parsers(parsers)))
    #return join_chars(group(parsers))

def join_chars(parser):
    return parser >> Parser.lift("".join)

def while_one_of(chars, min_count = 0):
    return many_chars(one_of(chars), min_count)

def until_one_of(chars, min_count = 0):
    return many_chars(none_of(chars), min_count)

def char_range(begin, end):
    return "".join(chr(num) for num in xrange(ord(begin), ord(end)))

def quoted_chars(start, end):
    assert len(end) == 1, "end string must be exactly 1 character"
    return quoted(start, many_chars(none_of(end)), end)

digit  = one_of(char_range("0", "9"))
digits = many_chars(digit, min_count = 1)
space  = one_of(" \v\f\t\r\n")
spaces = skip_many(space)


############# simplified JSON ########################

#from Pysec import Parser, choice, quoted_chars, group_chars, option_chars, digits, between, pair, spaces, match, quoted_collection, sep_end_by

#HACK: json_choices is used to get around mutual recursion 
#a json is value is one of text, number, mapping, and collection, which we define later 
json_choices = []
json         = choice(json_choices)

#text is any characters between quotes
text         = quoted_chars("'", "'")

#sort of like the regular expression -?[0-9]+(\.[0-9]+)?
#in case you're unfamiliar with monads, "parser >> Parser.lift(func)" means "pass the parsed value into func but give me a new Parser back"
number       = group_chars([option_chars(["-"]), digits, option_chars([".", digits])]) >> Parser.lift(float)

#quoted_collection(start, space, inner, joiner, end) means "a list of inner separated by joiner surrounded by start and end"
#also, we have to put a lot of spaces in there since JSON allows lot of optional whitespace
joiner       = between(spaces, match(","), spaces)
mapping_pair = pair(text, spaces & match(":") & spaces & json)
collection   = quoted_collection("[", spaces, json,         joiner, "]") >> Parser.lift(list)
mapping      = quoted_collection("{", spaces, mapping_pair, joiner, "}") >> Parser.lift(dict)

#HACK: finish the work around mutual recursion
json_choices.extend([text, number, mapping, collection])


############# simplified CSV ########################

def line(cell):
    return sep_end_by(cell, match(","))

def csv(cell):
    return sep_end_by(line(cell), match("\n"))

############# testing ####################

print json.parseString("{'a' : -1.0, 'b' : 2.0, 'z' : {'c' : [1.0, [2.0, [3.0]]]}}")
print csv(number).parseString("1,2,3\n4,5,6")
print csv(json).parseString("{'a' : 'A'},[1, 2, 3],'zzz'\n-1.0,2.0,-3.0")

The Easy Way to Print Flash Cards (with Python and ImageMagick)

2008-02-01T14:46:00.000-08:00

Here's a valued lessons that I learned the long and hard way: how to easily print flash cards. Don't waste any time doing it the hard way like I did. Follow my easy route and save yourself some time.

The other day, my wife had a very simple computer need: print and cut pictures into little uniform cards, like flash cards with pictures. It sounds like a simple problem, but there's a simple way and an easy way, and I'd like to share with you the easy way.

The simple way is what she did: use some software like Scribus (in her case) or Microsoft Word (if she were almost anyone else), copy the pictures in, manually align them, and print. That works great ... until you try and do 700 pictures (about 80 pages of 9 pictures per page). Scribus ate all of the computer's memory, the hard drive thrashed like mad, everything slowed down, and my poor wife spent hours putting it all together. I doubt Word would have fared much better.

But it still wasn't over. When she tried to print, the printer printed out one page with "error" on it. So, we exported to a PDF, and tried printing that: "error" again. So, we tried to print one page at a time: after about 5 minutes, it printed. All I could figure was that something bad was going on between the computer and the printer and involving sending these images uncompressed.

At this point, I decided that it was time to call it quits on manual work and use automated work: write a program to do this for me. I'm not about to manually tell 78 pages to individually print. So, with some quick bash command line work, I told it to print each page by itself. That worked for a few pages, but some were still too big and we got the dreaded "error".

Finally, I decdied to really role up my sleeves and write a program like we should have in the first place: in go pictures, out comes a PDF, and your print the PDF. Additionally, I wanted like to control the DPI of the images used to control the data flow to the printer. I did so, made the PDF, printed it and (after a while, still), it printed. Hurray! Even better, now if we wanted to change pictures or change sizes, we'll be able to do it with very little work.

So here's the program. Put some pictures in a directory, run the program, and print the pdf of "flash cards" or "image thumbnails" or "reading lessons" or whatever you want to call them. You could even make this into an Automator task in Mac OS X. It uses ImageMagick, though, so make sure you have that installed first.


from subprocess import call

MONTAGE = ["montage", "-bordercolor", "white"]
CONVERT = ["convert", "-bordercolor", "white"]

def montage_files_of_paths(paths, name,
                           columns =  3, rows    = 3,
                           width   = 10, height  = 8, xborder = .33, yborder = .33, density = 200,
                           frame   = 5,  spacing = 10,                                            
                           intermediate_ext = "png", final_ext = "pdf"):

    width, height, xborder, yborder = (int(val * density) for val in (width, height, xborder, yborder))
    thumbnail_width  = int((width  - (xborder * 2)) / columns)
    thumbnail_height = int((height - (yborder * 2)) / rows)  

    call(MONTAGE + ["-tile",     "%rx%r" % (rows, columns),
                    "-geometry", "%rx%r+%r+%r" % (thumbnail_width, thumbnail_height, spacing, spacing),
                    "-frame",    str(frame),
                    "-density",  str(density)]
                 + [path + "[0]" for path in paths] #[0] to ignore animated GIFS
                 + [name + "." + intermediate_ext])
          
    call(CONVERT + ["-border",   "%rx%r" % (xborder, yborder),
                    "-density",  str(density),
                    "-annotate", "0x0+%r+%r" % (xborder, yborder), name,
                    name + "*." + intermediate_ext,
                    name + "."  + final_ext])

import sys

if __name__ == "__main__":
    if len(sys.argv) < 2:
        print "usage: %s image_directory, image_directory, image_directory ..." % (sys.argv[0],)
    else:
        for dirname in sys.argv[1:]:
            montage_files_of_paths([dirname+"/*"], dirname)

Garlic Programmers for Silver Code?

2008-01-21T11:30:00.000-08:00

I just read Larry O'Brien's article about there being no silver programmers. He makes the case that although there may be great variance in programmer productivity, "the significant thing is not that some professional programmers are awesome, it's that some professional programmers suck". I admire Larry O'Brien greatly, and I think there is much wisdom in what he says here.

But I think he's missing something.

I have noticed a trend in my own productivity: my productivity varies greatly with the code base I'm working on. This variance may be greater than that between individual programmers. While many are rightly concerned with individual and team productivity, no ever talks about code base productivity. If we do, where does it lead us?

A few years ago, I was working for a small medical software company. One project was a new venture with a new code base. Though new, the code was already difficult to work with. Its design forced the developer to duplicate work. In my first meeting about the project, I was told we had to do lots of "fat fingering". I didn't even know what that meant. It turned out to mean typing almost the exact same thing over and over. I was horrified and ultimately wrote a code generation tool to automate the work. Though creating and maintaining it was extra work in itself, without it, doing many common tasks in this code easily took 3x longer than necessary.

After that project was "shelved", I was moved to the company's main product, which was older and had a much more "mature" code base. Actually, half was new-style (similar to what I had been working on) and half was old-style. The old-style code was even worse to work with. It was so bad that I was almost giddy whenever I could work on the new-style code. I'm sure you know what kind of code I'm talking about. Doing anything in this code easily took 3x even longer.

Combined, that's 9x slower. That seems too high. Is it even possible? How can a code base reduce productivity so much? Here are a few possibilities I thought of; I'm sure you can think of more:

Bad code leads to more code, and more code is slower to work with

Bad code is hard to understand

Bad code is dangerous to change

Bad code leads duplication of effort

Bad code leads to a slow change-compile-test cycle, leading to wasted time and loss of focus

Bad code from third party libraries can drive you crazy by crashing, malfunctioning randomly, or having little documentation

Bad code saps energy, interest, and morale

A bad code base makes any programmer less productive. Have you ever noticed that when you work from scratch with no code base to weigh you down, you can be much more productive? Imagine that as your baseline productivity. Now think of how long it takes you to accomplish something similar on a project that you're working on right now. How does it compare? I bet you're slower on the existing project.

But wait just a minute. Imagine if my list of the effects of bad code were reversed. What if, instead, it read:

Good code leads to less code, and less code is easier to work with

Good code is easy to understand

Good code is safe to change

Good code avoids duplication of effort

Good code leads to a quick change-compile-test cycle

Good code uses libraries which remove the need for "dirty work" and let you focus on the important problems

Good code is fun to work with!

A good code base makes any programmer more productive. Have you ever worked on a project that was so wonderful that you could crank out magnificent results almost effortlessly? Perhaps it has a great DSL embedded in it or has powerful infrastructure.

Even with conservative estimates, if bad code slows us down 5x and good code speeds us up just 2x faster, that's easily a 10x difference.

Maybe silver programmers don't exist. But is there "silver code"? What if there are programmers who are more adept at writing silver code? If they can make a code base that's just 2x easier to work with long-term, then that makes everyone that works on that code 2x more productive, possibly forever. If such programmers exist, then they must be extremely valuable, not so much because of their own productivity, but because of the effect they will have on the productivity of others in the future. Perhaps rather than "silver bullet" programmers that kill werewolves, these are just "garlic programmers" that ward of vampires.

Given that productivity can vary so much with quality of existing code, perhaps its worth looking for "garlic programmers" who will write code that will keep the rest us of productive long-term. I leave it as an exercise for the reader to figure out how to measure a programmer's garlic-ness :).

List Monad in Ruby and Python

2008-01-15T08:44:00.000-08:00

Recently, I wrote about ways to add something like Haskell's do syntax to programming languages like python and ruby. The python trick used bidirectional generators and the ruby trick used callcc. I have since been notified that there is one serious problem with both of them: the bindee (the function given to bind) can only be called once. For many monads, this limitation is acceptable, but for some, it means you can't use that nice syntax.

Take the List monad, for example, in ruby:


class ListMonad < Monad
  attr_accessor :array

  def initialize(array)
    @array = array
  end

  def bind(bindee)
    ListMonad.new(concat(array.map { |val| maybeUnit(bindee.call(val)).array }))
  end

  def self.unit(val)
    self.new([val])
  end

  def to_s
    joined = array.join(', ')
    "ListMonad([#{joined}])"
  end
end

## I'm hoping this if faster than using fold (inject)
def concat(arrays)
  all = []
  for array in arrays
    all += array
  end 
  all
end

class Array
  def bind(bindee)
    ListMonad.new(self).bind(bindee)
  end

  def bindb(&block)
    ListMonad.new(self).bindb(&block)
  end
end

Ruby gives us the ability to extend Array to get a pretty sweet looking use of the monad:


list1 = with_monad ListMonad do
  x =xx    [1,2,3]
  y =xx [10,20,30]
  x + y
end

It looks great, but list1 should be ListMonad([11, 21, 31, 12, 22, 32, 13, 23, 33]), be we get ListMonad([11]) instead.

Traditional binding works fine:


list2 = [1, 2, 3].bindb do |x|
  [10, 20, 30].bindb do |y|
    x + y
  end
end

list2 is ListMonad([11, 21, 31, 12, 22, 32, 13, 23, 33]). So, we know our monad is fine, but our with_monad doesn't work.

We have the same problem in python:


class ListMonad(Monad):
    def __init__(self, vals):
        self.vals = vals

    def bind(self, bindee):
        return self.__class__(concat((self.maybeUnit(bindee(val)) for val in self.vals)))

    @classmethod
    def unit(cls, val):
        return cls([val])

    def __repr__(self):
        return "ListMonad(%s)" % self.vals

    def __iter__(self):
        return iter(self.vals)

def concat(lists):
    return [val for lst in lists
                for val in lst]

@do(ListMonad)
def with_list_monad():
    x = yield    [1, 2, 3]
    y = yield [10, 20, 30]
    mreturn(x + y)

list1 = with_list_monad()

def with_list_monad_binding():
    return \
    ListMonad([  1, 2, 3])  >> (lambda x:
    ListMonad([10, 20, 30]) >> (lambda y:
    x + y))

list2 = with_list_monad_binding()

Again, it looks good, but list1 is ListMonad([11, None, None, None, None]) while list2 is ListMonad([11, 21, 31, 12, 22, 32, 13, 23, 33]). The result of list1 sure is bizarre.

Luckily, I have found a solution for ruby, and a bad hack that could be construed as a solution for python if you ignore some issues.

In Ruby, the trick is to monkey with the rbind continuation so that at the end of with_monad it returns control to the point where the continuation is called. In other words, we need to store a second continuation at the point right after the first continuation is called. Confused yet? Continuations will melt your brain, and this took a little while for met get right:


def with_monad_ext(monad_class, &block)
  finishers = []

  rbind_ext = lambda do |monad|
    begin
      checked_callcc do |outer_cont|
        monad.bindb do |val|
          callcc do |inner_cont|
            finishers.push(inner_cont)
            outer_cont.call(val)
          end
        end
      end
    rescue ContinuationUnused => unused
      raise MonadEscape.new(unused.result)
    end
  end

  val = begin
    monad_class.maybeUnit(block.call(rbind_ext))
  rescue MonadEscape => escape
    escape.monad
  end

  finisher = finishers.pop()
  if finisher
    finisher.call(val)
  else
    val
  end
end

list3 = with_monad_ext ListMonad do |rbind|
  x = rbind.call    [1,2,3]
  y = rbind.call [10,20,30]
  x + y
end

Success! list3 is correctly ListMonad([11, 21, 31, 12, 22, 32, 13, 23, 33]). The only real problem is that the normal rbind won't work. We have to make a special one and give it to the block as an argument. This wouldn't be that bad, except that Ruby has this silly limitation so we have to say rbind.call rather than just rbind, which makes it less fun to type. I named it with_monad_ext because I don't think it will be needed as often as with_monad, and with_monad is more convenient.

Now, back to python. The problem is harder. It's rooted in the fact that for a given iterator, itr.send() is not reentrant. But, if we could copy the iterator, that would give us a possible solution. I did a little googling and found that python isn't going to have copy.copy(itr) anytime soon because no one cares about them. Some people have made some progress, but it segfaults on my computer (64-bit Linux, in case you're wondering).

So, I came up with this terrible little hack which makes it possible to "copy" iterators:


class CopyableIterator:
    def __init__(self, generator, log = ()):
        self.generator = generator
        self.log       = list(log) #hmmm... if the logs were immutable, we wouldn't have to do this
        self.iterator  = None

    def getIterator(self):
        if self.iterator is None:
            self.iterator = self.generator()
            for value in self.log:
                self.iterator.send(value)
        return self.iterator
            
    def send(self, value):
        iterator = self.getIterator()
        self.log.append(value)
        return iterator.send(value)

    def next(self):
        return self.send(None)

    def copy(self):
        return self.__class__(self.generator, self.log)

That let's us define @do_ext:


@decorator_with_args
def do_ext(func, func_args, func_kargs, Monad):
    @handle_monadic_throws(Monad)
    def run_maybe_iterator():
        itr = func(*func_args, **func_kargs)

        if isinstance(itr, types.GeneratorType):
            @handle_monadic_throws(Monad)
            def send(itr, val):
                try:
                    # here's the real magic
                    monad = Monad.maybeNew(itr.send(val))
                    return monad.bind(lambda val : send(itr.copy(), val))
                except StopIteration:
                    return Monad.unit(None)
                
            return send(CopyableIterator(lambda : func(*func_args, **func_kargs)), None)
        else:
            #not really a generator
            if itr is None:
                return Monad.unit(None)
            else:
                return itr

    return run_maybe_iterator()

@do_ext(ListMonad)
def with_list_monad_ext():
    x = yield    [1, 2, 3]
    y = yield [10, 20, 30]
    mreturn(x + y)

list3 = with_list_monad_ext()

And list3 is ListMonad([11, 21, 31, 12, 22, 32, 13, 23]). Success again! There is a downside, though. First, all of the calculations are done for all of the combinations. This is especially bad if you do this:


@do_ext(ListMonad)
def with_list_monad_ext():
    print "foo"
    x = yield    [1, 2, 3]
    y = yield [10, 20, 30]
    mreturn(x + y)

Because now you'll print "foo" 9 times instead of 1.

So there you have it: you can do the List monad with do syntax in python and ruby, but you'll have to decide whether the trade-offs are worth it.

Monads in Ruby (with nice syntax!)

2008-01-09T10:34:00.000-08:00

My last article was about how you can do monads in python with nice syntax. Now I'd like to present nice monad syntax in Ruby. I'm not explaining what monads are or how you can use them. For now, I'm expecting you to be familiar with monads. If you aren't, go read a nice article on them.

Imagine you have a Monad base class like this:


class Monad
  def bind(func)
    raise "not implemented"
  end

  def self.unit(val)
    raise "not implemented"
  end

  # bind to block
  def bindb(&func)
    bind(func)
  end
end

As an aside, Please excuse there being a "bind" and a "bindb". It's silly that Ruby differentiates between a block and Proc like that. I
also think it's silly that I have to keep typing "lambda {|val| func(val)}" to turn a method into a Proc and "proc.call(val)" to call a Proc. In python, methods, functions, and lambdas are all the same thing, and it's a lot easier to code with. In this sense, python is way better. But Ruby has really slick syntax for passing in the block, and python's lambda restrictions are annoying. Why can't we have the best of both? I guess then I'd need Scala or Perl6. End aside.

Let's implement the Either monad, which I call it Failable:


class Failable < Monad
  def initialize(value, success)
    @value   = value
    @success = success
  end

  def bind(bindee)
    if @success
      bindee.call(@value)
    else
      self
    end
  end

  def self.unit(val)
    self.new(val, true)
  end

  def to_s
    if @success
      "Success(#{@value})"
    else
      "Failure(#{@value})"
    end
  end
end

def success(val)
  Failable.new(val, true)
end

def failure(val)
  Failable.new(val, false)
end

Now we can write some code that safely handles divide by zero without using exceptions (actually, exceptions essentiatlly are the Either monad, but never mind that for now):


def fdiv(a, b)
  if b == 0
    failure("cannot divide by zero")
  else
    success(a / b)
  end
end

def fdiv_with_binding(first_divisor)
  fdiv(2.0, first_divisor).bindb do |val1|
    fdiv(3.0, 1.0)        .bindb do |val2|
      fdiv(val1, val2)    .bindb do |val3|
        success(val3)
      end
    end
  end
end

puts fdiv_with_binding(1.0)
puts fdiv_with_binding(0.0)

Which prints:


Success(0.666666666666667)
Failure(cannot divide by zero)

But it's not very pretty. Luckily, ruby has callcc, which makes it very easy to define a function which I'll call "rbind" which can do this:


def fdiv_with_rbinding(first_divisor)
  with_monad Failable do
    val1 = rbind fdiv(2.0, first_divisor)
    val2 = rbind fdiv(3.0, 1.0)
    val3 = rbind fdiv(val1, val2)
    val3
  end
end

def with_monad(monad_class, & block)
  begin
    val = block.call()
    if val.class == monad_class
      val
    else
      monad_class.unit(val)
    end
  rescue MonadEscape => escape
    escape.monad
  end
end

def rbind(monad)
  begin
    checked_callcc {|cc| monad.bind(cc)}
  rescue ContinuationUnused => unused
    raise MonadEscape.new(unused.result)
  end
end

class MonadEscape < RuntimeError
  attr :monad

  def initialize(monad)
    @monad = monad
  end
end

def checked_callcc(&with_cc)
  callcc do |cont|
    val = with_cc.call(lambda {|val| cont.call(val)})
    raise ContinuationUnused.new(val) if cont
    val
  end
end

class ContinuationUnused < RuntimeError
  attr :result
  
  def initialize(result)
    @result = result
  end
end

Ruby's block syntax makes it very nice to say "with_monad Monad do", which I like. But I don't really like seeing "= rbind". I'd really like it if we could override "<<" and read that as "=<<", but I think we're stuck with unary operators ("+", "-", "~", all of which look bad here) or words. At least we can choose our name, unlike in python where we have to use "yield". Does anyone have any idea for a better name?

Maybe "xx" would work:


def fdiv_with_rbinding(first_divisor)
  with_monad Failable do
    val1 =xx fdiv(2.0, first_divisor)
    val2 =xx fdiv(3.0, 1.0)
    val3 =xx fdiv(val1, val2)
    val3
  end
end

So there you have it. You can have nice monad syntax in Ruby using callcc. Unfortunately, I've read that not all implementations of Ruby have continuatoins, which means JRuby and IronRuby may be left out in the cold. Keep in mind that Ruby's "yield" syntax is NOT a true generator, which means that we can't use the same trick that we used in python. It's callcc or nothing.

Here's the complete code in case you want to cut and paste it:

############# Monad Base ##############


class Monad
  def bind(func)
    raise "not implemented"
  end
  
  def self.unit(val)
    raise "not implemented"
  end

  # bind to block
  def bindb(&func)
    bind(func)
  end
end

def with_monad(monad_class, &block)
  begin
    val = block.call()
    if val.class == monad_class
      val
    else
      monad_class.unit(val)
    end
  rescue MonadEscape => escape
    escape.monad
  end
end

# "reverse" bind, or bind to the return value, or bind to the continuation
def rbind(monad)
  begin
    mycallcc {|cc| monad.bind(cc)}
  rescue ContinuationUnused => unused
    raise MonadEscape.new(unused.result)
  end
end


class MonadEscape < RuntimeError
  attr :monad

  def initialize(monad)
    @monad = monad
  end
end

def mycallcc(&with_cc)
  used = false
  val  = callcc do |cc|
    fake_cc = lambda do |val| 
      used = true
      cc.call(val)
    end

    with_cc.call(fake_cc)
  end

  raise ContinuationUnused.new(val) unless used
  val
end 

class ContinuationUnused < RuntimeError
  attr :result
  
  def initialize(result)
    @result = result
  end
end  

############# Failable Monad ##################

class Failable < Monad
  def initialize(value, success)
    @value   = value
    @success = success
  end
      
  def bind(bindee)
    if @success
      bindee.call(@value)
    else
      self
    end
  end

  def self.unit(val)
      self.new(val, true)
  end

  def to_s
    if @success
        "Success(#{@value})"
    else
        "Failure(#{@value})"
    end
  end
end

def success(val)
  Failable.new(val, true)
end

def failure(val)
  Failable.new(val, false)
end

######## Failable Monad Example ##########

def fdiv(a, b)
  if b == 0
    failure("cannot divide by zero")
  else
    success(a / b)
  end
end

def with_failable_binding(first_divisor)
  fdiv(2.0, first_divisor).bindb { |val1|
    fdiv(3.0, 1.0)        .bindb { |val2|
      fdiv(val1, val2)    .bindb { |val3|
        success(val3)
      }
    }
  }
end

def xx(monad)
  rbind(monad)
end

def with_failable_rbinding(first_divisor)
  with_monad Failable do
    val1 =xx fdiv(2.0, first_divisor)
    val2 =xx fdiv(3.0, 1.0)
    val3 =xx fdiv(val1, val2)
    val3
  end
end

puts with_failable_binding(1.0)
puts with_failable_binding(0.0)
puts with_failable_rbinding(1.0)
puts with_failable_rbinding(0.0)