Lisp

In 1956, the Lisp project emerged as part of the Dartmouth summer research on artificial intelligence. John McCarthy was then seeking an algebraic language to process lists on the IBM 704. He took an interest in the work of Newell, Shaw, and Simon on IPL 2, a language designed for the RAND Corporation’s JOHNNIAC, but refused to reproduce its form, which was too dependent on its original environment. The algebraic approach of Fortran appealed to him more.

Two circumstances favored this development: the creation of an IBM computing center at MIT, accessible from Dartmouth, and the launch by IBM of a program for demonstrating geometric theorems based on an idea by Marvin Minsky, for which McCarthy worked as a consultant. IBM seemed to be committing to emerging AI research.

In 1958, McCarthy proposed the concept of the Advice Taker, a system designed to represent information through sentences in a formal language and make decisions through logical deductions. The representation of sentences by list structures naturally emerged, as did the use of a list-processing language to program deductive operations.

The first technical challenge concerned the implementation of list structures on the IBM 704. This computer used 36-bit words, with two 15-bit sections named address and decrement. The addressing limited to 15 bits made it necessary to use pointers of identical size for list structures. McCarthy initially established functions including cwr (Contents of Word in Register) and four extraction functions. He noted that extracting a sub-expression required composing the address extraction with cwr, while progressing through the list required composing the decrement extraction with cwr. These observations gave birth to the car (Contents of Address Register) and cdr functions, which would become emblematic of the language.

During 1957 and 1958, McCarthy designed conditional expressions while programming chess routines in Fortran. The limitations of Fortran’s IF statement led him to create an XIF(M,N1,N2) function returning N1 or N2 depending on whether M was zero. This solution simplified programs but suffered from the systematic evaluation of all three arguments. He invented the true conditional expression, evaluating only the necessary expressions.

In the summer of 1958, invited by Nathaniel Rochester at IBM, McCarthy worked on differentiating algebraic expressions. This work introduced several advances: writing recursive functions using conditional expressions, the maplist function forming a list of applications of a functional argument to the elements of a list, and the use of Church’s λ notation to name functions. His recursive definition of differentiation did not provide for erasing abandoned structures, as he refused to compromise the elegance of his definition.

In the fall of 1958, McCarthy joined MIT as an assistant professor in communication sciences and launched the MIT artificial intelligence project with Minsky. Lisp development began with the initial goal of creating a compiler. The team started by manually compiling various functions into assembly language and writing Lisp environment subroutines to read and write list structures.

Programs were first written in an informal notation called M-expressions, designed to resemble Fortran. This notation used brackets for function arguments, reserving parentheses for list structure constants. The M notation would never be fully formalized, as the representation of Lisp functions by lists emerged as the dominant approach after the interpreter appeared.

The READ and PRINT functions established a standard external notation for symbolic information. For example, the expression x + 3y + z became PLUS X (TIMES 3 Y) Z. This notation would be named Cambridge Polish, in reference to Lukasiewicz’s prefix notation and its earlier use by Quine.

Memory management raised a particular problem. Explicit erasure, used in IPL, lacked elegance. Two options presented themselves: erasing the old contents of a variable when updating it, which required reference counters impossible to integrate into the six available bits, or using garbage collection, which abandoned storage until the free list was exhausted, marked storage accessible from variables and the stack, then transformed unmarked storage into a new free list.

Subsequent versions of Lisp brought various functionalities: property lists associated with atoms, insertion and deletion of elements in lists (via rplaca and rplacd), efficient application of numbers as atoms, and the program feature for writing sequential programs with assignment statements and jumps.

Two reasons explain Lisp’s longevity. On one hand, its core occupies a form of local optimum in the space of programming languages, with the recursive use of conditional expressions, the representation of symbolic information by lists, and the uniform representation of programs and data. On the other hand, Lisp offers unique operational characteristics that make it a privileged vehicle for symbolic computation and artificial intelligence systems: its runtime system providing access to host machine functionalities, its internal representation facilitating compilation from higher-level languages, and the availability of its interpreter as a command language.