Lisp

What it is

Lisp is a programming language whose name is an abbreviation of "List Processor", and linked lists are one of its main data structures ^[1]. Its source code is itself made of lists, which lets programs manipulate their own source as data and underpins its macro systems ^[1]. The Computer History Museum describes the same idea from another direction: a key feature of Lisp was that data and programs were simply lists in parentheses, so a program could treat another program, or itself, as data ^[3]. A linked list, in the ordinary sense, is a chain of items in which each item points to the next, so a list can be extended, split or passed around without being copied as a block.

Origins

John McCarthy began developing Lisp in 1958 while he was at the Massachusetts Institute of Technology ^[1], and the Computer History Museum's timeline likewise places the invention of LISP, short for List Processing, in 1958 at MIT ^[3]. Wikipedia lists the language as first appearing in 1960 ^[1]. McCarthy published its design in Communications of the ACM on 1 April 1960, in a paper titled "Recursive Functions of Symbolic Expressions and Their Computation by Machine, Part I" ^[1]; McCarthy's Stanford page identifies the same April 1960 paper as the original paper on Lisp ^[2].

Lisp was originally created as a practical mathematical notation for computer programs, and was influenced by, though not originally derived from, Alonzo Church's lambda calculus ^[1]. The paper showed that a Turing-complete language for algorithms could be built from a few simple operators and a notation for anonymous functions borrowed from Church ^[1]. Turing-complete here means what it means generally: the language is powerful enough to express any computation a general-purpose machine can carry out.

Implementation and early versions

The language was first implemented by Steve Russell on an IBM 704 using punched cards, after he realised that the eval function could be implemented in machine code ^[1]. On that machine, two assembly macros, car and cdr, became the primitives for taking the first element of a list and the rest of a list ^[1]; both names stayed in the language's vocabulary. LISP 1.5 was the first widely distributed version, developed by McCarthy and others at MIT ^[1].

The first complete Lisp compiler, written in Lisp itself, was implemented in 1962 by Tim Hart and Mike Levin at MIT, with a reported 40-fold speed improvement over the interpreter ^[1]. Garbage collection routines were developed by MIT graduate student Daniel Edwards prior to 1962, and Lisp introduced the concept of automatic garbage collection ^[1] — that is, the language runtime, rather than the programmer, works out when a piece of memory can no longer be reached and may be reused.

Place in AI research

Lisp quickly became a favoured programming language for artificial intelligence research ^[1], and the Computer History Museum notes that it is still used in a large number of artificial intelligence applications ^[3]. What made it durable is the property described above: because code and data share the same list form, a program can build, inspect and run other programs as ordinary values, which suits symbol manipulation better than languages built mainly around arithmetic do.