I’ve been experimenting a bit lately on Jekyll as a new platform for this blog.
The results so far can be found on Github, and the page is here: might as well hack it (Jekyll version).
Let’s see how that goes.
Hey there, thanks for reaching my old blog! I’ll probably stop posting here, so it would be awesome if you could visit the new version. Here, I’ll even give you the link to this post in the new location: JSON parsing with Python coroutines.
A while ago, I read a blog post by Python developer Eli Bendersky on Co-routines as an alternative to state machines, in which he presents evidence to support a very interesting observation quoted below:
Co-routines are to state machines what recursion is to stacks.
which is to say, state machines can be expressed as concisely and elegantly through the use of coroutines as recursive algorithms through recursive functions (as opposed to using an explicit stack).
Now, coroutines you say?
To quote from the Wikipedia entry:
Coroutines are computer program components that generalize subroutines to allow multiple entry points for suspending and resuming execution at certain locations.
Which, in simpler terms, means a coroutine is like a function from which you may yield and resume control at arbitrary instructions — there is no longer a single entry point to the procedure expressed as a coroutine.
The emphasized statement above is probably the main argument in favor of using coroutines to implement state machines, as it makes restoring the coroutine’s execution context (that is, the state in a state machine) when new input arrives much simpler, without requiring boilerplate control structures such as if in state 1: … elif in state 2 …
While coroutines don’t seem to be a recent addition to Python (support for them has apparently been under discussion since 2005, when PEP 342, which describes the implementation, was written), looks like they haven’t achieved widespread usage, which is my way of kindly stating I had never heard of them until very recently.
I won’t really go into details with regard to the syntax for coroutines, as their use is quite well described in Eli Bendersky’s post and references, and their abuse is cleverly documented by David Beazley’s presentation Generator Tricks for Systems Programmers.
So over the last couple of days I’ve been experimenting with the ideas above in a pet project: a simple JSON parser using state machines implemented as coroutines. I must remark that this parser has little to no actual utility, as it may still be buggy and is much, much less robust and efficient than the json module in Python’s standard library. Even so, I hope it might be useful for illustration and educational purposes.
Basically I converted the railroad diagrams in the JSON website into state machines that operate on one character at a time from the input, and made a familiar loads() function on top of those to simplify parsing from a string.
Railroad diagram for JSON strings
As an appetite whetter, let’s have a look at the string parser, corresponding to the diagram above:
@coroutine
def string_fsm():
'''
A coroutine implementing a finite state machine for parsing JSON
strings.
Accepts the string one character at a time, and yields
NOT_PARSED_YET until the string has been successfully parsed.
Once the JSON string has been parsed, yields the corresponding
Python string. The coroutine can't be used after that.
May raise JSONParseError on malformed strings.
Expects data with no leading or trailing whitespace (i.e., the
first and last input characters should be ").
'''
value = []
c = (yield NOT_PARSED_YET)
if c != '"':
raise JSONParseError("JSON strings must start with a quote")
while True:
c = (yield NOT_PARSED_YET)
if c == '"':
# end of string
break
elif c == '\\':
c = (yield NOT_PARSED_YET)
if c == 'u':
# unicode 4-digit hexadecimal
hexval = ""
for i in range(4):
hexval += (yield NOT_PARSED_YET)
value.append(unichr(int(hexval, 16)))
elif c == 'b': value.append('\b')
elif c == 'f': value.append('\f')
elif c == 'n': value.append('\n')
elif c == 'r': value.append('\r')
elif c == 't': value.append('\t')
elif c in ('"', '\\', '/'): value.append(c)
else: raise JSONParseError("Invalid escape character")
else:
value.append(c)
yield ''.join(value)
As you can see, there is a straightforward correspondence between the diagram and the code, with the yield expressions bringing in the characters that govern state transitions.
Writing this parser was a very pleasant experience that helped get my head around a convoluted construct. While I must concede that the parsing state machines do look pleasingly concise, I also felt that the use of coroutines also contributed to the complexity of the code in some aspects. For one, debugging resumable functions with multiple entry points certainly takes some time to get used to.
In case anyone wants to try it, the code is in my Github page, under the name jsonfsm. The repository contains the full code for the module and a few tests, some of which were borrowed from XMMS2 (thanks!). Check it out!
Hey there, thanks for reaching my old blog! I’ll probably stop posting here, so it would be awesome if you could visit the new version. Here, I’ll even give you the link to this post in the new location: Fun with sorting networks.
A pair of interesting threads about sorting algorithms recently surfaced on Stack Overflow, bringing to discussion an exciting concept (which was entirely unknown by me): sorting networks.
The first thread poses a straightforward question: what is the fastest way to sort 6 integers? The question calls for optimized code to sort an array of integers whose size is fixed and known in advance to be 6.
Experience shows that we can often sort elements a lot faster if we have some extra information about them, such as their distribution or range of values. So intuitively, one might expect better (albeit maybe not asymptotically better) performance from a sorting algorithm tailored for fixed-size arrays when compared to a generic version, fit for any input size.
And indeed some very interesting techniques were elicited in the replies to that thread. However, one of them struck me for its simplicity and sheer speed: using a sorting network. This turned out to be faster than the generic solutions (such as insertion sort) that were posted as replies, according to the original poster’s tests.
A brief explanation on that solution: sorting networks are abstract representations of the comparisons and swaps used to sort a fixed number of integers. They are often schematized as circuits in which input wires carry the values through pairwise compare-and-swap gates.
A simple sorting network for four elements
Sorting networks leverage the fact that, given a fixed number of integers, the comparisons needed to sort them are also fixed. That is, the same circuit for n integers can sort all inputs of that size just by comparing and swapping elements in a fixed order.
I must not have been the only one puzzled by these clever constructs, since a second thread on Stack Overflow soon wondered, why are sorting networks so fast? The answer appears to be a combination of two factors: one, sorting networks tend to make less comparisons than generic sorting algorithms, and two, the comparisons made by sorting networks are more easily parallelizable at CPU level.
So, in order to gain perspective on the power of that new sorting technique, I decided to run a few practical tests of my own.
The methodology is simple. I implemented the quicksort algorithm in three forms. The first is a plain and simple version, which can be found in most textbooks. The second uses the common optimization of resorting to insertion sort for small arrays, of sizes up to eight. And the third used sorting networks for small arrays, again for sizes eight and smaller.
I then ran tests for input arrays of ascending (that is, already sorted), descending (sorted in reverse), all-zeroes and random integers, of sizes doubling from 2^16 (65536) to 2^22 (4194304), and compared the average user CPU times of five runs as measured with time.
The codes were compiled with clang 2.9, using -O1 and -O2, and ran on a 64-bit Linux system, with a Core I3 380M processor.
The code I used for testing is available in my Github page, in the sorting-networks-test repository. Anyone is welcome to review and try it. I also included all raw test results in that repository.
For a short summary of my results, I did not notice much difference between the insertion sort and the sorting networks versions. In fact, the former slightly outperformed the latter in almost all tests. On the bright side, both were consistently (and considerably) faster than the textbook algorithm.
It may be the case that the speed-up provided by sorting networks is highly compiler/CPU dependent, so I’d like to see more test results on the matter before drawing a definitive conclusion. But the fact that this new technique was a match for the old and well-known quicksort + insertion sort duo in terms of performance makes it a nice addition to my toolbox anyway.
In the last progress update, I talked about how we were moving to the client side of the Service Clients implementation.
Things have progressed quite a bit since then, but unfortunately that part of the project is nowhere near ready (nor will it be by the end of GSoC, which is right around the corner). Anyway, I thought I’d share a bit of what I’ve been working on during the past weeks of coding.
The lower level of what we have in mind for the client side is complete and somewhat solid. This means it is possible for clients to pass messages and replies around reliably, using the server as a bridge. The plan now is to use that capability to model the Service Client functionality.
As a demonstration/proof-of-concept, we decided to brush up the very first two service clients that were conceived, sumclient and sumservice, and add them to the xmms2-tutorials submodule as tut9 and tut10.
I’m currently working on a higher level layer on top of that, which is the actual modelling of remote procedure calls and introspection. As a general concept, we agreed on allowing service clients to define and expose three types of basic entities to other clients: namespaces, methods and broadcasts. This means offering a service will be a matter of defining one (or more (or nested)) namespaces containing methods and broadcasts which can be accessed by regular clients by sending a specially-formatted message to the service client.
My work on this last week of GSoC has been on the code that defines these entities, which (I think) started to take shape around this commit. That code hasn’t yet been reviewed and may soon suffer alterations.
With that out of the way, the remaining work roughly boils down to implementing the code that articulates these data structures to offer the Service Client functionality. Basically that code should be a callback to the MESSAGE broadcast (which carries client-to-client messages routed through the server) that reacts to predefined types of messages, thus being able to dispatch method calls, reply to introspection calls, record a subscription to a broadcast and so on.
Hey there, thanks for reaching my old blog! I’ll probably stop posting here, so it would be awesome if you could visit the new version. Here, I’ll even give you the link to this post in the new location: Cyclical iterators in Python.
I recently came across an amazing technique for manipulating Python iterators in a recipe by Raymond Hettinger.
The technique consists in defining an iterator as a function of itself, thus making a cyclical definition. The recipe hinges on using itertools.tee to split the to-be iterator, which is forward-referenced in a function before it is built, and feeding one (or more) of the tee’d iterators into the other.
The Ouroboros comes to mind
Bear with me, I’ll explain in a moment.
Cyclical iterators can be quite useful when defining infinite iterators for recursive sequences. The problem solved by the recipe (generating 5-smooth numbers) has this very recursive notion, in the sense that, given a set of these numbers, mutiplying each by 2, 3 and 5 yields a larger set of such numbers.
Or, to explore the inductive side of the problem, given an iterator for the first n 5-smooth numbers, you can define a larger iterator for 5-smooth numbers by exhausting the first one and multiplying each number it outputs by 2, 3 and 5 (and eliminating duplicates).
And that is exactly what the recipe does: starting with a seed value of 1 (the first 5-smooth number), it builds an iterator that swallows itself, multiplying each already-generated number by 2, 3 and 5, sorting increasingly and eliminating duplicates.
I came up with this different (simpler) example while getting my head around the technique, which I’ll explain in greater detail:
01: import operator 02: import itertools 03: 04: def factorials(): 05: def delayed_output(): 06: for i in output: 07: yield i 08: 09: result, feedback = itertools.tee(delayed_output()) 10: seeded = itertools.chain([1], feedback) 11: output = itertools.imap(operator.mul, 12: seeded, 13: itertools.count(1)) 14: 15: return result 16: 17: if __name__ == "__main__": 18: print list(itertools.islice(factorials(), 10)) 19:
This returns a factorial iterator, which outputs sequentially 1!, 2!, 3! and so on. The inductive nature of the problem presents itself more clearly this time: given an iterator for the first n factorials, we can exhaust it and multiply the last value it generated by n+1 to obtain an iterator for the first n+1 factorials.
Let’s walk by it one line at a time.
Lines 01 to 03 aren’t of much interest. They only make a few imports we’ll need and define the function factorials(), which returns the factorial iterator.
Things start to get interesting in lines 04 to 07 as we define a generator inside factorials() which simply iterates through some output variable and yields every item in it. This is a delayed reference to output: we don’t want to evaluate it right now because it points to nowhere (that is, it’s not defined), but we want to use it anyway. Hence, we wrap output in a generator, so that it only gets evaluated when the generator is being traversed.
Then on line 9 we split the iterator returned by delayed_output() in two: one result, which we will return from factorials(), and a feedback iterator, which we will feed into itself.
This is the picture we have so far:
Diagram for line 9
Note that output still points to nowhere, and if we get it to point to feedback somehow, then we will be making feedback indirectly point to itself.
Also note that I represented output twice. This emphasizes that, once we tee’d the delayed reference to it, we can have result and feedback pointing to different parts of the iteration. More on that later.
In line 10 we seed the cyclical iterator with the first value, 1!, which is just 1. We do that by defining another iterator, seeded, which will first yield the seed value, then proceed with the values it finds in feedback. Here’s the diagram:
Diagram for line 10
And finally, on line 11, we define yet another iterator, which grabs one value from seeded, our inductive factorial generator, and one value from the infinite sequence 1,2,3,4…, multiplies them and yields the result. This is where the iterator for n factorials becomes an iterator for n+1 factorials.
But wait, what is that iterator called? output! The Python bites its own tail as we close the cycle and make feedback point to itself indirectly. Check out the diagram:
Diagram for line 11
And then we return result, which remained unchanged since line 09. It helps to think that result always points to one value before seeded. That is, every time a new factorial is requested from result, seeded moves one position ahead, on to the next factorial.
One of the things I like the most about vacation is having the time and disposition to code weird/silly/funny ideas, which I would never bother with if it weren’t for the fact that I’ve been having 16 free hours every day.
It is with that spirit that, once I learned that a few friends of mine (the geekiest, of course) had created an IRC channel, I came up with the idea of coding a bot.
Not a useful bot. Not even a smart bot. Just a funny bot.
To me, creating an IRC bot sounds like one of these things every hacker must absolutely do once, so the task was somewhat charmful. And as with almost every other pet project/prototype of mine, I decided to use Python for extra coolness.
After a little research, I came across python-irclib, which provides a framework for developing IRC bots. Yay, just what I needed, specially since I had spent most of the afternoon of the previous day just to get to know the IRC protocol and hand-code a vegetative-state bot that was pretty much only capable of keeping itself alive by replying to PINGs from the server. Lesson learned for code reuse.
The first command to be implemented was !batima, which makes the bot reply with a quote from Feira da Fruta, a classic trashy humor redub of an episode of the Batman series of the 1960s.
The implementation sounded pretty straightforward: given a list of such quotes, pick one at random and send it to the channel. The problem lied exactly in finding the list of quotes, which neither I nor any of my friends wanted to maintain.
Luckily over the years that redub has flocked a cult of fans, and there’s even a Twitter account dedicated to posting almost daily quotes from the video, all-caps for extra trashiness I presume. With some help from python-twitter, the rest was quite easy.
And along came !chuck, which yields a Chuck Norris Fact taken from another twitter account. Update: The account in question seems to have been disabled. I’ll probably re-implement the command as a fortune command.
Then came the fortune-based commands, suggested by Ivan. What better repository of funny/interesting/nonsensic quotes than the one used by the fortune Unix command? By implementing the generic functionality of grabbing a fortune cookie and sending it to the channel, we soon had Calvin & Hobbes, Futurama and even BOFH quotes at our disposal.
And then there’s the cool hack used for !wikipedia, which accesses Wikipedia Over DNS using dnspython to grab article summaries from our favorite encyclopedia.
I tried to keep the general structure of the code very modular with regard to adding/removing commands. Basically, each command is implemented as a separate module, and registered to a dispatcher class which resides in the main file, ec09bot.py. The command registration code is somewhat facilitated by not having the main file import all command modules; instead, they are grouped in a single Python package. This design was somewhat inspired by the http package on newer Python versions.
All in all, between new Python modules and a few design techniques, I have learned quite a bit in doing this. It has been quite fun as well. The code of the bot is on Github under the MIT license, anyone is welcome to try it.
Now that the server side of the Service Clients implementation has taken shape, it’s time to turn our attention to the design of the client side implementation, which is still somewhat immature.
The basic idea is that, now that the server is capable of dumbly passing messages and replies among clients, we can use that capability to model the actual Service Client functionality on the client-side. In other words, we want the clients to establish a protocol for remote procedure calls and introspection with the server, unaware of what is really going on, simply forwarding messages and replies back and forth between clients.
Our plan for the actual implementation will require, as expected, changes to libxmmsclient, but also the development of a new library, so far called libxmmsclient-sc. The new functionality added to libxmmsclient will merely facilitate message exchanging between clients, while the actual Service Client sugar will be laid on top of that in libxmmsclient-sc.
We already had some sketches for the client side of the implementation, most notably this one by nesciens, which gives a pretty good idea of where we are headed. Last week I published a sketch of my own, with an updated and slightly more concrete view of the implementation details now that we know what the server is capable of. It also contained a few more ideas.
While we have not yet throughly discussed these sketches and turned them into a more solid idea, they do provide a good basis we can work on refining over the next weeks.
One aspect of these sketches we had quite a lengthy discussion about was the alterations needed to accommodate the new message passing functionality in the asynchronous result mechanism in libxmmsclient. With valuable input from vdust, we reached a nice idea that I began implementing with this commit. It still needs some testing and polishing, which I will be doing in the next days.
