LISP: Programs become data

The event and the date question

In autumn 1958 John McCarthy, newly appointed at MIT, began building a language for manipulating symbolic expressions on the institute's IBM 704. By the end of October his internal memos were calling it LISP, for List Processor. Within eighteen months it had an interpreter, automatic reclamation of unused memory, and a journal paper, McCarthy's April 1960 article in the Communications of the ACM, presenting it as a way of defining computable functions over symbolic expressions. For three decades LISP and its descendants were the main language of American AI research; in 1992 Peter Norvig's textbook still called Lisp the most popular language for AI programming in the United States.

Chronicle dates the event to 1958, and the choice needs defending, because 1960 has a real claim. The 1960 paper was the first journal publication and the first full account of the features that made LISP distinctive: programs written as the same lists they manipulate, a universal function called eval that both defines and interprets the language, and garbage collection. None of these appears in McCarthy's first memo of September 1958. But the language as a project, with its name, its core list operations, its recursive definitions and a running implementation effort, began at MIT in 1958. McCarthy's own history of the language says implementation began that fall, and the Computer History Museum dates his invention of the language to 1958. The fair reading is that LISP was begun and named in 1958, took its defining form during 1959, and was published in 1960. This report keeps those three moments apart.

A language wanted since Dartmouth

McCarthy traced the idea to the 1956 Dartmouth summer project, where Allen Newell, Cliff Shaw and Herbert Simon described IPL 2, the list-processing language in which they had implemented the Logic Theorist. In his account of LISP's prehistory, McCarthy says he felt little temptation to copy IPL, whose form was tied to a loader for RAND's JOHNNIAC computer, because FORTRAN had shown the appeal of writing programs algebraically. What he took away was that any part of a symbolic expression could be reached by composing functions that extract its immediate parts.

The machine shaped the vocabulary. The IBM 704's 36-bit word held two 15-bit fields, the address and the decrement, and McCarthy's functions for the contents of each part of a register became car and cdr. At IBM, Nathaniel Rochester and Herbert Gelernter, on McCarthy's advice, built a list-processing extension of FORTRAN called FLPL for a plane-geometry theorem prover. Gelernter and Carl Gerberich made cons, the operation that builds a list cell, return the new cell's location, so structures could be built by nesting calls. But FLPL had no conditional expressions and no recursion, and discarded lists had to be erased by hand.

McCarthy supplied the missing pieces. While writing chess move routines in FORTRAN in 1957 and 1958 he invented the conditional expression, which evaluates only the branch a test selects. In the summer of 1958, at IBM's Information Research Department, he chose symbolic differentiation as a sample problem and found that it called for recursive definitions written with conditional expressions, a function he named maplist that applies another function to every element of a list, and Alonzo Church's lambda notation for passing functions as arguments. FLPL could not express the program, and McCarthy concluded that a new language was needed, since tinkering with FORTRAN was hard both technically and politically.

The intended application was the Advice Taker, McCarthy's proposal for a program that would hold knowledge as sentences in a formal language and decide what to do by logical inference. The 1960 paper opens by naming it: LISP was designed to support experiments with that system, proposed in November 1958.

What the first memo proposed

The earliest document, AI Memo 1, is dated September 1958 in the Computer History Museum's LISP archive, and it shows how far the starting point was from the language later histories describe. The memo outlines an "incomplete algebraic language" with FORTRAN-style assignment statements, go-to transfers, and functions named after the parts of a 704 word. It credits Newell, Simon and Shaw with the list representation and Gelernter with the algebraic notation for list processing. Recursion is there, with intermediate results saved automatically, as are conditional expressions and functions passed as parameters, and an appendix gives a differentiation routine built from maplist.

What is missing is as telling. Memory is managed by explicit erase functions that return words to a free-storage list. Programs are not themselves lists, and there is no universal evaluating function. The memo does list the uses McCarthy had in mind: theorem proving, the Advice Taker, algebraic simplification, formal differentiation and integration, compilers, and heuristic programs that explore trees of alternative actions. It is a fair map of what LISP would be used for over the next twenty years.

From hand-compiled routines to an interpreter

That autumn McCarthy and Marvin Minsky started the MIT Artificial Intelligence Project under the Research Laboratory of Electronics. McCarthy recalls that no written proposal was ever made; asked what they needed, the two requested a room, two programmers, a secretary and a keypunch ( History of Lisp). The plan was a compiler, but the group began by hand-translating functions, written in an informal FORTRAN-like notation called M-expressions, into 704 assembly language. An October 1958 memo on revisions to the language set conventions for saving registers on a single public push-down list (a stack) during recursive calls, and it used the name LISP, which the historian Herbert Stoyan identifies as the name's first written appearance. Simplifications followed: cons took two arguments, and LISP was left with a single data type that needed no declarations.

