Older blog entries for mbrubeck (starting at number 112)

Compleat: Programmable Completion for Everyone

Compleat is an easy, declarative way to add smart tab-completion for any command-line program. For a quick description, see the README. For more explanation and a brief tutorial, keep reading...


I'm one of those programmers who loves to carefully tailor my development environment. I do nearly all of my work at the shell or in a text editor, and I've spent a dozen years learning and customizing them to work more quickly and easily.

Most experienced shell users know about programmable completion, which provides smart tab-completion for for supported programs like ssh and git. (If you are not familiar it, you really should install and enable bash-completion, or the equivalent package for your chosen shell.) You can also add your own completions for programs that aren't supported—but in my experience, most users never bother.

When I worked at Amazon, everyone used Zsh (which has a very powerful but especially baroque completion system) and shared the completion scripts they wrote for our myriad internal tools. Now that I'm in a startup with few other command line die-hards, I'm on my own when it comes to extending my shell.

So I read the fine manual and started writing my own completions. Over on GitHub you can see the script I made for three commands from the Google Android SDK. It's 200 lines of shell code, fairly straightforward if you happen to be familiar with the Bash completion API. But as I cranked out more and more case statements, I felt there must be a better way...

The Idea

It's not hard to describe the usage of a typical command-line program. There's even a semi-standard format for it, used in man pages and generated by libraries like GNU AutoOpt. Here's one for android, one of the SDK commands supported by my script:

   android [--silent | --verbose]
   ( list [avd|target]
   | create avd ( --target <target> | --name <name> | --skin <name>
                 | --path <file> | --sdcard <file> | --force ) ...
   | move avd (--name <avd> | --rename <new> | --path <file>) ...
   | (delete|update) avd --name <avd>
   | create project ( (--package|--name|--activity|--path) <val>
                     | --target <target> ) ...
   | update project ((--name|--path) <val> | --target <target>) ...
   | update adb )

My idea: What if you could teach the shell to complete a program's arguments just by writing a usage description like this one?

The Solution

With Compleat, you can add completion for any command just by writing a usage description and saving it in a configuration folder. The ten-line description of the android command above generates the same results as my 76-line bash function, and it's so much easier to write and understand!

The syntax should be familiar to long-time Unix users. Optional arguments are enclosed in square brackets; alternate choices are separated by vertical pipes. An ellipsis following an item means it may be repeated, and parentheses group several items into one. Words in angle brackets are parameters for the user to fill in.

Let's look at some more features of the usage format. For programs with complicated arguments, it can be useful to break them down further. You can place alternate usages on their own lines separated by semicolons, like this:

  android <opts> list [avd|target];
android <opts> move avd (--name <avd>|--rename <new>|--path <file>)...;
android <opts> (delete|update) avd --name <avd>;

...and so on. Rather than repeat the common options on every line, I used a parameter <opts>. I can define that parameter using the same usage syntax.

  opts = [ --silent | --verbose ];

For parameters whose values are not fixed but can be computed by another program, we use a ! symbol followed by a shell command to generate completions, like this:

  avd = ! android list avd | grep 'Name:' | cut -f2 -d: ;
target = ! android list target | grep '^id:'| cut -f2 -d' ' ;

And any parameter without a definition will just use the shell's built-in completion rules, which suggest matching filenames by default.

The README file has more details of the usage syntax, and instructions for installing the software. Give it a try, and please send in any usage files that you want to share! (Questions, bug reports, or patches are also welcome.)

Future Work

For the next release of Compleat, I would like to make installation easier by providing better packaging and pre-compiled binaries; support zsh and other non-bash shells; and write better documentation.

In the long term, I'm thinking about replacing the usage file interpreter with a compiler. The compiler would translate the usage file into shell code, or perhaps another language like C or Haskell. This would potentially improve performance (although speed isn't an issue right now on my development box), and would also make it easy for usage files to include logic written in the target language.

Final Thoughts

Recently I realized that parts of my work are so specialized that my parents and non-programmer friends will probably never really get them. For example, Compleat is a program to generate programs to help you... run programs? Sigh. Well, maybe someone out there will appreciate it.

