# Recursive Functions of Symbolic Expressions and Their Computation by Machine

> An annotated edition of this paper on Fermat's Library, where scientists and readers explain its ideas, equations and history in the margins. Annotated edition: https://fermatslibrary.com/s/recursive-functions-of-symbolic-expressions-and-their-computation-by-machine

- **Authors:** John McCarthy
- **Published:** 1960
- **Topic:** Computer Science
- **Original:** http://www-formal.stanford.edu/jmc/recursive.pdf
- **Pages:** 34
- **Annotations:** 28 comments in 24 threads
- **Featured:** Fermat's Library Journal Club
- **Annotated edition:** https://fermatslibrary.com/s/recursive-functions-of-symbolic-expressions-and-their-computation-by-machine

## Annotations

### Annotation 1 (page 1)

Beside the passage: “and Their Computation by Machine, Part I”

**Annotation** by Ben Lerner (2015-11-01):

> This paper defines the core of the lisp programming language. It was intended as a theoretical exercise until Steve Russell, one of McCarthy's grad students, wrote a working lisp interpreter in machine code - much to McCarthy's surprise.

### Annotation 2 (page 1)

Beside the passage: “In t he course of its development the LISP system went through several stages of simpliﬁcation 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 a ny other electronic …”

**Annotation** by Ben Lerner (2015-11-01):

> For more background on the theory behind lisp, see "An unsolvable problem of elementary number theory" by Alonzo Church.

### Annotation 3 (page 3)

Beside the passage: “(p 1 → e 1 , · · · , p n → e n )”

**Annotation** by Ben Lerner (2015-10-28):

> This is written with `cond` in modern lisp.

### Annotation 4 (page 6)

Beside the passage: “If E is a for m in variables x 1 , · · · , x n , then λ((x 1 , · · · , x n ), E) will be ta ken to be the function of n variables whose value is determined by substituting the arguments for the variables x 1 , · · · , x n in that order in E and evaluating the resulting expression. For example, λ((x, y), y 2 + x) is a …”

**Annotation** by Ben Lerner (2015-10-29):

> Most lisps inherit `lambda` as an operator from here. Clojure use `fn` instead.

### Annotation 5 (page 7)

Beside the passage: “f. Expressio ns for Recursive Functions. The λ-notation is inadequate for naming functions deﬁned recursively. For example, using λ’s, we can convert the deﬁnition”

**Annotation** by Ben Lerner (2015-11-03):

> This isn't true: you can implement recursion without labels using the y combinator. For a great explanation, see http://mvanier.livejournal.com/2897.html

**Reply** by Kartik Singhal (2015-11-05):

> I think McCarthy here was just referring to inadequacy of "naming" recursive functions with \lambda. See comment about combinators in the previous paragraph.

### Annotation 6 (page 7)

Beside the passage: “In order to be able to write expressions for recursive functions, we introduce another notation. label(a, E) denotes the expression E, provided that occurrences of a within E are to be int erpreted as referring to the expression”

**Annotation** by Kartik Singhal (2015-11-05):

> `label` appears as `rec` in many modern Lisps.

**Reply** by Kartik Singhal (2015-11-05):

> No I was confused, it is the familiar `let` not `rec`.

**Reply** by Kartik Singhal (2015-11-24):

> `let rec` and `rec` are equivalent and just `let` won't do for defining recursive functions. Looking back at this after couple weeks. :)

### Annotation 7 (page 10)

Beside the passage: “car[x] car[cons[(A · B); x]] In these M-expressions (meta-expressions) any S-expression that occur stand for themselves.”

**Annotation** by Ben Lerner (2015-11-01):

> M-expressions aren't used in lisp. These lines would be:
>
> `(car x)`
>
> `(car (cons '(A B) x))`

**Reply** by Tom McNamara (2015-11-03):

