A month or two ago, I switched to using Chrome daily builds (on Debian) as my primary browser. As with most people switching to Chrome, I love the stability and speed, but there are a few extensions from Firefox I sorely miss. A major one is mozex, which allows you to edit textareas in an external editor (It’s All Text also does this). I used this for editing Gmail. I used Gnus as my primary mail and news client for years, and one of the big sticking points to switching to webmail was the anemic textarea editing interface. I’m just used to all of the trappings of Emacs — dict-mode, fill-paragraph, the keybindings, remembrance agent, etc.

Anyway, I decided to see if I could whip up a quick and dirty Chrome extension to substitute for mozex. And when I say quick and dirty, I mean it — this code would make a Perl-happy sysadmin blush. But I hacked something up in a few hours, and I thought I’d put it out there since I find it useful. Maybe someone else can run with it and make it more complete like mozex. With a few one-line edits, this extension can be made to allow the editing of virtually any textarea in any external editor. I limited it to Gmail because I don’t know if there is the possibility of resource leaks or other weird side-effects from running it more extensively. Also, it’s hard-coded to use Emacs, but you could just as easily use Gvim (have it spawn an xterm with an editor or use emacs-client or whatever).

I’ve put the extension source files up here:
http://www.thegibson.org/blog/files/emacs_chrome

Edit: see http://www.thegibson.org/blog/files/emacs_chrome/sync_ver — the original only works right on platforms like Linux due to a serendipitous interaction (see comments).
Edit2: see http://www.thegibson.org/blog/files/emacs_chrome/ba_sync_ver/ — this version uses a Chrome “browser action” rather than a “page action.” The “browser action” extension type is better suited for this. Note that some of the text below is not longer applicable to this new and simpler version, so see comments. I’ll try to make a new post soon with the updated info.

The extension comes with a Python script (you’ll need Python 2.6 to run it). The pycl.py script is a little web server running on port 9292. Run the web server and leave it in the background. Then add the extension to Chrome (go to chrome://extensions). Once you add the extension, you can load up Gmail and either compose or reply to a plain text message (not HTML). Then use the “compose in a new window” icon to open a new window, and you’ll see an Emacs 23 icon appear in the “page action” area (the upper right-hand corner of the address bar, where the SSL lock icon goes). Clicking the icon sends the contents of the text area to the Python web server, which writes it to a temporary file (using tempfile.NamedTemporaryFile) and spawns an editor. Edit your text; when you’re done, save and exit. In the meantime, the background script will start polling the web server to see if the editor has terminated. When the editor finishes, the file contents are read and sent back to Chrome, which modifies the textarea with the new contents.

Anyway, it has several major limitations — first and foremost, it only works consistently if you compose or reply in a new window (click that little diagonal arrow icon in the upper right hand corner of the message frame). Sometimes it works on the main Gmail page, but not always. Due to the hooks it uses, if you open the new window while viewing the message, and then click reply, you’ll have to type something in the textarea or un-focus and re-focus the window before it’ll “notice” the existence of the new textarea. This is a limitation of the way the extension content script is finding the textarea in the page. Maybe the fact that it only works consistently in a new window has to do with Gmail’s crazy dynamic DOM manipulation. Or maybe — perhaps even more likely — I’m missing something obvious. I’m sure someone with more Javascript / DOM / experience could probably fix this. I’ve never used Javascript in any context before, so it was an interesting experience. I basically looked at two Chrome example extensions — 1) the RSS feed subscription and 2) the Gmail checker — and munged their code and techniques together.

Changing editors
To change editors, just edit pycl.py and modify the line:

p = subprocess.Popen(["/usr/bin/emacs", f.name])

Making it work on arbitrary textareas
If you want to change the extension to work on more than just Gmail, first edit majifest.json and change the “matches” line:

"matches": ["http://mail.google.com/*", "https://mail.google.com/*", "file://*/*"],

"matches": ["http://*/*", "https://*/*", "file://*/*"],

The second matches example works on all http and https websites.

Then, in the ta_find.js file, change the getElementsByName(‘body’); line:

  result = document.getElementsByName('body');

  result = document.getElementsByTagName('textarea');

The second will find any textarea on the page (one limitation of the current incarnation is that it will only deal with the first textarea, however).

