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 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 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 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.
Top comments (38)
It's hard for me to even conceptualize writing a program without the concepts introduced by Lisp. These ideas are truly enduring. Why is it that we don't put more focus on this history when we teach CS?
"Why is it that we don't put more focus on this history when we teach CS?" I couldn't agree more. It appears "Computer Science" is the one "science" in which we don't really consider the history of the field itself, and the people who made significant contributions to it. Maybe that's why we keep reinventing the wheel.
I recently learned Lisp and thought it was the stupidest language in the world because it has no random access data structures, which are crucial to computers actually working. That's still true, but now I see that there are other things about the language which makes it great.
The Lisp-based languages that people generally use have random access data structures - they just may have different names than you're expecting. Common Lisp has the general construct of an array, and a specialized version called a vector. In Scheme they are called vectors: r6rs.org/final/html/r6rs/r6rs-Z-H-... . Similarly, Clojure has vectors.
That is not true, Lisp is not all about linked list. Optimised maps exist in all major lisps which are essentially Random access. Also Self balancing binary search trees can be easily implemented which are a good compromise, the only community that is keen on Random Access DS is the Haskell community which spends all its energy and resources in writing research papers on "Sieve of Eratosthenes" instead of doing something more productive.
But isn't that the whole point? I would expect Lisp, in practicality, to be kind of stupid, because everything that came after it is essentially building off of it. But the idea of Lisp and the history of how it came about is every bit as fundamental as other concepts that get way more attention.
And you'd be oh so wrong :)
Lisp doesn't just come first, it also evolves fastest (remember the article above? That it encourages experimentation in language design?)
For example the OOP features of Common Lisp (CLOS) are still unmatched by any other language. The "exception handling" (called conditions) are also much more advanced than elsewhere.
And what didn't originate in Lisp, Lisp can often trivially steal. There are libraries on the Internet that can make it have the features of pretty much any language and paradigm you want (coroutines, logic programming, whatever).
Exactly.
It's not that it doesn't have them, they're just not the preferred solution. Common Lisp has arrays (fixed size or dynamic), hash tables and everything - you use them when optimizing your program's performance.
What dialect of Lisp did you use? Are you sure it didn't have random access data structures? Of course Lispers know the importance of indexed arrays.
Great post about the history. In terms of modern development you could mention leiningen and figwheel, and all the other great dev-tools that have come out of the Clojure community and are in my opinion the most mature and modern eco-system at the moment.
Every time I read about Clojure, I get interested in trying it out, and I never end up doing that. I'm thinking ClojureScript is going to be my entry point. I've seen David Nolen show off some of the ideas, tools, etc., which definitely has me excited.
I've written code in almost every language in use today and many long since forgotten. I was exposed to LISP in grad school (CS) but couldn't get past the parens and odd fn names (car cdr etc.) My lasting impression was of a powerful language (solved nine puzzle very easily) but that it was awkward to work with.
I've since learned Clojure and am a complete convert. On so many levels Clojure got it right, especially forgoing the awkward fns and adding array/map syntax support. It isn't perfect but it's rigor and reach are unparalleled in any other language.
I strongly recommend giving it another try. If you need help the community is very open and helpful. Also, tooling has greatly improved. Tip: if you aren't already an emacs developer, try Cursive.
Another good one is ClojureScript for Skeptics by Derek Slager.
I learned more in one semester at MIT learning Lisp (MacLisp, moving to Scheme) than I had in the 7 years before that taking classes at the state university where I grew up (using Fortran IV and PL/I). The concepts that I learned (especially from Scheme) have held me in good stead for 36 years.
In fact, these days, I'm working 100% of the time using Julia, which is a very interesting language that inherits quite a lot from Scheme (two things to note: the parser (and AST lowering code) is actually writting in femto-lisp (which is a small, fast dialect of Scheme written by Jeff Bezanson), also, one of the 3 people of the panel at Jeff's PhD thesis defense was none other than Gerald Sussman ;-) ).
Anybody who loves the idea of Lisp, should definitely check out julialang.org/
"I mentioned this before, but it bears repeating: programmers were following math's lead and using one-letter variable names before McCarthy came along. "
You have overstated the case here, in particular. Certainly FORTRAN had multicharacter variable names, IAL did too as did ALGOL 58. I am pretty sure Hopper's Autocode did.
"Yes, John McCarthy invented the conditional expression. He lobbied the Algol committee to add them to Algol, from which most languages got them today."
According to McCarthy, the conditional expression in Algol was proposed by Backus. See footnote 2 in
edge.cs.drexel.edu/regli/Classes/L...
Also McCarthy did not develop LISP on his own, he had a number of collaborators.
Thanks for the clarifications and discussion. It's always good to read deeper and you've challenged me to clarify further.
"You have overstated the case here, in particular. Certainly FORTRAN had multicharacter variable names, IAL did too as did ALGOL 58. I am pretty sure Hopper's Autocode did."
Yeah. Fortran allows 1-6 character variable names. But look at the code. Lots of X, Y, I, J, K for variable names. That's what I meant: they were just following math's lead and rarely naming variables the way we would today.
"According to McCarthy, the conditional expression in Algol was proposed by Backus. See footnote 2."
Yes, the footnote is correct but very terse and can read ambiguously. McCarthy's syntax was not chosen, but the idea for how it worked was. Backus merely suggested new syntax(if..then..else..). See nyu.edu/classes/jcf/CSCI-GA.2110-0...
"Also McCarthy did not develop LISP on his own, he had a number of collaborators."
No argument there. He was working closely with a number of very smart people during the Dartmouth Summer Research Project, and McCarthy has been very forthcoming about the influences. I will grant that I took some poetic license to shorten the story. The first Lisp was actually written by Steve Russell from McCarthy's design.
However, as far as I'm aware, no one has ever contested him for being the inventor of Lisp. For those reading, I suggest reading the following if you're interested:
www-formal.stanford.edu/jmc/histor...
infoq.com/interviews/Steele-Interv...
The book excerpt is great. Who knew that McCarthy, who I used to argue with online in the early days of USENET and was deeply right wing, had communist labor union organizer parents and had been inspired by a Soviet Era children's science book? I had to look it up: ebay.co.uk/itm/100-000-Whys-A-Trip...
great informative background on Lisp. Also appreciate your blog and emails which always expand my thinking with new ideas and context.
do you have any thoughts on status of Clojure on CLR? it seems to be both acknowledged by its creators and deemphasized as well.
Thanks!
Clojure on CLR just needs more work. Rich Hickey is the original creator but got tired of doing everything twice to support JVM and CLR. There are maintainers but I think they need more help. Arcadia is Clojure + Unity3D, which is CLR.
FYI: One data point, we've been using Arcadia (and ClojureCLR) and it seems to "just work." I think there may be some newer Clojure features that may not be there yet but I haven't run across any (yet.)
First, thanks for the article Eric.
As someone that loves history, in general, I really love learning stuff like this. As a software developer that loves history, it's great to learn about all the things we now take for granted.
Second, Lisp, now Clojure, is at the top of my "To Learn" list. I hope to get started this year. For me it's a foundational thing. You see, I started my professional programming career writing Smalltalk. And because of Smalltalk I feel I'm 'different' kind of OO programmer. Learning Lisp, I hope, will help me learn about Functional Programming.
I feel, as a professional programmer, you should never stop learning; you should remain insatiably curious.
Thanks for feeding my curiosity!
Awesome, Mel!
I think Lisp will help you learn FP, but it will also make you a 'different' kind of Functional Programmer in the same way Smalltalk made you different.
Eric
I remember learning about lisp, and how to use the primitives to write the rest of lisp 1.5 in those primitives in my matters programming languages class ( thanks Tom Murtaugh). I always found lisp interesting, but at the lisp 1.5 level, it isn't all that easy to use. Fast forward to common lisp or clojure, and usability increases, but there is still a big learning curve as it isn't like other languages. In essence, you are writing the ast directly rather than having a compiler move from a vaguely English form to the ast. In the end, the syntax is a plus because it makes macros a lot easier.
One note, I believe oop is in similar 67, which came before Smalltalk.
Thanks for the article, Eric! I have no lisp background and it looks like you've convinced me to address that; I wrote up my experience implementing lisp as described in the original paper here.
Out of curiosity, what's the alternative to if/else? Assuming polymorphism wasn't around in the 50's, did people express the idea of conditional execution based on the result of evaluating some expression using and/or? Does this mean that lazy evaluation was around before conditionals?
Something like you have in assembly: a conditional GOTO that jumps if the argument is equal to zero. Algol actually had a three-way conditional that jumped whether the argument was zero, positive, or negative.
"Oh! so many parentheses!" is a common complaint, and is probably one of the most common reasons people ignore Lisp. Readability matters. If you're interested in Lisp, but want to use a more readable notation that retains Lisp's power (including homoiconicity), see the readable Lisp s-expressions project.
Give yourself two weeks and the parentheses will not be a problem. Adapting editors or changing to an editor that handles parentheses well also helps.