The Idea of Lisp
Eric Normand Dec 13, 2016
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 (
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.
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.
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 today.
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.