Making it not suck
This is my first foray into in-browser Javascript programming. I’m sure there’s a lot of missing exception handling in background.html when dealing with the XmlHttpRequest objects. There might be resource leaks too. And there are corner cases where it won’t get the textarea contents to send to the external editor correct (like if you only use mouse cut and paste to change the contents around without any keypresses). Also, in the Python script, there’s not much error handling either, and using a dedicated private directory (like mozex) rather than tempfile.NamedTemporaryFile is probably advisable on shared systems. Also, it’d be great if some Javascript wizard could help figure out why it only works with Gmail when you open a new window. Ideally I would have liked to add a context menu item to all textareas, but I figured it was easier to use existing Chrome extensions as templates and do it with the “page action” mechanism.

Thoughts on Javascript
Looking at the way that the Gmail checker and the RSS feed subscription work, I see an extensive use of closures and continuation-passing style asynchronous programming. Given JavaScript’s reputation, this is definitely a lot nicer and cleaner than than what I expected. Steve Yegge has also pointed out several times that JavaScript is a nicer language than people actually give it credit for, and now I know firsthand.

Recently I needed to generate binomially-distributed integers on demand for a micro-benchmark. Actually, I started with the idea of generating normally distributed numbers and rushed headfirst into reading about how to do that without thinking about the fact that I really needed a discrete distribution; later I switched distributions, but I found out it is quite easy to generate normally distributed numbers. Starting with the primitive of rand_r or drand48 (or the GNU drand48_r), we can get uniformly distributed random numbers on the interval [0, 1). If you aren't too picky about issues of numerical stability or speed, generating normally distributed numbers with uniformly distributed numbers is simple using the basic rectangular form of the Box-Muller transform. Assuming u_1 and u_2 are the uniform random numbers:

n_1 and n_2 are normally distributed. So that's nifty and really easy, but I then remembered that I needed to generate integers in the range [0, N], and the normal distribution is defined over the entire real line. I could just chop the tails off of each side of the distribution and create a truncated normal distribution, but it seemed like a better idea to just directly go with a discrete distribution.

The Binomial distribution with p=0.5 over [0, N] looks approximately normal when N becomes very large, so I decided to generate binomially-distributed integers. Even when there isn’t a simple, closed-form transform from uniformly random integers to another distribution, it seemed like you could just generate the cumulative distribution function; then you generate a uniform random number u_1 and then binary search for the greatest index i where cdf(i) <= u_1 (basically inverting the cdf). So my plan was to generate the probability mass function straight from the definition and then sum it to get the cdf. With 128-bit floating point and care in implementing the binomial coefficient (i.e. don’t perform factorials directly and divide, evaluate it a non-canceled term at a time), this worked fine for my tests the range of a few thousand. However, I quickly ran into trouble since N=72,000 in the real test. The definition of the pmf is:

Obviously you can see where this is going. That definition works somewhat well for smaller integers, but once you have quantities like 0.5^(72000), you can easily get underflows and overflows. I tried some term rearrangement, but I still ended up with a mass function that was +Inf in the middle and 0 everywhere else, which is completely worthless. Not wanting to spend a lot of time implementing this, I figured GNU R — the excellent statistical computing language/environment — could probably do this. So I ended up using R to generate the cdf (with the pbinom function), and wrote the results out to a file which I read in when I needed the cdf.

Later I looked into how R actually implements pbinom, and it delegates the problem to the Beta distribution cdf implementation, pbeta. The work in pbeta is all done by a function called bratio, which is the interesting part. The bratio function is in toms708.c. A comment at the top explains the name:

/*      ALGORITHM 708, COLLECTED ALGORITHMS FROM ACM.
 *      This work published in  Transactions On Mathematical Software,
 *      vol. 18, no. 3, September 1992, pp. 360-373z.
 */

Sure enough, you can locate “Algorithm 708; significant digit computation of the incomplete beta function ratios” in ACM’s digital library. The the bratio function computes the Incomplete beta function, and toms708.c is almost 2300 lines of fairly scary looking numerics code (lots of gotos and labels, and a fair number of magic looking constants). The original code from ACM TOMS was in Fortran, and the top of the source file says “Based on C translation of ACM TOMS 708.” They don’t explicitly say whether it was manual or if machine translation was involved at any point, but I found several comments above some variable declarations that says “System generated locals”. Googling on that phrase brings up references to f2c, the Fortran to C translator. That probably also explains the abundance of labels with names corresponding to line numbers in the original Fortran source.

