sitr.us

Functional Reactive Programming in JavaScript

2013-05-22T00:00:00-07:00

I had a great time at NodePDX last week. There were many talks packed into a short span of time and I saw many exciting ideas presented. One topic that seemed particularly useful to me was Chris Meiklejohn’s talk on Functional Reactive Programming (FRP).

I have talked and written about how useful promises are. See Promise Pipelines in JavaScript. Promises are useful when you want to represent the outcome of an action or a value that will be available at some future time. FRP is similar except that it deals with streams of reoccurring events and dynamic values.

Here is an example of using FRP to subscribe to changes to a text input. This creates an event stream that could be used for a typeahead search feature:

var inputs = $('#search')
    .asEventStream('keyup change')
    .map(function(event) { return event.target.value; })
    .filter(function(value) { return value.length > 2; });

var throttled = inputs.throttle(500 /* ms */);

var distinct = throttled.skipDuplicates();

This creates an event stream from all keyup and change events on the given input. The stream is transformed into a stream of strings matching the value of the input when each event occurs. Then that stream is filtered so that subscribers to inputs will only receive events if the value of the input has a length greater than two.

Streams can be assigned to variables, shared, and used as inputs to create more specific streams. In the example above inputs is used to create two more streams: one that limits the stream so that events are emitted at most every 500 ms and another that takes the throttled stream and drops duplicate values that appear consecutively. So when the final stream, distinct, is consumed later it is guaranteed that events 1) will be non-empty strings with length greater than two, 2) will not occur too frequently, and 3) will not include duplicates.

That stream can be fed through a service via ajax calls to show a live list of results:

function searchWikipedia(term) {
    var url = '//en.wikipedia.org/w/api.php?callback=?';
    return $.getJSON(url, {
        action: 'opensearch',
        format: 'json',
        search: term
    })
    .then(function(data) {
        return { query: data[0], results: data[1] };
    });
}

var suggestions = distinct.flatMapLatest(function(value) {
    return Bacon.fromPromise(searchWikipedia(value));
});

suggestions.onValue(function(data) {
    var $results = $('#results').empty();
    data.results.forEach(function(s) {
        $('<li>').text(s).appendTo($results);
    });
});

Here suggestions is a new stream that has been transformed from strings to search results using the searchWikipedia function. All of jQuery’s ajax methods return promises and Bacon.fromPromise() turns a promise into an event stream.

The flatMapLatest transformer builds a new stream from an existing stream and a stream factory - and it only emits events from the last stream created. This means that if the user types slowly and a lot of ajax requests are made responses to all but the last request will be disregarded.

The suggestions stream is ultimately used by calling its onValue method. That adds a subscriber that runs code for every event that makes it all the way through the stream. The result is a list of search results that is updated live as the user types.

There are some other tricks available. It is possible to bind data from an event stream to a DOM element:

var query = suggestions.map(function(data) {
    return data.query;
}).toProperty('--');

query.assign($('#query'), 'text');

This creates a new stream that is pared down to just the query used to produce each set of results. Whenever a result set is rendered the corresponding query will also be output as the text content of the '#query' element. The new stream is converted to a property to make this work. A property is a value that varies over time. The main practical distinction between a property and an event stream is that a property always has a value. In other words a property is continuous while an event stream is discrete. This example provides '--' as the initial value for the new property.

Notice that property binding as shown here is more general than some data binding frameworks in that the destination is not limited to DOM elements and the source is not limited to model instances. This example passes values to the text method of the given jQuery object. It is possible to push data to any method on any object.

Streams can be combined, split, piped, and generally manipulated in all kinds of ways. Properties can be bound, sampled, combined, transformed, or whatever.

I put this code up on JSFiddle so you can try it out and play with it: http://jsfiddle.net/hallettj/SqrNT/

There are several FRP implementations out there. Two that seem to be prominent are Bacon.js and RxJS. The examples above are code from the RxJS documentation that I rewrote with Bacon. That gave me an opportunity to learn a bit about both libraries and to see how they approach the same problem. The original RxJS code is here.

With FRP it is possible to describe complicated processes in a clean, declarative way. FRP is also a natural way to avoid certain classes of race conditions. When I wrote the initial version of the sample code above it worked perfectly on the first try. In my view that is a sign of a very well-designed library.

If you are interested in further reading I suggest the series of tutorials from the author of Bacon. And there is a great deal of information on the RxJS and Bacon Github pages, including documentation and more examples.

Monkey patching document.write()

2012-09-04T00:00:00-07:00

This is one of the crazier workarounds that I have implemented. I was working on a web page that embeds third-party widgets. The widgets are drawn in the page document - they do not get their own frames. And sometimes the widgets are redrawn after page load.

We had a problem with one widget invoking document.write(). In case you are not familiar with it, if that method is called while the page is rendering it inserts content into the DOM immediately after the script tag in which the call is made. But if document.write() is called after page rendering is complete it erases the entire DOM. When this widget was redrawn after page load it would kill the whole page.

The workaround we went with was to disable document.write() after page load by replacing it with a wrapper that checks whether the jQuery ready event has fired.

(function() {
    var originalWrite = document.write;
    document.write = function() {
        if (typeof jQuery !== 'undefined' && jQuery.isReady) {
            if (typeof console !== 'undefined' && console.warn) {
                console.warn("document.write called after page load");
            }
        }
        else {
            // In IE before version 8 `document.write()` does not
            // implement Function methods, like `apply()`.
            return Function.prototype.apply.call(
                originalWrite, document, arguments
            );
        }
    }
})();

The new implementation checks the value of jQuery.isReady and delegates to the original document.write() implementation if the page is not finished rendering yet. Otherwise it does nothing other than to output a warning message.

Disabling document.write() means that the problematic widget will not be fully functional if it is redrawn after page load. It happens that in the case of this app that is ok. The redrawn widget is only used as a preview when editing widget layouts.

A particular problem came up with IE compatibility. I wanted to use the apply method that is implemented by all functions in JavaScript to invoke the original document.write() implementation, like this:

return originalWrite.apply(document, arguments);

But in older versions of Internet Explorer, document.write() is not really a function. There are a lot of examples in IE of native API methods and properties that do not behave like regular JavaScript values. For example if you pass too many arguments to a DOM API method in old IE you will get an exception. Normal JavaScript functions just silently ignore extra arguments. If you look at the value of typeof document.write the result is not "function". What is particularly problematic in this case is that document.write does not implement call or apply.

Fortunately I found that the Function prototype does implement both call and apply and furthermore you can borrow those methods to use on function-like values like document.write. call and apply are themselves real function values - so call and apply both implement call and apply.

typeof Function.prototype.apply.apply.apply  // evaluates to 'function'
typeof Function.prototype.apply.call.call  // evaluates to 'function'

In the workaround above I applied apply to document.write by taking the Function.prototype.apply value and using its call method. So this expression,

Function.prototype.apply.call(originalWrite, document, arguments);

is equivalent to this one,

originalWrite.apply(document, arguments);

Except that the first version works in IE7.

If you find this difficult to follow, you are not alone.

We have had this workaround in our code for a couple of years now. So far it is working nicely.

Promise Pipelines in JavaScript

2012-07-31T00:00:00-07:00

Promises, also know as deferreds or futures, are a wonderful abstraction for manipulating asynchronous actions. Dojo has had Deferreds for some time. jQuery introduced its own Deferreds in version 1.5 based on the CommonJS Promises/A specification. I’m going to show you some recipes for working with jQuery Deferreds. Use these techniques to turn callback-based spaghetti code into elegant declarative code.

The basics of jQuery Deferreds

A Deferred is an object that represents some future outcome. Eventually it will either resolve with one or more values if that outcome was successful; or it will fail with one or more values if the outcome was not successful. You can get at those resolved or failed values by adding callbacks to the Deferred.

In jQuery’s terms a promise is a read-only view of a deferred.

Here is a simple example of creating and then resolving a promise:

function fooPromise() {
    var deferred = $.Deferred();

    setTimeout(function() {
        deferred.resolve("foo");
    }, 1000);

    return deferred.promise();
}

Callbacks can be added to a deferred or a promise using the .then() method. The first callback is called on success, the second on failure:

fooPromise().then(
    function(value) {
        // prints "foo" after 1 second
        console.log(value);
    },
    function() { console.log("something went wrong"); }
);

For more information see the jQuery Deferred documentation.

Note that if you are using a version of jQuery prior to 1.8 you will have to use .pipe() instead of .then(). That goes for all references to .then() in this article.

Sequential operations

Actions, such as HTTP requests, need to be sequential if input to one action depends on the output of another; or if you just want to make sure that actions are performed in a particular order.

Consider a scenario where you have a post id and you want to display information about the author of that post. Your web services don’t support embedding author information in a post resource. So you will have to download data on the post, get the author id, and then make another request to get data for the author. To start with you will want functions for downloading a post and a user:

function getPost(id) {
    return $.getJSON('/posts/'+ id).then(function(data, status, xhr) {
        return data;
    });
}

function getUser(id) {
    return $.getJSON('/users/'+ id).then(function(data, status, xhr) {
        return data;
    });
}

In jQuery 1.5 and later all ajax methods return a promise that, on a successful request, resolves with the data in the response, the response status, and the XHR object representing the request.

The .then() method produces a new promise that transforms the resolved value of its input. I used .then() here just because using $.when() is simpler if each promise resolves to a single value. We will get back to that in parallel operations. Since only one argument is provided to .then() in these cases the new promises will have the same error values as the originals if an error occurs.

The result is that getUser() returns a promise that should resolve to data representing the user profile for a given id. And getPost() works the same way for posts and post ids.

Now, to fetch that author information:

function authorForPost(id) {
    var postPromise = getPost(id),
        deferred = $.Deferred();

    postPromise.then(function(post) {
        var authorPromise = getUser(post.authorId);

        authorPromise.then(function(author) {
            deferred.resolve(author);
        });
    });

    return deferred.promise();
}

When authorForPost() is called it returns a new promise that resolves with author information after both the post and author requests complete successfully. This is a straightforward way to get the job done. Though it does not implement error handling; and it could be more DRY. More on that in a bit.

Parallel operations

Let’s say that you want to fetch two user profiles to display side-by-side. Using the getUser() function from the previous section:

function getTwoUsers(idA, idB) {
    var userPromiseA = getUser(idA),
        userPromiseB = getUser(idB);

    return $.when(userPromiseA, userPromiseB);
}

The requests for userA and userB’s profiles will be made in parallel so that you can get the results back as quickly as possible. This function uses $.when() to synchronize the promises for each profile so that getTwoUsers() returns one promise that resolves with the data for both profiles when both responses come back. If either request fails, the promise that getTwoUsers() returns will fail with information about the first failed request.

You might use getTwoUsers() like this:

getTwoUsers(1002, 1008).then(function(userA, userB) {
    $(render(userA)).appendTo('#users');
    $(render(userB)).appendTo('#users');
});

The getTwoUsers() promise resolves with two values, one for each profile.

We now have several well-defined functions that operate on asynchronous actions. Isn’t this nicer than the big mess of nested callbacks one might otherwise see?

I mentioned above that using $.when() is simpler when each of its input promises resolves to a single value. That is because if an input promise resolves to multiple values then the corresponding value in the new promise that $.when() creates will be an array instead of a single value.

Performing an arbitrary number of actions in parallel is similar:

function getPosts(ids) {
    var postPromises = ids.map(getPost);

    return $.when.apply($, postPromises).then(function(/* posts... */) {
        return $.makeArray(arguments);
    });
}

This code fetches any number of posts in parallel. I used apply to pass the post promises to $.when() as though they are each a separate argument. The resulting promise resolves with a separate value for each post. It would be nicer if it resolved with an array of posts as one value. The use of .then() here takes those post values and transforms them into an array.

Combining sequential and parallel operations

Let’s take the previous examples to their logical conclusion by creating a function that, given two post ids, will download information about the authors of each post to display them side-by-side. No problem!

function getAuthorsForTwoPosts(idA, idB) {
    return $.when(authorForPost(idA), authorForPost(idB));
}

From the perspective of a function that calls authorForPost(), it does not matter that two sequential requests are made. Because authorForPost() returns a promise that represents the eventual result of both requests, that detail is encapsulated.

Generalizing sequential operations

There are a couple of problems with the implementation of authorForPost() as presented above. We had to create a deferred by hand, which should not be necessary. And the promise that is returned does not fail if any of the requests involved fail.

These issues are not present in the parallel examples because $.when() does a nice job of generalizing synchronizing multiple promises. What we need is a function that does a similar job of generalizing flattening nested promises. Meet flatMap:

$.flatMap = function(promise, f) {
    var deferred = $.Deferred();

    function reject(/* arguments */) {
        // The reject() method puts a deferred into its failure
        // state.
        deferred.reject.apply(deferred, arguments);
    }

    promise.then(function(/* values... */) {
        var newPromise = f.apply(null, arguments);

        newPromise.then(function(/* newValues... */) {
            deferred.resolve.apply(deferred, arguments);
        }, reject);

    }, reject);

    return deferred.promise();
};

This function takes a promise and a callback that returns another promise. When the first promise resolves, $.flatMap() invokes the callback with the resolved values as arguments, which produces a new promise. When that new promise resolves, the promise that $.flatMap() returns also resolves with the same values. On top of that, $.flatMap() forwards errors to the promise that it returns. If either the input promise or the promise returned by the callback fails then the promise that $.flatMap() returns will fail with the same values.

Using $.flatMap() it is possible to write a function like authorForPost() a bit more succinctly:

function authorForPost(id) {
    return $.flatMap(getPost(id), function(post) {
        return getUser(post.authorId);
    });
}

By using $.flatMap() you also get error handling for free. If the request to fetch a post fails or the request to fetch the post’s author fails the promise that this version of authorForPost() returns will also fail with the appropriate failure values.

Another potential problem is that authorForPost() does not give you access to any of the information on the posts that it downloads. You can combine $.flatMap() and .then() to create a slightly different function that exposes both the post and the author:

function postWithAuthor(id) {
    return $.flatMap(getPost(id), function(post) {
        return getUser(post.authorId).then(function(author) {
            return $.extend(post, { author: author });
        });
    });
}

The promise that postWithAuthor() returns resolves to a post object with an added author property containing author information.

It turns out that .then() leads a double life. If the return value of its callback is a promise, .then() behaves exactly like $.flatMap()! This is the sort of thing that only a dynamic language like JavaScript can do. So if you want to skip the custom function, you could write postWithAuthor() like this:

function postWithAuthor(id) {
    return getPost(id).then(function(post) {
        return getUser(post.authorId).then(function(author) {
            return $.extend(post, { author: author });
        });
    });
}

Other uses for promises

The examples above focus on HTTP requests. But promises can be used in any kind of asynchronous code. They even come in handy in synchronous code from time to time.

Here is an example of a promise used to represent the outcome of a series of user interactions:

function getRegistrationDetails() {
    var detailsPromise = openModal($.get('/registrations'));

    detailsPromise.then(function(details) {
        $.post('/registrations', details);
    });
}

function openModal(markupPromise) {
    var deferred = $.Deferred(),
        modal = $('<div></div>').addClass('modalWindow'),
        loadingSpinner = $('<span></span>').addClass('spinner');

    modal.append(loadingSpinner);

    // Use .always() to add a callback to a promise that runs on success
    // or failure.
    markupPromise.always(function() {
        loadingSpinner.remove();
    });

    markupPromise.then(function(markup) {
        modal.html(markup);
    });

    modal.one('submit', 'form', function(event) {
        event.preventDefault();
        var data = $(this).serialize();
        modal.remove();
        deferred.resolve(data);
    });

    modal.appendTo('body');

    return deferred.promise();
}

$(document).ready(function() {
    $('#registerButton').click(function(event) {
        event.preventDefault();
        getRegistrationDetails();
    });
});

I suggest considering using promises anywhere you would otherwise pass a callback as an argument.

Conclusion

The promise transformations .then(), $.when(), and $.flatMap() work together to build promise pipelines. Using these functions you can define arbitrary parallel and sequential operations with nice declarative code. Furthermore, small promise pipelines can be encapsulated in helper functions which can be composed to form longer pipelines. This promotes reusability and maintainability in your code.

Use .then() to transform individual promises.

Use $.when() to synchronize parallel operations.

Use $.flatMap() or .then() to create chains of sequential operations.

Mix and match as desired.

I would like to thank Ryan Munro for coming up with the “pipeline” analogy.

Update 2012-08-01: .pipe() was added in jQuery 1.6. And it turns out that it behaves like $.flatMap() when its callback returns a promise. In jQuery 1.8 .then() will be updated to behave exactly like .pipe(), and .pipe() will be deprecated. So there is actually no need to add a custom method - you can just use .pipe() or .then() instead of $.flatMap().

Update 2013-01-30: jQuery 1.8 has been released, so I replaced references to .pipe() with .then(). I also included a more prominent explanation that .then() can do the same thing that $.flatMap() does.

Promises and Category theory

Good news! If you are able to follow the examples in this post then you have a working understanding of Monads. Specifically, $.flatMap() is a monad transformation, .then() with one argument is a functor transformation, and $.when() is almost a monoid transformation.

Monads, monoids, and functors are concepts from category theory that can be applied to functional programming. Really they are just generalizations of this idea of creating pipelines to transform values.

I bring this up because category theory can be useful, but is difficult to explain. My hope is that seeing examples of category theory in action will help programmers to get a feel for the patterns involved.

For more information on category theory in programming I recommend a series of blog posts titled Monads are Elephants. If you have read that and want to go further, I found the the book Learn You a Haskell for Great Good! to be very informative. And as a bonus it teaches you Haskell.

Those who are already into category theory will note that $.flatMap() could also be defined in terms of .then() and a $.join() function:

$.flatMap = function(promise, f) {
    return $.join(promise.then(f));
};

$.join = function(promise) {
    var deferred = $.Deferred();

    function reject(/* arguments */) {
        deferred.reject.apply(deferred, arguments);
    }

    promise.then(function(nestedPromise) {

        nestedPromise.then(function(/* values... */) {
            deferred.resolve.apply(deferred, arguments);
        }, reject);

    }, reject);

    return deferred.promise();
};

Except that this won’t actually work because .then() will join the inner and outer promises before the result is passed to $.join().

Installing a custom ROM on the Transformer Prime: A start-to-finish guide

2012-05-12T00:00:00-07:00

This guide provides step-by-step instructions for installing the Virtuous Prime community ROM on your Asus Transformer Prime TF201 tablet. This guide will be useful to you if you do not have root access to your tablet.

Be aware that following the instructions here will void your warranty and will wipe all of the data on your tablet. There is also a danger that you might brick your tablet. Proceed at your own risk.

So, why would you want to install a custom ROM on your tablet? In my case I wanted to gain root access, which allows one to do all sorts of nifty things. Community-made ROMS are also often customized to make the Android experience more pleasant for power users. And choosing your own ROM means that you are no longer dependent on the company that sold you your device to distribute firmware updates in a timely fashion. But if you are reading this then you probably already know why you want to install a custom ROM - so let’s get on to the next step.

This guide specifically covers installing Virtuous Prime, which is based on the official Asus firmware. If you like the features that Asus provides, like the ability to switch between performance profiles and to toggle IPS+ mode then this is probably the ROM for you. Virtuous also adds some features like root access, the ability to overclock the processors to 1.6 GHz, and so on. Note to the Virtuous ROM devs: it is really awesome to have you all putting in the effort to make the Android experience better for everybody. It is especially amazing that you give your ROM away for free. You are virtuous people indeed! That said, these folks do accept donations.

If you would rather get a vanilla Ice Cream Sandwich experience then you might check out AOKP.

If you just want root access and you do not want to install a custom ROM then there is a simpler procedure that you can follow using SparkyRoot. The catch is that SparkyRoot does not work in firmware versions v9.4.2.21 or later. Part of the reason that I went for a custom ROM is that I upgraded the firmware on my Prime as soon as I got it - so I missed my shot at using SparkyRoot. Don’t be like me: plan ahead!

If you have the newest firmware version it is possible to downgrade in order to use SparkyRoot. I chose to install a custom ROM instead because it seemed to me to be a safer option. Be aware that if you follow the directions here to install a custom ROM you will not be able to use the downgrade procedure in that link.

In brief, here are the steps that we are going to follow:

Unlock the bootloader using the official Asus tool.
Install ClockworkMod Recovery.
Install the Virtuous Prime ROM, using ClockworkMod.

Step 1: Unlock the bootloader

I am not completely sure that this step is necessary. I did not try installing ClockworkMod Recovery before unlocking. But even if it is not necessary, I imagine that there may come a time when I am glad to have an unlocked bootloader. You can try skipping this step; at worst nothing will happen.

The unlocking tool is provided by Asus. As you will see, Asus makes it very clear that using the unlock tool will void your warranty. But on the upside it will not wipe your data or anything like that. The only noticeable change will be that every time you boot up the tablet there will be a message in the upper-left corner of the screen that says, “The device is UnLocked”. I assume that is there so that customer service representatives can see that they are not supposed to help you.

Download the unlock tool directly onto your tablet from the TF201 support section of the Asus website. Select “Android” as the OS and grab the “Unlock Device App” from the “Utilities” section. The file that you get is an apk that you will install as an app.

If you have not done so already, you will have to enable unknown software sources in your tablet settings. Go to Settings > Security > Device Administration and check the box that says “Unknown Sources”.

Use your file manager to find the downloaded unlock tool. It is probably in /sdcard/Download/UnLock_Device_App_V6.apk. Tap it to install the app.

You will be prompted to confirm your Google account by entering your Google password. If you are using two-factor authentication on your Google account you will have to set up an application-specific password for this. You can revoke that password after your tablet is unlocked.

Next you will have to agree to a license and acknowledge a warning. Again, Asus wants to make it really clear that you are about to void your warranty.

After you agree to everything your tablet will reboot and your bootloader is now unlocked.

Step 2: Install ClockworkMod Recovery

ClockworkMod Recovery is a custom recovery image. The Transformer Prime comes with a recovery image provided by Asus that lets you do stuff like manually install OS updates. But the Asus recovery image will only let you install updates that are digitally signed by Asus. To install a community-made ROM you need a recovery mode that will let you install unsigned ROMs. That is what ClockworkMod does. It also provides extra features, like the ability to back up and restore your whole OS.

