What is Lisp, and why did John McCarthy create it for artificial intelligence?

Early computers were built to calculate. Their languages, such as FORTRAN, were good at arithmetic on numbers arranged in neat tables. But the first AI researchers wanted machines that could handle ideas: logical statements, words, chess positions, algebraic formulas. Those things come in all shapes and sizes, and they nest inside one another.

John McCarthy, the mathematician who had coined the term "artificial intelligence," decided AI needed its own language. The result was Lisp, and it turned out to be one of the most influential programming languages ever designed. It is the second-oldest high-level language still in wide use; only FORTRAN is older, by a year.

How Lisp came about

McCarthy traced the idea to the summer of 1956, at the Dartmouth workshop on artificial intelligence. There, Allen Newell, Cliff Shaw and Herbert Simon described IPL, the list-processing language they had built for their Logic Theorist on RAND's JOHNNIAC computer. McCarthy liked the idea of storing information as lists, but wanted something that read more like algebra, the way FORTRAN did.

Several pieces came together over the next two years. Working on chess programs in FORTRAN at MIT in 1957–58, McCarthy invented the conditional expression, a way to write "if this, then that value, otherwise this other value" inside a formula. In the summer of 1958, at IBM's Information Research Department, he chose the task of differentiating algebraic expressions (the calculus operation of finding a rate of change) as a test case. That exercise convinced him he needed recursive functions, functions that could be passed other functions, and the "lambda" notation for naming functions that he borrowed from the logician Alonzo Church.

IBM's existing list-processing tool could not do these things, and adding them to FORTRAN looked impractical. So in the fall of 1958, when McCarthy moved to MIT and started the Artificial Intelligence Project with Marvin Minsky, the team began building a new language for the IBM 704.

How Lisp works

Lisp has one basic kind of data, the symbolic expression or S-expression. An S-expression is either an atom, a single symbol such as CAT or X, or a list of other S-expressions in parentheses. Because lists can contain lists, Lisp can represent anything with a nested structure. McCarthy's notes give the formula x + 3y + z as:

(PLUS X (TIMES 3 Y) Z)

A handful of basic operations take lists apart and build them up. Their odd names come from parts of a word in the IBM 704's memory:

With those pieces plus conditional expressions, you can write recursive functions, which solve a problem by calling themselves on a smaller piece of it. Here is a function, in a modern Lisp dialect, that counts the items in a list:

(defun count-items (lst)
  (cond ((null lst) 0)
        (t (+ 1 (count-items (cdr lst))))))

It reads: if the list is empty, the answer is 0; otherwise, it is 1 plus the count of the rest of the list.

Surprises along the way

Lisp's history has some happy accidents. To show that Lisp could describe any computation as neatly as a Turing machine, McCarthy wrote a function called eval that takes a Lisp expression and computes its value. He meant it as a piece of theory. A programmer on the project, Steve Russell, realized eval could serve as a working interpreter, coded it by hand for the IBM 704, and suddenly Lisp could run programs directly.

That trick depended on another idea: Lisp programs are themselves written as lists, so a Lisp program can read, build and change other Lisp programs. The team also decided not to make programmers free up memory by hand. Instead, Lisp would periodically find data no longer in use and reclaim it, a technique called garbage collection that most modern languages now rely on.

McCarthy published the design in April 1960 in Communications of the ACM as "Recursive Functions of Symbolic Expressions and Their Computation by Machine, Part I." He explained that Lisp was meant for experiments with the Advice Taker, a proposed program that could accept statements about the world and reason from them with common sense. The first full Lisp compiler written in Lisp followed in 1962; two MIT researchers, Tim Hart and Mike Levin, wrote it.

Why it mattered

Lisp quickly became the favorite language of AI research. Its lists suited the symbolic approach that dominated the field: theorem provers, planners and language programs all manipulate structured symbols. Many ideas it pioneered, including recursion, functions as values, automatic memory management, and the interactive loop where you type an expression and see its value at once, spread into languages far beyond AI.

Is Lisp still used for AI today?

Lisp is no longer the main language of AI. In early 2019 most machine-learning work is done in Python, using libraries such as TensorFlow and PyTorch that run heavy number-crunching on fast hardware. Deep learning is mostly about multiplying large tables of numbers, the kind of task Lisp was never designed around.

Lisp itself is very much alive, though, in several dialects. Common Lisp has had an official ANSI standard since 1994. Scheme remains a well-known compact dialect. Clojure, a practical general-purpose Lisp, runs mainly on the Java virtual machine. The Emacs text editor is extended with its own dialect, Emacs Lisp.

Its deeper influence is everywhere. When a Python programmer writes a short anonymous function with lambda, passes one function to another, or never thinks about freeing memory, they are using ideas that Lisp made practical. If you want to understand how early AI researchers thought about symbols and reasoning, writing a few small Lisp functions is still one of the best ways to learn.