SIGUSR2

The Setup

2012-05-23T00:00:00Z

Perhaps you are familiar with The Setup—this is my setup.

Who are you and what do you do?

I'm Andrew Gwozdziewycz, creator and co-organizer of the original Hack and Tell in NYC, and lead engineer at OkCupid Labs, East.

What hardware are you using?

On my first day at Labs, I was given a bunch of boxes, and tasked with building a new machine. It's much more computer than I've ever had before—3.6Ghz Core i7, 16GB of RAM, a 120GB Intel SSD and a 27" HP monitor which probably needs to go back, as it randomly brings up the OSD and cycles through options from time to time. We've been working too hard for me to take the time and get on the phone to complain about it, and it seems to stop after my yelling at it for 5 minutes or so. I've used a Happy Hacking Keyboard Lite 2 for as long as I can remember. I guess at some point I should have opted for the true Happy Hacking Keyboard, but I could never get over the price tag.

At home, my setup is much less interesting. Until a few weeks ago, I was using a 13" unibody Macbook (the last model before the 13" went "Pro"), with 8GB of RAM, running Debian Sid. Some bad luck, and a recent backup caused me to reinstall, but I haven't been able to get grub to boot a Linux kernel again after several attempts and have sort of given up for now.

Instead, I've been using my Asus EeePC 1101HA, which is basically the perfect size, but falls totally short in terms of hardware and compatibility with GNU/Linux systems. It doesn't sleep or hibernate, getting even satisfactory video performance has been a chore (due mostly to the Poulsbo chipset, though Intel has been more helpful since it released the EMGD drivers), and in general is just underpowered. I do get about 5 hours of battery life out of it, which is super nice.

I haven't touched my Nikon D70s in a long while, so most of my photos recently have been taken on my Nexus S (Sprint), which is now running Ice Cream Sandwich. My intentions have been to replace the D70s with something a little more compact (probably a micro 4/3rds), but I haven't found quite what I'm looking for yet.

For reading on the subway, I recently got a Kindle Fire, which replaced my rooted Nook Color running Cyanogen Mod. When Cyanogen becomes a bit more stable on the Fire, I'll probably switch to that.

And what software?

Most of my day is spent in GNU/Emacs running full-screen, with dwm arranging windows, an 80 character wide xterm doing terminal emulation, running GNU screen with bash sessions, all on Debian Sid. I use Iceweasel for browsing, and fire up Chromium on occasion.

For almost everything else not in a web browser, I use Emacs. I listen to music via mplayer controlled through EMMS, interact with MySQL using sql-mode, connect to Guile using Geiser-mode, connect to Clojure via SLIME, and carry on conversations on freenode in rcirc. I'd love to make the switch to reading mail in GNUS, or rmail, but I haven't made the jump yet. I used to use bitlebee, but haven't really signed on to any of the instant messaging networks in a while.

A few years ago, I got used to using GMail, which has been an extremely difficult habit to break (have you noticed that no Free Software webmail system is nearly as slick or usable?). For easy syncing between work and home, I use two different Dropbox accounts with a shared folder. Organization of Hack and Tell, wouldn't be possible without Meetup. We've been using Google Docs to share monthly spreadsheets, but I'm unconvinced it offers us anything over sharing via Dropbox. I use GitHub quite a bit, but am secretly hoping and rooting for Gitorious to take over.

On the previously mentioned Kindle Fire, I pretty much only use Readability and the built in PDF reader. I fire up Firefox now and again, but I'd rather browse the web with a proper keyboard and trackpad. I miss having a Dropbox client on the Fire—syncing papers to read on the Nook Color was such a breeze.

What would be your dream setup?

I'd love to have a very powerful 11" laptop, with at least 16GB of RAM, a 256GB SSD, and a day of battery life, which runs perfectly under entirely Free Software. Of course it should be perfectly quiet and never get hot even under load. Since I'm dreaming, I'd love to have a large monitor at home to plug it into now and then, and a gigabit pipe in my living room.

My mobile reading experience would be almost perfect if I had a decent Dropbox client, and would be perfect if the screen was color EInk.

Last, but certainly not least, I'd love to have a nice digital rangefinder, or "rangefinder like" camera that has an optical viewfinder, is weather proof, and provides completely noise free photos at ISO 6400. Oh, and it should have a line of really fast prime lenses that don't require a second mortgage to purchase (or a first mortgage for that matter).

Small, Life Problems? Just a Matter of Programming

2012-03-23T00:00:00Z

Last year, we had a daughter, and it became my mission to spend at least 15 minutes a day with her. I'd love to spend much more time with her daily, but her bedtime (and spastic sleep schedule) nearly overlaps with my work schedule + commute.

People in NYC, for whatever reason, like to go to work late and stay late. I can't help but wonder if this is related to some perception of avoiding crowded trains, but most of the jobs I've had have done similar things. And we all know that if everyone is doing something to avoid the same problem, no one is avoiding it at all.

Until the switch to DST, I was doing fairly well ensuring that I left the office right at 6 o'clock (a half hour earlier than others in the office—I come in at least a half hour earlier to make up for this) to catch the train that would get me home by 6:45. But, as the days got longer, there suddenly was no visual cue that it was time for me to go.

I use dwm as my desktop environment/window manager. If you're not familiar, it's a very simple tiling window manager for X, which, out of the box doesn't even have a clock. It's stupidly easy to get a clock on the screen of course, but for whatever reason I hadn't taken the time to configure it.^[1]

It dawned on me yesterday that if dwm supported multiple colors for the status bar, I could turn the clock a different color just before 6 o'clock—my target departure. That'd be my visual cue.

Well, it turns out that multiple colors in the status bar is a solved problem, and so setting this up was just a small matter of programming. Now, at 5:45, the background of my clock turns red indicating to me that it's time to start wrapping things up for the day.

Is it the most robust solution out there? It works, but certainly not. When I need to create some other notification, monitor some stat, or watch the weather—well, I've learned that it's just a simple matter of programming.^[2]

Actually, this isn't entirely true. While dwm didn't display a clock, my GNU screen status bar did—of course that only shows on tag 1—which I don't see when my screen is fullscreen Emacs.
"HA! You idiot. This is not how the Jargon file defines SMOP!" Right you are. I'm not using the ironic definition. I'm saying that sometimes simple problems have stupidly simple solutions that aren't elegant but do the job anyway.

