Like many software devs, I have a wispy, tenuous, almost nonexistent relationship with Lisp. In high school I'd dabbled with emacs, in college I had one lambda-loving friend that I mostly ignored, and once I was in the workforce I'd always put "learn some Lisp" on my todo list, usually near the bottom.
It wasn't until a few weeks ago, when reading Eric Normand's article "The Idea of Lisp" that I finally got the itch. But how should I go about it? The article describes the original LISP as a set of five primitives of which the runtime is constructed, like Euclidean geometry which is based on five irreducible axioms. I had never actually written a language interpreter, and I thought it would be fun to read the original McCarthy paper and see if I could implement the language as described. Not having an IBM 704 handy I was going to write it in C, in as little code as possible reasonable, and leaning as heavily as I could on the primitives given. I wasn't going to cheat and look at other Lisp resources, though I did take a peek at the Wikipedia article on S-Expressions as the visual layout in the original paper wasn't as clear to me. In short, I wanted to pretend it was April 1960 and I'd just gotten the latest copy of CACM, like some modern-day hiker going out into the woods to pretend that they don't have GPS handy.
There are a few things that you work out as you implement the language in this paper. For one, most of the code in the paper is in M-expressions, which are not idiomatic to an Algol-ist like me, and apparently never implemented in software. Once you're over that hurdle and you're transcoding M-expressions into your language of choice, you'll notice that the function definitions in the paper are sometimes missing a termination condition, or the behavior in some area is unspecified, or the parentheses in a definition are not balanced (ironic in a paper about Lisp). After you've made some fixes and specified the unspecified, you'll also find that there's an error in the definition of eval. I spent half a day working out the latter, only to discover later that the error and the fix are well known (McCarthy hints at it in a 1995 update, and Paul Graham spells it out in The Roots of Lisp).
The result is, well, a crude Lisp implementation, with the features described in the paper including mark-and-sweep GC, plus some 2-function math. It's remarkable in that it can parse S-expressions and perform recursive functions in a few hundred lines of C, but it's not a language you'd want to live in. The first thing you'd want to do with it is make the obvious additions to make it more useful (I'd already started by adding a defun that puts the necessary lambda and label references in a global args scope). You can really tell that the original paper was an attempt to capture a moving object, that it was a snapshot in time, presumably not long after recursive functions were shown to work but before anyone had done useful work with them.
It's incredible that this existed in the fifties, a full decade before my universe is usually thought to have begun. The original Lisp is like a John Harrison clock in that you can't imagine how it was conceived, how it was crafted, or how everything fits so well together. Thanks for the article Eric, you've shown me a gem.
cover image by David Fielding (aviatordave@flickr) CC BY-NC-ND 2.0
Top comments (0)