Category: Projects

I’ve been playing with Erlang over nights and weekends off and on for a few months now. I’m loving it for several reasons. First off, it’s completely different than any other programming language I’ve worked with. It makes me think rather than take things for granted. I’m intrigued by concurrency abilities and its immutable no-shared-state mentality. I do go through periods of amazing productivity followed by hours if not days of figuring out a simple task. Luckily the folks in #erlang on irc.freenode.net have been extremely patient with myself and the hundreds of other newcomers and have been extremely helpful. I’m also finding that those long pain periods are happening less frequently the longer I stick with it.

One of the things that truly blew me away about Erlang (after the original Erlang Now! moment) is its bit syntax. The bit syntax as documented at erlang.org and covered in Programming Erlang is extremely powerful. Some of the examples in Joe’s book such as parsing an MP3 file or an IPv4 datagram hint at the power and conciseness of binary matching and Erlang’s bit syntax. I wanted to highlight a few more that have impressed me while I was working on some network socket programming in Erlang.

There are several mind-boggling examples in Applications, Implementation and Performance Evaluation of Bit Stream Programming in Erlang (PDF) by Per Gustafsson and Konstantinos Sagonas. Here are two functions for uuencoding and uudecoding a binary:

uuencode(BitStr) ->
<< (X+32):8 || <<X:6>> <= BitStr >>.
uudecode(Text) ->
<< (X-32):6 || <<X:8>> <= Text >>.

UUencoding and UUdecoding isn’t particularly hard, but I’ve never seen an implementation so concise. I’ve also found that Erlang’s bit syntax makes socket programming extremely easy. The gen_tcp library makes connection to TCP sockets easy, and Erlang’s bit syntax makes creating requests and processing responses dead simple too.

Here’s an example from qrbgerl, a quick project of mine that receives random numbers from the Quantum Random Bit Generator service. The only documentation I needed to use the protocol was the Python client and the C++ client. Having access to an existing Python client helped me bridge the “how might I do this in Python?” and “how might I do this in Erlang?” gaps, but I ended up referring to the canonical C++ implementation quite a bit too.

I start out by opening a socket and sending a request. Here’s the binary representation of the request I’m sending:

list_to_binary([<<0:8,ContentLength:16,UsernameLength:8>>, Username, 
<<PasswordLength:8>>, Password, <<?REQUEST_SIZE:32>>]),

This creates a binary packet that complies exactly with what the QRBG service expects. The first thing that it expects is a 0 represented in 8 bits. Then it wants the length of the username plus the length of the password plus 6 (ContentLength above) represented in 16 bits. Then we have the username represented as 8 bit characters/integers, followed by the length of the password represented in 8 bits, followed by the password (again as 8 bit characters/integers). Finally we represent the size of the request in 32 bits. In this case the macro ?REQUEST_SIZE is 4096.

While that’s a little tricky, once we’ve sent the request, we can use Erlang’s pattern matching and bit syntax to process the response:

<<Response:8, Reason:8, Length:32, Data:Length/binary, 
_Rest/binary>> = Bin,

We’re matching several things here. The response code is the first 8 bits of the response. In a successful response we’ll get a 0. The next 8 bits represent the reason code, again 0 in this case. The next 32 bits will represent the length of the data we’re being sent back. It should be 4096 bytes of data, but we can’t be sure. Next we’re using the length of the data that we just determined to match that length of data as a binary. Finally we match anything else after the data and discard it. This is crucial because binaries are often padded at the beginning or end of the stream. In this case there’s some padding at the end that we need to match but can safely discard.

Now that we have 4096 bytes of random bits, let’s do something with them! I’ve mirrored the C++ and Python APIs as well as I could, but because of Erlang’s no shared state it’s going to look a little different. Let’s match a 32 bit integer from the random data that we’ve obtained:

<<Int:32/integer-signed, Rest/binary>> = Bin,

We’re matching the first 32 bits of our binary stream to a signed integer. We’re also matching the rest of the data in binary form so that we can reuse it later. Here’s that data extraction in action:

5> {Int, RestData} = qrbg:extract_int(Data).
{-427507221,
 <<0,254,163,8,239,180,51,164,169,160,170,248,94,132,220,79,234,4,117,
   248,174,59,167,49,165,170,154,...>>}
6> Int.
-427507221

I’ve been quite happy with my experimentation with Erlang, but I’m definitely still learning some basic syntax and have only begun to play with concurrency. If the above examples confuse you, it might help to view them in context or take a look at the project on google code. I have also released an ISBN-10 and ISBN-13 validation and conversion library for Erlang which was a project I used to teach myself some Erlang basics. I definitely have some polishing to do with the QRBG client, but isbn.erl has full documentation and some 44 tests.

For a few weeks now I’ve been tinkering with, learning about, and falling in love with Erlang. I’ve been noticing the buzz about Erlang over the past few months, but two things won me over: the Erlang video and how amazingly simple and elegant concurrency and message passing is.

For the past few weeks I’ve been reading the Erlang documentation, Joe Armstrong’s new book, reading the trapexit wiki, and lurking in #erlang on irc.freenode.net. If you’re wading in the erlang waters, I highly suggest just about every link in this wonderful roundup of beginners erlang links.