Smart Moves in URL Shorteners

2012-03-13T00:00:00Z

It's no secret that virtually every popular (and non popular) site on the web has a URL shortener. What if that URL shortener ceases to exist? This has been discussed more times than I can enumerate I'm sure, but I'd really just like to pose an observation that seems like a good idea.

We've been playing around a bit with FreeBase at work. It's going to "solve" all of the data problems we have for a new product. In reality, it brings up way more, but bare with me.

Revolution OS, which should be in every hacker's Netflix queue if not consumed already, on FreeBase, has many links attached to it. Now, regardless of what you do with these links, it might make sense in the case of a film to extract the Netflix link to pull structured information from that service as well. The astute reader has already seen where I'm going with this, and will point out that the link is already expanded, but bare with me—I wanted to plug a favorite documentary (even if it is aging).

Notice the "movi.es" link. "movi.es", as it turns out, is the domain that Netflix uses for shortened URLs. The short link for Revolution OS is http://movi.es/ApRqW. Following that link, of course, will redirect you to http://movies.netflix.com/Movie/Revolution%20OS/60025132, which contains a bit of interesting information in it—the unique id of the movie on Netflix (in this case 60025132).

What's smart is that Netflix uses a predictable scheme for these mappings. Many other services do this. And, if you search DuckDuckGo (or your favorite search engine) for how to build a URL shortener, you're likely to find the similar methods illustrated. In fact, Netflix just uses Base 62, though with an unnecessary twist.

The twist is that they take the id (e.g. 60025132), prepend 1 to it (e.g. 160025132) and encode the result. It's simple and effective, but unfortunately not immediately obvious (it took about 20 minutes of trial, error and some Python to nail this down with a coworker).

It's obvious, and simple that will save immense effort in preserving the world wide web. We'll still need projects like 301works in the fight against Link rot—mostly for general purpose shorteners like bitly.

But, for specialized shorteners like "movi.es"—well, don't over engineer it. Do something simple, something predictable. Or, better yet, don't make me guess! Just tell me how to reverse them. That way I don't have to crawl your site unnecessarily.

Cleaning out the Keyboard

2012-01-15T00:00:00Z

From job to job, I travel with my own keyboard. It's a happy, little thing, but, hands down, the best keyboard I've ever owned. I own two—a PS/2 model and a USB model. The USB model gets more use these days, but I have a PS/2 to USB dongle that, when hooked up with a PS/2 mouse as well, saves me a USB port^[1].

Typing on it is a bit noisy, but it is not a buckling spring keyboard, like the trusty IBM Model M. I find it to be the perfect mix of tactile response and noise level. The noise is soothing to me—having this constant in my work environment is comforting.

It's very disruptive for a programmer to start a new job. No two code bases look the same.^[2] By "same," I mean a few things. For one, styles are different. Some people might use an IDE, which might handles TABs better. Some (smart) people just prefer spaces to TABs. Others might build modules and packages with convention X—or convention Y.

Where do utility functions go? There might be a junk drawer over here, as well as over here—depends on what it relates to, or who wrote it, or when it was written. Why is that function written so sloppily? Why does this use selection sort instead of merge sort? A new programmer coming on to a project, in a new (to them) code base, needs to learn all of the product's kludges, debt and inefficiencies.^[3]

To make matters worse though, the new developer, though perfectly capable of doing so, can't just start "fixing" things^[4], that are perceived by them to be broken, or kludgy. That'd be a horrible move. So they deal with it, and eventually learn to tolerate it, but they might mark up the code with // TODO: this should not declare 70 local variables, with names starting with `topicList.` hoping that they'll eventually get back to it and fix it—which may or may not actually happen.

I'm starting a new job soon, but this time things will be different. There isn't a lot of code to inherit. There isn't enough code for there to be major debt. There isn't a crystal clear vision as to what's actually being built. No, what there is though, is excitement. That new company smell where anything and everything is possible with a bit of elbow grease. Where ideas are flowing, and product people are frolicking in meadows, dreaming up the impossible. It's my job to execute. I'm the executor, and execute it I will.

But first, I've got to go clean out my keyboard.

Using one only USB port is handy, like say for laptops. The reason I own the PS/2 though is that I bought it in the days when USB for keyboards and mice on GNU/Linux was preposterous.
Unless of course both companies are working on the same product in sync. But how often does that happen?
Think about that. Technical debt has to be learned by someone new. The known wrong way to do something has to be learned by someone new. That's unfortunate, though necessary.
I once worked with a guy who was so appalled by the mess of code that he just started rewriting things. This was in the first month of employment mind you. He did the responsible thing and even merged it back into mainline to be released with the next round of changes. Since we launched bi-weekly or so (launching was expensive, literally, as it meant a bit of downtime while changes propagated and things came back up), there were lots and lots of changes, and with his set of "fixes" that no one else really had any idea about, things got really ugly really quickly. Luckily though, version control made it possible to removing the offending code, but it was a lot of work to get the "right" (well, wrong really) code back in place.

Code Blogging: Call With Current Continuation for Python

2011-08-09T00:00:00Z

Continuations are a snapshot of the programs control state at a given time. The concept exists in every language, but only some allow a programmer to bundle it up into an actual object to manipulate in some way.

That bundled, first-class, version of a continuation is applyable, like a function, and depending on the language is either invokable once (one-shot) or multiple times (multi-shot). In the case of multi-shot continuations, one can imagine a great number of use cases such as building coroutines, efficient backtracking and stateful web-servers.

For one-shot continuations, the number of things that can be done with them is more limited, but they are still extremely useful. These are often described as "escape-continuations" and are often compared to something like setjmp / longjmp—they can "escape" back to a save point, but can never jump forward. As such, often the example given for uses of them is exception handling.^[1] For instance, one couldn't implement nondeterminism as in Prolog because the continuation needs to be invoked multiple times to collect multiple values^[2]

Anyway, most languages do not have either type of first class continuations, and more often than not, already have the common use cases of them as part of the language.

For example, Python has exception handling built in, as well as the yield statement which supports a limited coroutine mechanism. For actual coroutines, an extension called greenlet can be used, which implements symmetric coroutines^[3].

What do coroutines have to do with continuations, aside from the fact that multi-shot continuations can be used to implement coroutines?

Well, it turns out^[4] that symmetric coroutines are all that is needed to support one-shot continuations, and with greenlet, this can be done in Python:

import greenlet

class ContinuationError(Exception): pass

def callcc(f):
    saved = [greenlet.getcurrent()]

    def cont(val):
        if saved[0] == None:
            raise ContinuationError("one shot continuation called twice")
        else:
            return saved[0].switch(val)

    def new_cr():
        v = f(cont)
        return cont(v)

    value_cr = greenlet.greenlet(new_cr)
    value = value_cr.switch()
    saved[0] = None
    return value

Its use is illustrated in the following simple example which adds 3 numbers, but only when the first one is not 5. In that case, 0 is returned from the computation:

def add3(x, y, z):
    def add_x_but_not_when_5(cont):
        if x == 5:
            cont(0)
        else:
            cont(x + y + z)
    return callcc(add_x_but_not_when_5)

Using it:

>>> add3(5, 6, 7)
0
>>> add3(6, 7, 8)
21
>>>

My haste in writing caused me to write something that wasn't correct. One-shot continuations and escape continuations are not the same thing. Thanks to the commenter below who pointed out my error.
Carl Bruggeman, Oscar Waddell, and R. Kent Dybvig; "Representing control in the presence of one-shot continuations"; In Proceedings of the SIGPLAN '96 Conference on Programming Language Design and Implementation, 99-107, May 1996.
Symmetric coroutines have a single control transfer which allows them individually to switch amongst themselves. In the Greenlet library, this is the switch method. Asymmetric coroutines, which is the other type, have two control operations, yield and resume, which makes them subordinates to their caller.
Ana Lucia de Moura and Roberto Ierusalimschy; "Revisiting Coroutines"; 2004

Parser Combinators Made Simple

2011-04-18T00:00:00Z

Parsing theory has been around for quite a long time, but it is often thought of as magic by the swarms of people who haven't bothered to read about it, and see how plain and dry it actually is. Algorithms for parsing LR(k) grammars (meaning Left-to-right, Right-most derivation, k tokens lookahead) for instance, normally just traverse a state machine that was computed before hand (either by hand, or by using a parser generator such as bison or yacc). Sure, there are many things to trip on, tedious to track down ambiguities, and other issues, but the general theory of parsing has remained unchanged for years—one might say, it is a solved problem.^[1]

When learning about parsing for the first time though, the idea of a recursive descent parser is often taught first. Recursive descent parsers, are relatively simple to reason about, to write and to shoot yourself in the foot with. A simple LL(1) parser (meaning Left-to-right, Left-most derivation, 1 token lookahead), for instance, can't parse left-recursive grammars, which is the most natural way to write certain types of grammars^[2]. Typically, when writing a recursive descent parser, the author takes the grammar and produces a function for each production (non-terminal). Each function then reads a token and recurses to the other non-terminals in the grammar reachable from the current production. And, eventually, at the end of the function the sub parts will be combined in such a way that a parse tree will be created.

This sounds boring and tedious, and in fact is. However, there is a useful technique for creating these types of parsers that was developed some time ago^[3], which involves composing a small set of functions into more meaningful, more advanced parsers. They still suffer from the same problems as your typical recursive descent parser (as presented), but with some other trickery can be made to overcome those deficiencies (we won't discuss that in this article).

In order to build a parser from the ground up, we need to think about what a parser actually is. In some sense, it is really just a function that takes an input string and produces some result. That result, in order to make any progress should contain the leftover string after consuming some part of it, or in the case of error (i.e. incorrect input), return some value indicating failure. In Python, a natural way to encode both results would be to use ("matched string", "leftover string") or None. For sanity's sake, let us refer to functions which match this criteria as parser functions.

To start off, we'll write a useful parser function, which at first glance seems pointless, anychar. anychar matches any (no trickery here!) character so long as there is at least one character left in the input string. (Note: we'll use the variable strn to always refer to the input string, which represents the string left to parse.)

def anychar(strn):
    if strn == "":
        return None
    return (strn[0], strn[1:])

It is easy to see that the result of this parser function matches our encoding. If there are no characters left in strn, then we return the failure condition, None, otherwise we return a tuple of what we parsed, and the rest of the string which we didn't parse.

It becomes more useful when we pair anychar with a test against the character it consumes. Enter chartest, which is a function that creates another parser function, given a predicate (i.e. a function which returns True or False).

def chartest(pred):
    def _(strn):
        c = anychar(strn)
        if c and pred(c[0]):
            return (c[0], c[1])
        return None
    return _

In order to use chartest, we pass it a predicate, like so:

>>> chartest(lambda x: x == 'a')('abc')
('a', 'bc')

To see what happened, remember that chartest creates a new parser function. With that, we just call the new parser function with the rest of the input string 'abc'. The result indicates success, because an 'a' was discovered as the first character. If we were unsuccessful, just like in anychar, instead of ('a', 'bc'), we'd have seen None returned.

It is a bit verbose to always create a lambda to match a single character, so matchchr gets a target character and calls chartest for us. (Remember, calling chartest creates a new parser function, this is an important thing to note.)

def matchchr(targetchr):
    return chartest(lambda x: x == targetchr)

Now we can match single characters against our input stream, which is a great starting point, but hardly makes for an easy to use library. One limitation is that there is no way to specify more than one character as a possible match, such as "all alpha numeric"—for that, we use oneof.

def oneof(target):
    chars = set([x for x in target])
    return chartest(lambda x: x in chars)

oneof creates a new test function to pass to chartest, which instead of testing if a character is equal to a single target character, checks to see if the character is in the set of characters we're looking for. Some useful definitions follow, which make parser functions using oneof, and a set of characters.

alpha = oneof('abcdefghijklmnopqrstuvwxyzABCDEFGHIJKLMNOPQRSTUVWXYZ')
loweralpha = oneof('abcdefghijklmnopqrstuvwxyz')
upperalpha = oneof('ABCDEFGHIJKLMNOPQRSTUVWXYZ')
digit = oneof('0123456789')
hexdigit = oneof('0123456789abcdefABCDEF')
whitespace = oneof(' \t\n\r')

While matching a single character is useful, it would be much more useful if we could match a token, like "while," or "Content-Type." Not to worry, matchstr produces a parser function that will combine the previously created matchchr for each character in the target string. It looks a bit complicated, so we'll go through it step by step.