Anyway, I just thought this was interesting. Numerical algorithms are fascinating: they can take a lot of care to get right and often require complex tricks to avoid over/under-flows and maintain numerical stability. Just working with floating point is perilous on its own, because there are things like cancellation errors, non-associativity of operations, non-intuitive notions of equality, etc. This is one area that wasn’t well covered in my undergraduate classes (although it might have been covered in graphics classes, which I never took). In the introductory systems class, they discussed floating point representations and had us encode/decode some numbers from scientific notation into IEEE 754, but no class really went into the pragmatics and pitfalls of using floating point numbers in mathematical algorithms. I learned about that mostly a) from reading the classic report, “What Every Computer Scientist Should Know About Floating-Point Arithmetic” and later; b) from working at the Federal Reserve in Economic Research, helping economists make use of distributed computing with their simulations and such.

Through my experience at the Fed, I gained a lot of insight into just how much effort it takes to do correct numerical algorithms, let alone fast ones. Of course, most of the economists relied on highly-tuned primitive libraries like IMSL, but it still takes work to make sure your own calculations (built on top of those primitives) don’t introduce accumulating error. Fortran and Matlab were, by far, the most popular languages, with a few economists choosing C or Mathematica. Anyway, this is a deep and interesting area.

As an aside, it’s not too hard to generate Zipf distributed numbers using a technique called “Rejection-Inversion” (it doesn’t require generating the cdf and searching). Take a look at FastBit which has an implementation in twister.h

/// Discrete Zipf distribution: p(k) is proportional to (v+k)^(-a) where a
/// > 1, k >= 0.  It uses the rejection-inversion algorithm of W. Hormann
/// and G. Derflinger.  The values generated are in the range of [0, imax]
/// (inclusive, both ends are included).

The referenced paper is “Rejection-inversion to generate variates from monotone discrete distributions”; the code to generate Zipf-distributed integers is only about 20 lines of C++, and it’s actually understandable.

A while ago, I published a paper describing an abstract distributed programming model – and middleware providing the abstractions of said model to applications – for a class of continuous stream analysis programs. I named the system Stampede^RT, which seemed like a good name at the time and was neatly abstracted underneath a short LaTeX macro. Unfortunately, I may have fallen into a naming trap: the fact that the name contains a superscript is problematic for web search. Now it is unclear how to search for my system. In the abstract, the name got transliterated as Stampede^RT (since the caret provides superscripting in LaTeX math mode). In other places, it may appear as “Stampede RT,” “StampedeRT” or “Stampede-RT.” Although Google and other search engines are generally pretty good at still finding things with similar names, it just makes life more difficult (and this whole issue is easily avoidable).

Search-engine ranking and friendliness are important for software projects, research efforts, businesses, etc. I’d been thinking of some key traps for future reference:

1. Unusual/extended characters – in some cases, they may be completely appropriate (e.g. “Improving flow analyses via ΓCFA: Abstract garbage collection and counting”), but it is probably best to avoid naming a project after your favorite Sanskrit phrase.
2. Sub/superscripts or various font manipulations – Stampede^RT could have just been StampedeRT.
3. Aliasing – don’t give your project the same name as another, higher-profile project/business/entity – big enough projects can get away with this (e.g. The R Project for Statistical Computing is the first hit if you Google just the letter R).

I’m sure other people have probably blogged/posted/ranted about this too, but this is just what I came up with off the top of my head when I first realized my folly.

slashdotv(“First post!”);

Yes, a blog. Now, people who know me in real life will probably say that I’m one of the last people they’d expect to start a blog. I’ve frequently ranted about how blogs are stupid, for hipsters, where people blather on about mundane details of their lives, etc. I don’t like social networking sites or anything similar, and I value my privacy. I also don’t like to reveal personal details of my life, particularly on the Internet. But this isn’t going to be that kind of blog.

I do, however, value technical blogs as a source of current information on software development, computer hardware, CS research and other things of that nature. In addition, blog commenters often provide valuable pointers to related work and feedback on ideas. Therefore, I decided to create a simple blog where I could post about random technical stuff that is either relevant to my research or just personally interesting.  Occasionally I may just rant on a related topic, hence the name /dev/rant.