(I wrote this article to help myself understand exactly
what McCarthy discovered. You don't need to know this stuff
to program in Lisp, but it should be helpful to
anyone who wants to
understand the essence of Lisp — both in the sense of its
origins and its semantic core. The fact that it has such a core
is one of Lisp's distinguishing features, and the reason why,
unlike other languages, Lisp has dialects.)
In 1960, John
McCarthy published a remarkable paper in
which he did for programming something like what Euclid did for
geometry. He showed how, given a handful of simple
operators and a notation for functions, you can
build a whole programming language.
He called this language Lisp, for "List Processing,"
because one of his key ideas was to use a simple
data structure called a list for both
code and data.
It's worth understanding what McCarthy discovered, not
just as a landmark in the history of computers, but as
a model for what programming is tending to become in
our own time. It seems to me that there have been
two really clean, consistent models of programming so
far: the C model and the Lisp model.
These two seem points of high ground, with swampy lowlands
between them. As computers have grown more powerful,
the new languages being developed have been moving
steadily toward the Lisp model. A popular recipe
for new programming languages in the past 20 years
has been to take the C model of computing and add to
it, piecemeal, parts taken from the Lisp model,
like runtime typing and garbage collection.
In this article I'm going to try to explain in the
simplest possible terms what McCarthy discovered.
The point is not just to learn about an interesting
theoretical result someone figured out forty years ago,
but to show where languages are heading.
The unusual thing about Lisp — in fact, the defining
quality of Lisp — is that it can be written in
itself. To understand what McCarthy meant by this,
we're going to retrace his steps, with his mathematical
notation translated into running Common Lisp code.