def matchstr(target):
    if not target:
        return lambda strn: ("", strn)

    def _(strn):
        c = matchchr(target[0])(strn)
        if c:
            cs = matchstr(target[1:])(c[1])
            if cs:
                return (c[0] + cs[0], cs[1])
        return None
    return _

target, just like targetchr in matchchr is the string we're eventually trying to match in full. If target is empty, then our parser function is simple—it doesn't advance the input string, and doesn't consume anything.

Why don't we return None here? Well, if our target is empty, we're not asking matchstr to do any work at all, so there isn't a failure (indicated by None). It, however, also makes for a great base case to the recursion that follows.

If there is a target string to match against, we attempt to match the first character within it. If that succeeds, we shorten the target string and recurse. We eventually return a combination of the result of matchchr and the result of the recursive call to matchstr. Take a minute to look over this and ensure you understand it—it's actually pretty straightforward assuming understanding of the previous functions.

Let's take a look at how we use it:

>>> matchwhile = matchstr('while')
>>> matchwhile('while True:')
('while', ' True:')

As you can see, we used matchstr to build a parser function which matches the string "while"—simple enough.

Ok, so what if we want to parse more complicated things, like say, the rest of the input string from the "while True:" example? We need some ways to combine these parser functions to make them more useful, otherwise, all we did was create the equivalent of:

if strn.startswith("while"):
    return (strn[0:5], strn[5:])

Which, in Python, would be much more efficient!^[4]

Another parser function that we need to make this whole thing useful is optional. optional takes as an argument a parser function, and returns a new parser function that succeeds even if the original parser function does not. Essentially, if there is a failure, it returns the original input string.

def optional(parserfn):
    def _(strn):
        c = parserfn(strn)
        if c:
            return c
        return ('', strn)
    return _

If we make matchwhile, from above, optional we get this:

>>> optional_matchwhile = optional(matchwhile)
>>> optional_matchwhile('foo')
('', 'foo')

Without optional, attempting to call matchwhile on the input string 'foo' would have resulted in None, the failure condition.

The presence of optional also leads us to repeat and repeat0 which are mutually exclusive. repeat will attempt to match the parser function at least once, with no boundary. repeat0 will match the parser function zero or more times:

def repeat(parser):
    def _(strn):
        c = parser(strn)
        if c:
            cs = repeat0(parser)(c[1])
            return (c[0] + cs[0], cs[1])
        return None
    return _

def repeat0(parser):
    return optional(repeat(parser))

Again, like optional, repeat and repeat0 build parser functions from existing ones. This is very much a common pattern when building parsers of this type.

The implementation of repeat0 and repeat is quite clever. Note that zero or more is the same as optionally one or more. The implementation of both follows from that realization. repeat first attempts to call the passed in parser function. If it succeeds it calls repeat0 on the rest of the input string after calling parser the first time. If repeat0 succeeds, which it always will given optional, we combine the results and return.

>>> optrepeat_while = repeat0(matchwhile)
>>> optrepeat_while('whilewhilewhile')
('whilewhilewhile', '')
>>> optrepeat_while('foo')
('', 'foo')
>>> repeat_while = repeat(matchwhile)
>>> repeat_while('foo')
None
>>> repeat_while('while foo')
('while', ' foo')

We still need the ability to do alternation, like "while" or "if." For that we introduce alt.

def alt(*parsers):
   def _(strn):
       for p in parsers:
           result = p(strn)
           if result:
               return result
   return _

This is really simple. We take a list of parser functions and try them one by one, from left to right, until we find one that passes.

>>> iforwhileorfor = alt(matchstr('if'), matchstr('while'), matchstr('for'))
>>> iforwhileorfor('if')
('if', '')
>>> iforwhileorfor('while')
('while', '')
>>> iforwhileorfor('for')
('for', '')
>>> iforwhileorfor('foof')
None

Alternation is important, but it is maybe even more important to ensure that many parser functions pass in order, a sequence of parser functions if you will. It is this operator that allows us to do something like whilestmt = sequence(whileToken, conditional, colonToken, codeBlock).

def sequence(*parsers):
    def _(strn):
        parsed = ''
        rest = strn
        for p in parsers:
            result = p(rest)
            if result:
                rest = result[1]
                parsed += result[0]
            else:
                return None
        return (parsed, rest)
    return _

Assuming simplified definitions of the supporting rules, our whileStmt example looks something like this:

>>> whileToken = matchstr("while")
>>> conditional = oneof("><=")
>>> colonToken = matchchr(":")
>>> codeBlock = alt(matchstr("if"), matchstr("for"))
>>> whileStmt = sequence(whileToken, conditional, colonToken, codeBlock)
>>> whileStmt('while<:if')
('while<:if', '')
>>> whileStmt('while>:if')
('while>:if', '')
>>> whileStmt('while>:for')
('while>:for', '')
>>> whileStmt('while:for')
None

sequence looks complicated, but is rather simple. It is basically reduce, combining the results of each parser into the results of all of the parser function outputs together.

That's all we really need to construct more interesting parsers, so we'll now construct a simplified parser for JSON.^[5]

We'll start with some utility functions:

def betweenchrs(parser, left="(", right=")"):
    def _(strn):
        lres = matchchr(left)(strn)
        if lres:
            pres = parser(lres[1])
            if pres:
                rres = matchchr(right)(pres[1])
                if rres:
                    return (left + pres[0] + right, rres[1])
        return None
    return _

betweenparens = lambda p: betweenchrs(p, left="(", right=")")
betweenbrackets = lambda p: betweenchrs(p, left="[", right="]")
betweencurlies = lambda p: betweenchrs(p, left="{", right="}")

betweenchrs lets us easily create a parser function which attempts to parse, using parser, only if it is between left and right. This is useful in JSON, because of its list and dictionary data types, which are delimited by [] and {} respectively.

Strings in JSON are composed of a series of characters between "'s. But, if you want to actually use a " within the string, you can do that by preceding it with a \. We can make a parser function that satisfies these rules rather easily, making use of anychar.

def charorquoted(strn):
    c = anychar(strn)
    if c[0] == '"':
        return None
    elif c[0] == '\\':
        c2 = chartest(lambda x: x in ('\\', '"'))(c[1])
        if c2:
            return (c[0] + c2[0], c2[1])
    else:
        return c