The decisive step came from an exercise in theory. To show that LISP was a neater formalism for computable functions than Turing machines, McCarthy wrote a universal LISP function, eval, which computes the value of any LISP expression given a list pairing variables with values. That required a way of writing LISP functions as LISP data, a notation McCarthy says he devised for the paper with no thought that programmers would use it. Steve Russell, one of the project's programmers, saw that eval could serve as an interpreter and coded it by hand. McCarthy later recalled, in an interview Stoyan quotes, warning Russell that he was confusing theory with practice; Russell did it anyway. The unexpected interpreter froze the language's form: the M-expression syntax was never finished, and programmers came to prefer writing programs directly as parenthesized lists.

The documents and the memories do not agree on exactly when this happened. Russell, in a 2008 Computer History Museum oral history, remembered a usable interpreter, without a garbage collector, before Christmas 1958. Stoyan, working from the contemporary paperwork, found a December 1958 Computation Center report describing a routine for applying functions as programmed but not yet debugged, and an April 1959 progress report stating that apply was working as an interpreter for the system. The defensible statement is that LISP became an interpreted language between the end of 1958 and the spring of 1959. By March 1959, AI Memo 8 already carried the published paper's title and, Stoyan notes, much of its structure.

How eval and garbage collection work

The 1960 paper builds everything from symbolic expressions, or S-expressions: atomic symbols such as A or PLUS, and parenthesized lists of S-expressions. Five elementary functions do the basic work: atom tests whether an expression is a symbol, eq compares two symbols, car takes the first element of a list, cdr takes the rest, and cons builds a new list cell from two parts. Conditional expressions choose among cases and recursion supplies repetition.

Because functions are themselves lists, such as (LAMBDA (X Y) (CONS (CAR X) Y)), one function can take another as data. The paper's example applies exactly that expression to the arguments (A B) and (C D) and obtains (A C D). The eval function works by inspecting the first element of an expression. QUOTE returns its argument unevaluated; COND evaluates tests in order until one is true; LAMBDA pairs its variables with the evaluated arguments, puts the pairs on the front of the list of current values and evaluates the body; LABEL, a device McCarthy credits to Nathaniel Rochester in his history, names a function so that it can call itself. The definition fits on a page, which is why eval could serve at once as the formal definition of the language and, translated into 704 code, as its interpreter.

The second mechanism solved a problem that the recursive style created. Recursive functions build new list structure freely and abandon old structure, and explicit erasure would have ruined the notation. McCarthy considered reference counts and, as his history explains, rejected them because the 704 word had only six spare bits, split across two fields. Instead the paper describes what it calls a reclamation cycle. Nothing happens until the free-storage list, initially about 15,000 registers, runs out. Then the program marks every register reachable by chains of car and cdr from a fixed set of base registers, by flipping its sign bit, sweeps the list area, and returns every unmarked register to the free list. The paper warned that a cycle took several seconds, so each one had to recover at least several thousand registers to be worthwhile.

That description ran ahead of the code. According to Stoyan, Daniel Edwards implemented the first garbage collector in June and July of 1959, and the LISP 1.5 Programmer's Manual credits the collector to him. Russell recalled in his oral history that collector bugs, caused by hand-made tables of where list pointers could be stored, kept turning up for at least a year. By the paper's status report of February 1960, the system let a programmer define functions as S-expressions, read and print them, trace them, and compile selected functions into machine code that ran about 60 times as fast as the interpreted version.

From LISP 1 to LISP 1.5

The paper was not LISP's first public description. The museum archive lists a preprint McCarthy presented at the ACM's 1959 national meeting, and McCarthy noted that the earliest publications on LISP were in the laboratory's quarterly progress reports ( History of Lisp). Phyllis Fox wrote the LISP I Programmer's Manual, dated March 1960. McCarthy never wrote the planned Part II, and he admitted that the paper had no influence on recursive function theorists, whose questions it did not address.

Its influence ran instead through the working system. The LISP 1.5 Programmer's Manual, dated August 1962 and published by MIT Press, names the people behind it: Michael Levin wrote the manual, Russell and Edwards programmed the interpreter, and Timothy Hart and Levin wrote the compiler. That compiler was written in LISP, and an MIT memo described it as the first compiler to have compiled itself by being executed in an interpreter ( CHM archive). The move to LISP 1.5 also brought numbers stored efficiently as atoms, functions that receive their arguments unevaluated, and functions that accept a variable number of arguments ( History of Lisp).

