Herbert Stoyan. Early Lisp History (1956–1959). In LFP ’84: Proceedings of the 1984 ACM Symposium on Lisp and Functional Programming, pp.299–310. 1984.

A study of Lisp’s evolution from first proposal to practical implementation.

It begins with McCarthy’s proposal (co-authored with Marvin Minsky, Nathaniel Rochester, and Claude Shannon, and dated 31 August 1955) for a summer research project at Dartmouth College to “study the relationship of language to intelligence”.

In a later (handwritten!) note McCarthy homed-in on the core challenges in this programme: the lack of a clear way to describe procedures to each other (what Abelson and Sussman later refer to as procedural epistemology), and the tight binding of programming systems at that time to specific machines, and hence their need to bow to engineering (rather than semantic) considerations. The language that became Lisp sought primarily to overcome these two challenges.

The journey proceeded by taking the list data structures developed by Allen Newell and Herb Simon as part of Logic Theorist and embedding them into FORTRAN (for which there was already a working compiler) – which also incidentally muddied the conceptual waters by trying to express list and list-functional concepts in a language built around numbers that barely allowed functions to be defined by the user at all. Indeed, McCarthy and others had long-running problems accepting that the list-processing functions were functions, given that their result does not depend solely on their arguments when viewed at the lowest level. This shows how pernicious a low-level implementation can be. The final resulting language, the FORTRAN List Processing Language (FLPL), shared many programming approaches function names with what became Lisp.

McCarthy went on to champion the functional approach, including the invention of conditional expressions (alongside or replacing conditional statements) and the power of the different kinds of function composition and higher-order functions. It’s important to remember that McCarthy’s driving interest remained in AI, not programming languages per se:

Already in 1956 it was clear that one had to work with symbolic expressions to reach the goal of artificial intelligence.

Which is a fascinating piece of history in itself, as a large branch of modern AI concerning machine learning and large language models has explicit rejects this view in favour of sub-symbolic AI. Which approach is “correct” in whatever sense remains to be seen.

But it remains McCarthy’s contributions to programming languages that stand out. As well as conditional expressions he can be credited with garbage collection, meta-circular interpretation, and clarifying the relationship between programming and proof:

We should mention here that McCarthy at the same time conceived the idea of logic-oriented programming, that is, the idea of using logical formulae to express goals that a program should try to establish and of using the prover as programming language interpreter.

(Although it’s important to recognise that Newell and Simon’s work, on logic as an application rather than as a general programming language, pre-dates McCarthy’s.)

Herbert Stoyan. The History of Lisp. 1980. Updated in the 1990s, translated into English 2023.

Includes a history of the route from PLANNER to CONNIVER, in which the former was criticised for being a theorem prover when a programming language was needed – an argument between two schools that’s still going on today, as seen in the emergence of Lean.

John McCarthy. History of Lisp. Artificial Intelligence Laboratory, Stanford University. 1979.

McCarthy’s own take on the early history. It’s quite brief, but is very careful to give broad credit to the others who were involved in the practical creation of the language.

It’s also got some great vignettes on why certain features came about - for example garbage collection coming from the need to clean up intermediate structures when experimenting with symbolic differentiation. McCarthy acknowledges taking the notation for functions from Church, before admitting that he didn’t understand the rest of Calculi of lambda conversion and so wasn’t tempted to add the more general aspects!

Perhaps the most fascinating part of the story is that it was originally so divorced from actual computers. The team had defined an eval function for interpreting Lisp programs – in the process making the decision to represent the programs as lists – before realising that this could be made interactive to provide a running interpreter.

What did McCarthy think of his creation? He was conscious that it would have a lifetime:

LISP will become obsolete when someone makes a more comprehensive language that dominates LISP practically and also gives a clear mathematical semantics to a more comprehensive set of features.

Haskell has a plausible claim to have accomplished the latter but this doesn’t seem to have led domination in practice.