Moore's Treadmill

Early in my PhD, I told my advisor I had implemented a particular cryptographic algorithm with a tolerable running time. It wasn’t that fast, but I figured within 2 years, microchips would be twice as powerful, so my code might be practical even on handheld devices.

He replied: "No. Then they’ll halve the power consumption to double the battery life." Or they’ll want to run it on yet smaller devices. Laptops, phones, smart cards. I still had plenty of work to do.

For me, user interfaces are trapped on the same treadmill.

Less is more

Not so long ago, my desktop had a 14-inch CRT display, a lonely and lowly processor clocked at 200MHz, a few gigs of hard disk space, and a 14.4k net connection. The dearth of screen real estate favoured spartan user interfaces, the CPU struggled unless tools were quick and nimble, and the cramped conditions of the hard disk and net connection favoured good things in small packages.

For example, when the time came to take sides in the text editor holy war, I chose vi because it would only take several minutes to grab a few hundred kilobytes. Emacs was over 6 megabytes.

Now I often work at a PC sporting multiple cores, each over 20 times faster than my old workhorse. I have multiple monitors, each so large that I turn my head to look at different parts of a screen. Network latency is low, and bandwidth is high.

Yet I remain minmalist. Indeed, I keep finding new ways to trim the fat, despite having ample space. For instance, my first web browser had big buttons and a plethora of bars: title bar, menu bar, bookmarks bar, status bar, location bar, etc. Today, even though I can afford extra fluff, my primary browser shows little apart from the webpage: a bar for tabs (itself a space-saving measure over multiple windows), a single textbox, and a handful of buttons.

I chose my style partly because I’m a programmer to the bone: my drive to automate, simplify, and optimize carries over from coding to real life. However, there is a more compelling reason.

Technological advances mean my laptop can handle tasks that once required a desktop. But the laptop screen is even smaller than my old monitor. The net connection can be spotty, especially via tethering or a smartphone WiFi hotspot. The CPU often underclocks to save battery, and moreover, I fritter away cycles on fripperies such as visual effects: I’m a Compiz plugin junkie. I therefore encounter the same problems I faced over a decade ago.

A Voyage to Lilliput

Beyond laptops, we have netbooks, tablets, and smartphones. The world is getting smaller. Being a geek means I’ll attempt text editing, gaming, programming, etc. even as devices keep shrinking, bringing new user interfaces challenges. My current extreme case is my Nexus One, with its 3.7 inch display and no keyboard.

Rather than work on the phone directly, I ssh to a more powerful computer via ConnectBot.

In the past I praised Bash one-liners. Shelling in from a smartphone drove me to appreciate Bash one-letter aliases. I’ve grown accustomed to using them on all computers. Some favourites:

alias c=cd
alias ..="cd .."
alias v=vim
alias g=git
alias l="ls -CF --color=auto"
alias s=sudo
alias k=colormake
alias rm='echo mv to /tmp instead'

(The "rm" alias trains me to avoid this command. See "Accidents Will Happen" in The UNIX-HATERS Handbook.)

Editing is unpleasant but bearable. In these circumstances, I feel Vim’s single-letter commands work in its favour, as does its modal nature. Also double-tapping the terminal brings up an "Esc" button, which suits Vim beautifully.

I don’t intend to code from my phone often as it’s like eating with tweezers. Though for fun, I followed through a suggestion in my last post and developed a J one-liner to sum the primes less than 100 using only a ConnectBox session on my phone. Soon I had:

   +/p:i.p:^:(_1)100
1060
   +/i.&.(p:^:_1)100    NB. Cooler version.
