Foreign Language Lessons

I’ve been tinkering around with [Lisp](http://en.wikipedia.org/wiki/Lisp_(programming_language) in my spare time lately. I recently finally got around to reading Paul Graham’s Hackers and Painters. He talks a lot about how Lisp was his business’s competitive advantage (he made his bankroll on what became Yahoo! Stores and now runs Hacker News and Y Combinator, and how it’s both the mark and maker of really good programmers. I’ve always written it off as being an “academic” language, but he convinced me to give it a try. I have no expectation of actually using it professionally, but I hoped that I might learn something that would be applicable in other languages.

Lisp is the Latin of programming languages. It’s been around forever (since 1958, which is the paleolithic era for programming). It never really caught on, outside of niche applications and user groups, but it’s never quite died out, and it seems to be enjoying a resurgence. It’s also inspired other languages, like Ruby and Erlang, that I’ve gotten interested in, and people who know it say that even those just have watered-down, training-wheel versions of features found in Lisp.

I had a good little sample problem to try it out on. I’d been sketching out a to-do list tool, something that would let me keep track of projects, nested sub-projects, and tasks. The key was that I wanted to keep the data in plain text, in some readable format, but also be able to munge it - filter and sort it and such; some sort of simple wiki-style markup language. The first part of this was the structure: I’d have a project, with its sub-projects indented below it, and their sub-projects and tasks indented further. The parser would build up a tree data structure. So you’d have plain text input that looks like this: and you’d want to end up with a data structure like this:

Now, I’d already done this in Ruby. I’d designed a set of classes to represent the stages of the parsed data. I start out with a list of strings, then I break each string into a simple object that just knows “indent” and “content”. It then adds that to the tree structure as a node that knows what its parent node is. As more nodes get added, they become its children. Eventually, I could extend those classes to understand particular bits of project-related markup, like priorities or dependencies. But for now, just the tree structure.

Already, there’s a bit of recursion here: I have a “current” node, the most recently added one. If the next node is indented further, I add it to the current node’s children. Otherwise, I tell the current node’s parent to try to add it. This way, you could pop up several levels before you find a parent to add the new node to. In this example, I try to add node “e” to “d”, then “c”, before finally adding it to “a”. Despite that, it’s still a pretty linear process. Each line is added in order, and you’re just moving up and down the tree, stitching each into place.

So for my first stab at doing this in Lisp, I just sort of transliterated it. I took the logic and structure of my Ruby code, and tried to just turn it into Lisp syntax. That didn’t go so well. It’s a bit hard to explain how it went wrong, other than to say that it came out like the programming version of Engrish. It didn’t work right, it was hard to follow what was going on in the code, and trying to fix it just made it uglier.

Normally, when I’m writing code it’s kinda like sculpting with clay or Play-Doh. I start out with a rough idea of what I want and gradually refine it, mushing chunks of logic around, whittling away bits I don’t need. I can see it taking shape. My understanding of what’s going on, the scope and nature of the problem I’m solving, gets clearer and clearer. This code was just getting messier. It felt more and more like a duct tape and bailing wire job. Even more than other programmers, Lisp people go on about the elegance and clarity of their code. So I gave up for the evening and went to bed pondering how to make it “Lispier”, maybe really work that recursion thing.

In the classification of programming languages, Lisp is a “functional” language, as opposed to an object-oriented or procedural language. The distinctions are a bit blurry, but they’re about how the language encourages you to organize your code and suggests the terms you use to describe the problem you’re dealing with. Like I said, vague, but programming is fundamentally an act of communication, so the mental constructs you bring to it are important.

Programming languages all have nouns and verbs: Data and things you do with the data. Procedural languages focus on the verbs, the procedures. You’re stepping through a process; it’s linear. Procedures are broken down into sub-procedures, but it’s still all about what you’re doing as you step through the process. You have data structures, but you’re kinda just trundling them along through the procedures like a shopping cart.

Object-oriented languages focus on the data, how it’s organized. The verbs are “methods” tied to the data, what you can do with it. Methods may do things with other objects, but they’re defined in terms of the thing doing it.

Functional languages are a little harder to explain. Rather than the steps of a process, they focus on the start and end points, what you put in and what comes out; results, not actions. That isn’t really how people think. We tell stories; we make sense of the world through narratives. But while it’s not entirely natural, the functional way of thinking can be useful because it forces you to focus on what you’re trying to accomplish.

The other part of “Lispy” code is its focus on handling lists of data recursively. You define a function that does something with the first element of the list, then applies itself to the rest of the list. Rather than

clnew_list = []
for thing in list:
    new_thing = do_stuff(thing)
    new_list.add(new thing)

You do something more like

cl(defun process-list (list)
  (list (do-stuff (first list))
        (process-list (rest list))))

process-list is a function that calls do-stuff on the first thing in a list, then calls itself on the rest of the list, and gloms the results together to make a new list. Weird way to do things, huh?

Anyway, in my case, I’ve got a node and a list of lines that are all either children or siblings of that node. Once you break the list into those two chunks, you just create a child and a sibling node, and hand them their lines to process. Your output is a list of the siblings, with you in the front. Your child hands you back a list of its siblings, your children, with itself in the front. Your sibling gives you it siblings (which are also your siblings) with itself in the front. By the time they get back to you, all of your siblings and children already have their siblings and children.

That’s a very clean, mathematical way of thinking about it, but it’s seriously non-linear. The Ruby code built its structure in order, “a” through “l”. The Lisp code built it in the following order: d e c b i h k j g l f a. It processes the children from the deepest up, and the siblings from the last to the first. Not intuitive.

The experience of programming Lisp ended up being a lot more like doing math than sculpting Play-Doh. I had to step away from the keyboard and just think about it for a while. But when I figured it out, everything just snapped into place. It wasn’t the gradual refining and polishing of an idea; it was like solving a puzzle. When I hit on the solution, I knew I had it. I felt it in my bones.

So it was a good learning experience. My hope was that Lisp would force me to think differently, and it did. The Lisp program I came up with is fundamentally unlike the Ruby version. (You can see the Ruby code here and the Lisp code here.) I think I’ve kinda wrapped my head around this functional programming approach. That, more than Lisp syntax, is the potentially useful bit.

The thing about functional programs is that they’re much easier to break into seprate processing chunks, whether you’re running them on some Google-grade cluster or compute cloud, or just on a multi-core chip. There’s a lot more demand for that kinda thing these days. The Ruby version of my code has this central tree structure that it adds onto line by line. There isn’t any way to farm that work out to a bunch of independent processes. In the Lisp version, at each node you’re splitting the work into two batches, children and siblings. You could distribute it naturally across as many processors as you have nodes. Each just has to get its set of lines to process, and the tree comes together in this non-linear way as they return their results.

I’ve always been all about code as a communication between programmers, rather than just a way of telling the machine what to do. Lisp doesn’t do so well on this count. It’s certainly not as friendly to the novice programmer. One of the things I love about Python is that pretty much anyone who knows how to program can read it - it looks like pseudocode. That’s so not true of Lisp. The syntax, with all those parentheses, isn’t like any other languages. It makes no sense at first, and takes a good bit of getting used to. (To be fair, it was there first.) But the harder thing is shifting to a new set of ideas and customs. Early on (and occasionally still) I would try to do something that should be simple and obvious, but in Lisp they just don’t do things that way. Like any foreign language, it’s much harder to write than to read, and the idioms are harder to learn than the grammar.

But again, like any foreign culture, once you spend some time there, you get used to it and it starts to feel comfortable, even normal. Recursion goes from being alien and academic to highly practical. All the crazy parentheses actually feel like a more logical and coherent way of grouping functions. And when you come home to Ruby or Java or whatever, you bring a little bit of all that with you.