Well, a new year, and (finally) a new post. In the past two weeks I have undertaken a complete rewrite of Project Posner from Common Lisp to Ruby on Rails. Now, before the Lispniks descend upon me with their sharp parenthetical barbs, allow me to explain. The Common Lisp version was never anything more than a cheap hack: a few hundred lines of code that crawls through a few tens of megabytes of plain-text documents and spits out about the same amount of HTML. It’s completely off-line, static, Web 0.5 stuff. For a search engine I used ht://Dig, whose last release was in 2004. All that being said, Common Lisp was a great language for doing it, and definitely made the process easier and more fun than it would have been in any other language.

But I want to move on with a more sophisticated search, more dynamic features (highlighting search terms and personal search histories to name just two), and, of course, AJAX! I could do all that in Common Lisp. Several people have successfully done so. But many hundreds more have done so with Ruby. With Rails, half the work is already done for me. I don’t have to think about how to connect to a database or even how to name my files. Someone else has already done that work. When I had a problem with Rails dropping MySQL connections on Ubuntu, Google delivered a one-command solution on the first try. Compare that with the endless speculation and one-upsmanship that might accompany such a query on comp.lang.lisp.

So any distaste I may have for Ruby’s syntax is completely overcome by my delight at Rails’ helpfulness. I’d still rather be working in Lisp, but Ruby is good enough, and Rails is better. It is not the path of least resistance — would that be PHP? — but it is the path of least work. As someone wrote, if Lisp’s audience had been harried sysadmins rather than AI researchers, it’d rule the world by now.

Amazon has a beta up of an interesting little app called UnSpun. It’s a way to create and vote on “best of” lists for any subject. It’s a little like Reddit, but less news-oriented. Ruby currently leads Best Programming Language by a 7-to-1 margin, not surprising given that the site’s built on Rails. I’m glad to see that Lisp made it to number 6, but why is it right below APL??

Perhaps I was premature worrying about how slow Ruby is. John Wiseman was benchmarking Montezuma, his Common Lisp port of Ferret/Lucene, and found out in the process that Ferret is 10 times faster than Java Lucene! As he says, Ferret gets help from about 65,000 lines of C code.

I’ve heard this before, perhaps not often enough to make a generalization, but at least enough to identify a trend: if you want performance from Ruby code, rewrite it in C. (The same is sometimes said of Python, or really any interpreted language.) The basic approach seems to be to extract the most performance-critical parts of your dynamic, interpreted language program and rewrite them in a static, compiled language, thus retaining most of the benefits of both.

It’s an interesting contrast to what I see as the Common Lisp approach to optimization, which is to keep everything in Lisp but add compiler declarations in hopes of speeding it up. Trouble is, unless you’re an expert on the inner workings of your compiler (or can read the disassembled code) it’s hard to know exactly what effects a particular declaration will have.

Eventually, I think manual optimization will become unnecessary. Experimental compilers like Stalin have been shown to produce faster machine code than hand-coded C. Stalin compiles a subset of Scheme down to a subset of C, making heavy use of type-inferencing and static analysis. If it can be done with Scheme, surely it can be done with Python, Ruby, or any other dynamic language.

I continue to sweat (see previous entry) over the question of language choice for future iterations of Project Posner (and some as-yet-unnamed similar projects). Ruby on Rails is the obvious mainstream choice, mainstream at least compared to Lisp. But a part of me really wants to do it in Common Lisp, just to prove I can.

One concern I do have speed. Ruby is pooh-poohed for being slow, which, its true, is not really fair for a 1.x version scripting language, but the Programming Language Shootout does support the accusation. I tried comparing Ruby and SBCL on the Shootout. As I expected, SBCL is up to several hundred times faster than Ruby, but I did not expect that Ruby would use two to five times less memory.

Maybe Ruby’s data structures are very close to their C analogs, lacking the extra padding that Lisp needs for type identification? But no, Ruby is dynamically typed, too, so surely it needs just as many tag bits. Ah, I know: The test must be counting the large size of the SBCL runtime (over 20MB, I recall reading somewhere) compared to Ruby’s (less than 2MB). For a limited-duration algorithmic test, this would certainly dominate the results.

I wonder, though: over longer run times, which language would use less memory for actual data storage? I suspect that carefully optimized Lisp arrays would win, but Ruby’s arrays, the standard way to represent lists in Ruby, might fit in less space than a linked list structure, the standard way to represent lists in Lisp.

