Recursive Functions of Symbolic Expressions and Their Computation by Machine, Part I
đź“ś Abstract
A programming system called LISP (for LISt Processor) has been developed for the IBM 704 computer by the Artificial Intelligence group at M.I.T. The system was designed to facilitate experiments with a proposed system called the Advice Taker, whereby a machine could be instructed to handle declarative as well as imperative sentences and could exhibit “common sense” in carrying out its instructions. The original proposal [1] for the Advice Taker was made in November 1958. The main requirement was a programming system for manipulating expressions representing formalized declarative and imperative sentences so that the Advice Taker system could make deductions. In the course of its development the LISP system went through several stages of simplification and eventually came to be based on a scheme for representing the partial recursive functions of a certain class of symbolic expressions. This representation is independent of the IBM 704 computer, or of any other electronic computer, and it now seems expedient to expound the system by starting with the class of expressions called S-expressions and the functions called S-functions.
✨ Summary
Summary
John McCarthy presents the mathematical and implementation foundations of LISP. The paper defines symbolic expressions, including atoms and recursively constructed ordered pairs, and introduces a compact list notation for representing them. It defines the elementary operations atom, eq, car, cdr, and cons, then shows how conditional expressions and recursive definitions can construct more powerful symbolic functions such as substitution, structural equality, list append, association lookup, and symbolic differentiation.
A central contribution is the representation of functions themselves as symbolic expressions. The universal function apply, together with eval, provides an interpreter capable of evaluating encoded LISP programs, making programs and data representations of the same general kind. The paper also describes functions taking other functions as arguments, IBM 704 list-structure storage, association lists, automatic reclamation of unused storage, compilation of recursive functions, and the relationship between recursive function definitions and conventional flowcharts.
Influence
The paper is identified by McCarthy’s Stanford archive as the original paper on Lisp. (www-formal.stanford.edu) Its definitions of S-expressions, symbolic list processing, recursive functions, and an evaluator formed the conceptual basis for subsequent LISP implementations. The LISP 1.5 Programmer’s Manual, published in 1962, documents a succeeding system using S-expressions as its data representation and interpreting programs represented as S-expressions; it also records applications in symbolic mathematics, mathematical logic, game playing, and artificial intelligence. (mitpress.mit.edu) The paper’s role in the early development of LISP is likewise treated as a milestone in the historical account of LISP development presented in the 1984 ACM symposium proceedings. (doi.org) Bibliographic records identify the article as a peer-reviewed Communications of the ACM publication dated April 1, 1960, with DOI 10.1145/367177.367199. (explore.openaire.eu)