> (car (cons '(A.B) x), right?

### Annotation 8 (page 11)

Beside the passage: “3. car. car[x] is deﬁned if and only if x is not atomic. car [(e 1 · e 2 )] = e 1 . Thus car [X] is undeﬁned.”

**Annotation** by Ben Lerner (2015-11-01):

> In clojure, `car` and  `cdr` are `first` and `rest`. Some languages use `head` and `tail`.

### Annotation 9 (page 11)

Beside the passage: “cons [X; A] = (X A) cons [(X · A); Y ] = ((X · A)Y )”

**Annotation** by Kartik Singhal (2015-11-05):

> There is little typo on this line, it should be:
> ```
> cons [X; A] = (X . A)
> ```
> (missing dot)

### Annotation 10 (page 11)

Beside the passage: “d. Recursive S-functions. We get a much larger class of functions (in fa ct, all computable functions) when we allow ourselves to form new functions of S-expressions by conditional expressions and recursive deﬁnition. We now give”

**Annotation** by Ben Lerner (2015-10-28):

> See 'An unsolvable problem of elementary number theory', by Alonzo Church for proof that this covers all computable functions, and 'Computability and $\lambda$-definability ' by Turing for proof of equivalence to a Turing machine specifically.

### Annotation 11 (page 12)

Beside the passage: “ﬀ[x] = [atom[x] → x; T → ﬀ[car[x]]] We now trace in detail the steps in the evaluatio n of ﬀ [((A · B) · C)]: ﬀ [((A · B) · C)]”

**Annotation** by Ben Lerner (2015-10-28):

> For readability:
>
> ![in clojure][1]
>
> [1]: http://caffeinatedanalytics.com/images/mccarthy_code/1.png
>
> (Expanded with clojure syntax. This uses the rainbow-delimiters emacs plugin, which colors parentheses by nesting depth.)

### Annotation 12 (page 14)

Beside the passage: “cadr[x] for car[cdr[x]], caddr[x] for car[cdr[cdr[x]]], etc. Another useful a bbreviation is to write list [e 1 ; e 2 ; · · · ; e n ] for cons[e 1 ; cons[e 2 ; · · · ; cons[e n ; NIL] · · ·]]. This function gives the list, (e 1 , · · · , e n ), as a function of its elements. The following functions are useful when …”

**Annotation** by Ben Lerner (2015-11-01):

> `fiiiirst` and `resssssst` haven't caught on.

### Annotation 13 (page 15)

Beside the passage: “We have”

**Annotation** by Ben Lerner (2015-10-29):

> How do you do arithmetic with pure S-expressions?
>
> One answer is treating the length of a list as an integer. Specifically, we can define the empty list as 0, take some variable, say `S`, and define 1 to be `'(S)`, two to be `'(S S)`, etc.
>
> You can start defining arithmetic on these numbers:
>
> ![arithmetic on s-expressions][2]
>
> [2]: http://caffeinatedanalytics.com/images/mccarthy_code/2.png
>
> The runtime, of course, is atrocious.

### Annotation 14 (page 16)

Beside the passage: “This no tation is writable and somewhat readable. It can be made easier to read and write at the cost of making its structure less regular. If more characters were available on the computer, it could be improved considerably. 4 f. The Universal S-Function apply. There is an S-function apply with the property that if f …”

**Annotation** by Ben Lerner (2015-10-29):

> `apply` and `eval` are the Maxwell's equations of lisp.

### Annotation 15 (page 16)

Beside the passage: “appq[m] = [null[m] → N IL; T → cons[list[QUOT E; car[m]]; appq[cdr[m]]]]”

**Annotation** by Ben Lerner (2015-10-29):

> In clojure, using cadr, etc. for readability:
>
> ![apply + eval in clojure][3]
>
> [3]: http://caffeinatedanalytics.com/images/mccarthy_code/3.png

### Annotation 16 (page 18)

Beside the passage: “We now explain a number of points a bout these deﬁnitions. 5 1. apply itself forms an expression representing the value of the function applied to the arguments, and puts the work of evaluating this expression onto a function eval. It uses appq to put quotes around each of the arguments, so that eval will regard them …”

**Annotation** by Ben Lerner (2015-10-29):

> Implementing `eval` in terms of itself might feel like cheating. More directly, eval uses `car` to implement `car`, which doesn't seem like it would work.
>
> The trick is something called a bootstrapped compiler: once you have a lisp, or any other language, you can write a compiler for the language in itself. The very first compiler has to be written in some other language, but it can be very basic, and you can throw out the source for that as soon as it runs.
>
> (This works for interpreters too.)
>
> The first lisp interpreter was implemented in machine code for the IBM 704.

### Annotation 17 (page 21)

Beside the passage: “maplist[x; f] = [null[x] → NIL; T → cons[f [x]; maplist[cdr[x]; f ]]]”

**Annotation** by Ben Lerner (2015-10-29):

> Just `map`, usually

### Annotation 18 (page 24)

Beside the passage: “An expression that has a given subexpression occurring more than once can be represented in more than one way. Whether the list structure for the subexpression is or is not repeated depends upon the history of the program. Whether or not a subexpression is repeated will make no diﬀerence in the results of a program as …”

**Annotation** by Ben Lerner (2015-11-01):

> This is true only if your structures are immutable. Everything is immutable in clojure, but not in most lisps.
>
> Subtle issues like this are why mutability should be used sparingly in any language: to avoid unpleasant surprises.

### Annotation 19 (page 25)

Beside the passage: “against an expression being a subexpression o f itself. Such an expression could not exist on paper in a world with our topology. Circular list structures would have some advantages in the machine, for example, for representing recursive functions, but diﬃculties in printing them, and in certain other operations, make …”

**Annotation** by Ben Lerner (2015-10-29):

> Both circular sequences and infinite sequences (e.g. the sequence of all integers) are useful. It's not a good idea to print them, though.

### Annotation 20 (page 25)

Beside the passage: “For the present, we shall only describe how print name s a re represented on association lists so that in reading or printing the program can establish a correspondence between information on punched cards, magnetic tape or printed page a nd the list structure inside the machine. The association list of the symbol …”

**Annotation** by Kartik Singhal (2015-11-05):

> Correction:
>
> ...whose association list this is, hangs from the next word...

### Annotation 21 (page 26)

Beside the passage: “c. Free-Storage List. At any given time only a part of the memory reserved for list structures will actually be in use for storing S-expressions. The remaining registers (in our system the number, initially, is approximately 15 ,0 00) are arranged in a single list called the free-storage list. A certain register, …”

**Annotation** by Ben Lerner (2015-10-29):

> i.e. the heap

### Annotation 22 (page 28)

Beside the passage: “constant in its address part: atom is programmed as an open subroutine that tests this part. Unless the M-expression atom[e] occurs as a condition in a conditional expression, the symbol T or F is generated as the result of the test. In case of a conditional expression, a conditional transfer is used and the symbol T …”

**Annotation** by Ben Lerner (2015-10-29):

> In modern terms, a 'closed' subroutine is a regular function, and an 'open' subroutine is an inlined function.

### Annotation 23 (page 32)

Beside the passage: “r[ξ] = [π 1 1[ξ] → S[f 1 [ξ]]; T → S[f 2 [ξ]]] S[ξ] = [π 2 1[ξ] → r[ξ]; T → t[f 3 [ξ]]] t[ξ] = [π3I[ξ] → f 4 [ξ]; π 3 2[ξ] → r[ξ]; T → t[f 3 [ξ]]]”

**Annotation** by Kartik Singhal (2015-11-05):

> Lot of typographical issues here, see original paper for the correct version.

### Annotation 24 (page 33)

Beside the passage: “The inadequacy of the λ-notation for naming recursive f unctions was noticed by N. Rochester, a nd he discovered an alternative to the solution involving label which has been used here. The form of subroutine for cons which permits its composition with other functions was invented, in connection with another …”

**Annotation** by Ben Lerner (2015-10-29):

> If you've made it this and you don't know lisp yet, try [Clojure for the Brave and True](http://www.braveclojure.com/) (if you have a little time) or [Structure and Interpretation of Computer Programming](https://mitpress.mit.edu/sicp/) (if you have a lot of time).

## Full text

Extracted from the PDF. [Annotation N] marks where each annotation above sits.

#### Page 1

Recursive Functions of Symbolic Expressions

and Their Computation by Machine, Part I [Annotation 1]

John McCarthy, Massachusetts Institute of Technology, Cambridge, Mass. ∗

April 1960

1 Introduction

A programming system called LISP (for LISt Processor) has been developed for the IBM 704 computer by the Artiﬁcial Intelligence group at M.I.T. The system was designed to facilitate experiment s 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 t he course of its development the LISP system went through several stages of simpliﬁcation 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 a ny other electronic computer, and it now seems expedient to expound the system [Annotation 2] by starting with the class of expressions called S-expressions and the functions called S-functions.

∗ Putting this paper in L A T E Xpartly s upported by ARPA (ONR) gra nt N00014-94-1-0775 to Stanford University where John McCarthy has been since 1962. Co pied with minor notational changes from CACM, April 1960. If you want the exact typography, look there. Current a ddress, John McCarthy, Computer Science Department, Stanford, CA 94305, (email: jmc@cs.stanford.edu), (URL: http://www-formal.stanford.edu/jmc/ )

1

#### Page 2

In this a r ticle, we ﬁrst describe a formalism for deﬁning functions recursively. We believe this formalism has advantages both as a programming language and as a vehicle for developing a theory of computation. Next, we describe S-expressions and S-functions, give some examples, and then describe the universal S- function apply which plays the theoretical role of a universal Turing machine and the practical r ole of an interpreter. Then we describe the representation of S-expressions in the memory of the IBM 704 by list structures similar to those used by Newell, Shaw and Simon [2], and the representation of S-functions by program. Then we mention the main features of the LISP programming system for the IBM 704. Next comes another way of describing computations with symbolic expressions, and ﬁnally we give a recursive function interpretation of ﬂow charts.

We hope to describe some of the symbolic computations for which LISP has been used in another paper, and also to give elsewhere some applications of our recursive function formalism to mathematical logic and to the problem of mechanical theorem proving.

2 Functions and Function Deﬁnitions

We shall need a number of mathematical ideas and notations concerning functions in general. Most of the ideas are well known, but the notion of conditional expression is believed to be new 1 , and the use of conditional expressio ns permits functions to be deﬁned recursively in a new and convenient way.

a. Partial Functions. A partial function is a function that is deﬁned only on part of its domain. Partial functions necessarily arise when functions are deﬁned by computations because for some values of the arguments the computation deﬁning the value of the function may not terminate. However, some of our elementar y functions will be deﬁned as partial functions.

b. Propositional Expressions and Predicates. A propositional expression is an expression whose possible values are T (for truth) and F (for falsity). We shall assume that the reader is familiar with the propositional connectives ∧ (“and”), ∨ (“or”) , and ¬ (“not”). Typical propositional expressions are:

1 reference Kleene

2

#### Page 3

x < y

(x < y) ∧ (b = c)

x is prime

A predicate is a function whose range consists of the truth values T and F .

c. Conditional Expressions. The dependence of truth values on the values of quantities of other kinds is expressed in mathematics by predicates, and the dependence of truth values on other truth values by logical connectives. However, the notations for expressing symbolically the dependence of quant ities of other kinds on truth values is inadequate, so that English words and phrases are generally used for expressing these dependences in texts that describe other dependences symbolically. For example, the function |x| is usually deﬁned in words. Conditional expressions are a device for expressing the dependence of quantities on propositional quantities. A conditional expression has the fo r m

(p [Annotation 3] 1 → e 1 , · · · , p n → e n )

where the p’s are propositional expressions and the e’s are expressions of any kind. It may be read, “If p 1 then e 1 otherwise if p 2 then e 2 , · · · , otherwise if p n then e n ,” or “p 1 yields e 1 , · · · , p n yields e n .” 2 We now give the rules for determining whether the value of

(p 1 → e 1 , · · · , p n → e n )

is deﬁned, and if so what its value is. Examine the p’s from left to right. If a p whose value is T is encountered before any p whose value is undeﬁned is encountered then t he value of the conditional expression is the value of the corresponding e (if this is deﬁned). If any undeﬁned p is encountered before

2 I sent a proposal for conditional expressions to a CACM forum on what should be included in Algol 60. Because the item was s hort, the editor demoted it to a letter to the editor, fo r which CACM subsequently apologized. The notation given here was rejected for Algol 60, because it had been decided that no new mathematical notatio n should be allowed in Algol 60, and everything new had to be English. The if . . . then . . . else that Algol 60 adopted was suggested by John Backus.

3

#### Page 4

a true p, or if all p’s are false, or if the e corresponding to the ﬁrst true p is undeﬁned, then the value of the conditional expression is undeﬁned. We now give examples.

(1 < 2 → 4, 1 > 2 → 3) = 4 (2 < 1 → 4, 2 > 1 → 3, 2 > 1 → 2) = 3

(2 < 1 → 4, T → 3) = 3 (2 < 1 → 0 0 , T → 3) = 3 (2 < 1 → 3, T → 0 0 ) is undeﬁned (2 < 1 → 3, 4 < 1 → 4) is undeﬁned Some of the simplest applications of conditional expressions are in giving such deﬁnitions as

|x| = (x < 0 → −x, T → x)

δ ij = (i = j → 1, T → 0) sgn(x) = (x < 0 → −1, x = 0 → 0, T → 1)

d. Recursive Function Deﬁnitions. By using conditional expressions we can, without circularity, deﬁne functions by formulas in which the deﬁned function occurs. For example, we write

n! = (n = 0 → 1, T → n · (n − 1)!) When we use this formula to evaluate 0! we get the answer 1; because of the way in which the value of a conditional expression was deﬁned, the meaningless

4

#### Page 5

expression 0 · (0 - 1)! does not arise. The evaluation of 2! according to this deﬁnition proceeds as follows:

2! = (2 = 0 → 1, T → 2 · (2 − 1)!)

= 2 · 1! = 2 · (1 = 0 → 1T → ·(1 − 1)!) = 2 · 1 · 0! = 2 · 1 · (0 = 0 → 1, T → 0 · (0 − 1)!) = 2 · 1 · 1 = 2

We now give two other applications of recursive function deﬁnitions. The greatest common divisor, gcd(m,n), of two positive integers m and n is computed by means of the Euclidean algorithm. This algorithm is expressed by the recursive function deﬁnition:

gcd(m, n) = (m > n → gcd(n, m), rem(n, m) = 0 → m, T → gcd(rem(n, m), m))

where rem(n, m) denotes the remainder left when n is divided by m.

The Newtonian algorithm for obtaining an approximate square root of a number a, starting with an initial approximation x and requiring that an acceptable approximation y satisfy |y 2 − a| < , may be written as

sqrt(a, x, )

= (|x 2 − a| <  → x,T → sqrt ( a, 1 2 (x + a x ), ))

The simultaneous recursive deﬁnition of several f unctions is also possible, and we shall use such deﬁnitions if they are required.

There is no guarantee that the computation determined by a recursive deﬁnition will ever terminate and, for example, an attempt to compute n! from our deﬁnition will only succeed if n is a non-negative integer. If the computation does not terminate, the function must be regarded as undeﬁned for the given arguments.

The propositional connectives t hemselves can be deﬁned by conditional expressions. We write

5

#### Page 6

p ∧ q = (p → q, T → F ) p ∨ q = (p → T, T → q)

¬p = (p → F, T → T ) p ⊃ q = (p → q, T → T )

It is readily seen that the right- hand sides of the equations have the correct truth tables. If we consider situations in which p or q may be undeﬁned, the connectives ∧ and ∨ are seen to be noncommutative. For example if p is false and q is undeﬁned, we see that according to the deﬁnitions given above p ∧ q is false, but q ∧ p is undeﬁned. For our applications this noncommutativity is desirable, since p ∧ q is computed by ﬁrst computing p, and if p is false q is not computed. If the computation for p does not terminate, we never get around to computing q. We shall use propositional connectives in this sense hereafter.

e. Functions and Forms. It is usual in mathematics—outside of mathematical logic—to use the word “function” imprecisely and to apply it to forms such as y 2 + x. Because we shall later compute with expressions for functions, we need a distinction between functions and forms and a notation for expressing this distinction. This distinction and a notation for describing it, from which we deviate trivially, is given by Church [3].

Let f be an expression that stands for a function of two integer variables. It should make sense to write f (3, 4) and the value of this expression should be determined. The expression y 2 +x does not meet this requirement; y 2 +x(3, 4) is not a conventional notation, and if we attempted to deﬁne it we would be uncertain whether its value would turn out to be 13 or 19. Church calls an expression like y 2 + x, a form. A form can be converted into a function if we can determine the correspondence between the varia bles occurring in the form and the ordered list of arguments of the desired function. This is accomplished by Church’s λ-notation.

If E is a for m in variables x 1 , · · · , x n , then λ((x 1 , · · · , x n ), E) will be ta ken to be the function of n variables whose value is determined by substituting the arguments for the variables x [Annotation 4] 1 , · · · , x n in that order in E and evaluating the resulting expression. For example, λ((x, y), y 2 + x) is a function of two varia bles, and λ((x, y), y 2 + x)(3, 4) = 19. The variables occurring in the list of varia bles of a λ-expression are dummy or bound, like variables of integration in a deﬁnite integral. That is, we may

6

#### Page 7

change the names of t he bound var ia bles in a function expression without changing the value of the expression, provided that we make the same change for each occurrence of the variable and do not make two variables the same that previously were diﬀerent. Thus λ((x, y), y 2 + x), λ((u, v), v 2 + u) and λ((y, x), x 2 + y) denote the same function. We shall frequently use expressions in which some of the variables are bound by λ’s and others are not. Such an expression may be regarded as deﬁning a function with parameters. The unbound variables are called free varia bles.

An adequate notation that distinguishes functions from forms allows an unambiguous treatment of functions of f unctions. It wo uld invo lve too much of a digression to give examples here, but we shall use functions with functions as arguments later in this report.

Diﬃculties arise in combining functions described by λ-expressions, or by any other notation involving variables, because diﬀerent bound variables may be represented by the same symbol. This is called collision of bound variables. There is a notatio n involving operators that are called combinators for combining functions without the use of variables. Unfortunately, the combinatory expressions for interesting combinations o f functions tend to be lengthy and unreadable.

f. Expressio ns for Recursive Functions. The λ-notation is inadequate for [Annotation 5] naming functions deﬁned recursively. For example, using λ’s, we can convert the deﬁnition

sqrt(a, x, ) = (|x 2 − a| <  → x, T → sqrt(a, 1 2 (x + a x ), ))

into

sqrt = λ((a, x, ), (|x 2 − a| <  → x, T → sqrt(a, 1 2 (x + a x ), ))),

but the right-hand side cannot serve a s an expression fo r the function because there would be nothing to indicate that the reference to sqrt within the expression stood for the expression as a whole.

In order to be able to write expressions for recursive functions, we introduce another notation. label(a, E) denotes the expression E, provided that [Annotation 6] occurrences of a within E are to be int erpreted as referring to the expression

7

#### Page 8

as a whole. Thus we can write

label(sqrt, λ((a, x, ), (|x 2 − a| <  → x, T → sqrt(a, 1 2 (x + a x ), ))))

as a name for our sqrt function.

The symbol a in label (a, E) is also bound, that is, it may be altered systematically without changing the meaning of the expression. It behaves diﬀerently from a variable bound by a λ, however.

3 Recursive Functions of Symbolic Expressions

We shall ﬁrst deﬁne a class of symbolic expressions in terms of ordered pairs and lists. Then we shall deﬁne ﬁve elementary functions and predicates, and build from them by composition, conditional expressions, and recursive definitions an extensive class of functions of which we shall give a number of examples. We shall then show how these functions themselves can be expressed as symbolic expressions, and we shall deﬁne a universal function apply that allows us to compute from the expression f or a given function its value for given arguments. Finally, we shall deﬁne some functions with functions as arguments and give some useful examples.

a. A Clas s of Symbolic Expressions. We shall now deﬁne the S-expressions (S stands for symbolic). They are formed by using the special characters

·

)

(

and an inﬁnite set of distinguishable atomic symbols. For atomic symbols, we shall use strings of capital Latin letters and digits with single imbedded

8

#### Page 9

blanks. 3 Examples of a t omic symbols a re

A ABA AP P LE P IE NUMBER 3

There is a twofold reason for departing from the usual mathema t ical practice of using single letters for atomic symbols. First, computer programs frequently require hundreds of distinguishable symbo ls that must be fo r med from the 47 characters that are printable by the IBM 704 computer. Second, it is convenient to allow English words and phrases to stand for atomic entities for mnemonic reasons. The symbols are atomic in the sense that any substructure they may have as sequences of characters is ig nor ed. We assume only that different symbols can be distinguished. S-expressions are then deﬁned as follows:

1. Atomic symbols are S-expressions. 2. If e 1 and e 2 are S-expressions, so is (e 1 · e 2 ). Examples of S-expressions are

AB (A · B) ((AB · C) · D)

An S-expression is then simply an ordered pair, the terms of which may be atomic symbols or simpler S-expressions. We can can represent a list of arbitrary length in terms of S-expressions as follows. The list

(m 1 , m 2 , · · · , m n )

is represented by the S-expression

(m 1 · (m 2 · (· · · ( m n · NIL) · · ·)))

Here NIL is an atomic symbol used to terminate lists. Since many of the symbolic expressions with which we deal are conveniently expressed as lists, we shall introduce a list notation to abbreviate certain S-expressions. We have

3 1995 remark: Imbedded blanks could be allowed within symbols, because lists were then written with commas between elements.

9

#### Page 10

l. (m) stands for (m ·NIL). 2. (m 1 , · · · , m n ) stands for (m 1 · (· · · (m n · NIL) · · ·)). 3. (m 1 , · · · , m n · x) stands for (m 1 · (· · · ( m n · x) · · ·)).

Subexpressions can be similarly abbreviated. Some examples of these abbreviations are

((AB, C), D) for ((AB · (C · N IL)) · (D · N IL)) ((A, B), C, D · E) for ((A · (B · NIL)) · (C · (D · E)))

Since we regard the expressions with commas as abbreviations fo r those not involving commas, we shall refer to them all as S-expressions.

b. Functions of S-expressions and the Expre s sions Th at Represent Them . We now deﬁne a class of functions of S-expressions. The expressions representing these functions are written in a conventio nal functional notat io n. However, in order to clearly distinguish the expressions representing functions from Sexpressions, we shall use sequences of lower-case letters for function names and variables ranging over the set of S-expressions. We also use brackets and semicolons, instead of parentheses and commas, f or denoting the application of functions to their arguments. Thus we write

car[x] car[cons[(A · B); x]] In these M-expressions (meta-expressions) any S-expression that occur stand [Annotation 7] for themselves.

c. The Elementary S-functions and Predicates. We introduce the following functions and predicates:

1. ato m. atom[x] has the value of T or F according to whether x is an atomic symbol. Thus

atom [X] = T atom [(X · A)] = F

2. eq. eq [x;y] is deﬁned if and only if both x and y are atomic. eq [x; y] = T if x and y are the same symbol, and eq [x; y] = F otherwise. Thus

10

#### Page 11

eq [X; X] = T eq [X; A] = F eq [X; (X · A)] is undeﬁned.

3. car. car[x] is deﬁned if and only if x is not atomic. car [(e 1 · e 2 )] = e 1 . Thus car [X] is undeﬁned. [Annotation 8]

car [(X · A)] = X car [((X · A) · Y )] = (X · A)

4. cdr. cdr [x] is also deﬁned when x is not atomic. We have cdr [(e 1 · e 2 )] = e 2 . Thus cdr [X] is undeﬁned.

cdr [(X · A)] = A cdr [((X · A) · Y )] = Y

5. cons. cons [x; y] is deﬁned for any x and y. We have cons [e 1 ; e 2 ] = (e 1 · e 2 ). Thus

cons [X; A] = (X A) [Annotation 9] cons [(X · A); Y ] = ((X · A)Y )

car, cdr, and cons are easily seen to satisfy the relations

car [cons [x; y]] = x cdr [cons [x; y]] = y cons [car [x]; cdr [x]] = x, provided that x is not atomic.

The names “car” and “cons” will come to have mnemonic signiﬁcance only when we discuss the representation of the system in the computer. Compositions of car and cdr give the subexpressions of a given expression in a given position. Compositions of cons form expressions of a given structure out of parts. The class of functions which can be formed in this way is quite limited and not very interesting.

d. Recursive S-functions. We get a much larger class of functions (in fa ct, [Annotation 10] all computable functions) when we allow ourselves to form new functions of S-expressions by conditional expressions and recursive deﬁnition. We now give

11

#### Page 12

some examples of functions that are deﬁnable in this way. 1. ﬀ[x]. The value of ﬀ[x] is the ﬁrst atomic symbol of the S-expression x with the parentheses ignored. Thus

ﬀ[((A · B) · C)] = A We have

ﬀ[x] = [atom[x] → x; T → ﬀ[car[x]]] [Annotation 11] We now trace in detail the steps in the evaluatio n of ﬀ [((A · B) · C)]: ﬀ [((A · B) · C)]

= [atom[((A · B) · C)] → ((A · B) · C); T → ﬀ[car[((A · B)C·)]]] = [F → ((A · B) · C); T → ﬀ[car[((A · B) · C)]]] = [T → ﬀ[car[((A · B) · C)]]] = ﬀ[car[((A · B) · C)]] = ﬀ[(A · B)] = [atom[(A · B)] → (A · B); T → ﬀ[car[(A · B)]]] = [F → (A · B); T → ﬀ[car[(A · B)]]] = [T → ﬀ[car[(A · B)]]] = ﬀ[car[(A · B)]] = ﬀ[A]

12

#### Page 13

= [atom[A] → A; T → ﬀ[car[A]]]

= [T → A; T → ﬀ[car[A]]]

= A 2. subst [x; y; z]. This function gives the result of substituting the Sexpression x for all occurrences o f the atomic symbo l y in t he S-expression z. It is deﬁned by subst [x; y; z] = [atom [z] → [eq [z; y] → x; T → z]; T → cons [subst [x; y; car [z]]; subst [x; y; cdr [z]]]] As an example, we have

subst[(X · A); B; ((A · B) · C)] = ((A · (X · A)) · C) 3. equal [x; y]. This is a predicate that has the value T if x and y a r e the same S-expression, and has the value F otherwise. We have equal [x; y] = [atom [x] ∧ atom [y] ∧ eq [x; y]]

∨[¬ atom [x] ∧¬ atom [y] ∧ equal [car [x]; car [y]]

∧ equal [cdr [x]; cdr [y]]]

It is convenient to see how the element ary functions look in the abbreviated list notation. The reader will easily verify that

(i) car[(m 1 , m 2 , · · · , m n )] = m 1 (ii) cdr[(m s , m 2 , · · · , m n )] = (m 2 , · · · , m n ) (iii) cdr[(m)] = NIL (iv) cons[m 1 ; (m 2 , · · · , m n )] = (m 1 , m 2 , · · · , m n ) (v) cons[m; NIL] = (m) We deﬁne

13

#### Page 14

null[x] = atom[x] ∧ eq[x; NIL] This predicate is useful in dealing with lists. Compositions of car and cdr arise so frequently that many expressions can be written more concisely if we abbreviate

cadr[x] for car[cdr[x]], [Annotation 12] caddr[x] for car[cdr[cdr[x]]], etc. Another useful a bbreviation is to write list [e 1 ; e 2 ; · · · ; e n ] for cons[e 1 ; cons[e 2 ; · · · ; cons[e n ; NIL] · · ·]]. This function gives the list, (e 1 , · · · , e n ), as a function of its elements. The following functions are useful when S-expressio ns are rega rded as lists. 1. app end [x;y]. append [x; y] = [null[x] → y; T → cons [car [x]; append [cdr [x]; y]]]

An example is append [(A, B); (C, D, E)] = (A, B, C, D, E)

2. among [x;y]. This predicate is true if the S-expression x occurs among the elements of the list y. We have

among[x; y] = ¬null[y] ∧ [equal[x; car[y]] ∨ among[x; cdr[y]]] 3. pair [x;y]. This function gives the list of pairs of corresponding elements of the lists x and y. We have

pair[x; y] = [null[x]∧null[y] → NIL; ¬atom[x]∧¬atom[y] → cons[list[car[x]; car[y]]; pair[cdr[x]; cdr[y]]] An example is

pair[(A, B, C); (X, (Y, Z), U)] = ((A, X), (B, (Y, Z)), (C, U)).

14

#### Page 15

4. assoc [x;y]. If y is a list o f the form ((u 1 , v 1 ), · · · , (u n , v n )) and x is one of the u’s, then assoc [x; y] is the corresponding v. We have

assoc[x; y] = eq[caar[y]; x] → cadar[y]; T → assoc[x; cdr[y]]]

An example is

assoc[X; ((W, (A, B)), (X, (C, D)), (Y, (E, F )))] = (C, D) .

5. sublis[x; y]. Here x is assumed to have the form of a list of pairs ((u 1 , v 1 ), · · · , (u n , v n )), where the u’s are ato mic, and y may be any S-expression. The value of sublis[x; y] is the result of substituting each v for the corresponding u in y. In order to deﬁne sublis, we ﬁrst deﬁne an auxiliary function. We have

sub2[x; z] = [null[x] → z; eq[caar[x]; z] → cadar[x]; T → sub2[cdr[x]; z]]

and

sublis[x; y] = [atom[y] → sub2[x; y]; T → cons[sublis[x; car[y]]; sublis[x; cdr[y]]]

We have [Annotation 13]

sublis [((X, (A, B)), (Y, (B, C))); (A, X · Y)] = (A, (A, B), B, C)

e. Representation of S-Functions by S-Ex pressions. S-functions have been described by M-expressions. We now give a rule for translating M-expressions into S-expressions, in order to be able to use S-functions for making certain computations with S-functions and for answering certain questions about Sfunctions.

The translation is determined by the following rules in rich we denote the translation of an M- expression E by E*.

1. If E is an S-expression E* is (QUOTE, E). 2. Variables and function names that were represented by strings o f lowercase letters are translated to the corresponding strings of the corresponding uppercase letters. Thus car* is CAR, and subst* is SUBST.

3. A form f[e 1 ; · · · ; e n ] is translated to (f ∗ , e ∗ 1 · · · , e ∗ n ). Thus cons [car [x]; cdr [x]] ∗ is (CONS, (CAR, X), (CDR, X)). 4. {[p 1 → e 1 ; · · · ; p n → e n ]} ∗ is (COND, (p ∗ 1 , e ∗ 1 ), · · · , (p ∗ n · e ∗ n )).

15

#### Page 16

5. {λ[[x 1 ; · · · ; x n ]; E]} ∗ is (LAMBDA, (x ∗ 1 , · · · , x ∗ n ), E ∗ ). 6. {label[a; E]} ∗ is (LABEL, a ∗ , E ∗ ). With these conventions the substitution function whose M-expression is label [subst; λ [[x; y; z]; [atom [z] → [eq [y; z] → x; T → z]; T → cons [subst [x; y; car [z]]; subst [x; y; cdr [z]]]]]] has the S-expression

(LABEL, SUBST, (LAMBDA, (X, Y, Z), (COND ((ATOM, Z), (COND, (EQ, Y, Z), X), ((QUOTE, T), Z))), ((QUOTE, T), (CONS, (SUBST, X, Y, (CAR Z)), (SUBST, X, Y, (CDR, Z)))))))

This no tation is writable and somewhat readable. It can be made easier to read and write at the cost of making its structure less regular. If more characters were available on the computer, it could be improved considerably. 4 f. The Universal S-Function apply. There is an S-function apply with the [Annotation 14] property that if f is an S-expression for an S-function f 0 and args is a list of arguments of the form (arg 1 , · · · , arg n ), where arg 1 , · · · , arg n are arbitrary Sexpressions, then apply[f ; args] and f 0 [arg 1 ; · · · ; arg n ] are deﬁned for the same values of arg 1 , · · · , arg n , and are equal when deﬁned. For example,

λ[[x; y]; cons[car[x]; y]][(A, B); (C, D)]

= apply[(LAMBDA, (X, Y ), (CONS, (CAR, X), Y )); ((A, B), (C, D))] = (A, C, D)

The S-function apply is deﬁned by

apply[f ; args] = eval[cons[f ; appq[args]]; NIL],

where

appq[m] = [null[m] → N IL; T → cons[list[QUOT E; car[m]]; appq[cdr[m]]]] [Annotation 15]

and

eval[e; a] = [

4 1995: More characters were made available on SAIL and later on the Lisp machines. Alas, the world went back to inferior character sets again—though not as far back as when this pap e r was written in early 1959.

16

#### Page 17

atom [e] → assoc [e; a]; atom [car [e]] → [ eq [car [e]; QUOTE] → cadr [e]; eq [car [e]; ATOM] → atom [eval [cadr [e]; a]]; eq [car [e]; EQ] → [eval [cadr [e]; a] = eval [caddr [e]; a]]; eq [car [e]; COND] → evcon [cdr [e]; a]; eq [car [e]; CAR] → car [eval [cadr [e]; a]]; eq [car [e]; CDR] → cdr [eval [cadr [e]; a]]; eq [car [e]; CONS] → cons [eval [cadr [e]; a]; eval [caddr [e]; a]]; T → eval [cons [assoc [car [e]; a]; evlis [cdr [e]; a]]; a]]; eq [caar [e]; LABEL] → eval [cons [caddar [e]; cdr [e]]; cons [list [cadar [e]; car [e]; a]]; eq [caar [e]; LAMBDA] → eval [caddar [e]; append [pair [cadar [e]; evlis [cdr [e]; a]; a]]] and

evcon[c; a] = [eval[caar[c]; a] → eval[cadar[c]; a]; T → evcon[cdr[c]; a]] and

evlis[m; a] = [null[m] → NIL; T → cons[eval[car[m]; a]; evlis[cdr[m]; a]]]

17

#### Page 18

We now explain a number of points a bout these deﬁnitions. 5 1. apply itself forms an expression representing the value of the function applied to the arguments, and puts the work of evaluating this expression onto [Annotation 16] a function eval. It uses appq to put quotes around each of the arguments, so that eval will regard them as standing for themselves.

2. eval[e; a] has two arguments, an expression e to b e evaluated, and a list of pairs a. The ﬁrst item of each pair is an atomic symbol, and the second is the expression fo r which the symbol stands.

3. If the expression to be evaluated is atomic, eva l evaluates whatever is paired with it ﬁrst on the list a.

4. If e is not atomic but car[e] is atomic, then the expression has one of the forms (QUOT E, e) or (AT OM, e) or (EQ, e 1 , e 2 ) or (CON D, (p 1 , e 1 ), · · · , (p n , e n )), or (CAR, e) or (CDR, e) or (CONS, e 1 , e 2 ) or (f, e 1 , · · · , e n ) where f is an atomic symbol.

In the case (QU OT E, e) the expression e, itself, is taken. In the case of (AT OM, e) or (CAR, e) or (CDR, e) the expression e is evaluated and the appropriate function taken. In the case of (EQ, e 1 , e 2 ) or (CONS, e 1 , e 2 ) two expressions have to be eva luated. In the case of (CON D, (p 1 , e 1 ), · · · (p n , e n )) the p’s have to be evaluated in order until a true p is found, and then the corresponding e must be evaluated. This is accomplished by evcon. Finally, in the case o f (f, e 1 , · · · , e n ) we evaluate the expression that results from replacing f in this expression by whatever it is paired with in the list a.

5. The evaluation of ((LABEL, f, E), e 1 , · · · , e n ) is accomplished by evaluating (E, e 1 , · · · , e n ) with the pairing (f, (LABEL, f, E)) put on the front of the previous list a of pairs.

6. Finally, the evaluation of ((LAMBDA, (x 1 , · · · , x n ), E), e 1 , · · · e n ) is accomplished by evaluating E with the list of pairs ((x 1 , e 1 ), · · · , ((x n , e n )) put on the front of the previous list a.

The list a could be eliminated, and LAMBDA and LABEL expressions evaluated by substituting the arguments for the variables in the expressions E. Unfortunately, diﬃculties involving collisions of bound variables arise, but they are avoided by using the list a.

5 1995: This version isn’t quite right. A comparison of this and other versions of eval including what was actually implemented (and debugged) is given in “The Inﬂuence of the Designer on the Design” by Herbert Stoyan and included in Artiﬁcial Intelligence and Mathematical Theory of Computation: Papers in Honor of John McCarthy, Vladimir Lifschitz (ed.), Academic Press, 1991

18

#### Page 19

Calculating the values of functions by using apply is an activity better suited to electronic computers than to people. As an illust ration, however, we now give some of the steps for calculating apply [(LABEL, FF, (LAMBDA, (X), (COND, (ATOM, X), X), ((QUOTE, T),(FF, (CAR, X))))));((A· B))] = A The ﬁrst argument is the S-expression that represents the function ﬀ deﬁned in section 3d. We shall abbreviate it by using the letter φ. We have apply [φ; ( ( A· B) )] = eval [((LABEL, FF, ψ), (QUOTE, (A·B))); NIL]

where ψ is the part of φ beginning (LAMBDA = eval[((LAMBDA, (X), ω), (QUOTE, (A·B)));((FF, φ))]

where ω is the par t of ψ beginning (COND = eval [(COND, (π 1 ,  1 ), (π 2 ,  2 )); ((X, (QUOTE, ( A·B) ) ), (FF, φ) )] Denoting ((X, (QUOTE, (A·B))), (FF, φ)) by a, we obtain = evcon [((π 1 ,  1 ), (π 2 ,  2 )); a] This involves eval [π 1 ; a] = eval [( ATOM, X); a] = atom [eval [X; a]] = atom [eval [assoc [X; ((X, (QUOTE, (A·B))), (FF,φ))];a]] = atom [eval [(QUOTE, (A·B)); a]] = atom [(A·B)], = F Our main calulation continues with

19

#### Page 20

apply [φ; ((A·B))]

= evcon [((π 2 ,  2 , )); a], which involves eval [π 2 ; a] = eval [(QUOTE, T); a] = T Our main calculation again continues with apply [φ; ((A·B))]

= eval [ 2 ; a] = eval [(FF, (CAR, X));a] = eval [Cons [φ; evlis [((CAR, X)); a]]; a] Evaluating evlis [((CAR, X)); a] involves eval [(CAR, X); a]

= car [eval [X; a]] = car [(A·B)], where we took steps fro m the earlier computation of atom [eval [X; a]] = A, and so evlis [((CAR, X)); a] then becomes

list [list [QUOTE; A]] = ((QUOTE, A)), and our main quantity becomes

= eval [(φ, (QUOTE, A)); a]

The subsequent steps are made as in the beginning of the calculation. The LABEL and LAMBDA cause new pairs to be added to a, which gives a new list of pairs a 1 . The π 1 term of the conditional eval [(ATOM, X); a 1 ] has the 20

#### Page 21

value T because X is paired with (QUOTE, A) ﬁrst in a 1 , rather than with (QUOTE, (A·B)) as in a.

Therefore we end up with eval [X; a 1 ] from the evcon, and this is just A.

g. Func tion s with Functions as Arguments. There are a numb er of useful functions some of whose argument s ar e functions. They are especially useful in deﬁning other f unctions. One such function is maplist[x; f ] with an Sexpression argument x and an argument f that is a function from S-expressions to S-expressions. We deﬁne

maplist[x; f] = [null[x] → NIL; T → cons[f [x]; maplist[cdr[x]; f ]]] [Annotation 17]

The usefulness of maplist is illustrated by formulas for the partial derivative with r espect to x of expressions involving sums and products of x and other varia bles. The S-expressions t hat we shall diﬀerentiate are formed as follows.

1. An atomic symbol is an allowed expression. 2. If e 1 , e 2 , · · · , e n are allowed expressions, ( PLUS, e 1 , · · · , e n ) and ( TIMES, e 1 , · · · , e n ) are also, and represent the sum and product, respectively, of e 1 , · · · , e n . This is, essentially, the Polish notation for functions, except that the inclusion of parentheses and commas allows functions of variable numbers of arguments. An example of an allowed expression is (TIMES, X, (PLUS, X, A), Y), the conventional algebraic notation for which is X(X + A)Y.

Our diﬀerentiation formula, which gives the derivative of y with respect to x, is

diﬀ [y; x] = [atom [y] → [eq [y; x] → O NE; T → ZERO]; eq [car [Y]; PLUS] → cons [PLUS; maplist [cdr [y]; λ[[z]; diﬀ [car [z]; x]]]]; eq[car [y]; TIMES] → cons[PLUS; maplist[cdr[y]; λ[[z]; cons [TIMES; maplist[cdr [y]; λ[[w]; ¬ eq [z; w] → car [w]; T → diﬀ [car [[w]; x]]]]]]]

The derivative of the expression (TIMES, X, (PLUS, X, A), Y), as computed by this formula, is

(PLUS, (TIMES, ONE, (PLUS, X, A), Y), (TIMES, X, (PLUS, ONE, ZERO), Y), (TIMES, X, (PLUS, X, A), ZERO))

Besides maplist, another useful function with functional argument s is search, which is deﬁned as

search[x; p; f ; u] = [null[x] → u; p[x] → f [x]; T → search[cdr[x]; p; f; u]

21

#### Page 22

The function search is used to search a list for an element that has the property p, and if such an element is found, f of that element is taken. If there is no such element, the function u of no arguments is computed.

4 The LISP Programming System

The LISP programming system is a system for using the IBM 704 computer t o compute with symbolic information in the form of S- expressions. It has been or will be used for the f ollowing purposes:

l. Writing a compiler to compile LISP programs into machine language. 2. Writing a program to check proofs in a class of f ormal logical systems. 3. Writing programs for formal diﬀerentiation and integration. 4. Writing progra ms to realize various algorithms for generating proofs in predicate calculus.

5. Making certain engineering calculations whose results are formulas rather than numbers.

6. Programming the Advice Taker system. The basis of the system is a way of writing computer programs to evaluate S-functions. This will be described in the following sections.

In addition to the facilities for describing S-functions, there are facilities for using S-functions in progra ms written as sequences of statements along the lines of FORTRAN (4) or ALGOL (5). These features will not be described in this article.

a. Representation of S-Expressions by List Structure. A list structure is a collection of computer wo r ds arranged a s in ﬁgure 1a or 1b. Each word of the list structure is represented by one of the subdivided rectangles in the ﬁgure. The lef t box of a rectangle represents the address ﬁeld of the word and the right box represents the decrement ﬁeld. An arrow from a box to another rectangle means that the ﬁeld corresp onding to the box contains the location of the word corresponding to the other rectangle.

22

#### Page 23

- -

-

- -

-

-

-

-

-

-

- - -

- - - -

-

- - - -

Fig. 1

It is permitted for a substructure to occur in more than one place in a list structure, as in ﬁgure 1b, but it is not permitted for a structure to have cycles, as in ﬁgure 1c. An atomic symbol is represented in the computer by a list structure of special form called the association list of the symbol. The address ﬁeld of the ﬁrst word contains a special constant which enables the pro gram to tell that this word represents an atomic symbol. We shall describe association lists in section 4b.

An S- expression x that is not atomic is represented by a word, the address and decrement parts of which contain the locations of the subexpressions car[x] and cdr[x], respectively. If we use the symbols A, B, etc. to denote the locations of the association list of these symbols, then the S-expression ( (A · B) · (C · (E · F ))) is represented by the list structure a of ﬁgure 2. Turning to the list form of S-expressions, we see that the S-expressio n (A, (B, C), D), which is an abbreviation for (A · ((B · (C · NIL)) · (D · NIL))), is represented by the list structure of ﬁgure 2b.

23

#### Page 24

-

-

- -

- - -

- - A B E F

C A

B C

D

(a) (b)

Figure 2

When a list structure is regarded as representing a list, we see that each t erm of the list occupies the address part of a word, the decrement part of which points to the wo r d containing the next term, while the last word has NIL in its decrement.

An expression that has a given subexpression occurring more than once can be represented in more than one way. Whether the list structure for the subexpression is or is not repeated depends upon the history of the program. Whether or not a subexpression is repeated will make no diﬀerence [Annotation 18] in the results of a program as they appear outside the machine, although it will a ﬀ ect the time and storage requirements. For example, the S-expression ((A·B)·(A·B)) can be represented by either the list structure of ﬁgure 3a or 3b.

-

- -

-

- - A B A B A B (a) (b)

Figure 3

The prohibition a gainst circular list structures is essentially a prohibition

24

#### Page 25

against an expression being a subexpression o f itself. Such an expression could not exist on paper in a world with our topology. Circular list structures would have some advantages in the machine, for example, for representing recursive [Annotation 19] functions, but diﬃculties in printing them, and in certain other operations, make it seem advisable not to use them for the present.

The advant ages of list structures for the storage of symbolic expressions are:

1. The size and even the number of expressions with which t he program will have to deal cannot be predicted in advance. Therefore, it is diﬃcult to arrange blocks of storage of ﬁxed length to contain them.

2. Registers can be put back on the free-storage list when they are no longer needed. Even one register returned to the list is of value, but if expressions are stored linearly, it is diﬃcult to make use of blo cks of regist ers of odd sizes that may become available.

3. An expression that occurs as a subexpression of several expressions need be represented in storage o nly once.

b. Association Lists 6 . In the LISP programming system we put more in the association list of a symbol than is required by the mathematical system described in the previous sections. In fact, any information that we desire to associate with the symbol may b e put on the association list. This information may include: the print name, that is, the string of letters and digits which represents the symbol outside the machine; a numerical value if the symbol represents a number; another S-expression if the symbol, in some way, serves as a name for it; or the locatio n of a routine if the symbol represents a function for which there is a machine-language subroutine. All this implies that in the machine system there are more primitive entities than have b een described in the sections on the mathematical system.

For the present, we shall only describe how print name s a re represented on association lists so that in reading or printing the program can establish a correspondence between information on punched cards, magnetic tape or printed page a nd the list structure inside the machine. The association list of the symbol DIFFERENTIATE has a segment of the form shown in ﬁgure 4. Here pname is a symbol that indicates tha t the structure f or the print name of the symbol whose association list this is hanging fro m the next word on [Annotation 20] the association list. In the second row of the ﬁgure we have a list of three words. The address part of each of these words points to a Word containing

6 1995: These were later called pro perty lists.

25

#### Page 26

six 6-bit characters. The last word is ﬁlled out with a 6-bit combination that does no t represent a character printable by the computer. (Recall that the IBM 7O4 has a 36-bit word and that printable cha racters are each represented by 6 bits.) The presence of the wor ds with cha racter information means that the association lists do not themselves represent S-expressions, and that only some of the functions for dealing with S-expressions make sense within an association list.

- - -

- - -

- - -

pname ... ....

DIFFER ENTIAT E ??????

Figure 4

c. Free-Storage List. At any given time only a part of the memory reserved for list structures will actually be in use for storing S-expressions. The remaining registers (in our system the number, initially, is approximately 15 ,0 00) are arranged in a single list called the free-storage list. A certain register, FREE, [Annotation 21] in the program contains the location of the ﬁrst register in this list. When a word is required to form some additional list structure, the ﬁrst word on the free-storage list is taken and the number in register FREE is changed to become the location of the second word on the free-storage list. No provision need be made for the user to prog r am the return of registers to the free-storage list.

This r eturn takes place automatically, approximately as follows (it is necessary to give a simpliﬁed description of this process in this report): There is a ﬁxed set of base registers in the program which contains the locations of list structures that are accessible to the pro gram. Of course, because list structures branch, an arbitrary numb er of registers may be involved. Each register that is accessible to the program is accessible because it can be reached from one or more of the base registers by a chain of car and cdr operations. When

26

#### Page 27

the contents of a base register are changed, it may happen that the register to which the base register formerly pointed cannot be reached by a car − cdr chain from any base register. Such a register may be considered abandoned by the prog ram because its contents can no longer be found by any possible program; hence its contents are no longer of interest, and so we would like to have it back on the free-storage list. This comes about in the following way.

Nothing happens until the program runs out of free storage. When a free register is wanted, and there is none left on the free-storage list, a reclamation 7 cycle starts.

First, the progr am ﬁnds all registers accessible from the base registers and makes their signs negative. This is accomplished by starting from each of the base registers and changing the sign of every register t hat can be reached fro m it by a car − cdr chain. If the program encounters a register in this process which already has a negative sign, it assumes that this register ha s already been reached.

After all of the accessible registers have had their signs changed, the program goes through the area of memory r eserved fo r the storage of list structures and puts all the registers whose signs were not changed in the previous step back on the free-storage list, a nd makes the signs of the accessible registers positive again.

This process, because it is entirely automatic, is more convenient for the programmer than a system in which he has to keep track of and erase unwanted lists. Its eﬃciency depends upon not coming close to exhausting the available memory with accessible lists. This is because the reclamation process requires several seconds to execute, and therefore must result in the addition of at least several thousand registers to the free-storage list if the program is not to spend most of its time in reclamation.

d. Elementary S-Functions in the Com puter. We shall now describe the computer representations of atom, = , car, cdr, and cons. An S-expression is communicated to the pro gram that represents a function as the location of the word representing it, and the programs give S-expression a nswers in the same form.

atom. As stated above, a word representing an ato mic symbol has a special 7 We already called this process “garbage collection”, but I guess I chickened o ut of using it in the paper—or else the Research Laboratory of Electronics grammar ladies wouldn’t let me.

27

#### Page 28

constant in its address part: atom is programmed as an open subroutine that tests this part. Unless the M-expression atom[e] occurs as a condition in a conditional expression, the symbol T or F is generated as the result of the test. In case of a conditional expression, a conditional transfer is used and the [Annotation 22] symbol T or F is not generated.

eq. The program for eq[e; f ] involves testing for the numerical equality of the locations of the words. This works because each atomic symbol has only one association list. As with atom, t he result is either a conditional transfer or one of the symbols T or F .

car. Computing car[x] involves getting the contents of the address part of register x. This is essentially accomplished by the single instruction CLA 0, i, where the arg ument is in index register, and the result appears in the address part of the accumulator. (We take the view that the places from which a function takes its arguments and into which it puts its results are prescribed in the deﬁnition of the function, and it is the responsibility of the programmer or the compiler to insert the required datamoving instructions to get the results of o ne calculation in position for the next.) (“car” is a mnemonic for “contents of the address part of register.”)

cdr. cdr is handled in the same way as car, except that the result appears in the decrement part of the accumulator (“cdr” stands for “contents of the decrement part of register.”)

cons. The value of cons[x; y] must be the location of a register that has x and y in its address and decrement parts, respectively. There may not be such a register in the computer and, even if there were, it would be time-consuming to ﬁnd it. Actually, what we do is to take the ﬁrst available register from the free-storage l i st, put x and y in the address and decrement parts, respectively, and make the value of the function the location of the register taken. (“cons” is an abbreviation for “construct.”)

It is the subroutine for cons that initiates the reclamation when the freestorage list is exhausted. In the version of the system that is used at present cons is represented by a closed subroutine. In the compiled version, cons is open.

e. Representation of S-Functions by Programs. The compilation of functions that are compositions of car, cdr, and cons, either by hand or by a compiler program, is straightforward. Conditional expressions g ive no trouble except that they must be so compiled that only the p’s and e’s that are re-

28

#### Page 29

quired are computed. However, problems arise in the compilation of recursive functions.

In general (we shall discuss an exception), the routine for a recursive function uses itself as a subroutine. For example, the program for subst[x; y; z] uses itself as a subroutine to evaluate the result of substituting into the subexpressions car[z] and cdr[z]. While subst[x; y; cdr[z]] is being evaluated, the result of the previous evaluation o f subst[x; y; car[z]] must be saved in a temporary storage register. However, subst may need the same register for evaluating subst[x; y; cdr[z]]. This possible conﬂict is resolved by the SAVE and UN- SAVE r outines that use the public push-down list 8 . The SAVE routine is entered at the beginning of the routine for the recursive function with a request to save a given set of consecutive registers. A block of registers called the public push-down lis t is reserved for this purpose. The SAVE r outine has an index that tells it how many registers in the push-down list are already in use. It moves the contents of the registers which are to be saved to the ﬁrst unused registers in the push-down list, advances the index of the list, and returns to the program from which control came. This program may then freely use these r egisters for temporary storage. Before the routine exits it uses UNSAVE, which restores the contents of the temporary registers from the push-down list and moves back the index of this list. The result of these conventions is described, in programming terminology, by saying that the recursive subroutine is tra nsparent to the temporary storage r egisters.

f. Status of the LISP Progra mming System (February 1960). A variant of the function apply described in section 5f has been translated into a program APPLY for the IBM 704. Since this routine can compute values of S-functions given their descriptions as S-expressions and their arguments, it serves as an interpreter for the LISP prog r amming language which describes computation processes in this way.

The program APPLY has been imbedded in the LISP programming system which has the following features:

1. The progr ammer may deﬁne any number of S-functions by S-expressions. these functions may refer to each other or t o certain S-functions represented by machine language program.

2. The values of deﬁned functions may be computed. 3. S-expressions may be read and printed (directly or via magnetic tape). 8 1995: now called a stack

29

#### Page 30

4. Some error diagnostic and selective tracing facilities are included. 5. The programmer may have selected S-functions compiled into machine language programs put into t he core memory. Values of compiled functions are computed about 60 times as fa st as they would if interpreted. Compilation is fast enough so that it is not necessary to punch compiled program for future use.

6. A “program feature” allows programs containing assignment and go to statements in the style of ALGOL.

7. Computation with ﬂoating point numbers is possible in the system, but this is ineﬃcient.

8. A programmer’s manual is b eing prepared. The LISP programming system is appropriate for computations where the data can conveniently be represented as symbo lic expressions allowing expressions of the same kind as sub expressions. A version of the system for the IBM 709 is being prepared.

5 Another Formalism for Fu nctions of Sym-

boli c Expressions

There are a number of ways of deﬁning functions of symbolic expressions which are quite similar to the system we have adopted. Each of them involves three basic functions, conditional expressions, and recursive function deﬁnitions, but the class of expressions corresponding to S-expressions is diﬀerent, and so are the precise deﬁnitions of the functions. We shall describe one of these variants called linear LISP.

The L-expressions are deﬁned as fo llows: 1. A ﬁnite list of characters is admitted. 2. Any string of admitted characters in an L-expression. This includes the null string denoted by Λ.

There are three functions of strings: 1. first[x] is the ﬁrst character of the string x. first[Λ] is undeﬁned. For example: first[ABC] = A 2. rest[x] is the string of characters which remains when the ﬁrst character of the string is deleted.

rest[Λ] is undeﬁned. For example: rest[ABC] = BC. 3. combine[x; y] is the string formed by preﬁxing the character x to the string y. For example: combine[A; BC] = ABC

30

#### Page 31

There are three predicates on strings: 1. char[x], x is a single chara cter. 2. null[x], x is the null string. 3. x = y, deﬁned for x and y characters. The advantage of linear LISP is that no characters are given special roles, as are parentheses, dots, and commas in LISP. This permits computations with all expressions that can be written linearly. The disadvantage of linear LISP is that the extraction of subexpressions is a fairly involved, rather than an elementary, operation. It is not hard to write, in linear LISP, functions that correspond to the basic functions of LISP, so that, mathematically, linear LISP includes LISP. This turns out to be the most convenient way of programming, in linear LISP, the more complicated manipulations. However, if the functions are to be represented by computer routines, LISP is essentially faster.

6 Flowch arts and Recurs i on

Since both the usual form of computer program and recursive function deﬁnitions a r e universal computationally, it is interesting to display the relation between them. The translation of recursive symbolic functions into computer programs was the subject of the rest of this report. In this section we show how to go the other way, at least in principle.

The state of the machine at any time during a computation is given by the values of a number of variables. Let these variables be combined into a vector ξ. Consider a program block with one entrance and one exit. It deﬁnes and is essentially deﬁned by a certain function f that takes one machine conﬁguration into another, that is, f has the form ξ 0 = f (ξ). Let us call f the associated function of the program block. Now let a number of such blocks be combined into a program by decision elements π that decide after each block is completed which block will be entered next. Nevertheless, let the whole program still have one entra nce and one exit.

31

#### Page 32

?

?

 

 

 

 

 

 

?

?

?



 X X Xz    H H Hj   +

- ?

?

f 1 f 2

f 3

f 4

π 3

π 2

π 1

S

T

Figure 5

We give as an example the ﬂowcart o f ﬁgure 5. Let us describe the function r[ξ] that gives the tra nsformation of the vector ξ between entrance a nd exit of the whole block. We shall deﬁne it in conjunction with the functions s(ξ), and t[ξ], which give the transformations that ξ undergoes between the points S and T, respectively, and the exit. We have

r[ξ] = [π [Annotation 23] 1 1[ξ] → S[f 1 [ξ]]; T → S[f 2 [ξ]]] S[ξ] = [π 2 1[ξ] → r[ξ]; T → t[f 3 [ξ]]] t[ξ] = [π3I[ξ] → f 4 [ξ]; π 3 2[ξ] → r[ξ]; T → t[f 3 [ξ]]]

Given a ﬂowchart with a single entra nce and a single exit, it is easy to write down the recursive function that gives the transformation of the state vector from ent rance to exit in terms of the corresponding functions for the computation blocks and the predicates of the branch. In general, we proceed as follows.

In ﬁgure 6, let β be an n-way branch point, and let f 1 , · · · , f n be the computations leading to branch points β 1 , β 2 , · · · , β n . Let φ be the function

32

#### Page 33

that transforms ξ between β and the exit of the chart, and let φ 1 , · · · , φ n be the corresponding functions for β 1 , · · · , β n . We then write

φ[ξ] = [p 1 [ξ] → φ 1 [f 1 [ξ]]; · · · ; p n [ξ] → φ n [ξ]]]

   @

@ @

 

@

@ @

 

 

 

 

 

 

     ?

A A

A A AU

C C CW ?

  

....

.....

..... f 1 f 2 f n

β

β 1 β 2 β n

φ 1 φ 2 φ n

φ

Figure 6

7 Acknowl edgments

The inadequacy of the λ-notation for naming recursive f unctions was noticed by N. Rochester, a nd he discovered an alternative to the solution involving label which has been used here. The form of subroutine for cons which permits its composition with other functions was invented, in connection with [Annotation 24] another programming system, by C. Gerberick and H. L. Gelernter, of IBM Corporation. The LlSP prog r amming system was developed by a group including R. Brayton, D. Edwards, P. Fox, L. Hodes, D. Luckham, K. Maling, J. McCarthy, D. Park, S. Russell.

The group was supported by the M.I.T. Computation Cent er, and by the M.I.T. Research Labora tory of Electronics (which is supported in part by the the U.S. Army (Signal Corps), the U.S. Air Force (O ﬃce of Scientiﬁc Research, Air Research a nd Development Command), and the U.S. Navy ( O ﬃce of Naval Research)). The author also wishes to acknowledge the personal ﬁnancial sup-

33

#### Page 34

port of the Alfred P. Sloan Foundation.

REFERENCES

1. J. McCARTHY, Programs with common sense, Paper presented at the Symposium on the Mechanization of Thought Processes, National Physical Laboratory, Teddington, England, Nov. 24-27 , 1958. (Published in Proceedings of the Symposium by H. M. Stationery Oﬃce).

2. A. NEWELL AND J. C. SHAW, Programming the log ic theory machine, Proc. Western Joint Computer Conference, Feb. 19 57.

3. A. CHURCH, The Calculi of Lambda-Convers i on (Princeton University Press, Princeton, N. J., 1941).

4. FORTRAN Programmer’s Reference Manual, IBM Corporation, New York, Oct. 15, 1956.

5. A. J. PERLIS AND K. SAMELS0N, International algebraic language, Preliminary Report, Comm. Assoc. Comp. Mach., Dec. 1958.

34

---

Source: [Fermat's Library](https://fermatslibrary.com/) — https://fermatslibrary.com/s/recursive-functions-of-symbolic-expressions-and-their-computation-by-machine. More annotated papers: https://fermatslibrary.com/llms.txt