After a few weeks of reading and tinkering in the shell I decided that it was time to come up with a quick project to hone my Erlang skills. I had tinkered with ISBN validation and conversion while writing a small django application to catalog the books on the bookshelf, so I thought that was a good place to start. The Wikipedia page and my collection of ISBN links provided me with more than enough guidance on validation, check digit generation, and conversion.

I found it very easy to build this module from the ground up: start with ISBN-10 check digit generation, then use that to build an ISBN-10 validator. I did a similar thing with ISBN-13, writing the check digit generator and then the ISBN-13 validator. From there I was able to build on all four public functions to write an ISBN-10 to ISBN-13 converter as well as an ISBN-13 to ISBN-10 converter (when that is a possibility). In the process of this very simple module I ended up learning about and applying accumulators, guards, the use of case, and lots of general Erlang knowledge.

Here’s a peek at how the module works. After downloading it via google code or checking out the latest version via Subversion, the module needs to be compiled. This is easily accomplished from the Erlang shell (once you have Erlang installed of course):

mcroydon$ erl
Erlang (BEAM) emulator version 5.5.4 [source] [async-threads:0] [kernel-poll:false]

Eshell V5.5.4  (abort with ^G)
1> c('isbn.erl').
{ok,isbn}

After that we can use any of the exported functions:

2> isbn:validate_13([9,7,8,1,9,3,4,3,5,6,0,0,5]).
true

Let’s trace the execution of a simple function, check_digit_10/1. The function expects a list of 9 numbers (the first 9 numbers of an ISBN-10) and returns the check digit as either an integer or the character 'X'. The first thing that the function does is check to see if we’ve actually passed it a 9-item list:

check_digit_10(Isbn) when length(Isbn) /= 9 ->
    throw(wrongLength);

This is accomplished with a simple guard (when length(Isbn) /- 9). If that guard isn’t triggered we move on to the next function:

check_digit_10(Isbn) -> 
    check_digit_10(Isbn, 0).

This forwards our list of 9 numbers on to check_digit_10/2 (a function with the same name that takes two arguments. We’ll see in a minute that the 0 I’m passing in will be used as an accumulator. The next function does most of the heavy lifting for us:

check_digit_10([H|T], Total) ->
    check_digit_10(T, Total + (H * (length(T) + 2)));

This function takes the list, splits it in to the first item (H) and the rest of the list (T). We add to the total as specified in ISBN-10 and then call check_digit_10/2 again with the rest of the list. This tail-recursive approach seems odd at first if you’re coming from most any object oriented language, but Erlang’s function nature, strong list handling, and tail-recursive ways feel natural very quickly. After we’ve recursed through the entire list, it’s time to return the check digit (or 11 minus the total modulus 11). There’s a special case if we get a result of 10 to use the character ‘X’ instead:

check_digit_10([], Total) when 11 - (Total rem 11) =:= 10 ->
    'X';

Finally we return the result for the common case given an empty list:

check_digit_10([], Total) ->
    11 - (Total rem 11).

Feel free to browse around the rest of the module and use it if you feel it might be useful to you. I’ve posted the full source to my isbn module at my isbnerl Google Code project, including the module itself and the module’s EDoc documentation. It is released under the new BSD license in hopes that it might be useful to you.

I learned quite a bit creating this simple module, and if you’re learning Erlang I suggest you pick something not too big, not too small, and something that you are interested in to get your feet wet. Now that I have the basics of sequential Erlang programming down, I think the next step is to make the same move from tinkering to doing something useful with concurrent Erlang.

Now that I have a RELAX NG Compact schema of GPX, it’s time to figure out how to get my data in to PostGIS. so I can do geospatial queries. I installed PostGIS on my Ubuntu box with these instructions. If I recall correctly, the latest version didn’t work but the previous release did.

GPX makes a great GPS data interchange format, particularly because you can convert just about anything to GPX with GPSBabel. I’m not aware of anything that can convert straight from GPX to PostGIS, but it is a relatively straightforward two-part process.

The first order of business is converting our GPX file to an ESRI Shapefile. This is easiest done by using gpx2shp, a utility written in C that is also available in Ubuntu. Once gpx2shp is installed, run it on your GPX file: gpx2shp filename.gpx.

Once we have a shape file, we can use a utility included with PostGIS to import the shapefile in to postgres. The program is called shp2pgsql, and can be used as such: shp2pgsql -a shapefile.shp tablename. I tend to prefer the -a option which appends data to the table (as long as it’s the same basic type of the existing data). shp2pgsql generates SQL that you can then pipe in to psql as such: shp2pgsql -a shapefile.shp tablename | psql databasename.

Once the data is in Postgres (don’t forget to spatially-enable your database, you can query it in ways that I’m still figuring out. A basic query like this will return a list of lat/lon pairs that corresponds to my GPS track: select asText(the_geom) from tablename;. I’m llooking forward to wrapping my head around enough jargon to do bounding box selects, finding things nearby a specific point, etc.

The examples in the PostGIS documentation seem pretty good, I just haven’t figured out how to apply it to the data I have. I feel like mastering GIS jargon is one of the biggest hurdles to understanding PostGIS better. Well, that and a masters degree in GIS wouldn’t hurt.