David Golightly - Patterns

Jaro-Winkler implementation in Ruby for User-Agent matching

2009-03-03T19:01:00.001-08:00

Working in the mobile web, it's hard to keep up with the constant glut of devices on the market and their rapidly evolving capabilities. Of course, progressive enhancement is key; the markup you use in a mobile site should be minimal and look good without any CSS, JavaScript, or images, which is the worst-case. But we don't want to stop there; we want our sites to look as good as they can on as many mobile devices as possible.

WURFL is here to help with that. A crowd-sourced database of mobile devices, updated regularly, WURFL gives you detailed information on the capabilities of over 10,000 mobile devices indexed by user-agent string and grouped by manufacturer. It's relatively straightforward to set up a cronjob for a rake task that downloads an updated WURFL file and stores it in a table in your database; using an ActiveRecord model, you can then query the data provided by WURFL to get all the details for any device which has a user-agent string in the database.

But device makers throw a wrench in these efforts: user-agent strings are frequently updated or modified from their canonical form without rhyme or reason.

Fortunately, we have the Jaro-Winkler distance algorithm, which gives us a quick-and-dirty matching algorithm for strings that are mostly the same but may vary in arbitrary ways. Using this algorithm, we can run indexed queries for exact matches, then pull in some subset (perhaps matching the first 20 characters of the mystery UA string), iterate over these devices, and find the best match to return. Failing to find any implementation of the Jaro-Winkler algorithm in Ruby, I had to cobble together my own; I hope you find it useful.

module JaroWinkler

    def self.distance(str1, str2)
      str1.strip!
      str2.strip!

      if str1 == str2
        return 1
      end

      # str2 should be the longer string
      if str1.length > str2.length
        tmp = str2
        str2 = str1
        str1 = tmp
      end

      lmax = str2.length

      # arrays to keep track of positions of matches
      found1 = Array.new(str1.length, false)
      found2 = Array.new(str2.length, false)

      midpoint = ((str1.length / 2) - 1).to_i

      common = 0

      for i in 0..str1.length
        first = 0
        last = 0
        if midpoint >= i
            first = 1
            last = i + midpoint
        else
            first = i - midpoint
            last = i + midpoint
        end

        last = lmax if last > lmax

        for j in first..last
          if str2[j] == str1[i] and found2[j] == false
            common += 1
            found1[i] = true
            found2[j] = true
            break
          end
        end
      end

      last_match = 1
      tr = 0
      for i in 0..found1.length
        if found1[i]
          for j in (last_match..found2.length)
            if found2[j]
              last_match = j + 1
              tr += 0.5 if str1[i] != str2[j]
            end
          end
        end
      end

      onethird = 1.0/3
      if common > 0
        return [(onethird * common / str1.length) +
                (onethird * common / str2.length) +
                (onethird * (common - tr) / common), 1].min
      else
        return 0
      end
    end

end

This will return a value such that 0 <= value <= 1. Matches near the beginning of the strings are weighted more heavily than matches near the end, making this a good algorithm to use with user-agent strings which are typically long and have minor variations toward the end.

That said, this isn't necessarily the optimal method to detect user-agent strings, and since it can easily give false positives in cases where a desktop and a mobile version of the same browser exist, it should be used in conjunction with a whitelist of known desktop browsers (which, though substantial, is much shorter than the list of all mobile browsers). So I offer this code with the disclaimer that Jaro-Winkler may not be the most effective algorithm for user-agent string matching.

By the way, I'm just learning Ruby, so if I'm doing anything atrocious here please let me know.

Asynchronous Image Caching with the iPhone SDK

2009-02-25T22:11:00.000-08:00

Coming from the web world, I'm used to not having to think about all the functionality implicit in the humble HTML <img> tag, including client-side resource caching and asynchronous loading. In fact, the browser will cache any resource sent with the appropriate HTTP response headers, but by far the most common use of this cache behavior on most websites is images of all kinds.

So in building a couple of simple iPhone apps recently that display a list of search results retrieved from a server call, one piece that was missing was an asynchronous image loader that retrieves and displays thumbnail images in UITableViewCells.

[UIImage imageWithData:[NSData dataWithContentsOfURL:url]] gives you default iPhone HTTP caching behavior using NSURLCache, but it turns out that's not good enough: NSURLCache only stores URL contents in memory for the duration of the use of the application. We also need a URL cache that writes results to disk so that frequently-accessed responses only, and it also needs to manage its capacity. After that, we need an image loader that will abstract away the work of downloading images asynchronously, so that when a cell needs an image, it can request the image from the CachedImageLoader, and the CachedImageLoader will call back with the image, whether loaded from cache or remotely. Let's start with the data cache, DiskCache, which simply caches NSData objects in files in the application's file path:

extern const NSUInteger kMaxDiskCacheSize;

@interface DiskCache : NSObject {
@private
        NSString *_cacheDir;
        NSUInteger _cacheSize;
        NSUInteger _diskCapacity;
}

@property (nonatomic) NSUInteger diskCapacity;
@property (nonatomic, readonly) NSString *cacheDir;
@property (nonatomic, readonly) NSUInteger size;

+ (DiskCache *)sharedCache;

- (NSData *)dataInCacheForURLString:(NSString *)urlString;
- (void)cacheData:(NSData *)data
                  request:(NSURLRequest *)request
                 response:(NSURLResponse *)response;
- (void)clearCachedDataForRequest:(NSURLRequest *)request;


@end

The implementation for this one will be pretty straightforward: it's a singleton class that obscures as much activity as possible, including the cache path and file naming scheme (the implementation actually just uses the original URL filename, though this is potentially brittle when resources with the same name are located in different paths). One detail that I find interesting is determining folder size, which is less straightforward than I expected under Cocoa. To determine the size of all files in a given directory, you have to walk the directory and add up their sizes:

- (NSUInteger)size {
    NSString *cacheDir = [self cacheDir];
    if (_cacheSize <= 0 && cacheDir != nil) {
        NSArray *dirContents = [[NSFileManager defaultManager]
                                directoryContentsAtPath:cacheDir];
        NSString *file;
        NSDictionary *attrs;
        NSNumber *fileSize;
        NSUInteger totalSize = 0;

        for (file in dirContents) {
            if ([[file pathExtension] isEqualToString:@"jpg"]) {
                attrs = [[NSFileManager defaultManager]
                         fileAttributesAtPath:[cacheDir
                             stringByAppendingPathComponent:file]
                         traverseLink:NO];

                fileSize = [attrs objectForKey:NSFileSize];
                totalSize += [fileSize integerValue];
            }
        }

        _cacheSize = totalSize;
        DLog(@"cache size is: %d", _cacheSize);
    }
    return _cacheSize;
}

Here, I'm only interested in files with the "jpg" extension, though this is the only hard-coded reference to images in the entire implementation and could easily be changed. Note the Objective-C syntax

for (NSString *file in dirContents)

which is known as fast enumeration and gets compiled down into pointer arithmetic, much faster than indexing using NSArray's objectForKey: method. Perhaps there's a more concise way to perform this task, but I haven't run across it yet.

While we're here, it's also worth taking a look at the mechanism for trimming the old files out of the disk cache when it reaches capacity. This involves first filtering the directory contents, then sorting the filtered contents by date modified; welcome to the wonderful world of NSArray sort functions:

NSInteger dateModifiedSort(id file1, id file2, void *reverse) {
    NSDictionary *attrs1 = [[NSFileManager defaultManager]
                            attributesOfItemAtPath:file1
                            error:nil];
    NSDictionary *attrs2 = [[NSFileManager defaultManager]
                            attributesOfItemAtPath:file2
                            error:nil];

    if ((NSInteger *)reverse == 0) {
        return [[attrs2 objectForKey:NSFileModificationDate]
                compare:[attrs1 objectForKey:NSFileModificationDate]];
    }

    return [[attrs1 objectForKey:NSFileModificationDate]
            compare:[attrs2 objectForKey:NSFileModificationDate]];
}


- (void)trimDiskCacheFilesToMaxSize:(NSUInteger)targetBytes {
    targetBytes = MIN([self diskCapacity], MAX(0, targetBytes));
    if ([self size] > targetBytes) {
        NSArray *dirContents = [[NSFileManager defaultManager]
                                directoryContentsAtPath:[self cacheDir]];

        NSMutableArray *filteredArray = [NSMutableArray 
                                arrayWithCapacity:[dirContents count]];
        for (NSString *file in dirContents) {
            if ([[file pathExtension] isEqualToString:@"jpg"]) {
                [filteredArray addObject:[[self cacheDir]
                                stringByAppendingPathComponent:file]];
            }
        }

        NSInteger reverse = 1;
        NSMutableArray *sortedDirContents = [NSMutableArray arrayWithArray:
                                     [filteredArray
                                sortedArrayUsingFunction:dateModifiedSort
                                                                             context:&reverse]];
        while (_cacheSize > targetBytes && [sortedDirContents count] > 0) {
            id file = [sortedDirContents lastObject];
            NSDictionary *attrs = [[NSFileManager defaultManager]
                                   attributesOfItemAtPath:file
                                   error:nil];
            _cacheSize -= [[attrs objectForKey:NSFileSize] integerValue];
            [[NSFileManager defaultManager] removeItemAtPath:file
                                                       error:nil];
            [sortedDirContents removeLastObject];
        }
    }
}

Next, we take a look at the CachedImageLoader, which uses a protocol ImageConsumer to for its clients; this keeps us from being locked into any particular image renderer (such as UITableViewCells or what have you); in fact, it's used in a few different places in the GoTime apps:

@protocol ImageConsumer <NSObject>
- (NSURLRequest *)request;
- (void)renderImage:(UIImage *)image;
@end


@interface CachedImageLoader : NSObject {
@private
        NSOperationQueue *_imageDownloadQueue;
}


+ (CachedImageLoader *)sharedImageLoader;


- (void)addClientToDownloadQueue:(id<ImageConsumer>)client;
- (UIImage *)cachedImageForClient:(id<ImageConsumer>)client;

- (void)suspendImageDownloads;
- (void)resumeImageDownloads;
- (void)cancelImageDownloads;


@end

Again, this is a singleton class, which is basically a wrapper for NSOperationQueue, which is a really handy high-level threading implementation. (There are reports that NSOperationQueue is broken on OS X Leopard, but the single-core chip architecture on the iPhone avoids the cause of this bug, so it can be safely used; indeed, I haven't had any problems with it.) NSOperationQueue allows you to add NSOperations, which get run FIFO on a number of threads specified in maxConcurrentOperationCount. I've found that a single image download thread is sufficient, even on edge networks: the network speed is always the bottleneck, not lack of concurrency. This allows the implementation of CachedImageLoader to be single threaded (counting the operation thread) and use synchronous downloading. A image consumer needing an image implements the ImageConsumer protocol, then calls addClientToDownloadQueue: passing itself as the argument:

- (void)addClientToDownloadQueue:(id<ImageConsumer>)client {
    UIImage *cachedImage;
    if (cachedImage = [self cachedImageForClient:client]) {
        [client renderImage:cachedImage];
    } else {
        NSOperation *imageDownloadOp = [[[NSInvocationOperation alloc] 
                        initWithTarget:self
                              selector:@selector(loadImageForClient:)
                                object:client] autorelease];
        [_imageDownloadQueue addOperation:imageDownloadOp];
    }
}

- (void)loadImageForClient:(id<ImageConsumer>)client {
    NSAutoreleasePool *pool = [[NSAutoreleasePool alloc] init];

    if (![self loadImageRemotelyForClient:client]) {
        [self addClientToDownloadQueue:client];
    }

    [pool release];
}

In cachedImageForClient, CachedImageLoader uses both the in-memory NSURLCache as well as our DiskCache class above, in turn. Failing to find the image in the cache, the loader creates an NSInvocationOperation which, in turn, gets called on our download thread; we create an autorelease pool and download the image synchronously, caching the image data when we have it (in both DiskCache and NSURLCache.)

So there you have it, most of an implementation of an asynchronous, caching image downloader for iPhone.

UPDATE 11/26/2009: The complete source code for the cache is available here.

Cracking Supercollider

2009-02-24T22:49:00.000-08:00

SuperCollider is an amazing language, if you are in the super genius club who can understand the extensive documentation or pursue graduate studies at CCRMA. I've been out of audio synth for a while, but recently found myself needing to apply a recursive delay line to an audio recording I'm working on for my music project, Midday Veil.

SuperCollider dates from the mid-90's, and is thus a peer to Ruby, sharing influences like Smalltalk and Lisp. As languages go, it's pretty nice, though the compiler leaves something to be desired - inexplicably, variables must be declared before use at the top of a function, much like in C. Other than minor gripes like that, it's a pretty nifty package: functions as first-class objects, native arrays and maps, garbage collection, dynamic typing, and classical OOP features to boot. However, there's a lot more to the platform than just the language, and the learning curve is quite steep. Much like Ruby, some of the syntax is "optional" or has multiple ways to express the same thing; functions need a "value" message sent to them to be executed. Also, most of even the basic language-level concepts are mixed in with advanced platform-specific concepts like OSC messaging, client-server internals, audio buffers, and so on, so getting your feet wet takes a lot of immersion in the concepts to understand SuperCollider's terse yet expressive syntax and impressive power. Getting started with Processing, which uses a much uglier language, is a cakewalk by comparison.

It doesn't help that the "introductory tutorial" launches first thing into a detailed description of how to use the platform to send OSC messages over the Internet, then SynthDefs, then SynthDescLibs, and then instantiating both them and their UDP equivalents, none of which, it turns out, are required to get started, when you really just want to figure out how to play a sound file from your hard disk and feed it through some reverb. Oh no, you don't get to that until you've drudged through page after page of detailed docs, explaining each concept in depth before moving on to the next incremental step. Memo to documentation writers: people (especially people making music) need to be able to sit down and play something after their first lesson. You don't come home from your first piano lesson with a stack of reading on Cristofori and the development of the modern soundboard, told that maybe you can start playing after you've written a 200-page treatise on the inner mechanics of the thing. Oh sure, that's all useful to understand before too long, but to start off you want to learn just enough of a subset of the thing to feel like you can begin to be creative with it. For an example of just how jargony the whole thing feels, I treat you to an excerpt from page 3 of the docs:

When notated as code in client programs, the engines have two essential parts: a name and a function. In the jargon of SuperCollider, the function is called a ugenGraphFunc. The term ugenGraphFunc derives from the notion of a graph, which is the data structure that SuperCollider uses to organize unit generators. SuperCollider constructs the graph for you from the code it finds in your function which means that don't have to know how a graph works or that it even exists.

Ok, so basically it's a parse tree with a funny name. I assumed something like that was under the hood, but if I don't have to know this, why the hell are you telling me on page 3 of the documentation?

With that in mind, I present to you my first hard-won miniature piece of software in SuperCollider, which I wrote from scratch with scant help from the docs:

(
 r = { |input, gain, decayTime = 0.5, decayFactor = 0.9|
 var output, buf;
 if (gain > 0.1, {
         buf = Buffer.alloc(s, 44100, 2);
         output = input + r.(BufDelayC.ar(
             buf,
             input,
             decayTime,
             gain
             ), gain * decayFactor)
     }, {
         output = 0
     });
 output;
 }
)


(
 var filepath = "remember-pans-cropped.aiff";
 var synth = Buffer.cueSoundFile(s, filepath, 0, 2);
 {
 r.value(DiskIn.ar(2, synth), 1, 0.5, 0.9);
 }.play;
)

Ok, it ain't much, but it's mine and I'm proud of it. I'll probably look at that example a few months from now and cringe knowing all the mistakes I just made, but know what? Hell with it. This is music, and if you leak a bit of memory here or there on your own machine before you learn how to fix it, well, that's not too steep a price for some wicked tunes. Start with what you want, then learn just enough to get yourself there.

Hitting the limits on iPhone Safari

2008-08-11T19:13:00.000-07:00

Hit a hard iPhone resource limit:

<!DOCTYPE html PUBLIC "-//W3C//DTD XHTML 1.0 Strict//EN"
"http://www.w3.org/TR/xhtml1/DTD/xhtml1-strict.dtd">
<html xmlns="http://www.w3.org/1999/xhtml">
<head>
<meta http-equiv="content-type" content="text/html; charset=utf-8"/>
<meta name="viewport" 
    content="width=device-width; initial-scale=1.0; maximum-scale=1.0; user-scalable=no;" />
<meta name="apple-touch-fullscreen" content="YES" />
<title>iPhone image loading test</title>
<script type="text/javascript">
var n = parseInt('02123003022000310', 4),
    nTiles = 0;

function drawTile() {
    n++;
    nTiles++;
    document.getElementById('img').src = 
        'http://h0.ortho.tiles.virtualearth.net/tiles/h0' +
        n.toString(4) + '.jpeg?g=131';
    document.getElementById('count').innerHTML = nTiles+'';

}

window.onload = function () {
    window.setInterval(drawTile, 500);
};
</script>
</head>
<body>
    <img src="#" id="img" />
    <p>Total tiles: <span id="count">0</span></p>
</body>
</html>

After downloading about 210 images, the iPhone simply stops downloading new ones. This is probably due to hitting the hard 30MB same-page resource limit as as documented on A List Apart. Apple itself documents the limit at 2 megapixels. Who knew that they also didn't free such resources when no longer in use?

I don't see any easy way around this one, and the implications are huge: even if your app is scrupulous in conserving JavaScript and DOM memory resources, sooner or later the browser itself will fail you. This precludes especially any browser-based Ajax mapping application, and many long-running Ajax apps in general.

So much for Web 2.0 on the iPhone.

Where are the JavaScript unittesting frameworks?

2008-07-08T09:25:00.000-07:00

Now that JavaScript has been patched together into a number of promising server-side frameworks (Synergy, Jaxer, and, coming soon(ish), Rhino on Rails), JavaScript is really taking off as a potentially full-stack enterprise solution.

One serious failing, however, seems to be the continued lack of decent developer support tools, the worst of which has got to be testing. Sure, there are a number of decent browser test automation frameworks out there:

Sure, these are all great platforms - for AUTOMATION. Let's be clear, however: Automation is in no way the same thing as unit testing. Automation requires a full environment, and seeks to replicate the end-user experience on the full product stack by means of emulated behaviors - mouse clicks, key presses, and so on. Usually, such tests launch a browser app, set up the environment, execute the test case steps (which can mean multiple page loads), and then close the browser app, for EVERY TEST CASE. Such tests are absolutely necessary for any non-trivial user-facing product.

At the same time, developers need more granularity than that. We need to test hundreds of individual methods and edge cases in our code that target specific functions. We need a framework that can be run at build-time, and can plow through hundreds of focused test cases in a matter of seconds. We need a browser, sans GUI.

For the purpose of headless, command-line browser code testing, it seems only the GPL Crosscheck framework offers the robustness of browser emulation required for any serious work. Built on Rhino with a Java layer of cleverly reverse-engineer browser behaviors, Crosscheck itself has numerous bugs and drawbacks in common browser features (no cookie emulation, poor DOM Level 0 support, nonexistent IFrames, incomplete CSS emulation), the greatest of which seems to be that development has stalled on the project.

It should be immediately apparent to any front-end developer maintaining a moderate-to-large codebase why command-line unit-testing is important. Also, I realize that, as a developer, I should be getting things done and building solutions. One could investigate building a command-line app for Windows (and perhaps a fork for Linux using Wine?) that would instantiate the actual browser binaries from the command line and run code without launching the browser chrome; it seems this should work at least for Internet Explorer (COM objects) and Firefox (XULRunner) and maybe Safari too. I would like to submit patches to Crosscheck, but I'm not sure if the core developers even have time to review patches, and I don't personally have the time to sink into development of a competing framework right now. My hope is that someone out there in the development community will take notice of this need and have the time and/or resources to tackle this problem, and maybe one day I'll be that person. In the meantime, we'll have to settle for running our test suites in a matter of hours and not minutes.

History

2008-04-15T15:04:00.000-07:00

$ history | awk '{print $2}' | sort | uniq -c | sort -rn | head

 149 cd
 138 ls
  42 svn
  27 python
  23 vim
  18 exit
  16 locate
  11 ssh
  10 rm
   8 less

via

New blog

2008-03-29T16:52:00.000-07:00

For all 2.3 of you out there reading this, I'd like to announce a new blog on "metaphysics?" so I can keep a clean sterile separation between work and life. My postings on this blog will continue to be exactly as infrequent as they have been since I started. Thank you.

Why Man Creates

2008-02-27T20:54:00.001-08:00

Strategies for Success (and other myths)

2008-02-09T11:50:00.000-08:00

The writings and thoughts of Karl Marx and Friedrich Engels and orthodox Communism in general date themselves squarely between the Industrial Revolution and Darwin's historic Origins. The revolutionary implementation of Communism was doomed to failure, of course, because by the time it gained critical mass it was already obsolete; groups of humans can't be organized as machines are organized. Top-down mandates of economic equality don't work, because the system will always be more complex than even the most tyrannical police state can enforce. People under duress may provide acceptable manual labor but don't contribute new ideas or new efficiencies to the process when their main concern is not personal investment in work but in following orders; thus micromanaged economies will always underperform freemarket systems.

The lesson of Communism that especially American right-wing capitalists don't want to learn is that micromanagement and monopoly are anathema to the principles of the free market. Applying the principles of Darwinian natural selection to the economic domain, we see that a healthy economic ecosystem is one in which no single player is too dominant (see: super predators), but rather neck-and-neck competition keeps everyone on their toes while allowing smaller players to emerge as competitive with more established ones. Conversely, an economy of monoculture tends toward stagnation. Companies that grow too large become entrenched in a single business model and risk the ire of large partners when proposing innovations in production methods (see: Microsoft and IE).

Government clearly has a role to play in keeping the market competitive by regulating and sometimes smashing large corporations into smaller pieces. But more importantly, ownership of past success is not a guarantor for future success. Top-down institutionalization of past success models is a sure sign that the business is failing to see the next step in its evolution. In this regard, corporate (read: Stalinist) ownership of information and ideas will always fail in the face of bottom-up Darwinian trial-and-error. This is especially true in industries touched by technology, and we're already seeing established media companies, record companies, and television networks collapse under their own weight.

Enter the Internet. To the extent that it remains free, equal, and open, it provides the most fertile soil yet for innovation and progress (of ideas, of creativity, of economic advancement, of democracy). The chaotic hordes of the MySpace/YouTube generation will surely hasten the extinction of the giant record companies and the television networks, as the wisdom of crowds will do a better job determining what the crowds like than any closed, proprietary group of mavens in a boardroom or a laboratory ever will.

The lesson for internet companies trying to attract millions? Release early and often. Keep your coupling loose. Submit to what your users are telling you - investing 10 months in a project you're sure will be a hit is a huge risk; you'd better be basing your decisions on reams of user feedback and research, because your perfect vision for the product will always fail you unless you're playing with rules that have been subjected to the Darwinian rigor of millions of little trial-and-error tests.

Easy Date Formatter

2008-02-02T09:14:00.000-08:00

This should do the trick for most uses:

/** 
 * takes a string in form 'd/m/Y'
 * 
 * d => day (2 digits, leading 0)
 * D => day (2 digits, no leading)
 * l => day (of week, text, 3 chars)
 * L => day (of week, text, full length)
 * 
 * m => month (2 digits, leading 0)
 * M => month (2 digits, no leading 0)
 * f => month (text, 3 chars)
 * F => month (text, full length)
 * 
 * y => year (2 digits)
 * Y => year (4 digits)
 * 
 * g => hour (12hr, leading 0)
 * G => hour (12hr, no leading)
 * i => minute
 * s => second
 * t => hour (12hr, formatted with am/pm)
 * 
 * @param {String} format String for the formatting of this Date object
 * @return {String}
 */
Date.prototype.format = (function () {
    var days = ['Sun', 'Mon', 'Tue',
        'Wed', 'Thu', 'Fri', 'Sat'];
    var fulldays = ['Sunday', 'Monday', 'Tuesday',
        'Wednesday', 'Thursday', 'Friday', 'Saturday'];
    var months = ['Jan', 'Feb', 'Mar',
        'Apr', 'May', 'Jun',
        'Jul', 'Aug', 'Sep',
        'Oct', 'Nov', 'Dec'];
    var fullmonths = ['January', 'February', 'March',
        'April', 'May', 'June',
        'July', 'August', 'September',
        'October', 'November', 'December'];

    function twoDigits(n) {
        return (n<10? '0':'')+n;
    }

    return function formatDate(format) {
        var d = this;

        var matches = this.matches || {
            'd': function () { return twoDigits(d.getDate()); },
                'D': function () { return d.getDate()+''; },
                'l': function () { return days[d.getDay()]; },
                'L': function () { return fulldays[d.getDay()]; },
                'm': function () { return twoDigits(d.getMonth()+1); },
                'M': function () { return d.getMonth()+1; },
                'f': function () { return months[d.getMonth()]; },
                'F': function () { return fullmonths[d.getMonth()]; },
                'y': function () { return (d.getFullYear()+'').slice(2, 4); },
                'Y': function () { return (d.getFullYear()+''); },
                'g': function () { return twoDigits(d.getHours()%12); },
                'G': function () { return d.getHours()%12+''; },
                'i': function () { return twoDigits(d.getMinutes()); },
                's': function () { return twoDigits(d.getSeconds()); },
                't': function () { return (d.getHours() > 11? 'am' : 'pm'); }
        };
        this.matches = matches;

        return format.replace(/[dDlLmMfFyYgGist]/g, function (match) {
            return matches[match]();
        });
    };
})();

Introducing CSSx

2008-01-25T12:55:00.000-08:00

Sick of the lack of syntactic sugar for CSS? While many designers are fine with the simplicity of CSS, some developers managing large codebases (such as Zillow's still-terse 2500-line master.css) have been flailing for sanity. Enter CSSx, a syntax-enhancing compiler for CSS. It accepts all currently-valid CSS syntax, so you can use your current CSS chops unaltered, but adds variables and block nesting to the language.

/* sample.cssx */

$red = #f00 /* a comment here*/;
$block = {
    div {
        padding: 10px;
    }
    color: $red;
    border-width: 1px;
    margin: 20px 10px 15px 0;
}

.warning {
    color: $red;
}

.content {
    .warning {
        width: 200px;
    }

    cite { @rule($block); }

    p {
        span.tooltip {
            color: blue;
        }
        font-size: 1.1em;
    }

    .header {
        @rule($block);
        font-size: 0.8em;
    }

    font-family: Verdana, Arial, sans-serif;
}

It's still very beta (I'd peg it at 0.1), but please download, give it a spin, and give me feedback on what works/doesn't work for you, or what you'd like to see added. Download CSSx from Google Code.

Type-Converting Operator Considered Ridiculous

2007-10-13T19:04:00.000-07:00

I have come to question the wisdom of the type-converting == operator in JavaScript. The algorithm (defined in §11.9.3 of the ECMA-262 v3 spec) requires no fewer than 22 steps to execute, and produces such amazing intrasitivities as:

>>> '0' == 0
true

>>> 0 == ''
true

>>> '' == '0'
false

and random quirkiness such as:

>>> ' \t\r\n' == 0
true

but:

>>> null == 0
false

>>> null == false
false

>>> null == ''
false

>>> null == undefined
true

Do these behaviors strike anyone else as, well, a bit off? In the first example (discussed elsewhere) the intransitivity of the equality operator is a result of wanting an equality operator to play well within a weakly-typed language. If you want to be able to compare numbers to their string representations as though they were of the same type, while still preserving string comparison, this is the logical result. The second example is a result of the ToNumber algorithm, described in §9.3ff. The whitespace conversion to number value 0 is strange, but defined in the spec (in fact, it's a result of the same algorithm that dictates Number(' ') => 0). The third example seems bizarre as well; I'm not sure why null would be treated differently than 0 or false, but the same as undefined, in such expressions. Many articles from otherwise reputable sources often describe all of these values in terms of "truthiness" and "falsiness", but these articles sometimes gloss over these distinctions.

I don't condone transitioning JS into a strongly-typed system, but some of these behaviors are quite subtle. Given the fact that the vast majority of JavaScript programmers seem to be unaware of the strict-equality operator === (and its negative counterpart, !==), it's no wonder behaviors such as these can cause confusion. See also this article for even more pitfalls, this time simply with math operators combining string and numeric types.

So as Crockford says, use the strict comparison operator === unless you know what you're doing.

All the Code Security You Need

2007-10-04T12:43:00.000-07:00

Lots of beginning JS coders seem to have this idea that the web is all about having your cake and eating it too. I want to participate in the glorious Internet revolution, I just don't want to share my ideas or information with anybody else. I'm writing rich internet applications that are so great, just so unique, that I want to make sure nobody else can possibly look at my code and steal all those great juicy super-awesome proprietary ideas I've got. And maybe, just for bragging rights, I want my files to look HUGE as well. I've mocked up a handy little device that can take care of both tasks at once. Behold, the decompressJS module:

var decompressJS = (function () {
    var encoding = [' ', '\t', '\n', '\r'];
    var revEncoding = (function () {
        var ec = {};
        for (var i=0; i<encoding.length; i++) {
            ec[encoding[i]] = i;
        };
        return ec;
    })();

    return {
        encode: function (codeText) {
            var out = [], cc, i=0, len=codeText.length;

            while (i<len) {
                cc = codeText.charCodeAt(i++);

                // JS chars are actually 16-bit UTF-16 chars, 
                // so we need 4 chars encoded per source char
                // to fully encode
                for (var j=0; j<8; j+=2) {
                    out.push(encoding[(cc>>j)&3]);
                }

            }
            return out.join('');
        },

        decode: function (encodedText) {
            var out = [], cur, i=0, len=encodedText.length;
            while (i<len) {
                cur = 0;
                for (var j=0; j<8; j+=2) {
                    cur += revEncoding[encodedText.charAt(i++)]<<j;
                }
                out.push(String.fromCharCode(cur));
            }
            return out.join('');
        }
    };

})();

Like any mature programming paradigm, my decompressJS can even effectively encode and decode itself, the above 1225-character-long code example (including whitespace) decompressed neatly into an all-whitespace string with no fewer than 4900 characters! Just run your code through this baby and it'll come out the other end fully converted into only invisible whitespace characters! Transfer your JS code over the wire, making it look like nothing but an empty file with all whitespace! Magically increase your file size by a factor of 4! Impress your colleagues with your invisible code! Who's laughing now, code stealers?

Glorious links

2007-07-27T17:47:00.000-07:00

BoingBoing's been on a good tear recently. Better than usual. For those of you whose eyes have glazed over, go back and re-read these posts:

All the Templating You Need

2007-07-17T21:52:00.000-07:00

function replicate(items, template, defaults) {
    var indices = {};
    var i=0, item;

    // build direct map of column names -> row index
    while ((item = data.columns[i])) indices[item] = i++;

    return data.rows.map(function (row) {
            return template.replace(/__\$\{(.+?)\}__/g, function (str, keyword) {
                return (keyword in indices)? row[indices[keyword]] : '';
                });
            }).join('\n');
}

var data = {
    'columns': ['adj', 'noun'],
    'rows': [
        ['main', 'man'],
    ['leading', 'lady'],
    ['green', 'dreams']
        ]
};

var template = '<p>__${adj}__ __${noun}__</p>';
replicate(data, template);

Peter Michaux has some nice ideas about keeping the JSON format DRY, so that data returned resembles something more like a list of Python tuples. (Python is also probably the single language that helped me to understand efficient JavaScript patterns.)

Client-side transforms - converting an XML or JSON response into HTML on the client, to save server bandwidth and processing time - are a key part of modern web apps, but I'm not sure about a transform system that implements full-blown JavaScript logic. Branching or looping can be implemented easily in transforming functions; several templates can be used and plugged in to each other, leading to nested data structures in the response. (Hopefully, time permitting, I'll get to demonstrate how that works soon.)

innerHTML may not be a part of any standard, but there's no reason why it shouldn't be. Sometimes we need to interact with the DOM as a tree, sometimes it's more useful to unleash JavaScript's string parsing and regex power on it.

One-line CSS minifier

2007-07-09T13:48:00.000-07:00

CSS minification in one line:

$ cat sourcefile.css | sed -e 's/^[ \t]*//g; s/[ \t]*$//g; s/\([:{;,]\) /\1/g; s/ {/{/g; s/\/\*.*\*\///g; /^$/d' | sed -e :a -e '$!N; s/\n\(.\)/\1/; ta' >target.css

With comments:

$ cat sourcefile.css | sed -e '
s/^[ \t]*//g;         # remove leading space
s/[ \t]*$//g;         # remove trailing space
s/\([:{;,]\) /\1/g;   # remove space after a colon, brace, semicolon, or comma
s/ {/{/g;             # remove space before a semicolon
s/\/\*.*\*\///g;      # remove comments
/^$/d                 # remove blank lines
' | sed -e :a -e '$!N; s/\n\(.\)/\1/; ta # remove all newlines
' > target.css

Using this script, I was able to chop about 29% (10K) off our master.css file. Assumes lines end in semicolons that should end in semicolons. May not play well with certain freakish outdated CSS hacks. Use at your own risk, and always test throughly before releasing into the wild.

The Problem with SlickSpeed

2007-07-07T17:11:00.000-07:00

For the past month or so, there's been a lot of noise about the SlickSpeed Selectors Test Suite. Since I'm in the market for a good selector engine for Zillow, and since it's a bit of a rite of passage (a front-end web dev's equivalent of compiler authoring?), I wrote my own, to see how well I could do and to see how it stacks up to the rest.

So of course, I modified the suite (under its MIT license) to test my little attempt as well. I was pleased with my initial results, but found the test document that comes packaged with the suite to be a little simplistic. Not enough variety or depth of nesting; the resulting DOM structures don't really resemble what I look at on a daily basis at work. I wanted to measure performance in the wild. So I replaced Shakespeare's As You Like It with the Home Details Page for Zillow.com, perhaps the most complex page on the site. Among other things, it includes a photo gallery, a Flash map, an Live Local-based Bird's Eye View map, a chart widget, several ads, tables, etc.

The results, you can see for yourself, here.

As it turns out, according to SlickSpeed, my engine outperforms all but 2 of the other engines on Firefox, and is the best performer on IE7.

So my misgivings on the nature of the document wandered over to the construction of the queries. The given queries perform a "breadth" pass, but they don't really provide a "depth" pass including all manner of combinations of possible selectors, so I wrote my own addition to the suite that picks random elements from the DOM and generates a matching CSS1 selector for it. You can see the dynamic test suite here.

Now, my Element.select engine's performance is fair to decent at best, but no longer the front-runner. Unless I can iron out the kinks, I might look into Ext's engine, especially since it fits nicely into the Yahoo! UI library we use at Zillow.

On the other hand, my Element.select engine is stand-alone and does not provide any other services or dependencies. It's a whopping 6KB (minified), but I wouldn't recommend the use of a CSS query engine for anything short of a full-scale web application anyway.

Some thoughts, though: For reasons that should be self-explanatory, it appears that all of the CSS engine makers are optimizing for Firefox. And once again, Opera's JavaScript engine (named Linear B) and DOM implementation beats out all the rest. Performance on IE looks to be all-around poorer. The Internet Explorer Team certainly has their work cut out for them, not only in improving their DOM and JScript performance and their developer tools (a decent profiler and a debugger that's not attached to Visual Studio would be nice), but also in winning over a hostile developer community. I guess that's what happens when the maker of the World's Number One Browser shuts down their development team for 5 years.

Prototype and MooTools appear to be compiling the CSS selectors into XPath statements for Firefox's (and Opera's) built-in xpath evaluator (too bad IE forgot to allow MSXML's XPath engine to apply to the HTML DOM). While the DOM performance for these XPath-based implementations is fantastic, they also help underline the end-user experience difference between browsers. Let's hope users take notice how much faster the leading non-IE browsers are in comparison; it's hard to win users over on the basis of standards compliance alone.

If nothing else, I hope my modified SlickSpeeds will help CSS query engine developers focus on what's important: CSS1 queries. The time scores at the bottom of the SlickSpeed test skew heavily toward obscure pseudoclass and attribute selectors which I for one won't use most of the time. It's the meat-and-potatoes tag, class, and ID that really count.

Sicko

2007-07-01T23:59:00.000-07:00

As we all know, Google has great power. It's power that comes from the masses: utilizing and channeling the activities, ideas and opinions of millions via the Web. All that information and trust capital can be a powerful tool for sustaining an environment that encourages democracy. Or not.

Update:

Apparently now, for some at Google, democracy is available to the highest bidder.

But the more important point, since I doubt that too many people care about my personal opinion, is that advertising is an effective medium for handling challenges that a company or industry might have. You could even argue that it's especially appropriate for a public policy issue like healthcare. Whether the healthcare industry wants to rebut charges in Mr. Moore's movie, or whether Mr. Moore wants to challenge the healthcare industry, advertising is a very democratic and effective way to participate in a public dialogue.

That is Google's opinion....

Web-Native UX

2007-07-01T18:54:00.000-07:00

I'd like to address something many in the User Experience community would rather avoid, since many times it may interfere with deploying the latest cool widget or Ajax technique that comes down the pike. I want to talk about User Experience Consistency and the web. Because while standards bodies have come into being to coordinate the development of the cornerstone technologies from which we build interfaces, and any web developer worth her salt pays attention to valid, semantic markup and the very latest in CSS techniques and the newest developments in unobtrusive scripting and REST and microformats, the pace of development in web-wide usability standards has been glacial at best.

I bring this up because I've been noticing a slower adoption rate of highly-usable, widget-heavy, responsive, dynamic, configurable, powerful web applications. My source? Purely anecdotal and completely unscientific, among my friends and family and even coworkers at Zillow, who express frustration and antipathy toward websites for even minor perceived flaws, while clunky interfaces in other, more primitive sites are tolerated and even preferred to their more elegant "web-application-y" counterparts. With the exception of certain Google and Yahoo! applications, many powerful, innovative web apps are being ignored. In the rush to push the browser to its limits, it's easy to lose sight of the end goal: making routine tasks easier for end users, in the most straightforward way possible.

Web developers are a sensitive bunch - the profession long disregarded in the eyes of "serious" programmers. Ajax was to change all of that. And with impressive things now being done in one of the most challenging software development environments, the front-end of web development has finally been able to attract some formidable talent away from server-side, OS, and game development. For the better, I should think, the Web has been gaining ground, not only as a place to exchange information, but as a valid, full-fledged platform for software development. That's the idea behind all those standards out there: eventually, if we clap our hands and work hard enough, the Web might supplant desktop-native applications for all but a few specialized purposes. Soon, your computer will connect into the World Wide Continuum; your data will mingle freely with the data of billions around the world on an indistinguishable platform of desktop/web-hybrid applications, the social utopia of the Web will supplant thick-client, rugged-individualist desktop computing, the Singularity will occur, and we will all live in happy harmony with the universe.

Fact of the matter is, not nearly enough consistency and code reuse is happening on the web. To an extent, that's good. I'd like to see the web remain a wild place that functions as laboratory as much as controlled platform. But too often, problems are approached like they've never been addressed before.

Sure, there are attempts at usability standards out there. But web usability is complicated, and in spite of the best attempts of several javascript libraries, nobody, not even Google, is as slick and consistent as OS-native applications.

When I'm designing an interface, I try to take into consideration three primary concerns:

Familiarity.: If I haven't seen it before, I don't know what it does, and I don't want to use it, and may not even recognize it as part of the UI. This becomes a huge obstacle for innovative interface development - more later.
Consistency.: If a widget looks more than 70% similar to something else, I will expect them to behave the same. This has ramifications beyond your website (duh).
Ease of use.: This is a big umbrella, encompassing everything from accesibility to ergonomics to "enjoyment": does my slider have a big enough click target? Can I elect to use the keyboard to control this thingie, or am I stuck with the mouse? Do I find myself repeating the same action for common tasks? Is my path into common tasks streamlined and foolproof?

Back in the dark ages, before DHTML graduated from the shadows of image rollovers, web interfaces were largely built out of browser-native form elements and links to more pages. Usability was a minimal concern, because layouts were simpler and interaction models were much less ambitious. Form interfaces were easy to manipulate, since they were largely designed to use OS-native widgets and behave comparable to their desktop-app counterparts. Links were all blue-and-underlined, and they all took you to a new page. Now that we've graduated from a website- to a webapplication-based web, however, many users haven't followed along. Widgets that don't look like text-input boxes can be hard to spot; a recent usability study at Zillow found as much. Part of the problem may be that many users simply haven't been exposed to web applications to expect that anything other than straightforward input controls to respond to input events. I'd like to think that's part of our responsibility as web developers: challenge our users to explore, experiment, discover. But it's also our responsibility to keep the guesswork out of our interfaces.

Web usability is a moving target. I don't have answers right now to many of these questions, but I'll be discussing them as they come up. This post was to survey the territory; I hope to be able to explore aspects of this issue in greater detail soon. I'll also be writing about the technical details of implementing a large-scale interface architecture that balances web standards with friendly, usable design. I believe in powerful, flexible user interfaces, but only inasmuch as they empower the user. Gratuitous lightboxes are not welcome!

The Blogging Professional

2007-06-30T17:48:00.000-07:00

It is a melancholy experience for a professional mathematician to find himself writing about mathematics. The function of a mathematician is to do something, to prove new theorems, to add to mathematics, and not to talk about what he or other mathematicians have done. Statesmen despise publicists, painters despise art-critics, and physiologists, physicists, or mathematicians have usually similar feelings: there is no scorn more profound, or on the whole more justifiable, than that of the men who make for the men who explain. Exposition, criticism, appreciation, is work for second-rate minds.

-- G. H. Hardy (PDF link)

Crockford's revisions to ECMAScript

2007-06-23T19:31:00.000-07:00

The ECMAScript standard is undergoing growing pains right now, and for the first time since 1999, it looks like major revisions to the language may take effect soon. Douglas Crockford has recommendations of his own. While I don't have any strong feelings about the new features he requests (they can mostly be implemented in the JavaScript we already have), his Corrections are mostly sane things that will remove a lot of the suckiness from the current standard:

Reserved words
Standardize implementation of trailing commas in object literals and arrays
Make arguments object a true array
Tail recursion optimization
Deprecate primitive type wrappers, the with statement, semicolon insertion, arguments.callee, typeof, and eval.

It looks like Brendan Eich is well aware of Crockford's longstanding laments, particularly against the with statement and the reserved words restrictions, and has addressed them in the draft spec for ECMA-262 v4.

Crockford objects to restricting the use of reserved keywords in object definitions as unnecessary. According to his argument, usage such as:

var o = {
    class: 'style', 
    with: function (n) { return n+'a top hat'; }
};

will preserve the original use of these names, as the names are merely being used for scoped member properties; they cannot be confused in this context, syntactically, with the "official" uses of these keywords. (This is, apparently, why the JSON spec requires double-quoted property names.) However, it seems this restriction is in place mainly to make possible the use of the with keyword; consider:

with (o) {
   class = 'none';
   with(class);
}

If using these keywords were legal above, their use with the with statement here invites syntax hell.

I for one would be happy to see the demise of the with keyword. It breaks with JavaScript's function-level scoping, and creates more problems than it's meant to solve. It "feels" uncharacteristic of the language, since it promotes an object's properties from "property" status into "variable" status, blending them indiscriminately into the surrounding scope. JavaScript has enough trouble affording decent namespacing as it is; this "feature" smacks of bad practice.

More than adding new features, we could use a "trimming-down" phase to the language. While Mozilla toils at turning JavaScript into Python and other power-players at ECMA (presumably MS?) seek to remake the spec in the image of Java or C#, I'm mostly happy with the way it is - just please, for God's sake, fix the problems that are currently there before bounding into a new round of ill-conceived feature bloat.

We front-end developers are lucky to be enjoying a golden age of JavaScript. But the clouds of confusion and incompatibility are on the horizon. I don't see a compelling reason to add Java-style classical inheritance to the language, and I see even less a possibility of the vendors agreeing to ship timely implementations of this new spec.

Surely wiser heads than mine are laboring on this problem. But I guess I'm just not seeing that JavaScript falls short in ways that warrant changing it beyond recognition.

Code Modularization and CSS Queries

2007-06-05T16:36:00.000-07:00

On his personal blog, YAHOO! front-end engineer Nicholas Zakas takes on the prevalence of the CSS query engine in client-side JavaScript libraries. The flexibility of some other quick syntax shorthand for accessing HTML elements and describing structure without using the conventional DOM methods has always appealed to me, so I wasn't sure what he was missing.

Granted, the recent proliferation of JS libraries in general (and query engines in particular) has been rather excessive, no doubt tracking a boom and bust path. I'm a fan of all of these efforts, though I wouldn't use most of them myself - they represent attempts to impose order onto the chaotic soup of client-side code that we've been dealing with since 1996. Each one - Prototype's dubious extensions to native objects, jQuery's wrapping of DOM elements and telltale method chaining, Mochikit's Python-like syntax - represents a new experiment in turning the best approximation we've ever had to a cross-OS, open-source application platform - the web browser - into the full-fledged application framework it's destined to be. Even if not all of these attempts have been useful, they've at least been instructive.

After reading his replies to comments to his post, and after an informal conversation with Joel Webber at the recent Google Developer Day, I realized that client-side techniques vary widely across organizations.

At Zillow, for example, we go to great lengths to separate our HTML, CSS, and JavaScript. Since our site is fairly complex and design-heavy, and code iterations happen with such frequency, this modularization is key to keeping sane. So we have a set of rules we follow:

All pieces of client-side code have a well-defined means for interacting with each other. For CSS -> HTML, it's CSS selectors. For JS -> HTML, it's the DOM. For JS -> CSS, it's classnames. For HTML -> JS, it's the DOM events model.
Do not mix HTML, CSS, and JavaScript. No inline styles, no inline event handlers, no creating elements via JavaScript.

You see where I'm going with this - HTML, CSS, and JavaScript are to exist independently of one another and "flip switches" rather than assemble by hand. For the same reason you wouldn't write code like

function makeBoldRed(el) {
    el.style.fontWeight = 'bold';
    el.style.color = 'red';
}

but rather

Element.addClass(el, CSS.ERROR_MESSAGE);

I prefer to use CSS-style selectors to fix the gap, and allow JavaScript to refer to HTML using the same syntax that its presentation counterpart does.

However, it appears that some large companies are generating HTML through JavaScript. This can work too, but in this case your goals are going to be much different. Once you start working this way, you risk accessibility and graceful degradation. You also lose the ability to develop and test presentation-layer components independently of one another, and this can lead to a poorer design or, at the very least, longer development and testing time. Another problem is debugging; if you start permitting your script to tinker with your HTML, or if your script depends on a fixed HTML structure to function properly, design changes can lead to interminable headaches when a complex script's dynamic change to the DOM structure goes undetected.

Sure, CSS queries can be performance bottlenecks. But usually they aren't, at least not when you're using a throughly-tested engine such as are available in the major JS libraries. A minor performance hit - most query engines can perform the most complex queries in under 5 ms, depending on your machine - is a small price to pay for the flexibility of modular code.

On a side note, I was most intrigued by Joel Webber's description of the Google Web Toolkit's function: to add a compile-time step to optimize and inline JavaScript code. I can appreciate that. Certainly, a well-written compiler will be able to optimize code to a greater degree than a meticulous programmer. But why Java? Why apply this essentially alien style of programming to the client? This question remains outstanding for me.