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.

At last

I don't play much DDR anymore. Making it through Max 300 on Heavy mode was an old goal I thought I had no hope of achieving. But several days ago I had energy to burn and played a few rounds on a whim. Oddly, my game has improved despite lack of practice. The arrows felt slower than I remember. I tried Max 300 almost as a joke, and was amazed that I finally passed it.

Now I have to work my way up to an A!

It's Go time

At last, the Go programming language has been publicly released so I can write about it without getting into big trouble.

Go was designed by programmers I hold in high regard. Although it is a new language, the same people already experimented with some of its ideas at least ten years ago.

Back then, I saw a demonstration of the Inferno operating system, the successor to Plan 9, which in turn was the sequel to UNIX. I remain awed that just a handful of programmers could implement a complex system so well. The venerable UNIX crew seem to make the right decision often, and make it ten years ahead of everyone else.

For example, the dis byte code ran on a register-based virtual machine and hence ran fast. In contrast, its chief competitor, Java, has a stack-based virtual machine, and it seemed to take years to realize that this was a poor solution. The problem is so severe that JIT compilation was introduced, weakening the "Write Once, Run Anywhere" mantra: the statement becomes almost meaningless if one requires some sort of compiler for every platform, as opposed to a simple byte code interpreter. Another workaround is to design a register-based virtual machine for Java from scratch.

Another case in point is Limbo, a novel programming language that accompanied Inferno. Sadly Limbo has far fewer adherents than Java, for non-engineering reasons. Like Plan 9 (which remained closed-source until 2000), Inferno was hard to obtain, whereas Java was being given away: indeed, users were once practically forced by their browsers to install Java virtual machines. The relative obscurity of Limbo is therefore expected, as with any human language possessing few speakers and few opportunities for growth.

A second chance

It’s much more exciting this time around. The powers that be have wisely made Go open source. Now that Go is playing on a level field, ideas that Limbo should have popularized finally have a chance to spread far and wide.

My favourite feature is something they left out. As with Limbo, there is no inheritance. There is no stifling type system. At least one generation of programmers has been trained to use a rigid type system, and I believe history will one day prove the inheritance mindset to be a passing fad. I have strong feelings about this topic because I was once a firm believer in inheritance, and it took years to realize my mistake.

Go instead emphasizes interfaces, and provides a simple concise syntax for them. A few neat lines perform the equivalent of several messy lines in C that deal with structs of function pointers.

Go also has strong concurrent programming features, which it shares with Limbo. Different threads (actually, "goroutines") communicate via channels (folowing the CSP model), eliminating race conditions. Channels are essentially type-safe UNIX pipes: they capture the power and delight of writing shell scripts to string together several tools.

Among lesser niceties: nested functions, anonymous functions, multiple return values, the package and import keywords, untyped numerical constants, reflection. Most of my wishes for C have been granted.

I’ll probably mostly stick with C. I’ve grown accustomed to its flaws, and I like squeezing every drop of performance out of code without dropping down to assembly. But for those tasks that require more than a shell script but less than a C project, Go might just fit the bill.