1 Introduction
1.1 Motivation and Context
In the late 1950s, the field of artificial intelligence was in its infancy, and most programming languages were designed for numeric computation. John McCarthy, then at the Massachusetts Institute of Technology, sought a language suitable for symbolic reasoning, theorem proving, and list processing. The 1960 paper "Recursive Functions of Symbolic Expressions and Their Computation by Machine" provided both a formal theoretical foundation and a practical implementation plan for a new language—Lisp. It addressed the need for a notation that could treat programs as data, enable recursion naturally, and facilitate symbolic manipulation.
1.2 Overview of Symbolic Computation
Symbolic computation involves the manipulation of symbols and symbolic expressions rather than numbers. McCarthy's paper defined a class of symbolic expressions (S-expressions) as the universal data structure. Primitive functions such as car, cdr, and cons operate on these expressions, and conditional expressions allow the definition of recursive functions. The paper demonstrated how any recursive function over S-expressions could be defined and then evaluated mechanically using a universal S-function (the eval function). This laid the groundwork for functional programming.
1.3 Relation to Lambda Calculus and Recursion Theory
McCarthy’s work was deeply influenced by Alonzo Church’s lambda calculus and the theory of recursive functions (Kleene, Gödel). The paper explicitly linked S-expressions to Church’s formal systems. However, it introduced practical innovations such as conditional expressions and the representation of functions as data structured as S-expressions. It also showed that the class of functions definable by this system was equivalent to the class of partial recursive functions, thus aligning with the Church–Turing thesis.
2 Symbolic Expressions (S-Expressions)
2.1 Definition of S-Expressions
2.1.1 Atoms and Pairs
An S-expression is defined recursively. The basic elements are atoms, which are indivisible symbols (e.g., numbers, letter strings, or special markers). The fundamental compound structure is an ordered pair, written as (A . B), where A and B are themselves S-expressions. Any S-expression is either an atom or a pair. This simple definition yields unlimited combinatory power.
2.1.2 List Notation
For readability, McCarthy introduced a shorthand for lists. A list of elements e1, e2, …, en is represented as (e1 e2 … en), which is a series of nested pairs ending with a special atom NIL. Thus (A B C) expands to (A . (B . (C . NIL))). This notation became standard in Lisp.
2.2 Representation of Data Structures
2.2.1 Hierarchical Lists
Because lists can contain sublists, S-expressions naturally encode tree structures. For example, ((A B) C) represents a list whose first element is itself a list. This hierarchical property allows the representation of arbitrary nested data, such as program code, mathematical formulas, or parse trees.
2.2.2 Tree Structures
Since every pair is a node with two branches (the car and cdr fields), any binary tree can be directly represented. Non-binary trees are encoded using lists. This universal data structure enabled Lisp to be used for symbolic reasoning, natural language processing, and game playing.
2.3 Comparison with M-Expressions
2.3.1 Meta-linguistic Notation
The paper described a second, more readable notation called M-expressions (meta-expressions). M-expressions were intended for human writing, while S-expressions served as the internal machine representation. An M-expression like car[cons[A;B]] would be translated into the S-expression (CAR (CONS (QUOTE A) (QUOTE B))). However, the M-expression syntax was never implemented in early Lisp systems; instead, programmers used S-expressions directly.
2.3.2 Translation to S-Expressions
The translation function mapped M-expressions to S-expressions, treating function names as atoms and combining them with arguments via the same pairing mechanism. This translation allowed the universal evaluator to work solely on S-expressions, while programmers could (in theory) write in the more convenient M-notation. Over time, the S-expression syntax became the dominant form.
3 Functions of Symbolic Expressions
3.1 Primitive Functions
3.1.1 car, cdr, cons
The paper defined a small set of primitive functions. car returns the first element of a pair; cdr returns the second element; cons constructs a new pair from two arguments. For example, car[(A . B)] = A, cdr[(A . B)] = B, cons[A;(B . C)] = (A . (B . C)). These functions are the foundation of all list manipulation.
3.1.2 atom, eq
atom is a predicate that returns T (true) if its argument is an atom, otherwise NIL (false). eq tests two atoms for equality, returning T or NIL. Together with car, cdr, and cons, these primitives are sufficient to build any recursive function over S-expressions.
3.2 Conditional Expressions
3.2.1 Syntax and Semantics
McCarthy introduced the conditional expression as a new syntactic form, written [p1 → e1; p2 → e2; …; pn → en]. The expression evaluates the predicates p1, p2, … in order until one returns T (true), then returns the corresponding expression e. If none is true, the value is undefined. This cleanly expresses branching without side effects.
3.2.2 Recursive Definitions
Conditional expressions allowed natural recursive definitions. For example, the length of a list could be defined as: length[x] = [atom[x] → 0; T → add1[length[cdr[x]]]] where add1 increments a number. This style eliminated the need for explicit loops or goto statements.
3.3 Recursive Function Definitions
3.3.1 Label and Lambda
To define recursive functions, McCarthy used the label form (with lambda). A function definition like ff[x] = [atom[x] → x; T → ff[car[x]]] could be written as label[ff; λ[[x]; [atom[x] → x; T → ff[car[x]]]]]. The label construct allowed the function body to refer to itself.
3.3.2 Examples: append, subst
Two classic examples illustrated the system. append[x; y] concatenates two lists, defined as: [null[x] → y; T → cons[car[x]; append[cdr[x]; y]]] subst[x; y; z] substitutes an atom x for all occurrences of y in the S-expression z: [atom[z] → [eq[y; z] → x; T → z]; T → cons[subst[x; y; car[z]]; subst[x; y; cdr[z]]]] These definitions showed the power of recursion in a few lines.
4 The Universal S-Function (Evaluator)
4.1 Definition of eval
4.1.1 Environment and Argument Evaluation
The universal function eval takes an S-expression representing a function application and an environment (list of variable assignments) and returns the result. It interprets the expression recursively: for primitive functions it directly applies the operation; for compound functions it evaluates arguments and then applies the function body.
4.1.2 Handling of Primitive and Compound Functions
In eval, the function name is checked. If it is one of the primitives (car, cdr, cons, atom, eq), the corresponding operation is performed on the (already evaluated) arguments. Otherwise, the function is assumed to be a lambda expression; the arguments are evaluated, the formal parameters are bound to them in a new environment, and the body is evaluated recursively.
4.2 Implementation of a Lisp Interpreter
4.2.1 Recursive Evaluation Algorithm
The eval function itself is defined recursively in the paper. The algorithm traverses the S-expression tree: for an atom it returns its value from the environment; for a list it dispatches based on the first element. This self-referential definition allowed the system to be bootstrapped—a small interpreter written in machine code could then evaluate Lisp functions written in S-expressions.
4.2.2 Representation of Functions as S-Expressions
A key innovation was that functions themselves could be represented as S-expressions. For example, a lambda expression λ[[x]; cons[x; x]] is encoded as (LAMBDA (X) (CONS X X)). This unified treatment of code and data enabled meta-programming, such as writing an interpreter that could interpret itself.
4.3 Proof of Completeness
4.3.1 Simulation of any Recursive Function
McCarthy argued that any partial recursive function (in the sense of Church and Kleene) can be defined using S-expressions and the primitive functions. The paper gave a construction to simulate the standard recursive function operations (successor, projection, composition, primitive recursion, minimization) using car, cdr, cons, atom, eq, and conditional expressions.
4.3.2 Church-Turing Thesis Implications
By showing that the class of S-expression functions is equivalent to the class of partial recursive functions, the paper reinforced the Church–Turing thesis. The universal function eval demonstrated that a single fixed algorithm could compute any computable function, given an appropriate encoding—a form of universal Turing machine in the symbolic computation domain.
5 Programming Techniques and Examples
5.1 Functional Composition
The paper demonstrated how simple functions could be composed to create more complex ones. For example, using car and cdr repeatedly, one can access arbitrary nested elements: cadr (the second element) is defined as car[cdr[x]]. This composition technique became a hallmark of Lisp programming.
5.2 Higher-Order Functions
5.2.1 mapcar and apply
Although not named explicitly in the 1960 paper, the techniques for passing functions as arguments were present. The function apply allowed a list of arguments to be passed to a function. mapcar (or its equivalent) could apply a function to each element of a list; it was later defined as: mapcar[fn; lst] = [null[lst] → NIL; T → cons[fn[car[lst]]; mapcar[fn; cdr[lst]]]] This illustrated the concept of higher-order functions.
5.2.2 Functional Arguments
Functions could be passed as arguments to other functions. For instance, a generic "tree traversal" function could take a function fn and apply it to every atom in a tree. The paper's recursive definitions naturally supported this, as functions were represented as S-expressions and could be arguments to eval.
5.3 Recursive Control Structures
5.3.1 Factorial and Fibonacci
Classic numeric recursion examples were given. The factorial function: factorial[n] = [zerop[n] → 1; T → times[n; factorial[sub1[n]]]] and Fibonacci: fib[n] = [lessp[n; 2] → 1; T → plus[fib[sub1[n]]; fib[subsub1[n]]]] These demonstrated recursion over integers, which were represented as lists of atoms or using Church numerals.
5.3.2 Symbolic Differentiation
A more advanced example was symbolic differentiation of algebraic expressions. Given an expression represented as an S-expression, a recursive function could compute its derivative with respect to a variable. This illustrated the practical use of Lisp in symbolic mathematics, a field that later flourished in systems like Macsyma.
6 Alternative Formalisms
6.1 Predicate Calculus and Logic Programming
McCarthy’s paper also hinted at the use of logical notation for problem solving. The conditional expression can be viewed as a form of case analysis. Later, the connection to logic programming (e.g., Prolog) became apparent, though McCarthy’s system emphasized computation via recursive functions rather than deduction.
6.2 Lambda Calculus Encoding
All S-expression functions can be translated into pure lambda calculus. For example, the functions car and cdr can be encoded as λx.x λy.y and λx.x λy.z (Church encoding). The paper acknowledged this equivalence, but the S-expression representation provided a concrete, implementable machine representation.
6.3 Comparison with Church’s Formulation
Church’s lambda calculus used only function application and abstraction. McCarthy added atoms, pairs, and conditional expressions for practical programming. While the lambda calculus is extremely minimal, the S-expression system was designed for efficiency on digital computers and for ease of implementation. The paper’s universal function eval corresponds directly to a meta-circular interpreter, a concept that later became influential in programming language theory.
7 Conclusion
7.1 Impact on Programming Languages
7.1.1 Influence on Lisp Dialects
The paper directly led to the creation of Lisp 1.0 in 1960. Subsequent dialects—such as MacLisp, Interlisp, Scheme, Common Lisp, and Clojure—all trace their roots to the concepts defined in this paper. The introduction of recursion, garbage collection, and dynamic typing were revolutionary.
7.1.2 Legacy in Functional Programming
The paper is considered a founding document of functional programming. Its emphasis on pure functions (no side effects), higher-order functions, and recursion predated similar ideas in languages like ML, Haskell, and Erlang. The eval function inspired many meta-circular interpreters and influenced the design of domain-specific languages.
7.2 Open Problems and Future Directions
7.2.1 Efficiency and Compilation
The paper described an interpreter, not a compiler. Early Lisp systems were interpreted and suffered performance issues. The paper identified the need for compilation and efficient storage allocation. This led to the development of Lisp compilers, incremental compilers, and memory management techniques (e.g., generational garbage collection).
7.2.2 Type Systems and Verification
The language was dynamically typed. The paper noted that runtime type checks (via atom, eq) were necessary. Later research addressed static type systems for functional languages, such as the Hindley-Milner type inference. Verification of recursive functions, using techniques like denotational semantics, also grew from McCarthy’s foundational work.