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.

It's not obvious that these six things are computationally complete (AKA Turing Complete). It defines 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 computationally complete. 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. 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 write a JavaScript interpreter in JavaScript, none of the work is done for you.

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

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.

Data-Driven Programming

Lispers often write their own interpreters in Lisp for new languages they create. They re-enact the bootrapping 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 the JVM and in JavaScript.

However, the ideas of Lisp actually live on in your favorite language:

The REPL

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.

Recursive functions

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.

Garbage collection

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.

Conditional expressions

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.