Installing ClockworkMod will probably void your warranty - in case you somehow got to this point with an intact warranty. There is also some danger that you could brick your tablet. Proceed at your own risk.

These instructions are adapted from a guide on TransformerPrimeRoot.com. I’m going to give you the slightly more complicated version that involves downloading files directly from ClockworkMod and from Google; and I will provide tips on what to do if the fastboot tool is not able to find your tablet. I personally appreciate it when I can get files from sources that I know I can trust. But if you are not convinced that is necessary then feel free to check out the TransformerPrimeRoot.com guide.

For this step you will need a computer.

Download the latest ClockworkMod Recovery image from ClockworkMod’s downloads page. As of this writing the latest version for the Transformer Prime is 5.8.2.0. According to TransformerPrimeRoot.com earlier versions can put your device into a reboot loop (which you can recover from but it is scary when it happens, I imagine).

The Touch Recovery image should also work. It comes with a nicer touch-based UI. But the guides that I have read call for the non-touch version, so that is what I went with.

You will also need the fastboot tool from the Android SDK to install the recovery image. Download the SDK from Google and extract it. Run the android executable in the tools/ directory to launch the SDK package manager and use that tool to install the Android SDK Platform-tools: check the box next to “Android SDK Platform-tools” and click “Install packages…”. After a few minutes that will add a new executable, fastboot, in the platform-tools directory in the Android SDK package. You will use the fastboot program to send commands to your tablet while the tablet is in fastboot mode.

Android devices have two boot modes apart from the normal boot-into-the-OS option: recovery mode and fastboot. Fastboot is a low-level mode that is used for flashing firmware. You can use fastboot to replace the recovery mode image - which is what we will be doing to install ClockworkMod. And you can use recovery mode to install a new OS. Likewise, if your OS breaks you can fix it from recovery mode and if recovery mode breaks you may be able to fix it from fastboot. What happens if fastboot breaks? Try not to let that happen! The Android devs have not yet provided us with an extra-fast-boot.

If you are on Windows then you will have to install a USB driver before proceeding. Linux and Mac users do not need any special drivers.

Make sure that your battery is charged to at least 50%. Bad things will happen if your battery dies while you are flashing a recovery image.

Boot your tablet into fastboot by holding down the power and volume-down buttons. The tablet will power off and reboot. Wait until you see several lines of white text in the upper-left corner of the screen, then let go of the power and volume buttons. Then wait for five seconds and you will see the fastboot options.

Press volume-down to highlight the USB icon and then press volume-up to select it. You have ten seconds to do this - after that the tablet will cold-boot Android instead. If that happens, don’t worry. Just start over by holding down the power and volume-down buttons.

Plug the tablet into your computer using the USB cable that came with your tablet.

On your computer open a terminal. Assuming that you have the ClockworkMod Recovery image and the extracted Android SDK in the same downloads folder, cd to that folder. Run this fastboot command to make sure that your computer is talking to your tablet:

android-sdk_r18/platform-tools/fastboot -i 0x0b05

The -i 0x0b05 part tells fastboot which USB device to communicate with. The number 0b05 is the Asus vendor id for USB interfaces. If you want to double-check that vendor id you can use the lsusb command on Linux. On my machine the output includes a line that looks like this:

Bus 002 Device 018: ID 0b05:4d01 ASUSTek Computer, Inc.

The vendor id is the portion of the ID before the colon.

Anyway, if the fastboot command that you ran worked you should see output that looks like this:

finished. total time: 1336881627.143s

On the other hand, if you see a message that says < waiting for device >, and you wait a minute or two and nothing happens, then hit Ctrl-c to cancel. If you are in Linux you can fix this problem by creating a udev rule. Create a new file, /etc/udev/rules.d/99-android.rules and add this line to it:

SUBSYSTEM=="usb", ATTRS{idVendor}=="0b05", MODE="0666", OWNER="yourusername"

But make sure to replace “yourusername” with your user name. Then restart udev with this command:

sudo restart udev

Now try the fastboot command again.

Ok, is fastboot talking to your tablet? Now for the next step: flashing ClockworkMod.

I recommend checking the md5 checksum on the ClockworkMod Recovery image to make sure that it has not been corrupted. On Linux you can use this command to do that:

md5sum recovery-clockwork-5.8.2.0-tf201.img

It appears that ClockworkMod does not list md5 checksums on its downloads page. But here is the checksum that I got for version 5.8.2.0:

08009bd8fa324116e71982945390cdde

You should proceed only if the checksums match.

Run this command - and again make sure that the paths match the locations of the fastboot and ClockworkMod Recovery image files:

android-sdk_r18/platform-tools/fastboot -i 0x0b05 flash recovery recovery-clockwork-5.8.2.0-tf201.img

If all goes well you should see some output like this:

sending 'recovery' (5378 KB)...
OKAY [  1.891s]
writing 'recovery'...
OKAY [  1.571s]
finished. total time: 3.462s

Now you have ClockworkMod Recovery installed.

Step 3: Install the Virtuous Prime ROM

Following the instructions here will wipe everything on your tablet. And you will void your warranty - again. Proceed at your own risk.

There are instructions on RootzWiki for installing Virtuous Prime. I’m going to give you the same instructions but with a bit more detail. But I recommend reading the information on RootzWiki too as there is a lot of useful background there.

Download the latest version of Virtuous Prime directly onto your tablet. As of this writing that is Virtuous Prime 9.4.2.21 v1, which is based on the Transformer Prime v9.4.2.21 firmware from Asus. You will get a zip file - don’t unzip it!

Next to the download link there will be an MD5 checksum. We will refer back to that in a moment.

Use your file manager to move the zip file, virtuous_prime_s_9.4.2.21_v1.zip from /sdcard/Download/ to /sdcard/. I think that this step is superfluous; but it makes me feel better.

This is optional, but highly recommended: install the free MD5 Checker app. You can use this app to check the MD5 checksum of the file that you downloaded to make sure that it was not corrupted. Open MD5 Checker, click on the button labelled “Load File 1”, browse to the Virtuous Prime zip file, and wait for MD5 Checker to compute the file’s checksum. Make sure that the checksum that you see in MD5 Checker is the same as the one from the Virtuous Prime downloads page. If the checksums do not match then do not proceed! Download the file again and check the checksum again.

Shut down your tablet. But make sure that your battery is charged to at least 50% first. And make sure that the USB cable is unplugged.

Boot into recovery mode by holding both the power and volume-down buttons. As with fastboot, when you see several lines of white text in the upper-left corner of the screen let go of both buttons. But this time press volume-up right away. If you do not press volume-up within five seconds then the tablet will go into fastboot. If that happens then just start over by holding the power and volume-down buttons again.

After a moment you should see the ClockworkMod menu. You can use the volume-up and volume-down buttons to highlight the different menu options and the power button to select the option that you want.

Make a backup of your current ROM. Select “backup and restore”, then “backup”. This will create a timestamped backup directory on your tablet under /sdcard/clockwork/backup/.

There is a lot of information on backing up and restoring your tablet here.

The backup process will take a few minutes. When it is done you will see the ClockworkMod menu again.

Select “wipe data/factory reset”. According to RootzWiki this step is optional, but is highly recommended. You will have to complete an elaborate confirmation step to start the wipe.

Once all of your data has been wiped, select “install zip from sdcard”, then “choose zip from sdcard”. Browse to the Virtuous Prime ROM and select it. And confirm that you are really sure about this.

You will be taken through a guided install process in which you will be prompted to choose between Typical, Complete, or Minimal install modes. There is a list of the differences between the three modes on RootzWiki.

When the installer is finished your tablet will reboot and you are done! Congratulations! Enjoy your new ROM!

More Resources

There is some useful information collected on TransformerPrimeRoot.com. Much of the information in my guide comes from that site.

If the worst should happen and your tablet becomes a brick, you may still be able to recover. Check out the recovery guide on XDA-Developers.

Update 2012-05-19

After about a week of use, the Virtuous Prime ROM is working very well. It does everything that the Asus firmware did and more. But I did run into some problems that I wanted to report along with some workarounds.

The Hulu Plus app does not work for me anymore. When I try to play a video I get this message:

Streaming Unavailable [91]

Sorry, we are unable to stream this video. Please check your Internet connection, ensure you have the latest official update for your device, and try again.

The Hulu app did work for me before I unlocked my tablet. There are reports that unlocking the bootloader is what causes this problem. This may not have anything to do with Virtuous Prime directly.

A helpful community member created a modified version of the Hulu Plus app that does work. From the first post in that thread you can download and install the Landscape Mod HuluPlus.apk package. You will need to enable “Unknown Sources” to install the package. Before you install this version I suggest wiping the data of the original Hulu app and uninstalling it.

The home view in the app is distorted; but the queue view works fine. This mod is based on a phone version of the original Hulu app rather than a tablet version. Video quality seems a bit low - I don’t know whether that is due to my connection or to the app. With those caveats, the modified app works great for me.

Netflix works perfectly. Hooray for Netflix!

The Amazon Kindle app crashes when I try to open a book. I have tried wiping the app’s data and reinstalling multiple times. I have also tried different books. And I have confirmed that I am running version 3.5.1.1, which is the latest version available in the Play Store right now.

I managed to fix the Kindle app by following instructions to fix Machinarium, which simply involves installing a missing font.

An alternative workaround is to use the Cloud Reader. Note that the Cloud Reader will work in Chrome for Android Beta, but will refuse to run in the default Android browser. You will not be able to install the extension that allows Cloud Reader to work offline since the mobile version of Chrome does not support extensions yet. So you will have to be connected to the internet to use the Cloud Reader.

Someone on the XDA Developers forum asked whether the game Machinarium would install under Virtuous Prime. I tested this and found that the game will install - but it crashes on startup. I did not test this game before installing Virtuous Prime. All other games that I have tested have worked fine.

It turns out that the problem with Machinarium is that there is a missing font in Virtuous Prime. Specifically the Droid Sans and Droid Sans Bold fonts are missing. There is a fix reported in the XDA Developers forum.

So with some digging it seems that I did not encounter any problems that I could not fix. Also, having root access to my tablet is excellent.

Cookies are bad for you: Improving web application security

2011-08-26T00:00:00-07:00

Most web applications today use browser cookies to keep a user logged in while she is using the application. Cookies are a decades-old device and they do not stand up well to security threats that have emerged on the modern web. In particular, cookies are vulnerable to cross-site request forgery. Web applications can by made more secure by using OAuth for session authentication.

This post is based on a talk that I gave at Open Source Bridge this year. The slides for that talk are available here.

When a user logs into a web application the application server sets a cookie value that is picked up by the user’s browser. The browser includes the same cookie value in every request sent to the same host until the cookie expires. When the application server receives a request it can check whether the cookies attached to it contain a value that identifies a specific user. If such a cookie value exists then the server can consider the request to be authenticated.

There are many types of attacks that can be performed against a web application. Three that specifically target authentication between the browser and the server are man-in-the-middle (MITM), cross-site request forgery (CSRF), and cross-site scripting (XSS). Plain cookie authentication is vulnerable to all three.

In a MITM attack the attacker is in a position to watch traffic that passes between some user’s browser and an application server. If that traffic is not encrypted the attacker could steal private information. One of the most dangerous things that an attacker can do in this position is to hijack the user’s session by reading cookie data from an HTTP request and including that cookie data in the attacker’s own requests to the same server. This is a form of privilege escalation attack. Using this technique an attacker can convince an application server that the attacker is actually the user who originally submitted a given cookie. Thus the attacker gains access to all of the user’s protected resources.

Last year a Firefox extension called Firesheep made some waves when it was released. The purpose of Firesheep was to raise awareness of the danger of MITM attacks. Most web applications, at that time and today, use cookie authentication without an encrypted connection between browser and server. Firesheep makes it easy to spy on anybody who is using well known applications like Facebook and Twitter on a public network. With the click of a button you can perform a MITM attack yourself, steal someone’s cookies, and gain access to that person’s Facebook account.

MITM attacks can be effectively blocked by using HTTPS to encrypt any traffic that contains sensitive information or authentication credentials. When using HTTPS you will almost certainly want to set the “secure” flag on any cookies used for authentication. That flag prevents the browser from transmitting cookies over an unencrypted connection.

More and more web applications are offering HTTPS - often as on opt-in setting. Any web site that requires a login should offer HTTPS - and ideally it should be enabled by default.

XSS attacks involve an attacker pushing malicious JavaScript code into a web application. When another user visits a page with that malicious code in it the user’s browser will execute the code. The browser has no way of telling the difference between legitimate and malicious code. Injected code is another mechanism that an attacker can use for session hijacking: by default cookies stored by the browser can be read by JavaScript code. The injected code can read a user’s cookies and transmit those cookies to the attacker. Just like in the MITM scenario, the attacker can use those cookies to disguise herself as the hapless user.

There are other ways that XSS be used can be used to mess with a user - but session hijacking is probably the most dangerous. Session hijacking via XSS can be prevented by setting an “httpOnly” flag on cookies that are used for authentication. The browser will not allow JavaScript code to read or write any cookie that is flagged with “httpOnly”; but those cookies will still be transmitted in request headers.

CSRF attacks authentication indirectly. A malicious web page can trick a browser into making cross-domain requests to another web site. If a user visiting the malicious page is already logged in to that web site then the malicious page can access the site resources as though it were logged in as the unsuspecting user. For example, if a malicious page can trick the browser into making POST requests to a microblogging site it can post updates with spam links that appear to have been written by the victim.

If you use Facebook you might have encountered attacks like this yourself. You see a post on a friend’s wall with a button that says “Don’t click the button!” When you click on it you are taken to another site and the same message ends up posted on your wall.

This works because the browser automatically sends cookies set on a given domain with every request made to that domain, regardless of where those requests originated. The browser has no way of knowing that the requests initiated by the malicious page are made without the user’s knowledge.

The malicious page could create a cross-domain request by including an image with a src attribute pointing to a URL on the site that it is trying to hack into. The URL does not have to be an image - the browser will make a GET request to that URL and will discard the response when it determines that the response is not image data. If that GET request produced any side-effects, like posting a microblogging update, then the malicious page has successfully performed an attack.

To make a cross-domain POST request the malicious site might include a hidden HTML form with an action attribute pointing at the site to be hacked. The malicious page can use JavaScript to submit the form without any interaction from the user. This is another case where the attacker cannot read the response that comes back but can trigger some action in the user’s account.

In some cases CSRF attacks can also be used to read data. Because JSON is a strict subset of JavaScript, HTTP responses that contain JSON data can be loaded into script tags and executed. In some browsers a malicious page can override the Object and Array constructors to capture data from the JSON response as it is executed so that it can be sent to an attacker.

The biggest problem with CSRF is that cookies provide absolutely no defense against this type of attack. If you are using cookie authentication you must also employ additional measures to protect against CSRF. The most basic precaution that you can take is to make sure that your application never performs any side-effects in response to GET requests.

To protect against cross-domain POST requests a commonly used option is to use an anti-forgery token that must be submitted with every POST, PUT, or DELETE request. The token is generally injected into the HTML code for forms in such a way that malicious code on another site does not have any way to access it.

JSON responses can be protected by pre-pending the JSON response with some code that makes the response non-executable. For example, you could place a JavaScript loop at the beginning of the response that never terminates. Or you could put in a statement that throws an exception. Putting the whole JSON response inside of a comment block also works. The only way for a browser to read JSON data that has been obfuscated like this is to fetch the resource using XHR and to remove the extra code before parsing the actual JSON data. XHR is limited by the same-origin policy; so a malicious page cannot make a cross-site XHR request.

Such multi-layered approaches to CSRF defense work but are a pain to implement. I know from experience that the stateful nature of anti-forgery tokens make them a constant source of bugs in Ajax-driven applications where users might submit several requests to the server without ever loading a new page. It is too easy for the client and server to get out of sync and to disagree about which anti-forgery tokens are fresh. And great care must be taken to include the anti-forgery feature in every form and Ajax call in an application or a security hole appears.

JSON obfuscation is easier to apply to every JSON response as a blanket policy thanks to server-side filters and client-side hooks, such as those in jQuery’s Ajax stack. But then you are not really serving JSON - you are serving a JSON-like type with a proprietary wrapper. I find that I spend a lot of time instructing people on the existence of obfuscation, explaining why it is there, and explaining how to set up hooks to remove it on the client side.

By combining the “secure” and “httpOnly” flags and using HTTPS you can make your application authentication proof against MITM attacks and against some XSS attacks. But there is nothing that will make cookie authentication resistant to CSRF attacks. The only way to protect against CSRF is to apply additional security measures. Often multiple measures are required to combat different possible CSRF vectors. And those measures are not always simple or transparent.

In my opinion CSRF stifles innovation on the web. Because cross-domain requests cannot be trusted, even if they appear to be authenticated, web applications have to be thoroughly locked down to reject any cross-origin traffic. There is a relatively new specification for making cross-origin XHR requests called Cross-Origin Resource Sharing (CORS). This specification could allow for exciting new mashups involving rich JavaScript applications and public APIs. Most modern browsers support CORS too - including Internet Explorer 8. But CORS is rarely used because it opens up a big hole that could be exploited by CSRF. Existing CSRF countermeasures rely on limiting XHR requests to the same-origin policy. For most web developers the risk is too great to justify experimenting with new technology.

The way to make the web a safer place is to switch to authentication mechanisms that provide strong protection against CSRF at the most basic level. The key is to choose a mechanism that is controlled by the web application, not the browser. The web browser has no way of distinguishing legitimate requests from forged ones - it will attach cookies to both. On the other hand, application code can be written to be smarter.

There are many authentication schemes that would work well. I lean toward OAuth 2.0. OAuth has some nice advantages: it is standardized; there are numerous server implementations; and the simplest form of the OAuth 2.0 draft specification is pretty easy to implement.

In a traditional OAuth setup there are three parties: the authorization server / resource server, the client and the resource owner. Through a series of steps the resource owner, typically a user working through a web browser, submits a password to the authorization server and the authorization server issues an access token to the client. You can read more about the OAuth protocol flow on the OAuth 2.0 web site.

When applying OAuth to session authentication the picture becomes simpler: the browser acts as both the resource owner and the client; so some of the indirection of three-legged OAuth can be skipped. Instead, a web application can use a protocol flow that the OAuth 2.0 specification calls Resource Owner Password Credentials in which the user enters her password into a login form, the password is submitted to the application server directly, and the server responds to that request with an access token. You can think of this as “two-legged” OAuth.

In both the two- and three-legged flows requests are signed by adding an “Authorization” header with one of two possible formats. In the bearer scheme the authorization header value is just the access token that was given to the client. For example:

GET /resource HTTP/1.1
Host: server.example.com
Authorization: Bearer vF9dft4qmT

The HMAC scheme is a bit more complicated: in that case the client is given an access token id in addition to the token itself and the authorization header includes the token id and an HMAC-signed hash of the request URL, the request method, a nonce, and possibly a nested hash of the request body. The OAuth access token is used as the key in the HMAC algorithm.

POST /request HTTP/1.1
Host: example.com
Content-Type: application/x-www-form-urlencoded
Authorization: MAC id="jd93dh9dh39D",
             nonce="273156:di3hvdf8",
             bodyhash="k9kbtCly0Cly0Ckl3/FEfpS/olDjk6k=",
             mac="W7bdMZbv9UWOTadASIQHagZyirA="

hello=world%21

The advantage of the HMAC scheme is that it can provide some protection against MITM attacks even if signed requests are not encrypted with HTTPS.

I propose a design in which the browser submits credentials from a login form to the server via XHR, gets an access token back, and uses that access token to sign subsequent requests. Full page requests and form posts are difficult to sign with OAuth - hyperlinks and form tags do not provide a way to specify an “Authorization” header. So OAuth-signed requests would probably be limited to XHR. The browser could store the OAuth access token in a persistent client-side store to give the user an experience that is indistinguishable from a cookie-based application - but that is more secure.

It is entirely possible for JavaScript code running in a web browser to sign requests with HMAC. There are pure JavaScript implementations available of many cryptographic functions, including SHA-1 and SHA-256, which are the hash functions that are used for OAuth HMAC signing. However, if your application uses HTTPS to protect every request then the simpler bearer scheme is entirely sufficient.

In this design form posts would be eliminated. Instead form data would be serialized in JavaScript and submitted using Ajax. That way all requests that produce side-effects would be channeled through OAuth-signed XHR. I am not suggesting eliminating form tags though - form tags are an essential tool for semantic markup and for accessibility. I recommend that JavaScript be used to intercept form “submit” events.

There are a couple of options for dealing with full page loads. One possibility is to not require any authentication for requests for HTML pages and to design your application so that HTML responses do not include any protected information. Such an application would serve pages as skeletons, with empty areas that to be filled in with dynamic and protected content after page load using Ajax. The dynamic responses could be HTML fragments that are protected by OAuth, or they could be JSON responses that are rendered as HTML using client-side templates.

Facebook uses a process like this which they call BigPipe. Facebook’s rationale for BigPipe is actually performance, not security. In my opinion the BigPipe approach gives a best-of-both-worlds blend of performance and security. Plus, it lets you put caching headers on full page responses, even in apps with lots of dynamic content.

A downside of BigPipe is that content that is loaded via Ajax generally cannot be indexed by search engines. Google’s recently published specification for making Ajax applications crawlable may provide a solution to that problem. Or you might choose to use the BigPipe approach everywhere in your application except for publicly accessible pieces of content.

Another way to handle full page loads would be to continue using cookie authentication for HTML resources. HTML responses are less vulnerable to CSRF snooping than JSON because HTML is not executable in script tags. In this case you should still require OAuth signing on requests for JSON resources and on any requests that could produce side-effects. But allowing cookie authentication on non-side-effect-producing GET requests for HTML resources should be safe.

Using JavaScript to manage access tokens rather than relying on a built-in browser function makes CSRF attacks impractical. A malicious third-party site can no longer rely on browsers to automatically attach authentication credentials to requests that it triggers. Client-side storage implementations are generally protected by the same origin policy - so only code running in your application can retrieve an access token and produce an authenticated request. And if you combine OAuth with HTTPS then you are also protected against MITM attacks.