Compleat was my weekends/evenings/bus-rides project for the last few weeks (as you can see in the GitHub punch card), and my most fun side-project in quite a while. It's the first "real" program I've written in Haskell, though I've been experimenting with the language for a while. Now that I'm comfortable with it, I find that Haskell's particular combination of features works just right to enable quick exploratory programming, while giving a high level of confidence in the behavior of the resulting program. Compleat 1.0 is only 160 lines of Haskell, excluding comments and imports. Every module was completely rewritten at least once as I tried and compared different approaches. This is much less daunting when the code in question is only a couple dozen lines. I don't think this particular program would have been quite as easy to write—at least for me—in any of the other platforms I know (including Ruby, Python, Scheme, and C).

I had the idea for Compleat more than a year ago, but at the time I did not know how to implement it easily. I quickly realized that what I wanted to write was a specialized parser generator, and a domain-specific language to go with it. Unfortunately I never took a compiler-design class in school, and had forgotten most of what I learned in my programming languages course. So I began studying parsing algorithms and language implementation, with Compleat as my ultimate goal.

My good friend Josh and his Gazelle parser generator helped inspire me and point me toward other existing work. Compleat actually contains three parsers. The usage file parser and the input line tokenizer are built on the excellent Parsec library. The usage file is then translated into a parser that's built with my own simple set of parser combinators, which were inspired both by Parsec and by the original Monadic Parser Combinators paper by Graham Hutton and Erik Meijer. The simple evaluator for the usage DSL applies what I learned from Jonathan Tang's Write Yourself a Scheme in 48 Hours. And of course Real World Haskell was an essential resource for both the nuts and bolts and the design philosophy of Haskell.

