Recursive Functions of Symbolic Expressions and Their Computation by Machine, Part I
Programs and data are the same lists — and one tiny function, eval, can run them all.
What if a program were made of the very same stuff as the data it works on — so it could read, build, and run other programs as easily as you add two numbers?
The idea, unpacked
McCarthy's LISP is built from almost nothing. Everything — data and program alike — is an S-expression: either a plain symbol like A, or a pair of two expressions written (e1 · e2). With two operations that pull a pair apart (car takes the left half, cdr the right), one that builds a pair (cons), and two questions — "is this a single symbol?" and "are these two symbols the same?" — you can assemble lists of any shape.
The twist is that a LISP program is itself just such a list. So McCarthy could write one short function, eval, that takes any program-as-list and runs it — an interpreter written in the very language it interprets. Define how to take things apart, put them together, choose between cases, and call yourself again, and you have a complete, universal computer.
Where it came from
In 1958 McCarthy, then at MIT, proposed the "Advice Taker," a program meant to reason with everyday facts. To build it he needed a language for handling symbols and expressions, not just numbers, and out of that goal grew LISP — short for "LISt Processor" — on the IBM 704. He published the design in 1960 in the Communications of the ACM. He had written eval as a piece of theory; a student, Steve Russell, realised it could simply be typed into the machine, and the first LISP interpreter blinked into existence — to McCarthy's surprise.
Why it mattered
LISP introduced, as working parts, ideas the whole computing world now takes for granted: the if-then-else choice; defining a function by having it call itself (recursion); the list as a universal container; and — quietly — automatic memory cleanup, which McCarthy later named "garbage collection." It became the language of artificial intelligence for thirty years, and the second-oldest high-level language still in use, after FORTRAN.
An analogy
Think of LEGO. An atom is a single brick; a pair is two things clicked together. car and cdr are "take the left piece" and "take the right piece"; cons is "click two pieces together." Now suppose the instruction booklet for a model could itself be written out of LEGO bricks. Then you could hand the model a copy of its own instructions and let it build itself. That self-reference — programs made of the same bricks as the data — is LISP's whole trick. Try taking expressions apart with the tool below.
Where it sits
LISP is the practical twin of Alonzo Church's λ-calculus (1936) and Alan Turing's machine (1936) — the abstract answers to "what is computable" — turned into a language you can actually run. Where John Backus's FORTRAN (1957) made numerical computing fast, McCarthy made symbolic computing possible. Its line of descent runs through Scheme and Clojure to the present day, and the garbage collection it pioneered now lives inside Java, Python, and JavaScript.
A programming system called LISP (for LISt Processor) has been developed for the IBM 704 computer by the Artificial Intelligence group at M.I.T.
the notion of conditional expression is believed to be new, and the use of conditional expressions permits functions to be defined recursively in a new and convenient way.
1. Atomic symbols are S-expressions. 2. If e1 and e2 are S-expressions, so is (e1 · e2).
car [cons [x; y]] = x · cdr [cons [x; y]] = y · cons [car [x]; cdr [x]] = x, provided that x is not atomic.
the universal S-function apply which plays the theoretical role of a universal Turing machine and the practical role of an interpreter.
Nothing happens until the program runs out of free storage. When a free register is wanted, and there is none left on the free-storage list, a reclamation cycle starts.