[FoRK] Larry Masinter talk today: origins of Lisp at PARC & modern Medley
Gregory Alan Bolcer
greg at bolcer.org
Thu Dec 17 21:39:10 PST 2020
The Idea of Lisp
Cover image for The Idea of Lisp
LISP. It conjures up visions of a bygone age of computers the size of
refrigerators, ALL CAPS CODE, and parentheses. Oh! so many parentheses!
So why is Object-Oriented Programming's creator so enamored with the
idea of Lisp? And what can he mean by a programming language being an
idea anyway? Should I blame my Computer Science education for not
teaching it to me?
Lisp was first introduced to the world in a paper called Recursive
Functions of Symbolic Expressions and Their Interpretation by Machines,
Part I, written by John McCarthy. In it, McCarthy introduces many new
ideas to programming. Among them are conditional expressions (that's
right, if/then/else) and using more than one letter--sometimes even
words and phrases--for variables (like they still do in math). Your
favorite programming language owes those two features to John McCarthy.
But there is an even deeper idea lurking in the definition of Lisp itself.
He defines 5 primitive operations (atom, eq, cons, car, and cdr) along
with a conditional expression. It also assumes the ability to define
functions. And then he uses those to define an entire programming
language, defined in itself. Let me say that again: John McCarthy wrote
6 easy things in machine code, then combined them to make a programming
language. Before that, the only higher-level programming language was
Fortran, which took 18 man-years to develop. Fortran was a big
achievement, but Lisp was a big idea.
Let's unpack this tremendous idea a bit:
The bootstrapping material was very small.
These 6 things give you lists of symbols which can be interpreted. They
define a very small "kernel" which can be easily ported to other
systems. It is a small "fixed point" of agreement. All other meaning can
be defined in terms of them.
The language was defined in terms of itself as an interpreter.
This is a proof by construction that the language is universal. The idea
of Turing Completeness actually has two parts. The first is that you can
compute anything computable. That one is satisfied by just about all
programming languages (Lisp included since it has recursive functions).
However, the second part is much more special. Turing Machines can be
seen as universal when they can interpret any other Turing Machine.
Well, Lisp is defined as an interpreter in terms of itself from the
get-go, just like a Universal Turing Machine. Lisp is a universal
language because it can interpret its own code. While you can certainly
The meaning of expressions in the language is defined by the interpreter.
You could write your own interpreter that assigned different meanings to
the expressions. This is Alan Kay's notion of "late binding". Since we
don't know much about how to program well, it would be a mistake to
build in too many assumptions into the base of the language. So we want
a system that will allow us to swap out the assumptions as we learn more
without having to throw it all away.
The expressions are written in data structures usable in the language.
The expressions are written as recursive linked lists. The 5 primitives
are all you need to walk these data structures and interpret them.
Lispers have enjoyed working with this highly flexible "kernel", though
most Lisp systems make practical compromises, like compiling the
expressions to machine code instead of interpreting it each time. Here
are some of the features of Lisp that follow directly from the Idea of Lisp.
Macros are functions that take code and return code. They are code
transformers. They extend the expressiveness of the language and allow
you to do computation at compile time.
Lispers often write their own interpreters in Lisp for new languages
they create. They re-enact the bootstrapping of Lisp for their own
languages. These can be seen as Domain-Specific Languages.
Programming language experimentation
Because it was made to write its own interpreter, Lisp is great for
experimenting with alternative semantics for languages.
We're all too forgetful of the history of our field. The most
significant languages in our industry are changed every so often. The
new hot language will be gone in 15 years. But Lisp, the idea, endures.
Its most promising incarnation at the moment is Clojure, which runs on
However, the ideas of Lisp actually live on in your favorite language:
REPL stands for Read-Eval-Print-Loop, which are the names of the four
Lisp constructs that defined it. If your language has an interactive
prompt where you can type in code and see it run, that comes from Lisp.
Computer Scientists in 1960 knew that recursive functions were possible,
but they thought they would be too expensive. Fortran, the other major
language at the time, did not have recursive functions back then. Now
recursive functions are table stakes.
Lisp was the first language with garbage collection, mainly because the
language created a lot of temporary objects and it ran for a long time.
Yes, John McCarthy invented the conditional expression. He lobbied the
Algol committee to add them to Algol, from which most languages got them
Multi-character variable names
I mentioned this before, but it bears repeating: programmers were
following math's lead and using one-letter variable names before
McCarthy came along.
Literal data structures
Can you write arrays and maps directly with syntax in your language?
Well, Lisp did that first using parens ().
Here's the full quote from Alan Kay:
Most people who graduate with CS degrees don’t understand the
significance of Lisp. Lisp is the most important idea in computer science.
I didn't graduate with that significance. It took a lot of reading and
exploration after university to feel like I had a proper education in
Computer Science. I try to share what I'm learning in my newsletter. The
more I read and learn, the more fascinated I am by the depth and breadth
of what was done over forty years ago.
If you're interested in the big ideas in Computer Science, the history
of programming, or Lisp, you should check out the PurelyFunctional.tv
Newsletter. It's a weekly romp through the history, present, and future
of Lisp and functional programming.
More information about the FoRK