A drawback is that you lose the XSS protection that the “httpOnly” cookie flag provides with cookie authentication. An application that uses OAuth will have to use other methods to block XSS. But in my opinion there are better options for dealing with XSS than there are for dealing with CSRF. By consistently sanitizing user-generated content you can effectively block XSS at the presentation layer of your application. That would be necessary anyway, since “httpOnly” only prevents XSS-based privilege escalation attacks and by itself does not prevent other XSS shenanigans.

To track a session using OAuth applications will need some way to store access tokens for the duration of a user’s session. There are various ways to do that:

In the simplest case you can store the token in memory by assigning it to a JavaScript variable. This might be useful in a single page application. The user will have to log in again if she goes to another page or opens your app in a new window.
localStorage can be used to store a token so that is persistent even if the user closes and re-opens the browser. Data stored in localStorage is available to all windows on the same domain. You will probably want to include a hook to clear local storage when the user logs out of your application.
sessionStorage works like localStorage, except that data is only accessible from the same window that stored it and the whole store for a given window is wiped when the user closes that window. So the user does not have to log in again if she goes to another page; but she does have to log in again if she opens your app in a new window.

sessionStorage can be a more secure option than localStorage - especially on a shared or a public computer. If you decide to use a storage option that does not expire automatically when the browser is closed I suggest including a “remember me” checkbox in your login form and using sessionStorage instead when the user does not check that box.
Although I have been arguing that cookies are not the best option for authentication, storing an access token in a cookie works just fine. The key is that the server should not consider the cookie to be sufficient for authentication. Instead it should require that the access token be copied from the cookie value into an OAuth header.

For the cookie option to be secure you should set the “secure” flag so that it is not transmitted over a connection that could be read via a MITM attack. You should not set the “httpOnly” flag because the cookie needs to be accessible from JavaScript.

A nice advantage of the cookie option is that users have been trained that they can delete cookies to reset a session. On the other hand, most users do not know about localStorage and most browsers do not provide an obvious way to clear localStorage. So the cookie option is likely to conform best to user expectations. Cookies can also be configured to expire when the browser is closed or to persist for a long period of time.
Other options include IndexedDB, which is a more sophisticated store that is similar to localStorage, Flash cookies, and userData in IE.

There is a good summary of client-side storage implementations and how to use them on Dive Into HTML5. Or if you want a pre-built solution that avoids most cross-browser headaches you can use PersistJS or a similar tool.

Web applications that rely on cookie authentication can often be designed to degrade gracefully, so that if JavaScript is disabled or is not available the application will still work. With OAuth that is not possible. I can imagine this being a major objection to ditching cookie authentication. Some people prefer to disable JavaScript for security or for privacy reasons. Many of the more basic mobile and text-only web browsers do not support JavaScript. And in the past screen readers have not handled JavaScript-driven web apps well.

In my opinion the requirement that JavaScript be enabled to use an application is generally worthwhile. Mobile browsers that do support JavaScript are rapidly pushing out those that do not. Text-only browsers will have to start supporting JavaScript sooner or later to keep up. The people who designed your web browser took great care to ensure that your security and privacy are protected even when JavaScript is enabled. Screen readers are much better than they used to be at making JavaScript-driven web sites accessible.

You should consider your target audience, your application requirements, and your security needs and decide for yourself whether dropping the noscript option is the right choice for your application.

No security protocol is bulletproof. Do lots of research and use common sense whenever you are working on an application that needs to be secure.

Image credits:

The OAuth logo by Chris Messina is licensed under the Creative Commons Attribution-Share Alike 3.0 Unported license.

Other images used in diagrams are from the Open Clip Art Library and are in the public domain.

tags: osb11

How Mobile Safari emulates mouse events

2011-07-28T00:00:00-07:00

When you are adapting web apps to touchscreen devices particular challenges come up around events like mouseover and mouseout. Touchscreen devices like the iPad do not have a cursor, so the user cannot exactly move the mouse over an HTML element. However, Mobile Safari, the web browser that comes with the iPhone and iPad, has a fallback for websites that require hovering or cursor movement.

Usually when you tap on an element on a link or other clickable element Mobile Safari translates that into a regular click event. The browser also produces some touch events that do not exist in a lot of browsers. But from the perspective of a web page that was not designed with a touchscreen in mind, what you get is a plain click. More specifically, the browser fires mousedown, mouseup, and click in that order. But if a clickable element also does something on mouseover then tapping on that element will trigger a mouseover event instead of a click. Tapping on the same element again will produce a click event. A random example of a page that exhibits this behavior is the schedule page from the Open Source Bridge website. Try tapping on session titles and see what happens.

Mobile Safari will only produce mouse events when the user taps on a clickable element, like a link. You can make an element clickable by adding an onClick event handler to it, even if that handler does nothing. On tap Mobile Safari fires the events mouseover, mousemove, mousedown, mouseup, and click in that order - with some caveats which are explained below. Those events all fire together after the user lifts her finger. You might expect the mousedown event to fire as soon as the user presses her finger to the screen - but it does not. When the user taps on another clickable element the browser fires a mouseout event on the first element in addition to firing the aforementioned events on the new element.

So how do we get to the behavior where one tap emulates mouseover and a second tap emulates click? It turns out that after any mouseover event handlers run Safari checks the DOM for changes and if the content has changed it skips the mousedown, mouseup, and click events. So these events do not fire. When the user taps on the same element again the mouseover event does not fire again, so the browser goes ahead with the other events.

The mousemove event behaves in a similar way: if the DOM has changed after any mousemove handlers are finished running then Mobile Safari skips the remaining events.

Diagram from Apple's documentation demonstrating how the browser determines which mouse events to fire.

Safari does not accept just any change to a DOM element as a “content change” though. Through testing I discovered that adding a regular element to the DOM or showing a previously hidden element in a mouseover handler would prevent the click event from firing. But removing an element, hiding an element, or changing the content of a text node do not prevent the click event. I also tried adding class names to elements - which Safari also did not treat as a “content change”. As far as I can tell only adding or showing an element will cause the mousedown, mouseup, and click events to be skipped.

I created some fiddles on jsfiddle.net to test Mobile Safari behavior. For your investigative pleasure I have an example of a mouseover handler that adds elements to the DOM, another that shows a hidden element, and a third that makes no changes to the DOM at all.

CouchDB Notes

2009-09-13T00:00:00-07:00

Recently I gave a talk at Portland Ruby Brigade meeting on CouchDB, a document-oriented database. I thought I would share my notes from that talk. In some respects this was a followup to an earlier talk that Igal Koshevoy gave comparing various post-relational databases. Igal also wrote some additional notes on my talk.

In summary, some of the distinguishing features of CouchDB are:

Schema-less data store stores documents containing arbitrary JSON data.
Incrementally updated map-reduce views provide fast access to data, support powerful data processing, and eliminate lookup penalties for data in large or deeply nested documents.
Map-reduce views - which are again, incrementally updated - provide fast access to aggregate data, such as sums or averages of document attributes.
Schema-less design means no schema migrations are ever required. And new map-reduce views can be installed with no downtime.
“Crash-only” design protects data integrity in almost every crash scenario. No recovery process is required when rebooting a crashed database server.
Lock-free design means that read requests never have to wait for other read or write requests to finish. Writes are only serialized at the point where data is actually written to the disk.
Integrated, robust master-master replication with automatic conflict handling
MVCC, or “optimistic locking”, prevents data loss from multiple writes to the same document from different sources.
RESTful interface makes it easy to integrate CouchDB with any environment that speaks HTTP.
Documents can contain binary attachments. Attachment support combined with the HTTP interface means that CouchDB can serve HTML, JavaScript, images, and anything else required to host a web application directly from the database.

More detailed information on all of the above points can be found in CouchDB’s technical overview.

Some of the downsides:

Writes and single-document lookups are slower than other databases due to HTTP overhead and frequent disk access.
CouchDB optimizes CPU and RAM use by using lots of disk space. The same data set will take up a lot more space in CouchDB than in other database systems.
You must create map-reduce views in advance for any queries you want to run. SQL users are used to processing data at query time; but this is not allowed by the CouchDB design (assuming you are not using temporary views in production, which you should not do.)
There is a serious learning curve when learning to think in terms of map-reduce views.
Map-reduce views, though very powerful, are not as flexible as SQL queries. There may be cases where it is necessary to push data processing to an asynchronous job or to the client.
CouchDB is a young project and its API is undergoing rapid changes.
Documentation can be sparse - especially when very new features are involved.

Ruby Interfaces to CouchDB

I also talked about some of the high-level interfaces to CouchDB that are available for Ruby. As ActiveRecord did for SQL, the idea behind these libraries is to abstract away as much of the database behavior as possible without sacrificing the powerful features that CouchDB provides. The term “ORM” does not quite apply to CouchDB because it is not relational. The term I am using for the time being is “object-document mapping”. The code examples I showed are all available in a gist.

Sadly I don’t think I can say that any of these libraries are production ready as is. If you use one expect to write some patches as you go. That said I think that all three show some exciting potential. And they all provide a better starting point for your CouchDB project than writing your own ODM or using a low-level interface. I plan to submit a few patches to CouchPotato as I get to know it better. With some more help I imagine we can turn one or more of these interfaces into a nicely polished library.

The winner in my mind is CouchPotato. The philosophy behind CouchPotato is to do things differently than ActiveRecord does. Though it does borrow features from ActiveRecord, for example dirty attribute tracking, life cycle callbacks, and validations. The biggest innovation in CouchPotato in my opinion is the extensible system for defining views. As with the other libraries, support for declaring simple views is built in:

class User
    include CouchPotato::Persistence
    property :name
    view :by_name, :key => :name
end

But similar shortcuts for more sophisticated types of views can be added by creating new view classes and passing a :type option to the view declaration method. For example, it might be possible to declare views like this:

class Invoice
    ...
    property :ordered_at, :type => Time
    property :items
    view(:total_sales, :type => :aggregate, :key => :ordered_at,
         :sum => 'items[].qty * items[].price_per_unit')
    view(:average_sale, :type => :aggregate, :key => :ordered_at,
         :average => 'items[].qty * items[].price_per_unit')
end

My runner-up is CouchRest. CouchRest is a widely used low-level interface to CouchDB. But it also includes a high-level interface called CouchRest::ExtendedDocument. A neat feature of this library is that you can declare a different database to use for each model. It also supports declaring simple views with dynamic methods for querying those views:

class Comment < CouchRest::ExtendedDocument
    property :post_id
    view_by :post_id
end

Comment.by_post_id :key => 'foo'

CouchFoo is another strong contender. The goal of CouchFoo is to provide an API that is as close to ActiveRecord’s as possible. The project may even be porting a large amount of ActiveRecord code for this purpose. The intention is to make migrating to CouchDB as painless as possible.

An interesting feature is that CouchFoo will create views automatically on demand. For example this query will automatically create a view that indexes Post documents by title:

post = Post.find(:first, :conditions => { :title => "First Post" })

On-demand view creation could be convenient. But my instinct is that it is a bad thing to do. Adding a new view to a large database comes with an expensive initial build step. It seems to me that that type of thing should only be done explicitly.

Testimonials

I mentioned a case where one team found that they got great performance improvements by pushing some data reporting tasks from a SQL database to CouchDB. That story was written up in a series of blog posts. An explanation of why this team went with CouchDB is presented in part 3 of that series.

There is a list on the CouchDB Wiki of sites that are currently using CouchDB in production. A couple of notable examples not on the list that have used CouchDB are the BBC and possibly Meebo.

Of note for Ubuntu fans: Canonical is working on a project called Desktop Couch which will be installed by default in Karmic Koala. The idea is to create a portable store for stuff like browser bookmarks, contacts, music playlists and ratings, and so on. There are already plugins to allow Firefox and Evolution to store bookmarks and contact data in CouchDB. Desktop Couch will provide CouchDB databases for every user to store this information, and will include tools for “pairing” computers on the same network. Desktop Couch will use CouchDB’s built-in replication features to automatically replicate data between paired computers; so you will get the same bookmarks and contacts on all of your computers. This will all integrate with Ubuntu One too. Desktop Couch will be able to replicate your data to Ubuntu One’s servers so that you can replicate that data back down to computers on a different network.

Exploring Further

The best resource for learning more about CouchDB is probably CouchDB: The Definitive Guide. This is a book that J. Chris Anderson, Jan Lehnardt, and Noah Slater are writing for O’Reilly. It is still a work in progress, but the latest draft is available online.

For API reference my source is the CouchDB Wiki.

Finally, as the CouchDB developers will tell you, the most up-to-date reference for the latest CouchDB features is the included test suite. This is a set of tests written in JavaScript that you can run from CouchDB’s web interface to verify that your build of the latest SVN checkout is working correctly. These tests are run externally and access the database server via its HTTP API; so you don’t have to know any nitty gritty Erlang stuff to understand what the tests are doing. When any changes to the API are introduced this test suite is updated accordingly.

How to install Haskell "Batteries Included" Platform on Ubuntu Jaunty

2009-07-02T00:00:00-07:00

Just for kicks I thought I would take another shot at some Haskell programming. To get all of the common libraries and the automated package installer, cabal, I set up the Haskell Platform. Here is how I did it.

Ubuntu Jaunty includes a package for the Haskell compiler, ghc, at version 6.8. The Haskell Platform installer will roll its eyes at you if you try to proceed with this version of ghc. So the first step is to install ghc 6.10.

Paste these lines into /etc/apt/sources.list.d/haskell.list:

deb http://ppa.launchpad.net/someone561/ppa/ubuntu jaunty main
deb-src http://ppa.launchpad.net/someone561/ppa/ubuntu jaunty main

To get the key to verify packages from that PPA, run this optional command:

sudo apt-key adv --keyserver keyserver.ubuntu.com --recv-keys E51D9310

Then update your package list and install Haskell:

sudo apt-get update
sudo apt-get install ghc6 ghc6-prof ghc6-doc haddock

The Haskell Platform website does not list a package for Ubuntu yet. So download the source installer.

Before you run the installer you will want to install the necessary build dependencies:

sudo apt-get install libglut-dev happy alex libedit-dev zlib1g-dev

Please leave a comment if you discover that I have left out any dependencies.

To perform the final installation step you will also need to have checkinstall installed:

sudo apt-get install checkinstall

Unpack the source installer wherever you like:

tar -xzf haskell-platform-2009.2.0.1.tar.gz

Finally cd into the installer directory and run the generic installation procedure:

./configure
make
sudo checkinstall -y

This will build and install a deb package called haskell-platform. If you ever want to remove Haskell Platform just uninstall that package.

If all of the above worked, you should be good to go. You compile Haskell code with ghc. You can run an interactive read-eval-print-loop with ghci. And you can install Haskell libraries with cabal.

Updated 2009-07-23: Added zlib1g-dev to list of build dependencies. Thanks Jack Siler and Fernand.
Updated 2009-08-01: Added step for installing checkinstall. Thanks Paulo.

Database Queries the CouchDB Way

2009-06-30T00:00:00-07:00

CouchDB is a document-oriented database. It has no rows or tables. Instead CouchDB is a collection of JSON documents. It uses a map-reduce pattern to index data. Queries in CouchDB pull data from what are essentially stored procedures called views. A view is made up of a map function and optionally a reduce function. Ninety percent of the time all you need is the map function, so I will focus on map-only views here.

A map function is a JavaScript function that takes a single document as an argument and emits any number of key/value pairs. Both the key and the value can be any JSON value you choose. The map function is run on every document in the database individually and the emitted key/value pairs are used to construct an index of your data.

A Simple Example

Imagine you have a database with user records and you want a view of those records using the last name of each user as keys.

function(doc) {
    if (doc.last_name) {
        emit(doc.last_name, doc);
    }
}

The above map function will produce and index something like the one below. Because doc is used as a value for each entry the entire content of each JSON document will be accessible as the indexed values.

[
  ...
  { key: "Clarke", value: { last_name: "Clarke", ... } },
  { key: "Kelly",  value: { last_name: "Kelly",  ... } },
  { key: "Smith",  value: { last_name: "Smith",  ... } },
  ...
]

Notice that the map function checks each document for a last_name attribute before emitting a key/value pair. There may be documents in the database that are not user records. By performing that check the view excludes any non-user-record documents from the resulting index.

If you include the couch.js library in a web page you can create client-side queries to pull data from CouchDB over HTTP. The function below will fetch all of the user records from your database by returning the value of each key/value pair emitted by the view above.

function users(db) {
    return db.view('users/last_names').rows.map(dot('value'));
}

// Run the query and output data to the console.
var db = new CouchDB('database-with-users');
console.log(users(db));

Map functions operate on one document at a time and cannot access data from other documents. The advantage of this is that the functions can process data in any order and can run on any piece of a data set independent of the rest of the set. CouchDB builds static indexes from the output of view map functions so that queries against those views will run quickly. When any documents change CouchDB can incrementally rebuild the indexes for just those documents without having to rebuild entire indexes from scratch.

The CouchDB design gets you great performance on large data sets. But it means that you cannot pass dynamic parameters to your map function when you run a query. You cannot ask for it to emit only user records with a given last name unless you want to maintain a special view for that particular last name. In most cases it is not practical to build separate views for every query that you might want to run someday. So what you can do is to run a query against the general purpose view above and request only key/value pairs that match a particular key.

function find_users_by_last_name(db, last_name) {
    var matches;
    matches = db.view('users/last_names', { key: last_name });
    return matches.rows.map(dot('value'));
}

This client code creates a query that requests data from the last_names view with a key parameter. CouchDB will only send back key/value pairs with keys that match the key parameter. In this case the query will return all user records with last names matching the last_name argument.

In a more advanced case you may want to take the first few letters of a last name and look up user records that match.

function find_users_whose_last_names_start_with(db, query) {
    var matches;
    matches = db.view('users/last_names',
                      { startkey: query,
                        endkey:   query + "\u9999" });
    return matches.rows.map(dot('value'));
}

Data returned by a query is always sorted by key. In the case where the keys are strings the sorting will be lexicographic. The startkey and endkey parameters restrict the results of the query to key/value pairs that fall in the given range according to CouchDB’s sort order.

When the above function is given the query string “Ha”, it will fetch documents with keys sorted after “Ha” lexicographically, e.g. “Hallett”, “Hathaway”, and “Hazzold”. The endkey is created by appending “\u9999” to the startkey. “\u9999” is a unicode character that comes after most other characters in lexicographic order and that is unlikely to appear in a data set. Effectively the string “Ha\u9999” sorts after every other string that begins with “Ha”, but before any string that starts with “Hb”.

Note that CouchDB uses the Unicode Collation Algorithm to sort strings. Sorting comes out differently than you may be used to if your are accustomed to the ASCII way. UCA collation is intended to mimic the order of strings you would see in a dictionary. For example, two strings that differ only in case will appear together in sorted order. The lower-case string will appear immediately before the upper-case string. So if you force your startkey to lower-case and your endkey to upper-case you will get case-insensitive matches. See the CouchDB wiki for more details.

Search by Keyword

Indexing text content can be a hard problem because you need a large index if you want to query data by arbitrary keywords or substrings. Fortunately CouchDB excels at managing large indexes.

Here is a map function that creates an index of all the words that appear in the text field of every document in a database.

function(doc) {
    var tokens;
    if (doc.text) {
        tokens = doc.text.split(/[^A-Z0-9\-_]+/i).uniq();
        tokens.map(function(token) {
            emit(token, doc);
        });
    }
}

The code splits text on word boundaries stripping out non-alphanumeric characters. It runs the resulting list of tokens through a unique filter so that only one index key is produced for each word in the text of a single document.

This is an example of a view that emits more than one key/value pair for each document. The values in each pair are the same for the same document. But a different key is recorded for each word in the document’s text attribute. The index that would be created by this view for a document with the text “Live long and prosper” is below.

[
  { key: "and",     value: { text: "Live long and prosper." } },
  { key: "Live",    value: { text: "Live long and prosper." } },
  { key: "long",    value: { text: "Live long and prosper." } },
  { key: "prosper", value: { text: "Live long and prosper." } }
]

To look up documents that contain a given keyword you just need to create a query with that keyword as the key parameter. But what if you want to look for documents that contain a list of keywords? You could create index keys for every combination of words in each document. But that index would grow exponentially and might get to be unreasonably large. A better way might be to pick one keyword to perform your query and then to use client code to select the documents that match all of the keywords out of the results returned by CouchDB.

function find_documents_by_keywords(db, keywords) {
    var possible_matches;

    // Query documents that include the first keyword.
    possible_matches = db.view('documents/keywords', 
                               { key: keywords[0] });

    // Pull the value attribute out of each returned key/value
    // pair.
    possible_matches = possible_matches.rows.map(dot('value'));

    // Pick out the documents that include all of the given
    // keywords.
    return possible_matches.select(function(m) {
        return keywords.reduce(true, function(match, keyword) {
            return m.text.match(keyword) && match;
        });
    });
}

When you want more dynamic data processing than you can get with pure-CouchDB views, some client-side processing can make up the difference nicely. From a perspective of deploying applications leveraging your users’ CPU cycles for data processing can really help getting your application to scale.

There is another approach to full text search documented on the CouchDB wiki.

Search by Substring

Maybe keyword search isn’t good enough. Maybe you need to be able to search for occurrences of any substring in a data set.

function(doc) {
    var i;
    if (doc.text) {
        for (i = 0; i < doc.text.length; i += 1) {
            emit(doc.text.slice(i), doc);
        }
    }
}

For each document, this map function emits a key/value pair for every possible substring that runs to the end of the document’s text. The idea is that the beginning of any substring in the data set can be lined up with the beginning of one of these keys. Here is an example of the index created for a document with the text “Hello, world!”:

[
  { key: " world!",       value: { text: "Hello, world!" } },
  { key: ", world!",      value: { text: "Hello, world!" } },
  { key: "!",             value: { text: "Hello, world!" } },
  { key: "d!",            value: { text: "Hello, world!" } },
  { key: "ello, world!",  value: { text: "Hello, world!" } },
  { key: "Hello, world!", value: { text: "Hello, world!" } },
  { key: "ld!",           value: { text: "Hello, world!" } },
  { key: "llo, world!",   value: { text: "Hello, world!" } },
  { key: "lo, world!",    value: { text: "Hello, world!" } },
  { key: "o, world!",     value: { text: "Hello, world!" } },
  { key: "orld!",         value: { text: "Hello, world!" } },
  { key: "rld!",          value: { text: "Hello, world!" } },
  { key: "world!",        value: { text: "Hello, world!" } }
]

The substring that you want to search for can begin at any character within some document’s text. It may or may not run until the end of that document’s text field. We have an index with the beginning characters for every possible substring. So we can create a query that asks for a key range that encompasses both the given substring and a substring that runs all the way to the end of the document text.

function find_all_by_substring(db, str) {
    return db.view('documents/substrings',
                   { startkey: str,
                     endkey: str + "\u9999" }
                  ).rows.map(dot('value'));
}

CouchDB does not just sort data when responding to queries. In its internal representation indexes are always sorted by key. So a query with a key range targets a contiguous block of data from the database. Because of that CouchDB can serve up a key range very efficiently.

Just as with the keyword search, if you want to search for documents that match a list of substrings then get the matches for one of the substrings from CouchDB and use client code to select results that contain all of the rest of the given substrings.

function find_all_by_substrings(db, strs) {
    var matches;
    matches = db.view('documents/substrings',
                      { startkey: strs[0],
                        endkey: strs[0] + "\u9999" });
    return matches.rows.map(dot('value')).select(function(d) {
        return strs.reduce(function(r, s) {
            return d.text.match(s) && r;
        });
    });
}

If the text of your documents tends to be very long you can avoid a lot of really long keys by limiting the lengths of substring keys in your view. In that case make sure to truncate the key parameters in your queries so that they are not longer than the index keys.

Updated 2009-07-05: Updated examples to demonstrate that CouchDB stores indexes sorted by key. Thanks to J. Chris Anderson for pointing that out.
Updated 2009-08-06: Added link to full text search implementation on CouchDB wiki.
Updated 2009-08-09: Fixed a typo.

Appendix: Helper Function Definitions

Some of the functions that I used in the examples above are not built into JavaScript or couch.js. Here are definitions of those functions for reference.

Given an attribute name, dot returns a function that when given an object returns the value of the specified attribute. This function is used in examples above to get the value attributes of rows fetched by CouchDB queries.

function dot(attr) {
    return function(obj) {
        return obj[attr];
    }
}

map is an Array method that given a function that takes a single argument returns a new array formed by applying the given function to every element of the original array in turn.

Array.prototype.map = function(func) {
    var i, r = [],
    for (i = 0; i < this.length; i += 1) {
        r[i] = func(this[i]);
    }
    return r;
};

reduce is an Array method that given an initial value and a function that takes two arguments returns a single value produced by applying the given function to every element of the array in turn with the value from the previous function invocation and returning the last result.

Array.prototype.reduce = function(val, func) {
    var i;
    for (i = 0; i < this.length; i += 1) {
        val = func(val, this[i]);
    }
    return val;
}

select is an Array method that given a test function returns a new array made up of only elements in the original array that pass the test.

Array.prototype.select = function(test) {
    return this.reduce([], function(r, e) {
        if (test(e)) {
            return r.concat([e]);
        } else {
            return r;
        }
    });
};

uniq is an Array method that returns a new array with any duplicate values from the original array removed.

Array.prototype.uniq = function() {
    return this.reduce([], function(list, e) {
        if (list.indexOf(e) < 0) {
            return list.concat([e]);
        } else {
            return list;
        }
    });
}

How to use RSpec to describe a Sinatra application

2008-07-29T00:00:00-07:00

This information was written a long time ago and has become pretty outdated.

Sinatra is a fun little web application microframework. Recently I started working on an application using Sinatra - and since I am working on good programming habits, before I dove into any coding I sat down to work out how to write specs for a Sinatra application.

Sinatra comes bundled with support for test/spec: a spec framework that builds on top of Rail’s own Test::Unit to provide support for writing specs. Which is a really neat idea. But I have been using RSpec for my other work, and I wanted to continue doing so.

It turns out that RSpec takes a little bit of manual work to get going with Sinatra. I read a helpful article on gittr.com that pointed me in the right direction. The article advised me to add these lines to my spec files:

require File.expand_path(File.dirname(__FILE__) + '/your_application')
require 'spec'
require 'spec/interop/test'
require 'sinatra/test/unit'

The first line loads your application; the second line loads RSpec; the third loads an RSpec-Test::Unit compatibility layer; and the fourth loads Sinatra’s test helpers, which are written for Test::Unit.

Contrary to Sinatra’s instructions for writing tests, you want to avoid loading ‘sinatra/test/spec’, which defines Sinatra’s helper methods for test/spec, because that would load test/spec itself which conflicts with RSpec.

Those instructions mostly worked. I could write and run specs. But I had trouble with matchers. For example, this example:

it "should not have a cookie"
  instance.cookie.should be_nil
end

Would give an error message like this:

