zetl

Recursive Functions of Symbolic Expressions and Their Computation by Machine, Part I

Reference: John McCarthy (1960). “Recursive Functions of Symbolic Expressions and Their Computation by Machine, Part I.” Communications of the ACM 3(4): 184-195. (Author-hosted LaTeX reformatting with minor notational changes.) Source file: mccarthy-recursive.pdf. URL

Summary

The Lisp paper. McCarthy describes a programming system — LISP, for LISt Processor — developed for the IBM 704 at MIT, originally designed to support the advice taker of Programs with Common Sense by giving it a substrate for manipulating symbolic (declarative and imperative) sentences. The system evolved into a representation of partial recursive functions over a class of symbolic expressions (S-expressions) whose elegance transcended its motivating application. The paper presents S-expressions, a small set of elementary S-functions (atom, eq, car, cdr, cons), conditional expressions (newly introduced here), recursive function definitions via a λ-calculus-flavored notation, and the universal S-function apply that plays the role of a universal Turing machine and the practical role of an interpreter — the now-iconic code-is-data eval/apply kernel.

The paper then translates this formalism into IBM 704 list structures (the famous CAR/CDR naming reflecting the 704’s address and decrement register fields), describes the main features of the LISP system (garbage collection, interpreter, compiler sketch, free storage), and gives a recursive-function interpretation of flow charts — i.e., a semantics for imperative programs via recursive functions, anticipating much later work on denotational semantics. Conditional expressions, submitted by McCarthy as a letter to CACM and “demoted to a letter” by its editor (notes the footnote), were the notation Algol 60 then rejected in favour of if ... then ... else.

Lisp is simultaneously an AI implementation vehicle and a theory of computation — and the paper’s code-is-data property (programs are S-expressions) is what seeded the Lisp extensibility tradition (macros, embedded DSLs) that later runs through The Extensible Language - Graham, Code as Data, Macros as Language Extension, and Creating Languages in Racket. McCarthy closes promising a Part II on symbolic applications and a companion paper applying the recursive-function formalism to mathematical logic and theorem proving — the latter effectively becoming Correctness of a Compiler for Arithmetic Expressions and Towards a Mathematical Science of Computation.

Key Ideas

  • S-expressions: uniform tree/list data structure for both programs and data (code-is-data).
  • Five primitive functions (atom, eq, car, cdr, cons) suffice to define all computable functions over S-expressions.
  • Conditional expressions (p1 → e1, ..., pn → en) as a first-class construct — introduced to computer science here.
  • Recursive function definitions and λ-notation for anonymous functions.
  • Universal function apply — a meta-circular evaluator — plays the role of a universal Turing machine and a working interpreter.
  • Partial functions are inherent to computation (non-termination) and must be handled explicitly.
  • Flow charts reinterpreted as recursive function applications — an early denotational-style semantics for imperative programs.
  • Garbage collection (the concept of automatic reclamation of unreferenced list cells) introduced in the implementation notes.

Connections

Conceptual Contribution

Tags

#foundational #mccarthy #lisp #programming-languages #ai-history #code-as-data #1960 #recursive-functions

Backlinks