It inherited a famous mistake as well. When James Slagle wrote a search function that took another function as an argument, the interpreter used the most recent binding of a variable rather than the one in force where the function had been written. In modern terms Slagle wanted lexical scoping and got dynamic scoping. McCarthy treated it as a bug, and Russell fixed it with the FUNARG device, which carries the defining environment along with a functional argument ( History of Lisp). The tension between that fix and fast compiled code ran through Lisp dialects until Scheme, designed by Gerald Sussman and Guy Steele in the second half of the 1970s, made lexical scoping and closures central ( Common Lisp history).

After the 1962 manual, McCarthy wrote, implementations were made for numerous computers, although no organization ever tried to propagate the language. Steele and Gabriel's history of Lisp's evolution describes it spreading in the early 1960s to a Univac military computer, the SDC Q-32 and the PDP-1, whose BBN version was written in 1963 by a high-school student, L. Peter Deutsch.

Three decades as the working language of AI

The first users were AI researchers. McCarthy lists Slagle's thesis on symbolic integration, Rochester and Saul Goldberg's symbolic analysis of electrical networks, and Paul Abrahams's proof checker among the early applications ( History of Lisp). Russell recalled five to ten serious graduate students, plus about 20 students from McCarthy's introductory AI course, using it in those early years.

The language then shaped hardware. McCarthy wrote that the half-word and stack instructions of Digital Equipment's PDP-6 and PDP-10 were developed with LISP's requirements in mind, and that the MIT and BBN dialects helped make those machines the standard computers of AI research ( History of Lisp). The history section of the Common Lisp standard calls the PDP-10 the mainstay of Lisp and AI work at MIT, Stanford and Carnegie Mellon from the mid-1960s through much of the 1970s, and records that MacLisp was in use at more than 50 sites by the end of that decade. BBN's dialect, renamed Interlisp in 1973 when Xerox PARC began sharing its maintenance, was the other main branch ( Steele and Gabriel).

Because LISP treated programs as data, other AI languages were built on top of it. Steele and Gabriel describe Micro-Planner, a goal-directed theorem-proving language, embedded inside MIT's PDP-6 Lisp; the frame-based KRL, implemented in Interlisp; and OPS5, the rule language behind Digital Equipment's XCON configuration system, which was first implemented in Lisp before being recoded in BLISS for speed. Programs such as Terry Winograd's SHRDLU were written in it. Norvig's 1992 preface adds an important qualification: in Europe and Japan, Prolog had been as popular as Lisp for AI work. That geography matters, since Japan's Fifth Generation project bet on logic programming, not on Lisp.

Lisp machines and the commercial test

By 1973 the PDP-10's 18-bit address space of 262,144 words limited the size of a single program ( Common Lisp history). One answer was a computer built for Lisp. Richard Greenblatt started the MIT Lisp Machine project in 1974, aiming at a single-user machine costing less than $70,000 with hardware support for type checking and garbage collection ( Steele and Gabriel). Its successor, the CADR, was described in 1979 as a 32-bit microprogrammable processor designed as a high-performance, economical implementation of Lisp. Dozens were built, and disagreements among the principals produced two companies, Lisp Machines Inc. and Symbolics, whose 3600 led Lisp machine performance for five years. Commercial Lisp machines from Xerox, LMI and Symbolics were on the market by 1981.

The spread of incompatible dialects worried DARPA, which funded much of American AI. After a DARPA-sponsored meeting in April 1981, Symbolics, Carnegie Mellon's SPICE project and the NIL and S-1 Lisp projects joined to define Common Lisp, described in a 1984 book, and in 1986 the X3J13 committee began work toward an ANSI standard ( Common Lisp history).

The machines did not survive the decade's economics. Steele and Gabriel describe how non-intrusive garbage collectors on ordinary workstations, first from Lucid and Franz in 1989, undercut the claim that only special hardware could run Lisp fast, and how stock-hardware Lisp companies came to dominate as RISC workstations improved. The fall of the Lisp machine makers became part of the second AI winter.

The honest limits

Several popular claims need trimming. LISP was not the first list-processing language: IPL preceded it and supplied the list representation, as McCarthy's first memo acknowledged, and FLPL already composed list operations algebraically. Nor was AI born in LISP. The Logic Theorist ran in IPL and IBM's geometry prover in FLPL ( History of Lisp).