In the case that we find a '"' character without a '\' character preceding it, it is a failure.

Whitespace doesn't much matter between tokens in JSON, so let us define something that ultimately ignores it. ignorews uses repeat0 to strip the preceding whitespace, calls the parser function given using the left over input string. If the parser function passes, it calls repeat0 again against whitespace and ultimately returns the passed in parser function's parsed result and the ignored whitespace's left over input string. That's a mouthful, but it's fairly easy to understand:

def ignorews(p):
    def _(strn):
        w = repeat0(whitespace)(strn)
        if w:
            pres = p(w[1])
            if pres:
                w2 = repeat0(whitespace)(pres[1])
                if w2:
                    return (pres[0], w2[1])
        return None
    return _

anint, astring, acolon and acomma are just helper functions which do exactly what they describe. We're simplifying this implementation, as it is for demonstration purposes, so we're not taking into consideration floating point numbers, or integers specified using hexidecimal and other formulations of numbers.

anint = sequence(optional(matchchr("-")), repeat(digit))
astring = betweenchrs(repeat0(charorquoted), left='"', right='"')
acolon = matchchr(':')
acomma = matchchr(',')

When we define dictionaries and lists, we run into a problem. Both lists and dictionaries can contain lists and dictionaries (as well as numbers and strings of course), which represents a problem for when we define these functions (we can't recursively define something that doesn't already exist!). One solution to this problem is to use a mutable object which acts as a "forward reference." When we finish defining the pieces we need, we update the forward reference, and then all is well.

For both aesthetic, and practical reasons, we'll use a class instance which overrides __call__, and __ilshift__, which will allow us to use an instance of Forward as a parser function, and <<= (from __ilshift__) as a way to update the parser function that's contained within the reference.

class Forward(object):
    def __init__(self):
        self.p = None

    def __call__(self, *args, **kwargs):
        return self.p(*args, **kwargs)

    def __ilshift__(self, p):
        self.p = p
        return self

To use a Forward, we simply create an instance of Forward and assign it to a variable, just as if we were creating a parser function. Forward is like a promise. "If you act like a parser function for me for a little bit, I promise I'll actually turn you into one later." If the promise is kept, and the Forward is updated, parsing will proceed as if nothing was ever not specified to begin with.

avalue = Forward()
akey = ignorews(alt(anint, astring))
akeyvaluepair = sequence(akey, acolon, avalue)

Both lists and dictionaries have items that are separated by comma. commaseparated is essentially repeat0 except that it ensures a comma appears after each item, except in the last item.

def commaseparated(parser):
    def _(strn):
        r = repeat0(sequence(parser, acomma))(strn)
        if r:
            r2 = parser(r[1])
            if r2:
                return (r[0] + r2[0], r2[1])
        elif r:
            return r
        return None
    return _

Now that we have all the pieces specified, we put a commaseparated key value pair between curly braces to parse a dictionary, and a commaseparated value parser function between square brackets to parse a list.

adict = betweencurlies(commaseparated(akeyvaluepair))
alist = betweenbrackets(commaseparated(avalue))

We still have our promise to keep for avalue, and with the definitions of alist and adict, we now can. avalue, as in JSON, should either be a number, a string, a list or a dictionary, and whitespace is ignored.

avalue <<= alt(*map(ignorews, [adict, alist, anint, astring]))

To achieve alternation, we make use of alt, but before we do that, we wrap each parser function contained in avalue in an ignorews parser function builder to satisify that requirement. Finally, we shift the newly created parser function into the forward reference for avalue.

To parse a top level JSON document, we look for either a list, or a dictionary. The parser function to do that is quite easy to specify.

json = alt(adict, alist)

Last, but certainly not least, let's actually use what we've constructed:

>>> json('''{"hello": {1: "how are you?"}, "i is": "fine", "how": "are you?", 1: ["these", "values", "work", 2]}''')
('{"hello":{1:"how are you?"},"i is":"fine","how":"are you?",1:["these","values","work",2]}', '')

Success!

While we haven't shown how to formulate an LL(k) grammar, or even talked about what that actually is formally, we have shown that with a few simple functions that build parser functions, we can build, quite easily, parsing functions which parse complicated things. However, we've only shown that the input is valid, actually constructing a parse tree, or acting upon it, is left as an exercise to the reader.

Source code for all this is here

I'm not sure if parsing is really "solved," but the algorithms we have work well enough in practice that there isn't a ton of interesting new research going on around it. Yacc is Dead, for instance used the results of a paper from 1964, but came under fire. Can parsing be made trivially easy? Maybe, but it's likely that ambiguity will be somewhere—which would be the unsolved in parsing.↵
See left recursion. All joking aside, left recursion occurs in a grammar when a non-terminal rule is used recursively and appears on the left. For example: expr = expr + tail. ↵
Graham Hutton. Proceedings of the 1989 Glasgow Workshop on Functional Programming (Fraserburgh, Scotland), Springer-Verlag Series of Workshops in Computing, Springer-Verlag, Berlin, 1990.↵
The purpose of this article isn't to describe an efficient parsing technique for Python, but to rather demonstrate a useful technique that could be adapted and built upon, to build an efficient parsing framework for any language that supports first class functions. There's a follow up article to this which shows just how much of this can actually be abstracted out in order to make it even more simple.↵
We limit our parser to strings, integers, dictionary and lists. The complete specification appears at http://json.org ↵

Softserv Serves Requests

2011-01-07T00:00:00Z

Anyone that knows me knows that I have a lot of projects, most of which are in some sort of unfinished but partially functional state. Then there are others that have a solid 0.1 release, maybe lacking documentation, but usable. There are yet others that never make it to 0.1, and despite my happy thoughts about how this piece of code will change the world, or be the future, it's as good as deadpooled.

One project that will certainly not be deadpooled is being developed in my 10% time at work, though on hiatus whilst I resolve some other issues that I inadvertently committed and finish up some other tasks that have higher priority.

But, I don't wanna discuss that project right now, it is in a sort of discovery phase where I'm attempting to iron out the network protocol, and what functionality it actually provides for its initial run^[1].

It does, however, do what many servers do—listen to and accept requests via a socket.

Clojure comes with many ways, of course, to do just that. It is certainly possible to use one of the many frameworks for Java for writing servers, but clojure.contrib/server-socket, looked to be exactly what I needed, and I decided to have a look.

