Google Wave and Clojure

Google Wave is an attempt to reinvent communication and collaboration on the web. Or, it's just a web site where you can share information, with a documented protocol and an API for extensions. Google wave consists of three pieces:

1. The User Interface (Google Wave Client application)
   
2. The Programming Interface (Google Wave APIs)
   
3. The Communication Protocol (Google Wave Federation Protocol)
   

A wave is a conversation which may include both human and computer participants. The wave stores state and maintains historical information. Participants can modify the wave in real-time. A wave contains one of more wavelets.

A wavelet is a threaded conversation spawned from a wave. A wavelet contains one or more messages, also known as blips. A wavelet spawned from a wave is an independent entity with it's own access control. This means, for example, you could spawn off a side conversation bemoaning your PHB and safely (hopefully) keep that wavelet under wraps.

A blip is the basic unit of conversation and consists of a single message (or interaction event) that appears on a wavelet. Blips can be stored as a draft before being published. Each wavelet always consists of at least one root blip. Finally, a document represents the actual content of a blip. This is in XML format which can be retrieved, modified or added to by the API. Documents are typically managed through an API rather than direct XML manipulation.

You can interact with the Wave API by extension or integration.

One of the ways to extend Google Wave is via a Robot. A Robot is an automated participant on a wave. A robot has exactly the same rights as any other participant in a wave. For example, a robot can modify information in a wave, talk with other participants and communicate details to the outside world. A robot communicates using the Wave Robot HTTP protocol (which is currently undocumented). For now, the only way in which a robot can be created is to build one using the Google App Engine. Now that GAE supports Java we've already seen how easy it is to write a Google App using Clojure, so it should be pretty simple to write a basic Wave Robot in Clojure.

The first step is to create and register with Google App Engine (see http://appengine.google.com). A Google Wave robot is basically exactly the same as a GAE application. A robot is represented as a standard servlet. The directory structure used is almost exactly the same as that described here.

Project Root
|-build.xml   
|-src/
|-war/
  |- WEB-INF/
     |- app-engine.xml
     |- web.xml
     |- lib
  |- _wave
     |- capabilities.xml

As it involves Java, there's a pretty heavy amount of XML involved. We'll pretend that doesn't exist for the moment and look at the basic implementation of a robot.



This is the "parrot" example from the Google Wave Robots Java Tutorial. It monitors events and when participants join or leave utters a really exciting greeting. processEvents is the event loop for robots. In this case we just filter out the interesting events (me joining a conversation, or people joining a conversation I'm in) and spout out some gibberish.

Back to the XML files. The tutorial explains them better than I can, but in short:

• capabilities.xml - what your robot can do, versioning
  
• web.xml - servlet mappings
  
• appengine-web - name and version information of your application.
  

Examples of all these files and the directory structure is available here. Using this and the SDK to deploy you can get your robot up and running in the Google wave sand box.



So do I think Google Wave is going to change the way we communicate? It's (obviously) too early to tell. If it becomes integrated within standard email clients, allows me to mix mediums (e.g. Twitter, Facebook, email, IM, voice mail) and so on, then it has the potential to unseat email. There's some big questions too. How will robots be regulated? How will you stop spam becoming a nightmare? (you should see Eliza dishing out advice!). Exciting times ahead though!

Parsing Logs with Map/Reduce

Map/Reduce is a software pattern for processing large data sets. It's been popularized by Google, and has now inspired other frameworks, such as Hadoop and CouchDB.

Map/Reduce is based on two very simple functions. Map simply converts values from one domain to the other. reduce (also known as fold) takes a sequence of values and converts them into a single value. For example (reduce + [1 2 3 4 5]) translates to 1 + 2 + 3 + 4 + 5. Distribution is simple to achieve for map because it is functional (no side effects, translating one value doesn't affect any other). Reduce usually operates on particular keys, allows the results to be computed in parallel (though this depends on some logic when distributing workloads).

I recently had to parse some log files and get an idea of the distribution of some timing information. Usually, I'd knock together a Perl script or just use Excel, but I thought I'd try it with a "functional programming" slant with Clojure.

The log file was in the following format.

  Event 23435 
  3.4
  Event 23511
  32

And so on. The actual events are of no consequence, I just wants to get an idea of what the distribution was like. Using clojure.contrib.duck-streams file reading is very simple (read-lines returns a lazy sequence of lines from the file).


(map second (partition 2 (read-lines filename)))


(update: Alternatively (take-nth 2 (drop 1 (read-lines filename)) does the same thing and feels nicer).

This returns a lazy list of all the timing information. Now all I need to do is get a distribution. All we do is use reduce to build up an association between the value of each element (floored to be within a range) and the number of times it occurs. The code below bunches it up into 10 second chunks and counts the occurrences of each.



Less than 10 lines of code to produce a histogram of a silly log file format. And using Map/Reduce, I could scale exact same example up to run on hundreds of gigabytes of data on huge clusters of computers.

This is exactly why, as a software developer, you should be excited about programming languages (not just functional programming!). The quote below is from Joel Spolsky and sums it up well.

Without understanding functional programming, you can't invent MapReduce, the algorithm that makes Google so massively scalable. The terms Map and Reduce come from Lisp and functional programming. MapReduce is, in retrospect, obvious to anyone who remembers from their 6.001-equivalent programming class that purely functional programs have no side effects and are thus trivially parallelizable. (The Perils of Java Schools)

Pattern Matching Tools

In order to implement the STUDENT program, we first need a more advanced series of pattern matching tools. Chapter 6 of PAIP generalizes the pattern matching tools we saw in Eliza (see here).

The idea is that matching is extended to be customizable. The algorithm is presented in a "data-driven programming" manner. Each pattern (such as is, or, and, not, if) is associated with a corresponding function that does the work. It's a very extensible system because if we want to add an extra pattern, we just add an entry to the table and the job is done. This is a common theme throughout the book so far, and it's slowly beginning to sink in!

The Common Lisp version uses symbol properties to associate data with symbols. To my knowledge, Clojure doesn't support this (please correct me if I'm wrong!), so I modelled this as a simple associative structure with lookups based on the symbol name.



Most of the other functions were pretty trivial to port across to Clojure, but progv presented some problems. progv is a special operator which creates special bindings. This effectively allows you to inject additional environment into a lump of code you want to evaluate. For the match-if function, the Common Lisp code looks like this:



This effectively makes bindings available to the item that you want to fiddle with. From some of the comments on Critiquing Clojure it looks like there may be a better way of doing this, than the hacky way I've done it. I simply replaced all occurrences of the variables (?var) with the appropriate bindings. On the way, I discovered the oddly named postwalk-replace which traverses deeply into a structure and replaces using a provided map. (note that this is in no way the same as progv because it's just search and replace and doesn't handle the fact that someone could declare a variable overwriting the bindings).



You can find the complete source for the pattern matching chapter of PAIP on my Clojure Projects github page.