LISP — The Ancestor of Functional and AI Languages

Lisp is a programming language for computing with symbolic expressions — nested lists of symbols — rather than with numbers. Its name is short for LISt Processor. John McCarthy began implementing it at MIT in the autumn of 1958 and published the design in Communications of the ACM in April 1960 as "Recursive Functions of Symbolic Expressions and Their Computation by Machine, Part I". Writing in 1979, McCarthy called it "the second oldest programming language in present widespread use", after FORTRAN.

The ideas are older than the code, and McCarthy's own History of Lisp splits the story into two periods: summer 1956 to summer 1958, when most of the key ideas formed, and autumn 1958 to 1962, when the language was implemented and put to work on artificial intelligence.

1956–58: wanting a list language for AI

By McCarthy's account, the wish for "an algebraic list processing language for artificial intelligence work on the IBM 704" arose during the Dartmouth summer project of 1956. There Allen Newell, Cliff Shaw and Herbert Simon described IPL 2, the list language in which they had written the Logic Theorist. McCarthy did not want to copy it: its form was tied to the JOHNNIAC computer, and the FORTRAN idea of writing programs algebraically was more attractive.

Three steps before MIT shaped what Lisp became.

FLPL had neither conditional expressions nor recursion, and the IBM group did not want the drastic changes needed to add them. In McCarthy's words, it was "very difficult both technically and politically to tinker with Fortran". A new language was necessary.

Autumn 1958: the MIT AI Project

In autumn 1958 McCarthy became an assistant professor at MIT, and he and Marvin Minsky started the MIT Artificial Intelligence Project. No written proposal was ever made. Asked what they needed, they requested a room, two programmers, a secretary and a keypunch.

Implementation began that autumn. The first plan was a compiler, but that was a major undertaking, so the group started by hand-compiling functions into assembly language. Two names that still survive came from the hardware. An IBM 704 word had an "address" part and a "decrement" part, and the operations to fetch them were named car (Contents of the Address part of Register number) and cdr (Contents of the Decrement part of Register number).

The 1960 paper states the purpose plainly: LISP was designed to support experiments with a proposed system called the Advice Taker, a machine that could be instructed with declarative as well as imperative sentences and show "common sense" in carrying them out. The paper dates that proposal to November 1958.

eval, Steve Russell, and the parentheses

McCarthy wanted to show that Lisp was a neater way of describing computable functions than a Turing machine. The proof was a universal function, eval, which takes a Lisp expression and computes its value. To write it he had to represent Lisp programs as Lisp data — the S-expression, the parenthesised list — a notation devised, he says, "with no thought that it would be used to express LISP programs in practice".

People were meant to write M-expressions, a FORTRAN-like notation with square brackets. Then Steve Russell noticed that eval could serve as an interpreter, "promptly hand coded it", and the project had a working language with an interpreter.

McCarthy is candid about the consequences. The unexpected interpreter "tended to freeze the form of the language", including decisions made "rather lightheartedly" for the paper, such as the COND notation and using zero for both the empty list NIL and false. Defining M-expressions properly was never finalised nor explicitly abandoned; it "just receded into the indefinite future". The parentheses stayed.

Garbage collection, under another name

The 1960 paper describes how unused list cells return to the free-storage list automatically: when free storage runs out, the program marks everything reachable from its base registers and sweeps the rest back. The paper calls this a reclamation cycle. A note McCarthy added to his online copy says they already called it "garbage collection" but he "chickened out" of using the term in print. See also garbage collection in the glossary.

The term was not secret for long. In History of Lisp, McCarthy recalls the first online Lisp demonstration, for MIT industrial visitors, during which the Flexowriter suddenly began printing a full page of garbage-collector statistics at ten characters a second, eating the rest of the time slot.

From LISP I to LISP 1.5

The Software Preservation Group dates the LISP I Programmer's Manual, by Phyllis Fox, to 1 March 1960. The LISP 1.5 Programmer's Manual, by McCarthy, Paul Abrahams, Daniel Edwards, Timothy Hart and Michael Levin, followed in August 1962 from MIT Press, and McCarthy says many implementations on other computers followed its publication.

Along the way came property lists, numbers stored as atoms, Russell's FUNARG device for what would now be called lexical scoping, and the first successful Lisp compiler, by Hart and Levin. It was written in Lisp; its memo describes it as the first compiler to have compiled itself by being executed interpretively — the memo's own claim. Numerical work stayed slow: McCarthy puts early Lisps at 10 to 100 times slower than FORTRAN for arithmetic.

What came after

McCarthy notes that no organisation ever tried to propagate Lisp, and it spread anyway. The most important implementations, by his account, were for DEC's PDP-6 and PDP-10, whose half-word and stack instructions were designed with Lisp in mind; MACLISP and INTERLISP grew there. Later dialects include Scheme (1975), Common Lisp, standardised by ANSI in 1994, and Clojure on the Java virtual machine. Its approach of treating functions as values runs through functional programming generally.

McCarthy's own explanation of Lisp's survival is an odd one: perhaps it lasted precisely because its programs are lists, "which everyone, including me, has regarded as a disadvantage".

The language's place among its contemporaries is on the programming-languages timeline; the man who began it, on John McCarthy.