When evaluating any sort of library, the first thing I always do is create something simple that makes use of it. This is not uncommon of course, and the "Hello World" of network programming is the trusted echo server, in which, everything you say will be parroted back to you. That's pretty simple using server-socket:

(ns echo
  (:require [clojure.contrib.server-socket :as ss]
            [clojure.contrib.duck-streams :as ds]))

(defn echo-server [in out]
  (binding [*in* (ds/reader in)] ^[2]
     (ds/with-out-writer out
        (println (read-line)))))

(ss/create-server 1025 echo-server)

(comment
$ echo "HELLO WORLD" | nc 127.0.0.1 1025
HELLO WORLD
$ 
)

Simple enough, but it is unfortunately too simple. For one, it creates a thread per connection, which is just asking for trouble with a public server. Secondly, since it only gives you an InputStream (in) and an OutputStream (out), there isn't a way to log who connected, or anything about the user who connected other than time. Hell, there's nothing guaranteeing that you're even connecting via a network for this!

Now, I understand that server-socket was not really meant for production use—it is meant for quick toying around, and testing out ideas as quickly as possible, something it does extremely well, but with a little bit of modification, I think it can be almost just as simple and still be suitable for production use.

Enter softserv, a still simple, but slightly more complicated replacement for server-socket.

So what is more complicated about it? Let's look at "Hello World" and find out:

(ns echo
  (:use [softserv.core :only (create-server
                              defservice
                              defhandler
                              with-shutdown)])
  (:require [clojure.contrib.duck-streams :as ds]))

(defn echo-parser [s]
  (binding [*in* (ds/reader s)]
    {:data (read-line) :type :echo}))

(defservice echo-server :type echo-parser)

(defhandler echo-server :echo
  [s req]
  (with-shutdown s
    (ds/with-out-writer s
      (println (:data req)))))

(create-server 1025 echo-server 10)

(comment
$ echo "HELLO WORLD" | nc 127.0.0.1 1025
HELLO WORLD
)

Phew! That was a mess of code to write to get a simple echo server, surely softserv isn't so, well, soft? Just look at what we've gained, though!

First and foremost, we've gained the ability to specify a maximum number of threads to create. That's what the 10 is for in create-server. Softserv executes request handlers in a thread pool. This of course has some limitations over the thread-per-connection model (like making it harder to allow for long running session based servers), but for resource constrained single request services, it's probably a plus. Maybe relaxing this requirement and figuring out an appropriate way to handle long running connections is a good next step.

Secondly, and without any hit in the number of symbols or parentheses, we're passing an actual socket object to the function that does the handling. You'd think that we'd have to call (.getInputStream s), but duck-streams knows how to get an InputStream for a Socket. This is almost identical to the original example.

Third, and most importantly, we've made it possible to dispatch based on the type of request. Softserv enforces what you'd have done anyway. The handler function that server-socket/create-server takes in almost all cases will end up being a cond statement dispatching to other functions. Softserv just makes that explicit and up front.

Enough chatter, how can I make use of it? Well, our echo server would be much more interesting if in fact we echoed back more interesting things. For instance, we could translate the input, or rot-13 the input, or for ease of illustrative purposes echo back the actual date, a more useful echo, when someone sends the string "DATE".

(ns echo
   (:use [softserv.core :only (create-server
                               defservice
                               defhandler
                               with-shutdown)])
-  (:require [clojure.contrib.duck-streams :as ds]))
+  (:require [clojure.contrib.duck-streams :as ds])
+  (:import [java.util Date]))

(defn echo-parser [s]
  (binding [*in* (ds/reader s)]
-    {:data (read-line) :type :echo}))
+    (let [l (read-line)]
+      (assoc {:data l} :type (if (= l "DATE") :date :echo)))))

(defservice echo-server :type echo-parser)

+(defhandler echo-server :date
+  [s req]
+  (with-shutdown s
+    (ds/with-out-writer s
+      (println (str (Date.))))))

(create-server 1025 echo-server 10)

(comment
$ echo "HELLO WORLD" | nc 127.0.0.1 1025
HELLO WORLD
$ echo "DATE" | nc 127.0.0.1 1025
Wed Jan 05 08:29:38 EST 2011
)

Using a single request parsing function of course has its limitations, but in general, network services are not the type of thing that really have diverse request types. The protocol normally allows you to tell within a few bytes what kind of request it is. In the case of softserv servers the handlers can then finish reading the request and taking the appropriate actions.

I'd really appreciate any feedback on this.

There's also the question of non-blocking vs. blocking, but the first pass will be blocking until there are real numbers to look at.
I'm not sure of the reasoning, but (with-in-reader s ...) throws an exception saying java.io.PushbackReader cannot be cast to java.io.BufferedReader. This doesn't seem right to me, since it'd work if it were a LineNumberingPushbackReader, but PushbackReader's don't have a .readLine method, and don't derive from BufferedReader. Nevertheless, I feel as though read-line should know how to handle it, or wrap the PushbackReader in a LineNumberingPushbackReader temporarily, if that's possible.

unipoint-mode: A minor-mode for Mathematical Unicode

2010-11-04T00:00:00Z

Last week I reblogged Poul-Henning Kamp's article "Sir, Please Step away from the ASR-33".

If you haven't read it, do so. It has an interesting outlook on what it means to write code, and asks the question, "why the hell are we stuck in the 60s?" His basic premise is that we're married to ASCII, despite having all sorts of other characters at our disposal via unicode, which provides much clearer and concise possibilities for syntax. He also goes on about how none of us have monochromatic screens, so color could play some role in what our programs mean, as well as arguing that the vertical nature of code is unjustified, since we have column editing.

If you ask me, his other arguments are crap, but the unicode argument is completely valid. There's just one problem, have you ever tried to type unicode? It's a mess. In Emacs, to type →, it's C-x 8 RET RIGHTWARDS ARROW RET, or if you know the hex value, C-x 8 RET 2192 RET. Sure, there are other options, but most editors aren't nearly as flexible to customize as Emacs is, so who knows what it's like outside of it—I can't imagine it's any better.

But, when I commented on the fact that "typing unicode sucks," I was greeted by an email from a friend of mine:

DrRacket lets you enter common Unicode characters by typing their LaTeX name followed by control-\. For example, you type ∈ by typing "\", "i", "n", "control-\". It's easy enough that I use Unicode in my code all the time. I bet it wouldn't be too hard to hack something like this feature into Emacs. —Casey Klein