undefined method `be_nil' for nil:NilClass

Which I’m sure you can imagine is pretty annoying.

It was easy enough to identify ‘sinatra/test/unit’ as the root of the problem. When I removed that line RSpec’s matchers worked fine; but then I didn’t get Sinatra’s test helpers, which make spec-writing much easier. So that wasn’t a great solution either.

Examining Sinatra’s code, I found that all ‘sinatra/test/unit’ does is to load ‘sinatra/test/methods’ - the actual helper methods - and mixes them into Test::Unit::TestCase. So I bypassed ‘sinatra/test/unit’ by copying and adapting some code from it to make the top of my spec file look like this:

require File.expand_path(File.dirname(__FILE__) + '/your_application')
require 'spec'
require 'spec/interop/test'
require 'sinatra/test/methods'

include Sinatra::Test::Methods

Sinatra::Application.default_options.merge!(
  :env => :test,
  :run => false,
  :raise_errors => true,
  :logging => false
)

Sinatra.application.options = nil

Since that is a fair amount of setup, I moved all of it into a separate file called spec_helper.rb, which I loaded into my actual spec files. Because I am weird enough to write a Sinatra application that is split into multiple files and multiple spec files.

Anyway, now my specs run just as they should, with Sinatra’s helpers and everything:

it "should deliver a cookie" do
  get_it '/cookie'
  @response.should be_ok
  @response.headers['Content-Type'].should == 'application/x-baked-goods'
  @response.body.should_not be_empty
end

The next challenge was to write specs for Sinatra helpers. Although Sinatra actions and helpers generally appear in the outermost namespace, the DSL methods that define them actually bind the helpers to Sinatra::EventContext. You can’t invoke helper methods directly from an example context; you have to create an instance of Sinatra::EventContext and send the method call to that - much the same way Rails instantiates a subclass of ActionController::Base to handle a controller action. Here is the code you will want in your example groups:

before :all do
  request = mock("request")
  response = mock("response", :body= => nil)
  route_params = mock("route_params")
  @event_context = Sinatra::EventContext.new(request, response, route_params)
end

A body= method has to be defined on the response mock to prevent an error. But it doesn’t have to actually do anything. With that setup code in place, you can do this:

it "should use a helper to make cookies" do
  @event_context.bake_a_cookie.should be_an_instance_of(Cookie)
end

and write something like this in your application:

helper do
  def bake_a_cookie
    Cookie.new(:kind => :chocolate_chip)
  end
end

And now you have a reasonably complete speccing setup. There are still a couple of issues though. For one thing, the spec helpers are missing a much needed assigns[] method. As it stands there is no good way to pry apart the behavior of an action if there is no convenient method call to stub. You can only define the parameters that are passed to it, and read response. On the upside, this does help to enforce good behavior-driven development.

The other issue is more of an annoyance than a serious problem. It seems that somewhere in all of this there are one or two method_missing definitions that bounce calls back and forth. If call a method that is not defined, you generally won’t get an “undefined method” error, you will get a “stack level too deep” error instead. This is particularly unhelpful because it does not tell you what class received the undefined method, or which method is undefined. So a little extra manual stack tracing is required when this happens.

Update 10/11/08: The Sinatra application that led to this article is now open source and is available at http://github.com/hallettj/restful_captcha. If you want to see the RSpec techniques that I used in context, check out the code there.

Updated 2009-08-09: This article is pretty outdated. Added a note to that effect.

International Phonetic Alphabet

2007-10-02T00:00:00-07:00

In last week’s post I provided phonetic transcriptions of some example words using the International Phonetic Alphabet, or IPA for short. I thought it would be helpful to follow that up with some information about what the IPA is, and how to read it. And as a bonus, after learning about IPA transcription you will be able to better read pronunciation guides on Wikipedia.

You have probably seen many phonetic transcriptions before - especially as pronunciation guides in dictionaries. In dictionaries it is common to see a transcription convention that uses English spelling conventions to represent sounds. For example, the word “elucidate” might be transcribed as (ee-LOO-suh-date). That system is handy because it is immediately familiar to anyone who has experience reading stuff in English. But it has drawbacks too. There are a few main problems that are especially important for linguists; there are lots of linguists all over the world who are used to languages with entirely different spelling conventions. For example, the sound in English that is represented as “y” - the consonant, not the vowel - is written in Icelandic as “j”. There are also a lot of languages with sounds that just don’t exist in English. Linguists need to be able to transcribe those sounds; but since they don’t exist in English there is no spelling convention to represent them. In fact there is no one language with enough spelling conventions to represent every sound in every language in the world. And finally, English spelling is ambiguous, as is the spelling of almost any language. That is already demonstrated by the need to add a note to distinguish “y” the consonant from “y” the vowel or any of the other vowel sounds represented by “y”.

To solve all these problems, a group of linguistics developed the International Phonetic Alphabet in the late nineteenth century. The first standardized version was created in 1888. But it has been revised somewhat since then. The purpose of IPA is to provide a standard set of symbols that are used to represent sounds so that the same symbols always represent the sounds, even to people from different language backgrounds. Using the IPA it is theoretically possible to represent every sound in every language in the world. Though occasionally a new language is discovered with a new sound that we didn’t know anything about before, which has to be quickly added to the IPA.

IPA was originally developed by French and British linguists, so it uses characters derived from the Latin alphabet and symbols are matched to sounds in a ways that are generally familiar to Europeans. But even in the Western world people have different ideas about how to spell things, so the IPA adopts some different phonetic conventions from different languages. For example, I mentioned earlier that the sound represented by “y” in English is spelled “j” in, among others languages, Icelandic; and in fact the symbol for that sound in IPA is [j]. Here is the complete IPA chart in its most recent revision. And by the way: in IPA, the word “elucidate” is transcribed [i’lu.sə.deɪt].

The sound an IPA symbol represents is described by the place of articulation of the sound, an the manner of articulation. When you voice a consonant you, you press your tongue against the roof of your mouth, or in some cases you press your lips together or put the tip of your tongue between your teeth. The exact spot on where you press your tongue is the place of articulation. For example, when you say [t] you press the tip of your tongue against a spot towards the front of your mouth called the alveolar ridge; whereas when you say [k] you press the back of your tongue against your soft palate, which linguists call the velum. [t] and [k] have the same manner of articulation - they are both plosives, which means that they are articulated by completely stopping air from flowing out of the mouth for a moment. But they have different places of articulation. Early on in a linguist’s career he learns all about the structures of the mouth, throat, and nose to learn how each can be used to produce various sounds. I will explain some of the details in future articles; in the meantime it would probably be easiest to look up IPA symbols using this IPA chart on Wikipedia, which is specially designed for English speakers and provides example words to illustrate each sound.

Wikipedia provides the transcription for the English “r” as [ɹ]. This is the most technically correct transcription, since in IPA [r] represents a rolled “r”, which is heard in Spanish. In linguistics speak, [r] is a trill and [ɹ] is a liquid. However, English doesn’t have a trill, so people transcribing English often use [r] instead of [ɹ] because the former is more familiar - and easier to type. It is considered acceptable to make substitutions like that in cases where readers are unlikely to be confused by the switch. So when I transcribe an English word using [r] instead of [ɹ] I’m not actually trying to make you practice pronouncing trills.

As an aside, the rolled “r” in French is not the same sound as the rolled “r” in Spanish. The French “r” is transcribed [ʀ]. Both sounds are trills, so they share the same manner of articulation; but they have different places of articulation. [ɹ] is alveolar, meaning that to pronounce it the tip of the tongue is positioned on the alveolar ridge, in the same spot it is placed when pronouncing [t]. The sound is produced by vibrating the tongue against the roof of the mouth, which is what makes it a trill. To pronounce [ʀ], the back of the tongue is placed against the uvula and vibrates against that.

To make the alphabet more flexible, IPA employs a number of diacritics. Diacritics are small marks placed above or below a character. In IPA they are used to describe characteristics of a sound that differ slightly from the sound usually represented by a bare character. Last week I talked about consonants that are used as syllable nuclei, which are called syllabic consonants. Syllabicity is considered a phonological feature, so it is indicated with a diacritic. For example, the syllabic version of [n] is [n̩].

Another example of a diacritic is ʰ, which is used to indicate aspiration. Did you know that the letter “p” in English is used to represent two different sounds? The “p” sounds in “pull” and “stop” are slightly different. You can tell if you put your hand in front of your mouth, less than an inch away, and say each word. You will feel a puff of air on your hand when you say the “p” in “pull”; there is a puff when you say “stop” too, but it is not nearly as strong. A sound that makes that strong puff of air is said to be aspirated, and is marked with a diacritic that looks like a superscripted “h”. So the IPA representation for an aspirated “p” is /pʰ/ and an unaspirated “p” is simply /p/.

Even though they are technically different sounds, English speakers treat /p/ and /pʰ/ as being the same. So they are written with the same letter. And in IPA they are usually both transcribed as [p] for simplicity. But on occasion it is important to have the ability to distinguish the two. The difference between sounds that are exactly the same and sounds that are treated as the same by language speakers is a very important consideration in linguistics - and it has to do with the sudden switch from square brackets to slashes surrounding the transcriptions above. I will talk about that in a future article too.

Anatomy of a Syllable

2007-09-24T00:00:00-07:00

The syllable is a constant feature in every spoken language in the world. Each language has its own rules about what kinds of syllables are allowed, and what kinds aren’t - but the general structure is the same everywhere.

A syllable has as many as three parts: onset, nucleus, and coda. The onset and the coda are consonants, or consonant clusters, that appear at the beginning and the end of the syllable respectively. The nucleus forms the the core of the syllable; it is most often a vowel, or a combination of vowels - but there are many exceptions to that. If you examine enough languages you can find almost every kind phone used as a syllable nucleus. In the word “far”, [f] is the syllable onset, [a] is the nucleus, and [r] the coda. If a coda is present in a syllable, the nucleus and the coda form a single unit called a rhyme; otherwise the nucleus makes up the rhyme by itself. Looking at “far” again, [ar] forms the rhyme. A syllable does not necessarily have to have an onset or a coda - depending on the language - but a nucleus is always present.

Even in English, syllable nuclei are not restricted to vowels. For example, in the monosyllabic word, “hmm”, the syllable nucleus is [ṃ], which is a consonant but is more specifically a nasal. Another nasal, [n], can be seen as a syllable nucleus in the word “isn’t”, which is transcribed into the International Phonetic Alphabet (IPA) as [ɪzzṇt]. In this case there are two syllables, and [ṇ] forms the nucleus of the second syllable.

The small dot underneath the characters ṇ and ṃ indicates that the sound represented is a syllabic consonant, which is any consonant that forms a syllable nucleus. Vowels are not marked with the same diacritic because they are always considered to be syllabic. Usually syllabicity is marked in IPA with a vertical stroke under the character instead of a dot; but in this case a dot was as close as I could get.

Anyone following closely may notice that it is difficult to decide exactly how to divide “isn’t” into syllables. It seems like it should be either [‘ɪz.ṇt], or [‘ɪ.zṇt], where the dot (.) represents a syllable boundary and the apostrophe (‘) represents the beginning of a stressed syllable; but it is tricky to figure out whether the [z] is the coda of the first syllable or the onset of the second syllable. That is because in the [z] in “isn’t” demonstrates ambisyllabicity, a common feature in English that I will write about in a future article. The short explanation is that [z] is both an onset and a coda, which is why I transcribed the word with two [z]’s. Anyway, in both analyses [ṇ] forms the nucleus of the second syllable, so we don’t need to worry about the placement of [z] for now.

There are also arguably cases where a liquid forms the nucleus of a syllable in English. The liquids in English are [l] and [r]. Consider the word “sir” and the second syllable of “apple”. If it is the case that the liquids in these syllables are the nuclei, then the words would be transcribed as [sṛ] and [æppḷ] respectively. However, not everybody agrees with that interpretation, and so these words are often analyzed as [sər] and [æppəl]. That would make the syllable nuclei [ə], which is a vowel. And by the way, the [p] in “apple” is also ambisyllabic.

The reason vowels are so likely to form syllable nuclei is that they are the most sonorous sounds available in spoken language. It is a general rule that syllable nuclei are formed by sonorous phones. Liquids and nasals are right behind vowels in that they are more sonorous than any other type of consonant. But it is possible to find syllable nuclei in other languages that are considerably less sonorant than any of the above. For example, there is at least one Berber language that contains syllables like [tḳt], where the nucleus of the syllable is [ḳ].

The onset and coda are always made up of consonants. Many languages have strict rules about how many consonants can appear, and what sort of order they appear in. English is relatively lax in this respect, so we can see syllables with several consonants clustered together in both positions. For example, “scrumptious”, transcribed as [‘skrʌmp.ʃəs], has three distinct consonant phones in the onset and two in the coda of the first syllable. But notice that you would never see a word in English like [‘rksʌpm.ʃəs], which would probably be spelled “rksupmtious”. Try pronouncing that and see what happens - and remember that it’s cheating to make the [r] or the [m] into separate syllables!

Consonants in syllable onsets and codas are also governed by sonority. There is a rule, called the sonority sequencing generalization, that says that the sonority of a syllable peaks at the nucleus and decreases toward either boundary. So the sonority of consonants in the onset is supposed to increase going forward, and the sonority in the coda is supposed to fall of. This is a generalization, so there are exceptions - but if you deviate too much from the rule the result becomes difficult to pronounce. In the made-up word above I reversed the order of the consonants in the onset and coda of the first syllable, thus making the sonority sequence “wrong”.

Every sound in a language has a place somewhere in the sonority hierarchy. And every language has its own sonority hierarchy ordering. So for example [star] is easy for English speakers to pronounce, but you don’t see a word like [tsar]: [t] is more sonorous than [s] in English. But in Russian it is not uncommon to see a word like [tsar].

Restrictions on what is allowed in a syllable vary from language to language. Not all languages allow as many consonants to be clustered in a syllable onset as English does, while some allow more. Some languages require every syllable to have an onset, while others allow naked nuclei. Syllable codas are especially restricted. For example, in Mandarin Chinese the only syllable codas that are allowed are nasals. There are no languages that forbid onsets, but many languages don’t allow syllable codas to appear at all.

For more information, and some neat diagrams, visit What is a syllable? and the Wikipedia entry for “Syllable”.

Deixis

2007-09-17T00:00:00-07:00

When someone says to you, “here” or “now”, you probably know what he means. “Here” might the room that you are both sitting in. “Now” would be the span of time you spent sitting together. But if either word were uttered under different circumstances, it could mean something very different. For example, if I called you from the Andes and I used the word, “here”, it would mean a mountainside somewhere - possibly thousands of miles away from the aforementioned room. The same word can mean both the room and the mountainside because of deixis.

Deixis is a form of exophora, which is an utterance that is given meaning by the context it is uttered in. Specifically, deixis represents the speech event itself: deictic expressions reference the speaker, the speaker’s utterances, the speaker’s location, and the time at which the speech event occurs. There are different types of deictic expressions that refer to each particular aspect.

Personal pronouns, such as “I”, “you”, “he”, and “she”, are deictic expressions. “I” refers simply to the speaker. The other pronouns are defined by the relation the referenced person has to the speaker in the discourse. As the role of speaker switches from person to person, the context represented by deixis in understood by participants of the discourse to change too.

Location and time are a little more complicated. Whenever someone speaks - or writes, or is quoted, etc. - there is an implicit deictic center that is formed in the minds of the speaker and any listeners. A deictic center is the point in space and time that spatial and temporal deictic expressions refer to. “Here” and “now” are the simplest examples. The verbs “to come” and to “to go” are also spatial deictic expressions: “to come” means motion towards the deictic center, and “to go” means motion away.

Based on this analysis, the phrase “come here” seems redundant at first. But actually the addition of “here” can be important, due to a phenomenon called sympathetic deixis. It is not uncommon, especially in phone conversations, to hear an utterance like, “I will come by later”. For the speaker to move toward the deictic center is almost nonsensical when the speaker is the deictic center. But in this case sympathetic deixis causes the deictic center to shift from the speaker’s location to the listener’s location. So motion towards the deictic center actually translates to motion toward the listener.

Note that the shift caused by sympathetic deixis does not necessarily affect all the aspects of deixis. In the example above the meanings of personal pronouns do not change after the deictic center has shifted; in a similar sentence, “I will come to see you”, “I” refers to the speaker, and “you” refers to the listener - as would be expected with or without a shifted deictic center.

An especially fun deictic puzzle is often heard in answering machine messages like, ”I’m not here right now”. It isn’t possible that the deictic center is fixed upon the speaker during this message, because it is not possible for the speaker to not occupy his own location. So there must be sympathetic deixis in effect to shift the deictic center either spatially or temporally. As someone who has been on the receiving end of this message, I expect “here” to mean the location where the message was recorded, and “now” to be the time when I am calling. By that analysis the spatial location of the deictic center remains fixed on the location of the speech event, while the temporal aspect shifts to the listening event via sympathetic deixis. There is another possible analysis where both spatial and temporal sympathetic deictic shifts occur. In that case the spatial shift does not move the location of the deictic center to the listener, but instead moves it to the place where the listener expects it to be: in this case wherever the speaker’s phone is. Under either analysis, the answering machine example demonstrates that deictic shifts can be temporal as well as spatial.

There are other forms of deictic expressions. There is a more complete list in the Wikipedia article on deixis.