LISP was also never the pure functional language of later legend. Stoyan argues that at the end of the 1950s nobody, McCarthy included, seriously based programming on the mathematical function, and McCarthy conceded that LISP kept functions with side effects, such as rplaca and rplacd, which break the rule of replacing equals by equals. In all the early LISPs, numerical computation ran 10 to 100 times slower than in FORTRAN ( History of Lisp). Using zero for both the empty list and false was a choice McCarthy came to regret, and dynamic scoping was an accident that later dialects spent years undoing.

Credit is not fully settled either. Stoyan reports that Abrahams and Klim Maling remembered Roland Silver first proposing garbage collection, while McCarthy maintained that he had conceived it. LISP's dominance of AI was, on Norvig's own account, largely American. And its central role was tied to symbolic methods. The neural network systems that lead the field today were built around other languages; the 2019 paper introducing the PyTorch library, for example, stresses that every part of it is a regular Python program ( Paszke and colleagues).

How to place LISP in AI history

LISP is an infrastructure event, judged by what it let others do. Its novelty was a combination. List processing came from IPL, lambda notation from Church and the algebraic style from FORTRAN; conditional expressions, recursion over symbolic data, programs written as data, a universal eval and automatic garbage collection were what McCarthy's group added, most of them during 1959. Together they gave AI researchers a medium in which programs could build, inspect and run other programs.

Its influence is documented in the field's own tools: AI programs and languages were built in LISP for three decades, computers were designed around it, and an industry rose and fell on it. Its reach went beyond AI. In 1979 McCarthy called it the second oldest programming language in widespread use, after FORTRAN ( History of Lisp: Conclusions), and Norvig's preface notes dialects living on inside the GNU Emacs editor and the AutoCAD design package. McCarthy received the 1971 ACM Turing Award, and the Computer History Museum lists LISP with the naming of AI and the idea of time-sharing among his contributions.

The right placement is at the base of symbolic AI rather than of AI as a whole. LISP made the symbol-manipulating programs imagined in the Dartmouth proposal practical to write and carried that tradition through planners, language-understanding systems, expert systems and the Lisp machines. When the field's center of gravity moved to learning from data, its particular role faded, but for thirty years it was the material most of AI was made of.

References

• John McCarthy, MIT Artificial Intelligence Project (1958). An Algebraic Language for the Manipulation of Symbolic Expressions, AI Memo 1.
• John McCarthy, MIT Artificial Intelligence Project (1958). Symbol Manipulating Language, Memo 4: Revisions of the Language.
• John McCarthy, MIT Artificial Intelligence Project (1959). Recursive Functions of Symbolic Expressions and Their Computation by Machine, AI Memo 8.
• John McCarthy, Communications of the ACM (1960). Recursive Functions of Symbolic Expressions and Their Computation by Machine, Part I.
• John McCarthy, Stanford University (1979). History of Lisp: LISP prehistory, Summer 1956 through Summer 1958.
• John McCarthy, Stanford University (1979). History of Lisp: The implementation of LISP.
• John McCarthy, Stanford University (1979). History of Lisp: From LISP 1 to LISP 1.5.
• John McCarthy, Stanford University (1979). History of Lisp: Beyond LISP 1.5.
• John McCarthy, Stanford University (1979). History of Lisp: Conclusions.
• Herbert Stoyan, ACM Symposium on LISP and Functional Programming (1984). Early LISP History, 1956 to 1959.
• Computer History Museum (2008). Oral History of Steve Russell.
• John McCarthy, Paul W. Abrahams, Daniel J. Edwards, Timothy P. Hart and Michael I. Levin, MIT Press (1962). LISP 1.5 Programmer's Manual.
• Paul McJones, Computer History Museum Software Preservation Group (2026). LISP 1.5 family: source code, documentation and papers.
• Guy L. Steele Jr. and Richard P. Gabriel (1993). The Evolution of Lisp.
• LispWorks (1996). Common Lisp HyperSpec, Section 1.1.2: History.
• Thomas F. Knight, David A. Moon, Jack Holloway and Guy L. Steele, MIT AI Laboratory (1979). CADR, AI Memo 528.
• Peter Norvig (1992). Paradigms of Artificial Intelligence Programming: Preface.
• Computer History Museum (1999). John McCarthy, 1999 Fellow.
• Adam Paszke et al. (2019). PyTorch: An Imperative Style, High-Performance Deep Learning Library.