So besides producing a tool that will be useful to me and hopefully others, I also filled in a gap in my CS education, learned some great new languages and tools, and kindled an interest in several new (to me) research areas. It has also renewed my belief in the importance of "academic" knowledge to real engineering problems. (I've already come across at least one problem in my day job that I was able to solve faster by implementing a simple parser than I would have a year ago by fumbling with regexes.) And I'll be even happier if this inspires some friends or strangers to take a closer look at Haskell, Parsec, or any problem they've thought about and didn't know enough to solve. Yet.

Syndicated 2009-10-30 07:00:00 from Matt Brubeck



This site is powered by Jekyll and based on styles and markup by Tom Preston Werner. Comments are run by Disqus and hosting is by Dreamhost.

Before starting this site, I had an Advogato diary for writing about software. I also have a personal journal (mostly interesting to my friends and family).

Syndicated 2009-10-28 07:00:00 from Matt Brubeck

11 Mar 2009 (updated 5 May 2010 at 22:24 UTC) »

position:fixed in Android Webkit

Good news for mobile web developers! In the latest development build of Android ("cupcake"), WebKit supports iPhone touch events and CSS3 animations/transforms. This means that Richard Herrera's iPhone fixed positioning hack will soon work on Android too.

The WebKit CSS Animation demos also work, but lack of hardware acceleration in Android makes them painfully slow compared to the iPhone.

5 Mar 2009 (updated 5 Mar 2009 at 22:04 UTC) »

Async Map and Fold in JavaScript

My latest experiment is an implementation of asynchronous/parallel "map" (and other array functions) in JavaScript and Oni. Oni is a "structured concurrency language" embedded in JavaScript. For my source code and commentary, see oni-map at GitHub. You can leave comments at GitHub too.

All this time reading Real World Haskell must really have warped my brain if a simple testing framework for a JavaScript program has got me thinking about higher-order functions and concurrency semantics...

Bash Completion for the Google Android SDK

If you're developing for Android, try out the bash script I wrote to add tab-completion for the "adb" command-line tool.

MapReduce with Parallel Make

Ted Gould’s post about transcoding music files using Make got me thinking about combining Make and RecordStream into a barebones MapReduce framework. As a demonstration, I wrote a partial solution to Tim Bray’s Wide Finder challenge, to calculate hit counts from web server logs.

More details (and code).

24 Nov 2008 (updated 24 Nov 2008 at 23:08 UTC) »

The Timeless Way of Building: Diagnosis and Repair

Architect Christopher Alexander's A Pattern Language is well known among programmers as the inspiration for the Design Patterns school of thought, but for some reason his other books are less widely read. My mother and father are both architects—"real" ones, not "software architects." :) My own amateur interest in the subject led me to read several of Alexander's books over the past couple of years.

The Timeless Way of Building is the first volume of an open-ended series. (A Pattern Language is the second.) It is in this book that Alexander first lays out the idea of a pattern language. More importantly, he explains an entire theory and practice of design and construction, of which the pattern language is only one piece.

Another piece of the Timeless Way is the practice of diagnosis and repair. Rather than a detailed plan of future projects, Alexander prefers to maintain a diagnosis of current problems. Each new project must be targeted at fixing these existing problem in the system: "At every moment we use the defects of the present state as the starting point for the definition of the new state" (p. 485). Alexander's goal is to create a type of spontaneous growth and order that is possible when change is incremental and decision-making authority is decentralized.

Alexander was hired to produce a new type of master plan for the University of Oregon campus. The result was published as the third volume in the "Timeless Way" series: The Oregon Experiment. In it, he writes again about diagnosis and repair:

It is still not clear where global order will come from, without a master plan.… How is the problem solved in an organism? Essentially, the problem is solved by a process of diagnosis and local repair.… The master plan tells us what is right for the future. The diagnosis tells us what is wrong for the present. (p. 146–148)

In software, the same problems and conclusions have led to "agile" processes, which emphasize incremental change and flexible planning. But I haven't seen any software companies adopt a consistent practice of "diagnosis"—keeping track of what's wrong or unsatisfactory with the current system. This extends beyond defect tracking; it should include a constantly updated list of code that, although it works, is hard to understand, difficult to change, or otherwise likely to cause problems. (This should be easy to generate—every programmer knows certain parts of their code base that they dread working on for one reason or another.) This knowledge can then guide new development to include "repair" and address such problems before they become defects. I've applied this on a small scale to my own work, and now I wish I had used it at Amazon, where my team spent much more time maintaining and improving old code than writing new code.

Flip Video Ultra on Linux

My Flip video camera arrived yesterday, and I'm quite happy with it. It does everything it's supposed to: starts up fast, records and plays back through an astoundingly simple interface, and mounts as a USB mass storage device. The videos play back perfectly on my Ubuntu 7.10 system, and Kino can import and edit them if ffmpeg is installed.

I did have some problems using the camera with a Windows XP laptop. The Windows program stored on the camera failed to start up, saying that "E:\SYSTEM\VIEWER\PD\settings\pathsInfo.txt does not contain a valid list." The firmware updater from the Flip web site failed with a similar error. Finally I found the Flip Video Program installer, which fixed both of those problems. (It took me a while to figure this out, so I'm documenting it here in case other Flip owners have the same problem.)

26 Nov 2007 (updated 26 Nov 2007 at 16:43 UTC) »

PDF on Kindle

I've seen plenty of good commentary on the Amazon Kindle. Robert Love's hands-on review and follow-up cover both Linux-hacker and regular customer views. But there's one question that I haven't seen answered elsewhere: Why doesn't the Kindle support PDF natively?

I think the answer is simple: The Kindle's 800×600 e-ink screen has too few pixels to render a typical PDF file readably, and its refresh rate is too slow for comfortable scrolling. The only practical solution for most PDFs is to extract the text and convert it to a reflowable format like HTML (which Kindle users can do with Amazon's $0.10 wireless service or free PC-based service). The US$700 iLiad (with 64% more pixels) is much better for PDF reading, but will still run into trouble with some files. It seems that the current generation of ebook readers comes with a decision—cheap, e-ink, or PDF: choose any two.

The refresh problem is one reason I'm not sold on e-ink. I'm curious to compare the Kindle screen to my XO laptop, which seems like an interesting compromise between normal LCD and e-ink displays.

Disclaimer: I work for Amazon, but I don't know anything about the Kindle except what I learned from the user's guide and from playing with one at the office.

27 Aug 2007 (updated 28 Aug 2007 at 15:16 UTC) »


Joey wonders why vim addons are not enabled by default using the new Debian infrastructure.

For single-user systems, Joey is right: enabling addons by default would be best. But for multi-user systems, I think disabled-by-default is better. Otherwise, installing an add-on would change vim's behavior unexpectedly for all users. (Unlike a daemon, which runs once per system; a vim addon is run by each user, every time they start vim.) This is especially bad because vim users tend to have carefully personalized configurations.

Should the defaults cater to multi-user systems at the expense of single-user ones? Probably not, since admins of large multi-user systems are generally willing and able to figure out how to change their configurations, while many single-user machine owners need something that "just works". Perhaps the default configuration should load all installed addons, but local admins should be able to easily change this to load only addons enabled by the current user.

103 older entries...

New Advogato Features

New HTML Parser: The long-awaited libxml2 based HTML parser code is live. It needs further work but already handles most markup better than the original parser.

Keep up with the latest Advogato features by reading the Advogato status blog.

If you're a C programmer with some spare time, take a look at the mod_virgule project page and help us with one of the tasks on the ToDo list!