Early LISP History (1956-1959)

✨ Summary

Summary

Herbert Stoyan reconstructs the development of LISP from John McCarthy’s early work on programming languages for artificial intelligence through the emergence of a functioning LISP 1 implementation in May 1959. The paper emphasizes that LISP was not originally conceived as a purely functional language grounded directly in mathematical function theory. Instead, it developed incrementally from practical concerns about representing symbolic information, describing procedures concisely, and supporting artificial-intelligence research.

The account begins with McCarthy’s 1955 Dartmouth proposal for a language suitable for expressing knowledge, arguments, self-reference, and intelligent behavior. It then traces the influence of Newell and Simon’s list-processing work and McCarthy’s attempt to combine list manipulation with FORTRAN. This work produced the FORTRAN List Processing Language and exposed conceptual limitations in treating symbolic structures as machine words and addresses rather than as a distinct domain of symbolic expressions.

The paper identifies several ideas that became central to LISP: conditional expressions, recursion, functional arguments, function composition, symbolic differentiation, maplist, list-based program representation, quotation, and the use of lists to represent both programs and data. It also follows the transition from early FORTRAN-like proposals to a separate language after it became clear that recursion, higher-order functions, and conditional expressions could not be added cleanly to FORTRAN or ALGOL-style languages.

A substantial part of the reconstruction concerns the sequence of early interpreter designs between late 1958 and spring 1959. Stoyan describes the introduction of the name LISP, the development of apply and eval, the use of substitution and association lists, the emergence of S-expressions, and implementation problems involving variable binding, functional arguments, and recursive evaluation. The paper presents these early interpreter designs critically, noting that several contained errors and that their implementation history is partly uncertain because many intermediate documents were lost.

The paper also describes practical implementation work on the IBM 704, including hand translation into SAP assembly language, stack management, function-call conventions, free-storage management, and the emergence of automatic garbage collection. By May 1959, LISP had become a usable system for symbolic algebra and electrical-network analysis, although it still lacked later sequential constructs such as PROG and PROGN.

Research and industry influence

The paper’s documented influence is primarily historiographical rather than a direct contribution to programming-language implementation. It became a recognized source for reconstructing LISP’s early development: the ACM record identifies it as a historical account of LISP’s evolution and reports 11 citations, while bibliographic records preserve it as a standard reference for the 1956–1959 period. (doi.org) John McCarthy’s historical archive explicitly points readers to Stoyan’s account and states that Stoyan’s analysis of the surviving documents provided a more accurate picture than McCarthy’s own recollections. (www-formal.stanford.edu) The Computer History Museum’s guide to the Stoyan collection also catalogs the paper as part of the documentary record used to preserve LISP history. (archive.computerhistory.org)

The paper is subsequently cited in historical surveys and bibliographies of functional programming and LISP, including a NASA survey of functional programming and later accounts of LISP’s origins. (ntrs.nasa.gov) No evidence was found that the paper itself directly drove an industrial language implementation or commercial technology; its concrete impact is instead as a source for scholarship, archival preservation, and historical interpretation of LISP’s formation.