1060
   v=:[:+/i.&.(p:^:_1)  NB. Tacit verb definition.
   v 100
1060

J and I

For years, I’ve been meaning to investigate the APL programming language family. Months ago, I finally leafed through a few introductions to the new and improved APL known as J.

I liked what I saw. I enjoy paring down C code, but J makes my best efforts look as verbose as a legal contract. Introductory J examples are already cryptic enough to induce watering in the untrained eye. In the right hands, a J program can be compressed so densely that it threatens to collapse into a black hole of inscrutability.

I’ve heard about an obfuscated C tattoo, as well as a Lisp tattoo. They should have gotten J tattoos! Instead of Hello World or the Fibonacci sequence, why not sport a terse program that solves a Sudoku, or finds a QR decomposition of a matrix?

More generally, J appears to be ideal when source size matters most. For example, programming via a smartphone with a tiny screen and keyboard.

A day at play with J

J systems are freely available, but I reasoned I’d get a better feel for the language by writing my own interpreter. Thanks to J’s elegant design, I soon got the celebrated "mean=:+/%#" example working. That was enough to gain an appreciation (but also a little contempt) for J’s simple grammar, array handling, and above all, compact notation. A J symbol is worth a thousand machine words. See my J notes.

I kept picking at it for a while, but I think I’ll stop soon. It’d take substantial effort to implement types apart from doubles, not to mention error handling, memory management, arrays with axes of zero length, and fills.

Git repository: a primordial J interpreter.

The timeless beauty of shell scripts

Long ago, Doug McIlroy wrote: “This is the Unix philosophy: Write programs that do one thing and do it well. Write programs to work together. Write programs to handle text streams, because that is a universal interface.”

Years later, Rob Pike observed: “Those days are dead and gone and the eulogy was delivered by Perl.” His statement mostly stands, except Python is the new Perl.

I refuse to abandon the old ways. So when a friend pointed me to the intriguing Python Challenge, I avoided Python as much as I could. Instead, I used the Bash shell to string together special-purpose tools.

The FAQ states the purpose of the challenge is to “provide an entertaining way to explore the Python Programming Language”, and “demonstrate the great power of Python’s batteries”. However, I feel it is better suited for training shell script muscles: most of the problems are of the one-shot trivial variety that suit Unix tools.

A full-featured language is often overkill. Abraham Maslow’s quote comes to mind: “It is tempting, if the only tool you have is a hammer, to treat everything as if it were a nail.” I don’t mean to disparage Python, but I feel shell scripts are often overlooked and under-appreciated, especially as they are so accessible. Technically, you’re already shell programming when you run a program from the command-line. Why not learn a bit of Bash or similar, and increase the power available at your fingertips?

Brevity is the soul of wit

While general-purpose scripting languages have their place, judging by the posted solutions, for typical riddles in the Python Challenge, a short Python script is often outdone by a shorter still Bash incantation. In fact, in the first challenge you can stay in your shell. Did you know Bash natively handles (fixed-width precision) arithmetic? For example:

$ echo $((2**42))

Naturally, if arbitrary precision were needed, we could invoke a specialized tool:

$ echo 10^100 | bc

Humble Unix tools yield the most succint solution for several challenges. For example, a Caesar shift is probably terser with tr than any popular language:

$ tr a-z l-za-m

Or extracting lowercase letters from a file:

$ tr -cd a-z

When regular expressions are involved, even though the code may look similar, the old guard such as awk, sed, and grep that feature regularly in Bash scripts have an inherent advantage over Python (and Perl, PHP, Ruby, …). Python takes exponential time to match some regular expressions whereas the classic Unix tools take polynomial time to match the same expressions.

On the downside, Bash makes some tasks tiresome. I can’t think of an easy way to convert an decimal number to an ASCII character. This Bash FAQ suggests the cumbersome:

$ for a in 66 101 110; do printf \\$(printf '%03o' $a); done; echo

Another chore is repeating a character a given number of times. Other than a loop, perhaps the easiest hack is something like:

$ printf "%042d" 0 | tr 0 x

A tiny elegant Haskell solution exists for problem 14, thanks to the transpose function and the language’s concise notation for recursion and composition. A search revealed Bash fans often employ a simple but tedious Awk script for matrix transposition, suggesting a Bash solution is necessarily significantly longer.

Happily, these blemishes are dwarfed by the successes of the Unix philosophy. More than once, my script has been simpler and briefer than any other posted solution because the complexity is hidden within a tool that does one thing, and does it well. My proudest achievement is a one-liner to compute the look-and-say sequence [hint: uniq -c].

Chinese Input

Google Translate supplies a clumsy but straightforward means for entering Chinese characters with a US keyboard, especially for those learning the language. Simply type the English meaning, and copy the result. You can check the character is indeed the one you want by clicking on "Show romanization", or on the speaker icon to hear a synthesized reading.

However, sometimes I have a particular character in mind. A short-term solution is to use an online rendition of a traditional dictionary ordered by radical and stroke count, or a pinyin dictionary. Additional speed and convenience requires investment; one must learn one of the many fascinating methods for entering Chinese characters on a computer.

I’ve read that the Wubizixing input method is fastest, though as one might expect, it requires the most investment. Proficiency demands much practice with a suitably annotated keyboard.

For now, I’ve opted for the Wubihua method, which mimics how humans write characters. It may be slower, but it can be learned quickly. Also it applies when sending Chinese text messages on mobile phones.

I supplement Wubihua with a pinyin method, as I’m practically illiterate in Chinese.

Chinese input in Linux

To setup Chinese input methods in Ubuntu, I installed the scim and scim-pinyin packages, then modified my .xsession as follows. I prepended:

export XMODIFIERS="@im=SCIM"
export GTK_IM_MODULE="xim"

and appended:

scim -d

after which pressing Ctrl+Space toggles Chinese input.

"Stroke 5" is Wubihua mode. Stroke types are mapped to 5 keys along the bottom row. From right to left:

/: | (vertical; top-to-bottom)

.: \ (downwards left-to-right)

,: / (downwards right-to-left)

m: - (horizontal; left-to-right)

n: other stroke types, e.g: 乙

Perhaps one can remember this as follows: 乙 looks like a rotated N. A lowercase M takes more horizontal space than most letters, so it corresponds to the horizontal stroke. On the next two keys, the less-than and greater-than signs point left and right, so they correspond to the left and right downward strokes. Lastly, the stem of the question mark suggests a vertical stroke.

Although the pinyin method is found in the Simplified menu (智能拼音; "smart pinyin"), it also offers Traditional characters. I originally learned zhuyin (aka bopomofo), a more traditional pronounciation-based method for producing Traditional characters, but it is ill-suited for a US keyboard. Fortunately converting from zhuyin to pinyin is trivial.

Chinese to English

In a pinch, I’ll use Google Translate to learn Chinese phrases. However, browser plugins are much handier; see the Chrome Zhongwen extension and the Firefox Perapera-kun add-on.

Stack-smashing remains fun and profitable

Buffer overflows have long been a rich source of security vulnerabilities. Unfortunately, its popularity led to a family of knee-jerk reactions: W^X; Data Execution Prevention (DEP); the NX (No eXecute) bit; executable space protection.

As the terms suggest, code is divorced from data. For example, an operating system may forbid execution of any instructions lying in the stack. A simple buffer exploit now causes the program to halt, rather than execute injected code.

My knee-jerk counter-reaction was suspicion and hostility. Shouldn’t we be focusing on the causes of buffer overflow disease, and not its symptoms? Also, some of the most beautiful and fundamental results in computer science involve feeding a Turing machine to a Turing machine. Data is code and code is data.

Self-modifying code considered awesome

Self-modifying code is fascinating by virtue of its self-referential nature, but it is not just a pretty face: it has practical applications. Just-in-time compilation is perhaps the best-known example. However, I find it most useful for nested functions in C.

Thomas Breuel describes how a C compiler can be modified to allow nested function via trampolining. Briefly, for each nested function, we generate its code as usual, but we also add a local variable to the scope where it is defined: we add an array of bytes, whose contents are opcodes that simply rig a pointer to make it look like we’re in the current stack frame before jumping to the nested function.

Standard C code expecting a function pointer still works when passed a pointer to this array. When they call the function pointer, they jump to the array, where they run the stack-frame-rigging code before continuing on with the call. By magic, the code in the nested function executes within the desired scope. One pointer does the work of two.

Observe we require the array to be local and populated at runtime, because only then do we know the address of the current stack frame. We cannot setup this tomfoolery in advance. In other words, we must execute code we just placed on the stack.

Like duct tape, treating data as code deftly solves a host of problems. W^X and friends block this avenue, or at least make it less efficient. Breuel writes:

"There are, however, some architectures and/or operating systems that forbid a program to generate and execute code at runtime. We consider this restriction arbitrary and consider it poor hardware or software design. Implementations of programming languages such as FORTH, Lisp, or Smalltalk can benefit significantly from the ability to generate or modify code quickly at runtime."

Return-oriented programming

Hovav Shacham recently filled me in on return-oriented programming. I’m a fan. I now have more than gut feelings to support my stance. I can gloat and say "I told you so".

Return-oriented programming skirts around stupid restrictions via one level of indirection. Instead of putting code in the stack, we put pointers to the code in the stack. We choose to point at code that soon runs into a return instruction. On typical architectures, a return instruction increments the stack pointer before jumping to the address to which it points. Hence the stack pointer becomes a sort of indirect instruction pointer: we run a snippet of code until it hits a return statement, which causes us to run the next snippet of code, and so on.

Thus using a compromised stack, attackers cleverly glue together snippets of code in executable parts of memory, such as the BIOS or the standard C library. On popular systems there’s enough stuff to do anything. Tools for automating the process exist; namely, you can write source and have it compile to a sequence of cherry-picked memory addresses. It’s the return-to-libc attack on steroids.

I had hoped return-oriented programming could cut both ways; does it allow self-modifying code even in the presence of an NX bit? Sadly, on further reflection, return-oriented programming appears to have no legitimate uses. Arbitrary code execution is only possbile within the stack frame of a function we control, and, for example, we still have no means of adjusting the static link pointer when qsort() invokes our nested function. Hopefully I overlooked a sneaky trick.

In short, thanks to return-oriented programming, executable space protection is a minor inconvenience for the bad guys, and a major inconvenience for the good guys.

Self-publishing with CreateSpace

From time to time, somebody sends me a kind email saying that they only truly appreciated Git after encountering my Git guide. One such reader had already bought a few Git books, and he suggested I should therefore turn my website into a book.

I had idly thought about doing this, but why bother? Was: FREE, Now: $9.95!? However, the email made me realize that some seek information by buying books first, then look around online if they want more. Making a book out of my guide might be a good idea after all: I’m not trying to sell it to people who already know they can read it for free; rather, I’m aiming for those who might not otherwise find it until much later because they visit bookshops before search engines.

CreateSpace

Because the most renowned technical publishers already offered books on Git, I chose to self-publish on CreateSpace. Their tools are free, and they list your work on Amazon (who owns CreateSpace). I’d love to have bricks-and-mortar bookshops carry copies of the book too, but an Amazon listing should be enough for now.

In a brief search, I found controversy over CreateSpace ISBNs, but Richard Sutton’s post reassured me: firstly, for my book, the issues stemming from CreateSpace being the registered owner of the ISBN are irrelevant, and secondly, if you really want you can have an ISBN registered in your name (but you’ll have to buy it yourself).

The whole process is not quite free. After submitting your PDF file, you must order a proof copy. If you find errors, you submit a corrected PDF, and repeat. I made a stupid mistake the first time, so I went through this cycle twice and finished down about 16 bucks.

It’s not all bad though. I was surprisingly pleased to hold my book in my hand, as it felt like I had accomplished something. Also, in print form, the same old sentences become more authoritative and strangely convincing. Online, they look like stuff that some guy posted on some random website.

Preparing the book took much longer than expected. I had mentioned to a reader that I was considering making a book. I tried follow advice he gave me so it would look less amateurish. I cut a chapter and an appendix. I added an index. I renamed headings so they were more descriptive. I replaced all variables (e.g. "SHA1_HASH") in the command-line examples with values (e.g. "1b6d"). I selected a 6 inch by 9 inch form factor, which meant I had to shorten some lines to get them to fit. While doing all this, I found poorly spelled words, poorly worded paragraphs and poorly organized sections. I doubt I caught them all.

To avoid further delays, I used their Easy Cover Creator. Perhaps I’ll revisit this eventually, as I want a more spartan look: something like Kernighan and Ritchie’s "The C programming language". Or perhaps a sort of cheat sheet so the book would be useful even while shut.

I set the price to $9.95 USD, which means I get 2 bucks or so per sale. I considered a lower price, but I’ll be lucky to make my $16 back as it is! Still, it ought to be low enough that a buyer won’t be too annoyed when they find out the material is freely available on my homepage. (I would have linked to the free version from the book description, but this is forbidden.)

AsciiDoc, xsltproc, fop

I had some trouble with my tool chain that produces PDFs from text files. AsciiDoc produces a DocBook XML file out of the source text, which xsltproc turns into an XSL-FO file, which fop renders into a PDF. The design of the various formats probably have technical merit, but I found it difficult to figure out how to get what I wanted.

For example, I replaced variables with values because I could not italicize them easily with AsciiDoc. The only methods I discovered destroyed the natural beauty of the source text.

It seems the smaller the detail, the larger the effort required to tune it. Changing page sizes, font sizes and chapter heading styles was easy enough to figure out, but I still don’t know the right way to insert a blank page after the front matter so the first chapter starts on an odd page. I gave up editing some XSL file or other. Instead, I scripted a fragile search-and-replace on the XSL-FO output.

Nonetheless, I stand by my choices. There’s something appealing about source files which resemble old-school text files. Also, once the configuration nightmare is over, editing is simple: I can use any text editor, and the tool chain will automatically produce several HTML versions as well as a reasonable PDF for a book.

Shameless plug

I couldn’t possibly end this post without a link to my book: "Git Magic". It’s the most important book you’ll ever have, or my name is not Winston! Buy it now!

Nginx and FastCGI

One perk I miss from my first days of grad school was my office computer with a permanent IP address. I could run all sorts of servers. (Later, the environment became harsher because unlike me, many of us ran Windows, but like me, they did not know how to do so securely. The IT team restricted most ports as the first line of defence, though you could ask for exceptions. Hopefully they didn’t tighten control further after I graduated.)

Wanting to be cool, I experimented with PHP when it started becoming popular. Until then, I had only dabbled with CGI programs in compiled languages. PHP was intoxicating. A Common Gateway drug, so to speak. In those Web 1.0 days, dynamic webpages were so easy and fun to make with PHP that I overdosed.

Years later I finally admitted to myself that my content was static apart from a few needless gimmicks, and this was unlikely to change. Using PHP was only increasing the CPU load. It didn’t matter because I received few hits, but it offended me as a computer scientist. I sobered up and returned to vanilla HTML.

I’ve been thinking how I might write a web application today, and I realized I’ve come full circle. I’ve lost my taste for LAMP stacks at a time when they are more widespread than ever, and once again espouse compiled languages.

Nginx

Firstly, I’ve moved on from Apache, which was once my favourite web server. I used to watch Netcraft's market share graphs so I could cheer on Apache against commercial products. But one day, I noticed a newcomer on the graphs. A strange jumble of letters: "nginx". I couldn’t resist looking it up.

Nginx shows how powerful pure unadulterated C can be in the right hands. Written by Igor Sysoev, this webserver runs on numerous platforms, hardly using any memory even as it handles thousands of requests at light speed. Nginx has somehow dodged Jeff Darcy’s Four Horsemen of Poor Performance.

Nginx cannot do CGI, but it can do FastCGI, which is a plus. Instead of spawning a new process for every request, FastCGI spawns a long-lived program once, which communicates with the webserver when necessary, possibly over a network. Of course, this program can run threads of its own if desired.

An advantage of LAMP stacks was that scripts could run without requiring a new process or thread. FastCGI puts all languages on the same footing. In fact, FastCGI is more flexible: for example, you can restart FastCGI programs independently of webservers. Perhaps this is why some run PHP via FastCGI.

Compiled languages

I prefer a compiled language to a scripting language like PHP because I crave speed and scalability. Also, one feature of PHP is useless to me: I discovered I lack the discipline to mix code with HTML. At first I found it was convenient, but eventually my webpages became hard to maintain. I now insist on strict separation between languages: my CSS, JavaScript, HTML, and whatever else ideally reside in distinct files.

Also, now that JavaScript is ubiquitous, it seems best to push as much work as possible to the client side: the FastCGI should do the minimum possible and supply its results (perhaps in JSON) to JavaScript which then plays with the data using the client’s CPU. This diminishes the need for a language designed to mingle with HTML.

Running a web application with a scripting language purportedly allows rapid prototyping, but it seems the only drawback to a compiled language is a compilation step and a FastCGI program restart. This is negligible provided your language has a fast compiler (like C and Go). Besides, I bet much of the development cycle involves presentation tweaks, that is, edits to CSS, HTML, and JavaScript: not the compiled language.

The L and M of LAMP

I’d still run my servers on Linux. I’ve had good results with it so far. As for MySQL, I cannot say, having never experimented much with databases. Its reputation seems solid enough.

How-to

On the latest Ubuntu, you’ll need to install the packages nginx, spawn-fcgi, libfcgi-dev. Then edit the nginx configuration file in /etc/nginx/sites-available/default. In the server clause, add something like:

location = /test {
  fastcgi_pass 127.0.0.1:9000;
  fastcgi_param QUERY_STRING $query_string;
}

The file /etc/nginx/fastcgi_params contains other parameters you might want to pass. Restart nginx, by running for example:

$ sudo /etc/init.d/nginx restart

Visiting http://localhost/test should result in a 502 error because no FastCGI program is running yet.

Let’s fix this. In C, I recommend using fcgiapp.h and not fcgi_stdio.h; it’s not much more trouble, and you avoid conflicts with the standard stdio library.

#include <fcgiapp.h>

int main() {
  FCGX_Stream *in, *out, *err;
  FCGX_ParamArray envp;
  while (FCGX_Accept(&in, &out, &err, &envp) >= 0) {
    char *q = FCGX_GetParam("QUERY_STRING", envp);
    FCGX_FPrintF(out, "Content-type: text/plain\r\n\r\n");
    if (!q) {
      FCGX_FPrintF(out,
          "no query string: check web server configuration\n");
    }
    FCGX_FPrintF(out, "Query: '%s'\n", q);
  }
  return 0;
}

Compile your code:

$ gcc a.c -lfcgi

Then spawn the binary on your machine on port 9000:

$ spawn-fcgi -a 127.0.0.1 -p 9000 -n -- a.out

Test it by visiting http://localhost/test?example.

In a real application, you might want to run the binary as a daemon, and place the process ID in a temporary file for easy access:

$ spawn-fcgi -a 127.0.0.1 -p 9000 -P /tmp/pid -- a.out

I had planned to continue this post by writing about embedding HTML files in C, and fetching data with JavaScript but it’s too long as it is. Some other time maybe.