List Processing
List processing is both a data structure and a programming paradigm: information is held in chains of cells, each linked to the next by a pointer, so that structures can grow, shrink, and be rearranged freely while a program runs, and computation consists largely of building, traversing, and transforming such structures. It was the technique that let early AI researchers compute with symbols and relationships, not just numbers, and it is distinct from the history of any single language that used it.
The motivating problem was that the numeric arrays of 1950s programming could not hold the irregular, changing structures that symbolic work produced. A theorem prover or a chess program generates expressions, move sequences, and search trees whose size cannot be known in advance and whose parts are constantly inserted, deleted, and shared. A fixed block of consecutive memory locations handles that poorly, since inserting an item means shifting everything behind it. A linked list stores each item in a cell that holds a value and a pointer to the next cell, so insertion at a known position only changes a pointer, and the structure can be extended anywhere memory is available. Newell, Shaw, and Simon built this idea into their Information Processing Language in 1956, and McCarthy's Lisp soon made it elegant.
The basic repertoire of operations is tiny, and the names in Lisp's version have become part of programming folklore. Cons builds a new cell from an item and an existing list, car returns the first element, and cdr returns the rest, so that the list of a, b, and c is cons applied to a and the result of consing b onto the result of consing c onto the empty list. A function that processes a list typically asks whether it is empty, and if not handles the first element and calls itself on the rest, which is why list processing and recursion grew up together. Because an element may itself be a list, the same cells represent trees, nested expressions, and networks, and structure can be shared between several lists without copying.
As a paradigm, list processing meant treating symbols and their relations as the primary objects of computation. The data of a program such as the Logic Theorist (1956) were logical expressions, and the operations were pattern matching and substitution on those expressions. This was the technical content of the symbolic AI tradition: knowledge as structured symbol strings, reasoning as manipulation of them. IPL did this with low-level, assembly-like primitives, while Herbert Gelernter and colleagues built FLPL, a Fortran-based list-processing system, around 1959 for a geometry theorem prover. Lisp raised the idea to the level of a full language by making lists also the form of programs, which is a different matter from the paradigm itself, and the later language article should be read for that biography.
List processing has costs that explain why it is no longer the default data structure. Reaching the nth element of a linked list means following n pointers, and cells scattered across memory behave badly with modern processor caches, so contiguous arrays and hash tables usually beat linked lists in practice even for tasks that look list-shaped. The paradigm's lasting contributions are therefore conceptual and linguistic: dynamic allocation, which needed automatic reclamation of unreachable cells and so led to garbage collection, immutable and persistent lists used in functional languages such as Haskell, and the habit of writing programs as transformations of sequences, visible in the map, filter, and reduce operations that are standard in Python, JavaScript, and many others.
A frequent misunderstanding is that Lisp lists and the lists of other languages are the same thing. Python's list is a resizable array rather than a chain of cells, and real Lisps provide vectors and hash tables as well, so the name list processing describes a technique and a founding emphasis more than everything the languages do today. Another is that the idea belongs only to symbolic AI, when linked structures underlie operating systems, file systems, compilers, and the abstract syntax trees through which language tools and modern code-generating models see programs. Even the pointer-chasing style persists inside databases and graph engines, where the shape of data is as irregular as it was for Newell's theorem prover.
Read list processing as the early insight that computation could be about structures of symbols rather than arrays of numbers: a few operations on linked cells, born with IPL and polished in Lisp, that made symbolic AI practical and left dynamic data structures and recursion in the common toolkit.