History of Lisp

History of Lisp (The history of LISP according to McCarthy's memory in 1978, presented at the ACM SIGPLAN History of Programming Languages Conference.)

This is such a fun paper which I couldn't find on LtU. It's about the very early history of programming (1950s and '60s), back when things we take for granted today didn't exist yet.

On taking apart complex data structures with functions like CAR and CDR:

It was immediately apparent that arbitrary subexpressions of symbolic expressions could be obtained by composing the functions that extract immediate subexpressions, and this seemed reason enough to go to an algebraic language.

On creating new data, i.e. CONS:

At some point a cons(a,d,p,t) was defined, but it was regarded as a subroutine and not as a function with a value. ... Gelernter and Gerberich noticed that cons should be a function, not just a subroutine, and that its value should be the location of the word that had been taken from the free storage list. This permitted new expressions to be constructed out of subsubexpressions by composing occurrences of cons

On inventing IF:

This led to the invention of the true conditional expression which evaluates only one of N1 and N2 according to whether M is true or false and to a desire for a programming language that would allow its use.

On how supreme laziness led to the invention of garbage collection:

Once we decided on garbage collection, its actual implementation could be postponed, because only toy examples were being done.

You might have heard this before:

S.R. Russell noticed that eval could serve as an interpreter for LISP, promptly hand coded it, and we now had a programming language with an interpreter.

And the rest is history...

Comment viewing options

Select your preferred way to display the comments and click "Save settings" to activate your changes.

Good paper

Looks as if there was supposed to be a link to it at LtU's Language Design Docs page, but the link is now broken.

Looks like many of the links

Looks like many of the links there are dead anyway


s-exprs (over Fortranesque m-exprs) providing homoiconicity (the concept not named) though a typeless interpreter only as a happy accident - I'm glad constraints of the time led things the way they did. And I love the admission, "I did not understand the rest of [Chruch's] paper..."

happy accident

Fwiw, my take on the happy accident (from a relatively recent blog post) is that a crucial factor was failure to give functions first-class status.


I should probably explain that here, a bit. To my understanding, McCarthy envisioned an S-expression as made up of only symbols and pairs, without anything else in it. When he set out to show that his model could do the universal-simulation thing more elegantly than Turing machines could, he had to encode an M-expression using only symbols and pairs; but he was able to take a shortcut when encoding an S-expression, exactly because an S-expression was already only symbols and pairs. So he just encoded an S-expression <S> as (QUOTE <S>). And when eval was implemented, the resulting interpreter afforded practical meta-programming only because QUOTE made the encoding of a data structure look just like the encoding of a program. If McCarthy had been thinking that <S> could contain an embedded M-expression, such as a function, that would require encoding, he likely would have used a homomorphic encoding instead of QUOTE, and as a result, the interpreted programming language would not have been a practical tool for meta-programming.