The first draft of Project Posner was written in Common Lisp. I thought it would be fun to see how Common Lisp fared as a language for doing heavy text processing with a web front end. It worked well, and I’m convinced it made the process easier than it would have been with any other language. But everything I’ve done with it up till now is off-line. I used Lisp to statically generate the site on my desk, then uploaded the HTML pages to the server. Search is handled by ht://Dig, an old-school CGI app written in C.

I’d love to continue to develop Project Posner in Lisp, especially since I’m currently the only programmer working on it. But to add any more features I need server-side programming. I find myself wondering … do I dare try to use Lisp? First off, I’d have to get a new web host, probably a virtual server, since no shared-host server offers Lisp pre-installed. That would cost more. Then I’d have to set up and maintain the OS on the server, which I’d frankly rather not be bothered to do. Then there’s the multiple headache of getting Apache, mod_Lisp, PostgreSQL, and a CL implementation all running and talking to one another. Then, and only then, can I start work on the application itself. And then I don’t have much pre-written code to draw on. Sure, HTML and JavaScript generation is in the bag, but there aren’t any drop-in libraries for forums, guestbooks, user authentication, or any of that good stuff.

I could probably write that stuff myself in Lisp. But could I do it faster and better than the hundreds of other people who have already done it in Perl/PHP/Python/Ruby? I don’t think so. I’m not that good.

So there it is. Web application development is an evolving problem, but by and large a solved one. And it wasn’t solved in Lisp. When Paul Graham was creating Viaweb, no one else was even thinking of web applications, so he had to create his own tools. But the biggest recent poster child for Lisp on the Web, Reddit, gave up and switched to Python (to much gnashing of teeth in the Lisp world). It has nothing to do with the language itself. Lisp is still great. It’s all about the tools, the libraries, the “borrowablility” of other people’s code.

So I’ll continue using Lisp for off-line stuff, private projects and such. But for building Project Posner version 2.0, I’ll probably look elsewhere.

Been too busy with work and class to post much, but here’s a link for all the IANALs out there: Project Posner. It’s an on-line database collecting the case opinions of Richard A. Posner, judge on the 7th Circuit Court of Appeals. This was the brainchild of law professor and former Posner clerk Tim Wu. I wrote all the code to parse and format the cases, in 100% Common Lisp! Specifically, about 800 lines of code that spits out 36 MB of static HTML in about 5 minutes — whee! Currently having some problems with Google’s free web search; maybe they’ll crawl the site now that I’ve linked to it. Or maybe I’ll break down and implement my own search function. In any case, take a look, comments welcome.

I’m playing some more with the early chapters of Artificial Intelligence: A Modern Approach, looking at basic tree search techniques for the 8-puzzle. I wrote simple breadth-first and depth-first search algorithms for this puzzle in Common Lisp. Here’s the code. It’s an interesting demonstation of how inefficient these alogrithms really are.

I represent the puzzle as a simple list of integers numbered 0 through 7, with the symbol B representing the “hole.” The “winning” position is (0 1 2 3 4 5 6 7 B). I also added a little code to have the algorithm track the number of iterations; how many “nodes,” or board positions, it has to expand in the search tree; and the maximum number of positions it has to keep stored in memory.

Just to test that I’ve coded it right, I make sure the algorithm does nothing when given a solved puzzle to start with:

CL-USER> (breadth-first-search '(0 1 2 3 4 5 6 7 B))
"Found (0 1 2 3 4 5 6 7 B) in 0 steps.
Expanded 0 nodes, stored a maximum of 0 nodes."

Next, I try it on a puzzle that is just one move away from a solution:

CL-USER> (breadth-first-search '(0 1 2 3 4 5 6 b 7))
"Found (0 1 2 3 4 5 6 7 B) in 3 steps.
Expanded 9 nodes, stored a maximum of 5 nodes."

All well and good. Now lets try shuffling the pieces a bit more:

CL-USER> (breadth-first-search '(0 1 2 b 3 6 4 5 7))
"Found (0 1 2 3 4 5 6 7 B) in 18327 steps.
Expanded 49075 nodes, stored a maximum of 8422 nodes."

Ouch. That’s kind of slow. And that wasn’t even the hardest possible starting arrangement. So much for that.

Let’s see how depth-first search does on the one-move-away puzzle:

CL-USER> (depth-first-search '(0 1 2 3 4 5 6 b 7))

Dum de dum dum. Tick tock.

Half an hour later, I get bored and interrupt it. Obviously depth-first search is not a very good algorithm for solving the 8-puzzle. I’ll have to wait for the next chapter, which introduces A* and other informed searches.

It’s funny to me, because both of these algorithms seem like reasonable ways of searching a tree of possibilities. I guess it’s hard for my mind to grasp just how overwhelmingly large exponential growth really is.

Ran across an interesting remark in a discussion of Microsoft hiring interviews:

If I remember, a lot of MIT people back in the 70s broke the computer world into the Lisp and non-Lisp data typers. The Lisp folk took a casual attitude towards data structures - just shove them in a list, put them on a plist, stash them in a cache. If it gets slow or confusing, add some tags and a hash algorithm. Most non-Lisp folk were appalled at this. They wanted to see the data structure design up front, the data relationship dictionary, complete and comprehensive, even before any coding started.

This sounds like it could be a language-induced habit as much as a programming style. E.g., in Java you have to write “class foo” at the start of a program before you can do anything else, so it makes sense that you’d start by defining data structures. In Lisp, it’s really easy to jump straight to the algorithms, making up “casual” data structures as you go along, so that’s what you do.

The “stuff everything into a list, add some tags later when it gets too big or confusing” is exactly how my largest-to-date Lisp programming project panned out. It worked fine, and made the code pretty short and simple. As the big list got too big to handle in-place, I wrote a handful of functions that pulled out specific pieces of data. Since function calls look identical to method calls in Lisp, the code looked like I had defined a class with a bunch of accessor methods, while in fact it was still just a big list. This was especially helpful given that I was working with free-form data parsed from text files, not a table of predetermined fields. (This could also have been handled somewhat less elegantly with XML.)

Update Oct. 3, 2006: In case anyone was misled, the title was a joke. Data structures are certainly useful. I was merely commenting on the programming styles induced by different languages.

To clarify for some respondants to Voted Off the Planet: As far as I know, the decision to remove my blog from Planet Lisp was not made collectively by readers but solely by the site’s maintainer. As is apparent from comments on the announcement, some people approved of the decision and some did not, but those comments came after it had already been done. The emailed responses I’ve gotten have been uniformly positive — thank you to those people, and to anyone who is still reading.

I was never actually notified either when my blog was added or when it was dropped. I think that’s revealing: I was not being invited into the community, I was being tested. According to one person’s standards, I failed. That in itself does not surprise me. I was not ready for such a large and demanding audience. I only started this blog a few months ago, and I am definitely still feeling my way towards a writing style.

What did surprise me was the viciousness of the criticism, some of it from people who were clearly only skimming my posts anyway. E.g., I was “hassling” Planet Lisp by announcing “UFFI bindings to a C library.” Well, 1) It was CFFI, not UFFI; 2) only half of it is bindings, the rest re-implements bits of the Perl API in Lisp and translates data between the two; and 3) I said it was just for fun.

Or was the idea of embedding Perl code in Common Lisp just too heretical? ;)

But the lesson I can take from all this is that I still have a long way to go. So bear with me, gentle readers, as this page (hopefully) evolves into an interesting and enjoyable discussion.

A Usenet posting sent me to a short article by Edsger W. Dijkstra titled Why numbering should start at zero.

Now, I have never used a programming language that wasn’t zero-indexed (like Fortran), but neither have I adopted the habit of numbering lists starting with zero.

I think the difficulty I have with zero-indexing is that in normal English we refer to items in a list by ordinals: “first, second, third, … nth.” But translated into Common Lisp, we get the slightly disorienting:

(first *list*) ≠ (nth 1 *list*)

(that’s a not-equals sign for the Unicode-deprived)

Now, I understand that nth is zero-indexed, just like elt, and that’s consistent with how most other programming languages work. But then why don’t we have zeroth?

I guess the simple answer is that zeroth isn’t normally thought of as a real word, except occasionally to refer to something added to a sequence “before the first.” My Websters Collegiate doesn’t even define it. Of course, the copy I have is from 1973; Webster’s online does include zeroth. Has zeroth entered the English language because of computers?