Wednesday, October 20, 2004
Principia Lispia
The other day, I stumbled onto Paul Graham's ILC 2003 talk describing the development of Arc (probably after reading Bill Clementson's blog, where all this sort of thing shows up first). Graham is trying to develop Arc from a small set of foundational, axiomatic functions on which the whole language will then rest. I won't go into everything here, as that isn't the subject of my posting, but read Graham's talk if you are interested in Arc development. The thing that caught my eye was that Graham mentioned that McCarthy had done the same thing with Lisp originally. Googling for "John McCarthy" got me McCarthy's home page which has links to the original 1960 paper in which John described LISP (note the caps).
Anyway, I didn't have time to read the paper right then and there, but took it with me on the flight to London last week. When I finally started reading on the airplane, I was pretty blown away. Suffice it to say, if you are a Lispnik, you should read this paper. This paper impacted me with a number of things:
- First, it distilled down the essence of Lisp for me in a way that no other work has. The idea of a universal
apply
function is really quite staggering when you think about it. While I have started reading Lisp in Small Pieces, it hasn't had quite the impact on me. McCarthy conveys the essence of Lisp in 34 pages in this paper. Note that this is not a slam on Christian Queinnec. He does a great job in Lisp in Small Pieces, but it's building on the foundation that McCarthy layed down. - Second, the fact that you can define the universal
apply
function in only about a page of code is quite staggering. - Third, I was amazed at how much of modern Lisp (lowercase) was present in the original 1960 paper. Obviously, the elementary functions are there:
atom
,eq
,car
,cdr
,cons
,cond
, andquote
. You also have S-expressions, garbage collection, and a whole host of derived functions, includingsubst
,equal
,null
,cadr
,caddr
(etc...),append
,among
(likefind
),assoc
, and some others.
This was a pretty amazing piece of work, particularly if you consider that in 1960 people were still doing most everything in machine/assembly language and perhaps in FORTRAN. McCarthy was thinking so far outside the box, it's just beyond comprehension. It's also staggering that the ideas were so well formed at that point to have survived to the present day almost unchanged (caddr
and friends, for instance).
Effectively, we have here a work that is as foundational for computer science as Newton's PhilosophiƦ Naturalis Principia Mathematica was for physics and calculus or Whitehead and Russel's Principia Mathematica was for mathematics. I'm not sure if there is a translation of "Lisp" into Latin (I took ancient Greek at university), but if there is, surely we have here a Principia Lispia. And in 34 pages, no less!
That's why Alan Kay calls this paper the Maxwell's equations for computer science.
It's one of those the-world-changes-underneath-your-feet kind of papers.
I had the exact same thought about how mind blowing this must have been in 1960. Although can you imagine typing in Lisp code on 80-col punch cards? That's scary.
If you liked McCarthy's Recursive Functions, you'll love John Allen's Anatomy of LISP. I'm halfway through it right now, and it covers McCarthy's Lisp in great depth, with many topics on data structures, representation, pattern matching, program verification, and (I haven't read this yet) compilation (it's like a snapshot of 1970's computer science!). From the style, you can see that that book was probably a major influence on Abelson and Sussman when they were writing SICP. I think it's still relevant to modern Lisp programming for the emphasis it places on formal description and verification, something that not a lot of modern Lisp books do.
Vladimir Sedach
I love Lisp. I love John McCarthy. But lets remember that Church and his lambda calculus is the real progenitor here.
Post a Comment
Links to this post: