Recursive Functions of Symbolic Expressions and Their Computation by Machine, Part I
đź“ś Abstract
This paper is concerned with the problem of computing by machine, a class of functions that can be defined recursively in terms of symbolic expressions. A formalism for describing such functions is introduced for getting inherently non-local symbolic expressions and for working with functions whose elements are recursively defined.
✨ Summary
John McCarthy’s seminal paper, published in 1960, laid the groundwork for the development of LISP, a programming language designed for symbolic computation. It introduced the concept of recursive functions on symbolic expressions, which became foundational in computer science, particularly in the fields of artificial intelligence and functional programming. This work formalized the computation of symbolic expressions through recursion, providing a language construct that supports computation in the abstract and complex problem-solving typical of AI research. LISP’s impact is widespread in AI due to its flexibility in handling symbolic data and its support for rapid prototyping of AI algorithms. The concepts from this paper also influenced the design of subsequent programming languages that support functional programming paradigms. Research that cites this paper often focuses on AI’s historical progress and the foundational nature of LISP. Influences can be seen in documents such as “LISP: An Interactive LISP System,” by Anthony I. Wasserman and James C. Morris, in the Proceedings of the Fall Joint Computer Conference, 1969 and in “History of LISP,” by John McCarthy, in the ACM SIGPLAN Notices, Volume 39, Issue 4, April 2004. These references highlight how the principles established in McCarthy’s paper guided the evolution of algorithms and programming languages in AI and computer science.