An Algebraic Language for the Manipulation of Symbolic Expressions (1958) [pdf] (softwarepreservation.computerhistory.org)

John McCarthy’s 1958 memorandum sketches an “algebraic language for the manipulation of symbolic expressions” — the blueprint that became Lisp. It proposes a language tailored to AI tasks such as theorem proving, heuristic search, symbolic algebra (differentiation, simplification), and compilers. McCarthy emphasizes algebraic/functional notation, recursion, conditional expressions, and first‑class use of functions and predicates, arguing these features make representation and transformation of dynamically sized tree-like expressions far more natural than existing languages (e.g., Fortran). The memo explicitly links the design to early AI work by Newell, Simon, Shaw and Gelernter. Technically, McCarthy specifies a list-as-linked‑words memory model for IBM 704/709 machines (36‑bit words split into address/decrement/prefix/tag fields), with list links stored in the decrement field and data in the address field (often stored as the complement). He defines kinds of quantities (arithmetic, propositional bits, locational addresses, functional), propositional predicates as single bits, conditional expressions, and mechanisms for passing functions or locational expressions as parameters. Control primitives include go(e) and set(Ai …) for dynamic arrays, declarative “property lists” on symbols, and Fortran‑like arithmetic and iteration forms. The memo is deliberately partial but introduces core ideas — list-based storage, automatic protection of temporaries in recursion, and algebraic composition — that underlie symbolic computation and functional programming in AI.