Algorithmics In The Dark Compiler Alley

My upcoming "write a compiler" project is about writing a industrial strength compiler. The good news is that it is wonderful to be in a position where you get paid to do something like this (vs say, writing yet another J2EE/dotNet/framework du jour [something that starts with "R"? :-P] "enterprise app"). The bad news is that I have to deliver a 2 person year project in about 6 person months ( 1 person - Yours Truly - and about 6 months starting in August).

One way to "shrink" such a project is to use powerful languages. A compiler, while quite complex, has very few library dependencies. What this means is that you can write a compiler in any language you want and not sacrifice any advantages while doing so. The converse of this is that one can abandon brain dead languages like say, Java, and use something truly powerful, like say, Haskell.

I've spent the last few weeks writing 'compiler like' bits and pieces in various languages, and have short listed 3 - Lisp, Scheme, and Haskell. Besides their power, these languages have another feature in common - none of them have an open source, batteries included IDE. (And "no IDE" implies "use emacs". And the sheer customizability of emacs is exhilarating but more on that in another post).

An interesting (and unexpected) development is that evaluating alternative designs calls for a degree of algorithmic sophistication. For example, in the code generation phase of the compiler the decision to use an RTL (gcc's intermediate language)clone vs (say) a BURS (bottom up rewriting system) based graph traversal needs the ability to (mathematically) analyse the competing code gen algorithms and the trade offs of each. The key to getting a grip on BURS, for e.g., is to understand Dynamic Programming. More interestingly, there is often a need to augment an existing algorithm or data structure to accomodate application specific constraints. The paradigm embodied by the language under consideration determines the "shape" of the runtime. The demands of the runtime and the level of optimization required determines the appropriateness of a particular code gen algorithm, which in turn influences the transformations required on the abstract syntax tree, and so on.

There aren't too many books which teach you to design algorithms and data structures (vs memorizing a few standard ones). Of course if you are an "enterprise" programmer, you don't need any of this and can get by with simple lists and hashtables provided by your language's libraries. But if you (intend to) work in more challenging (and, if I may say so, interesting) domains, learn to analyze and design algorithms (and data structures). It might even help you get an interesting and satisfying job. Companies like Google and Amazon have very algorithmics heavy interviews. As Cormen et al say in Introduction To Algorithms (the best book ever written on Algorithms and Data Structures),

"Having a solid base of algorithmic knowledge and technique is one characteristic that separates the truly skilled programmers from the novices. With modern computing technology, you can acccomplish some tasks without knowing much about algorithms, but with a good background in algorithms, you can do much, much more)".

Another interesting, though less comprehensive and more lightweight textbook is The Algorithm Design Manual by Steven Skiena. It is more of a complement to Cormen and Rivest than a substitute and has a distinctive writing style. Every chapter has an accompanying "war story", drawn from the author's extensive consulting experience, where he reports how he applied the technique taught in the chapter to solve a real world problem or optimize (sometimes in a very dramatic fashion) an inefficient solution. Imagine - algorithmics consulting - I guess they won't be outsourcing those jobs anytime soon :-D.

The one "problem" with the Cormen and Rivest book is that it calls for a certain level of mathematical sophistication on the part of the student. This is unavoidable in a book that avoids a "cookbook of algorithms" approach and tries to teach how to design new algorithms and adapt existing ones to teh problem space. So, before you buy this book ( and it IS a book that should be on every programmer's bookshelf) be sure to learn basic discrete mathematics, probability, linear algebra and set theory. Working through Concrete Mathematics really helps. The effort will repay itself a thousand fold.

But be warned. Once you taste the power of algorithms you'll never be able to go back to your "build (or even worse, maintain) yet another Visual Blub dotNet banking app in Bangalore" day job. On the other hand, you may find that programming is challenging, meaningful, and above all, fun. Red Pill or Blue? :-)