Exposing the inner beauty of code
September 13, 2007
During this coming term, I’ll be taking a variety of courses that look mighty interesting. Among others, a course in distributed systems, and two courses in artificial intelligence. And because I’m mostly insane (I prefer the term “passionate”), I’m also giving myself a couple of personal education objectives, beyond those that my curriculum is giving me. The long and short of it: I don’t know any functional programming language well, and I want to address this.
I started out in the world of programming and software in a pretty traditional way for your regular run of the mill geek: writing programs in Omikron BASIC on my dad’s Atari ST. After moving to x86, I spent a few years being seduced by the dark side of the Force, QBasic and Visual Basic (3.0 and 4.0 - wow, I feel old now). Then, linux happened to me, I learned C, and eventually got rather good at it, if I say so myself.
After that, I diversified a fair amount. I don’t think it is possible to not diversify as a programmer on a unix platform, since knowing some kind of scripting-oriented programming language is absolutely crucial to wielding the full power of a unixy system. So I went and learned Perl. A few years later, I learned Python, and have never looked back. My university studies and various internships made me learn C++ and a little Java (I don’t really like Java the language, its obscene verbosity is aesthetically offensive to me).
My personal curiosity made me learn a little x86 assembler, my Lego Mindstorms related projects made me learn ARM7 assembler (which is beautiful - I like RISC architectures), and general curiosity (read: very vocal and enthusiastic advocates) made me take a look at Ruby (I still prefer Python for now). While I’m no master in most of these languages, I know enough to muddle along, and I’m confident that I could get up to speed on any of them if I suddenly had a specific need for it (that actually happened recently for C++).
What is the common point of all the languages in my personal programming history? They are all imperative programming languages. With the exception of a limited amount of non-imperative features in some of them, all these languages derive from ye olde mutating state model of computing. Which in a way is good, because those languages have an undisputed mindshare majority nowadays. Being knowledgeable in the lore of that majority is nothing to be frowned upon.
And yet, it means that in all these years, I have missed out on the other great family of programming languages: functional languages. In these languages, the focus is not on state and mutations, but on values and their interactions within functions. There are many arguments to the effect that this functional model, by eliminating the capacity for mutation, elegantly rids itself of a huge class of programming bugs. There is also the argument for beauty, since functional languages tend to be very mathematical and pure in their expression of solutions to problems. I cannot comment on the validity (or even, at this stage, the truthiness) of these arguments.
And that is precisely the problem. It bothers me that I am unaware of a whole way and art of writing programs, and that I therefore have insufficient data to answer a fundamental question: am I using the right tools?
Now, I have lied a little. I am not completely ignorant of functional programming, thanks in large to three small comments in Subversion’s source code. I stumbled upon them by accident while I was hacking on Subversion during the Summer of Code, a couple of years ago. Here is the relevant section of libsvn_wc/merge.c for your enjoyment:
/* I miss Lisp. */
SVN_ERR(svn_io_open_unique_file2(NULL,
&left_copy,
merge_target,
left_label,
svn_io_file_del_none,
pool));
/* Have I mentioned how much I miss Lisp? */
SVN_ERR(svn_io_open_unique_file2(NULL,
&right_copy,
merge_target,
right_label,
svn_io_file_del_none,
pool));
/* Why, how much more pleasant to be forced to unroll my loops.
If I'd been writing in Lisp, I might have mapped an inline
lambda form over a list, or something equally disgusting.
Thank goodness C was here to protect me! */
SVN_ERR(svn_io_open_unique_file2(NULL,
&target_copy,
merge_target,
target_label,
svn_io_file_del_none,
pool));
Aside from the comic relief that these comments provide in an otherwise rather austere piece of code, they are making a powerful statement. Or at least it was very powerfully disturbing to me at the time, since I was young and stupid, and the suggestion that the above code was ugly actually came as a complete surprise to me. I mean, how else would you do it? That seemed like a perfectly elegant way of dealing with what had to be done in that particular place of the code.
But those comments come from Karl Fogel, one of the founders of the Subversion project. By the way, he also writes great books, and questions copyright both eloquently and constructively. Go read his stuff! Seriously, it’s worth it. Anyway, back to our regular rant. Since Karl is one of my geek jedis, when he says that he misses Lisp, I think that I may also be missing something, though not quite in the same way.
So that’s how I casually started reading various Lisp tutorials, and caught a glimpse of what I’d been missing. Eric S. Raymond famously says in his hacker HOWTO:
LISP is worth learning for a different reason: the profound enlightenment experience you will have when you finally get it. That experience will make you a better programmer for the rest of your days, even if you never actually use LISP itself a lot.
Then I got distracted, and dropped Lisp on the floor for a while. One problem I had was finding something to do with it. When you are faced with such an alien language, tackling a decently sized project with it is essential to crystallizing your knowledge, and actually “getting it” as ESR puts it. I didn’t really have such a project handy, and so meandered off for a bit.
Studies to the rescue! I took an introduction to AI and knowledge representation course two years ago, which taught us the fundamentals of Lisp and Prolog. We were also given a project: writing a solver for a multiple tower of hanoi problem.
For those of you unfamiliar with the tower of hanoi puzzle, now would be a good time to check Wikipedia. The solution to the N-disc tower of hanoi puzzle is a classic recursive algorithm. We studied it in this AI class, and again caught a glimpse of the beauty of the solution when expressed in Lisp.
The multiple tower of hanoi puzzle is an extension, where instead of one N-disc tower and 3 pegs, you have M different towers (each having any number of discs, not necessarily the same) and K pegs. The objective is to move the towers from their starting position to some predetermined goal position. This problem has no known algorithms solving it, and so we were tasked with building a solver in Emacs Lisp, and experimenting with various heuristics (read: invent one).
That project gave me a real insight into how much sheer undiluted fun it can be to program in Lisp, which is something that I was missing from my previous quick incursion into the land of the functional. Along with Jflesch, we built the solver in three days of straight hacking, and spent another week playing around with heuristics and interesting tower configurations (my favorite is the one where you start with two towers, and the goal configuration is a single tower built from alternating discs from each source tower).
Why am I ranting about this again? Oh, right. It was to explain why I’d lied about knowing diddly squat about functional programming languages. So I guess I do know some Lisp, and the concepts of functional programming aren’t alien to me. But I haven’t written any Lisp since that AI project, and I still feel horribly undereducated when it comes to functional programming. And that is something that has to change.
So, this term, I think I’m going to be educating myself by learning at least two of Objective Caml, Haskell and Erlang. All three are very, very far removed from my everyday Python and C hacking, so it should be a very enlightening path to walk.
I chose those three as my pool of functional languages because each of those three have something interesting to offer beyond being simply functional:
- Objective Caml features a world class native code compiler,
ocamlopt, which produces platform native programs that beat the crap out of everything but C, C++ and D in programming language shootouts. That makes it the fastest functional language I know of, and I am still irrationally attracted to those kinds of lean mean killing machines of languages. - Haskell features an obsessive emphasis on remaining a pure functional language (where functions cannot have side-effects). And because we as programmers do actually want programs to have side-effects (the biggest side-effect of all: I/O), Haskell has come up with monads, which apparently neatly and beautifully separate the pure and impure portions of a Haskell program, and thus raises the bar of making programs beautiful, as well as usefully expressive.
- Erlang is founded on a fascinating idea: what if threading were free and easy? Erlang proposes a world where concurrency is not something to be afraid of as it is in most languages. In Erlang, concurrency is the natural way of writing programs. Thousands of processes, even hundreds of thousands, is perfectly normal and quite fast. By restricting communication between processes to message passing only, Erlang delightfully dances its way around all the ugly aspects of the C model of concurrency, and also provides a rich framework for writing distributed, fault tolerant and highly reliable soft realtime systems. I like this.
All three also feature awesome data structure pattern matching syntax, which let you match variables against skeletons of data structures, and poke around with disconcerting expressiveness within the data when there is a match. This is unlike anything I’ve seen in my imperative universe, and I am hideously excited by the power of expression that this new toy gives me.
You know when in The Matrix: Revolutions, Trinity flies the Logos through the layer of clouds, and can only gasp “Beautiful…” as the ship briefly sails through an ocean of sunlight and blue sky? That’s the kind of sensation I get a glimpse of when I finally “get it” just a little bit more than I did before. I think I’m still only just started on the path to Enlightenment (which, apparently, ends with the brutal realization that the universe is actually written in Perl).
But it looks like a fun path to walk down.
And is it me, or is that grass paren-shaped?