This got me thinking about the problem, and in 20 minutes I had C-\ bound to a function that would read a TeX symbol name from the minibuffer and looked up the unicode character in a table then spit it out. I then began to go on a typing spree, seeing how easy it actually was to use. Of course, this wasn't exactly what Casey had described, but it was close enough, and made it way better than before.

It actually had some great features of it's own, too. For one, it had TAB completion, to cut down on typing. DrRacket didn't have that.

I told Casey about my efforts and mentioned TAB completion and how "this isn't all that bad." Casey was intrigued by the TAB completion, and I wanted to see if C-\ after typing \in was better—it is, but there's still value some value in the prefixed entry.

So now I had a function bound that would do the right thing. If point was at the end of a word boundary with a \ to the left of it (the word), it'd attempt to convert the sequence to a symbol, otherwise it'd be left alone. If you were in empty space or the completion failed, you'd be asked for the symbol as if you were going the prefix route.

This all worked wonderfully well, and our conversation about why I don't like entering unicode went on; he was still convinced it was woefully easy. I, too, was beginning to see that it's not as painful with the proper tools as I originally thought.

The 43 message thread of back and forth sparked inspiration in him around the idea of completion for DrRacket. His idea was simple, hit C-\ and it'd attempt to complete whatever was before it, or output the longest subsequence of the symbols, prefixed with whatever you typed, in the lookup table. In other words, if you had "\sub" it'd complete to "\subset" because both "\subset" and "\subseteq" are in the lookup table. Hit C-\ again and the substitution to ∈ takes place.

I couldn't help but be inspired to add that behavior to what I had now dubbed unipoint. His changes went into DrRacket. We both found solace in the fact that typing symbols was a bit easier than it was before.

I'm a lot less scared now to see symbols in code, and certainly advocating for them, so long as they stay mathematical in nature. I can't help but feel, though, that most people see this still as a problem. It's because of this that I recorded a quick screencast tutorial (no audio) of how unipoint is used. Hopefully it does its job in showing that it doesn't have to be so painful, and Kamp's dream will eventually become a reality.

ant.el: A Code Walkthrough

2010-10-29T00:00:00Z

In April of last year, I blogged about how powerful Emacs is, and shared my enlightenment story.

Today, I'm even closer to Emacs than I was before, having an extra year and a half of experience than I did then. My daily interactions with Emacs are still very much in the same vain—I am still a programmer after all, but I've also discovered some more frustrations which were fairly easy to rectify.

In July of this year, I started a new job^[1]. My role at Meetup has been different in many regards than my previous jobs. It's the first role I've had since entering into the industry that someone doesn't see the output of my code. In fact, if they do see the output of my code, I've sort of failed.^[2] It also represents the first time that I've primarily used a compiled language (outside of college), targetted the JVM and used Java for the bulk of my work.

Naturally, Emacs could help me. Compilation Mode, for instance allows you to do M-x compile to run make, or ant (with -emacs) or some other build tool that generates compilation mode compatible output, that the mode will then mark up and allow you to easily jump to places the compiler thinks^[3] are errors.

Compilation Mode by default is fine, but complicated Java source trees are normally nested quite complexly and ant isn't the greatest at locating a suitable build file. What I needed were some interactive functions that I could use to run ant properly, in Compilation Mode using the project's build file. What I came up with after a few hours, works fairly well.

Basically, instead of M-x compile, I type M-x ant, or M-x ant-compile, or M-x ant and then TAB complete all the available build targets. This allows me to save some typing, and save some precious brain cells, since I don't have to remember all 40 build targets.

The code is fairly simple, and I think it's a great candidate for a walk through on how to solve your own problems using Emacs Lisp, so I'd like to go through it here.

The code starts out simply enough:

(defvar ant-last-task "compile")
(defvar ant-build-file-name "build.xml")
(defvar ant-command "ant -emacs")
(defvar *ant-tasks-cache* '())
(defvar *ant-tasks-command* "grep -e '<target.*name=\"[^\-][^\"]*.*$'")
(defvar ant-tasks-default '("compile" "test" "clean"))

We just define a bunch of global variables that can be overridden by a user if they need to be. We do however create *ant-tasks-cache* and *ant-tasks-command* which are meant to be internal state. In elisp, and other Lisps, wrapping * around a variable normally indicates that the variable is special in someway, here it means it's a global and shouldn't be modified outside of the functions defined within.

Next we have a helper function, ant-find-tasks, which, given a directory, issues a shell command *ant-tasks-command* that is used to extract the lines from the ant build file that declare targets:

(defun ant-find-tasks (directory)
  (let ((output (shell-command-to-string (concat *ant-tasks-command* " "
                                                 directory "/"
                                                 ant-build-file-name))))
    (if (> (length output) 0)
        (mapcar '(lambda (x) (replace-regexp-in-string ".*<target.*name=\"\\([^\-][^\"]*\\).*" "\\1" x)) 
                (split-string output "[\n]"))
      nil)))

Essentially, we first save the output of the shell command that gets built up to the variable output. If the length of output is greater than 0, we split the output (split-string) into individual lines, and iteratively replace the junk in the line with just the name of the target (replace-regexp-in-string). The only non-obvious thing in here is mapcar which is a fancy way of transforming a list into another list via the function passed as the first argument.

That gives us all the tasks defined in the build file—well for most cases anyway. It doesn't handle all possible, valid build.xml files, but should work if the target's declaration and name attribute appear on the same line.

When we need a list of tasks for a project, we call ant-tasks. This function really just caches the returned value of ant-find-tasks into the global variable *ant-tasks-cache* for the current project:

(defun ant-tasks (directory)
  (let ((tasks (assoc-string directory *ant-tasks-cache*)))
    (or tasks
        (progn 
          (let ((newtasks (or (ant-find-tasks directory) ant-tasks-default)))
            (setq *ant-tasks-cache*
                  (cons (cons directory newtasks) *ant-tasks-cache*))
          newtasks)))))

The only interesting thing about the above code is the use of or. In Lisp, or short circuits and returns the first truthy value—it doesn't convert it to a boolean, so it can easily be used to select the first truthy value from a list of values. That's what's happening there.

I mentioned that I wanted TAB completion on task names so as to not clutter my brain matter with useless task names:

(defun ant-get-task (directory)
  (let ((task (completing-read-multiple (concat "Task (default): ") 
                                        (ant-tasks directory))))
    (if (> (length task) 0)
        (mapconcat 'identity task " ")
      "")))

Well, here it is. Emacs has built in completion via the completing-read function. Here, we want the ability to issue one or more tasks, so we use completing-read-multiple to get the job done. Notice we're calling our function from above, ant-tasks.

You'll notice mapconcat above. It's like mapcar from above, in that it takes a list of things and transforms them, but instead of returning a new list, it concatenates the elements into a string using the last argument (here just a space) as a separator. completing-read-multiple returns to us a list, which we need to turn into a string with spaces between the targets in order to issue the build command.

(defun ant-find-root (indicator)
  (let ((cwd default-directory))
    (while (and (not (file-exists-p (concat cwd indicator)))
                (not (string-equal (expand-file-name cwd) "/")))
      (setq cwd (concat cwd "../")))
    (if (file-exists-p (concat cwd indicator))
        (expand-file-name cwd)
      nil)))

The above function locates the base directory of the project, given the current file being edited. It just loops up the file system looking for the first directory it finds that has a build file in it. When I originally wrote this function, I didn't realize that Emacs already had this functionality built into it with the function locate-dominating-file.^[4]

ant-kill-cache,

(defun ant-kill-cache ()
  (interactive)
  (setq *ant-tasks-cache* '()))

does exactly what it says it does. It destroys the cache that is built up from ant-tasks.

The main entry point, ant, is fairly trivial as well. It sets the variable default-directory, which is Emacs' current working directory, to the project directory, reads a task from the reader (if being called interactively) and calls compile, which is the main entry point into Compilation Mode.

(defun ant (&optional task)
  "Run ant `task` in project root directory."
  (interactive)
  (let ((default-directory (ant-find-root ant-build-file-name)))
    (if default-directory
        (let ((task (or task (ant-get-task default-directory))))
          (setq ant-last-task task)
          (compile (concat ant-command " " task)))
      (message "Couldn't find an ant project."))))

In the first code block, there was a variable, ant-last-task, defined that is used above to store the last target run. After a target is given, it's saved off in there.

(defun ant-last ()
  "Run the last ant task in project"
  (interactive)
  (ant (or ant-last-task "")))

(defun ant-compile ()
  (interactive)
  (ant "compile"))

(defun ant-clean ()
  (interactive)
  (ant "clean"))

(defun ant-test ()
  (interactive)
  (ant "test"))

The rest of the code above, just defines some convenient, interactive commands for common targets. M-x ant-compile will just issue the compile target, likewise for ant-clean. The only moderately interesting interactive command here is ant-last which reuses the variable ant-last-task from above to redo the last compilation.

It doesn't feel like much code, and in all reality it's not. However, it has saved me quite a bit of time, as I don't have to go running to a terminal (either switching buffers, or switching windows entirely) in order to issue an ant task. I just do something I've grown very accustomed to—I issue another Emacs command, and let Emacs take care of it for me.

We're hiring for most positions.
Most of what I do is related to our product's infrastructure—not interaction, and not engineering new features. My work would be visible if some error leaked to your browser, and that'd probably be bad.
It's fairly difficult to trick the compiler, but in Java, for instance, you can write type-safe code using Generics that it can't prove is safe. If you do that though, you should make use the SuppressWarnings annotation to tell the compiler it's OK.
Actually, I wasn't surprised that Emacs actually had the functionality, just that the name is non-trivial. I gave up looking for it after a couple of minutes and just rolled my own. I'll replace it in a future version, but the existing code works for now.

Clojure Conj Reading List

2010-10-24T00:00:00Z

This past weekend, the first (hopefully annual) Clojure Conj took place in Durham, NC.

In my opinion, the conference was a great success, and was greatly inspirational, as well as enjoyable in many regards. I left the conference recharged with energy to better learn about and help improve the Clojure ecosystem, and just get more involved. But, that's not all I left with of course. I left with great information and even more pointers to new thoughts, opinions and ideas.

I've compiled a small reading list of things that were mentioned in talks. I also got a chance to (briefly) meet Michael Fogus, whose talk discussed the influences of Clojure and asked him if it would be possible for him to make a reading list. I certainly hope he does. Anyway, here's my list:

MonetDB, a novel spatial column-store DBMS—Maarten Vermeij, Wilko Quak, Martin Kersten, Niels Nes: Abstract: Column-store database engines are a promising track in database research to handle data warehouses. In this paper we describe our experiences in extending the open-source database management system MonetDB with geo-spatial functionality. The approach taken is to leverage the existing geo-spatial software library GEOS through the extensibility features of this DBMS. The result is a high-performance solution using a software stack that enables future research and development improvements in many directions. In our paper we first give an overview of the MonetDB architecture then we describe how this architecture is beneficial for the handling of spatial data.
The Zipper—Gerard Huet: Capsule Review: Almost every programmer has faced the problem of representing a tree together with a subtree that is the focus of attention, where that focus may move left, right, up or down the tree. The Zipper is Huet's nifty name for a nifty data structure which fulfills this need. I wish I had known of it when I faced this task, because the solution I came up with was not quite so efficient or elegant as the Zipper.
Finding Flow: The Psychology of Engagement with Everyday Life—Mihaly Csikszentmihalyi
Computer Power and Human Reason—Joseph Weizenbaum
Finger Trees: A Simple General-purpose Data Structure—Ralf Hinze, Ross Paterson: Abstract:We present 2-3 finger trees, a functional representation of persistent sequences supporting access to the ends in amortized constant time, and concatenation and splitting in time logarithmic in the size of the smaller piece. Representations achieving these bounds have appeared previously, but 2-3 finger trees are much simpler, as are the operations on them. Further, by defining the split operation in a general form, we obtain a general purpose data structure that can serve as a sequence, priority queue, search tree, priority search queue and more.
How to Solve It: A New Aspect of Mathematical Method—G. Polya
Updates and other suggestions
Infinity: Beyond the Beyond the Beyond—Lillian R. Lieber
The Education of T.C. Mits: What modern mathematics means to you—Lillian R. Lieber
The Einstein Theory of Relativity: A Trip to the Fourth Dimension—Lillian R. Lieber