Next: The LISP Programming System Up: Recursive Functions of Symbolic Previous: Functions and Function Definitions

# Recursive Functions of Symbolic Expressions

We shall first define a class of symbolic expressions in terms of ordered pairs and lists. Then we shall define five 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 define a universal function that allows us to compute from the expression for a given function its value for given arguments. Finally, we shall define some functions with functions as arguments and give some useful examples.

a. A Class of Symbolic Expressions. We shall now define the S-expressions (S stands for symbolic). They are formed by using the special characters

and an infinite set of distinguishable atomic symbols. For atomic symbols, we shall use strings of capital Latin letters and digits with single imbedded blanks.4 Examples of atomic symbols are

There is a twofold reason for departing from the usual mathematical practice of using single letters for atomic symbols. First, computer programs frequently require hundreds of distinguishable symbols that must be formed 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 ignored. We assume only that different symbols can be distinguished. S-expressions are then defined as follows:

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

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

is represented by the S-expression

Here 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

l. stands for (m ).

2. stands for .

3. stands for .

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

for for

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

b. Functions of S-expressions and the Expressions That Represent Them. We now define a class of functions of S-expressions. The expressions representing these functions are written in a conventional functional notation. However, in order to clearly distinguish the expressions representing functions from S-expressions, 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, for denoting the application of functions to their arguments. Thus we write

In these M-expressions (meta-expressions) any S-expression that occur stand for themselves.

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

1. atom. 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 defined 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

eq [X; X] = T

eq [X; A] = F

eq [X; (X A)] is undefined.

3. car. car[x] is defined if and only if x is not atomic. car . Thus car [X] is undefined.

car = X
car

4. cdr. cdr [x] is also defined when x is not atomic. We have cdr . Thus cdr [X] is undefined.

cdr = A cdr = Y

5. cons. cons [x; y] is defined for any x and y. We have cons . Thus

cons [X; A] = (X A)
cons

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 significance 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 fact, all computable functions) when we allow ourselves to form new functions of S-expressions by conditional expressions and recursive definition. We now give some examples of functions that are definable in this way.

1. . The value of is the first atomic symbol of the S-expression with the parentheses ignored. Thus

We have

We now trace in detail the steps in the evaluation of

ff [((A B) C)]:
ff [((A B) C)]

2. subst . This function gives the result of substituting the S-expression for all occurrences of the atomic symbol in the S-expression . It is defined 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

3. equal [x; y]. This is a predicate that has the value if and are 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 elementary functions look in the abbreviated list notation. The reader will easily verify that

(i)

(ii)

(iii)

(iv)

(v)

We define

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

for

for , etc.

Another useful abbreviation is to write list

for .

This function gives the list, , as a function of its elements.

The following functions are useful when S-expressions are regarded as lists.

1. append [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 occurs among the elements of the list . We have

3. pair [x;y]. This function gives the list of pairs of corresponding elements of the lists and . We have

An example is

4. assoc [x;y]. If is a list of the form and is one of the 's, then assoc is the corresponding . We have

An example is

5. . Here is assumed to have the form of a list of pairs , where the 's are atomic, and may be any S-expression. The value of is the result of substituting each for the corresponding in . In order to define sublis, we first define an auxiliary function. We have

and

We have

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

e. Representation of S-Functions by S-Expressions. 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 S-functions.

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

1. If is an S-expression * is (QUOTE, ).

2. Variables and function names that were represented by strings of lower-case letters are translated to the corresponding strings of the corresponding uppercase letters. Thus car* is CAR, and subst* is SUBST.

3. A form is translated to Thus cons [car [x]; cdr [x]] is (CONS, (CAR, X), (CDR, X)).

4. is (COND, .

5. is (LAMBDA, .

6. is (LABEL, a, .

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 notation 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.5

f. The Universal S-Function apply. There is an S-function with the property that if is an S-expression for an S-function and is a list of arguments of the form , where are arbitrary S-expressions, then and are defined for the same values of , and are equal when defined. For example,

The S-function apply is defined by

where

and

eval[e; a] = [

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

and

We now explain a number of points about these definitions. 6

1. 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 . It uses to put quotes around each of the arguments, so that will regard them as standing for themselves.

2. has two arguments, an expression to be evaluated, and a list of pairs . The first item of each pair is an atomic symbol, and the second is the expression for which the symbol stands.

3. If the expression to be evaluated is atomic, eval evaluates whatever is paired with it first on the list .

4. If is not atomic but is atomic, then the expression has one of the forms or or or , or or or or where is an atomic symbol.

In the case the expression , itself, is taken. In the case of or or the expression is evaluated and the appropriate function taken. In the case of or two expressions have to be evaluated. In the case of the 's have to be evaluated in order until a true is found, and then the corresponding must be evaluated. This is accomplished by . Finally, in the case of we evaluate the expression that results from replacing in this expression by whatever it is paired with in the list .

5. The evaluation of is accomplished by evaluating with the pairing put on the front of the previous list of pairs.

6. Finally, the evaluation of is accomplished by evaluating with the list of pairs put on the front of the previous list .

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

Calculating the values of functions by using is an activity better suited to electronic computers than to people. As an illustration, 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 first argument is the S-expression that represents the function ff defined in section 3d. We shall abbreviate it by using the letter . We have


[; ( (AB) )]

= eval [((LABEL, FF, ), (QUOTE, (AB))); NIL]

where  is the part of  beginning (LAMBDA

= eval[((LAMBDA, (X), ), (QUOTE, (AB)));((FF, ))]

where  is the part of  beginning (COND

= eval [(COND, ()); ((X, (QUOTE, (AB) ) ), (FF, ) )]

Denoting ((X, (QUOTE, (AB))), (FF, )) by , we obtain

= evcon [((), ()); ]

This involves eval []

= eval [( ATOM, X); ]

= atom [eval [X; ]]

= atom [eval [assoc [X; ((X, (QUOTE, (AB))), (FF,))];]]

= atom [eval [(QUOTE, (AB)); ]]

= atom [(AB)],

= F

Our main calulation continues with

[; ((AB))]

= evcon [((],

involves eval [] = eval [(QUOTE, T); ] = T

Our main calculation again continues with

[; ((AB))]

= eval []

= eval [(FF, (CAR, X));]

= eval [Cons [; evlis [((CAR, X)); ]]; ]

Evaluating evlis [((CAR, X)); ] involves

[(CAR, X); ]

= car [eval [X; ]]

= car [(AB)], where we took steps from the earlier computation of atom [eval [X; ]] = A,

so evlis [((CAR, X)); ] then becomes

list [list [QUOTE; A]] = ((QUOTE, A)),

our main quantity becomes

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



The subsequent steps are made as in the beginning of the calculation. The LABEL and LAMBDA cause new pairs to be added to , which gives a new list of pairs . The term of the conditional eval [(ATOM, X); ] has the value T because X is paired with (QUOTE, A) first in , rather than with (QUOTE, (AB)) as in .

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

g. Functions with Functions as Arguments. There are a number of useful functions some of whose arguments are functions. They are especially useful in defining other functions. One such function is with an S-expression argument and an argument that is a function from S-expressions to S-expressions. We define

The usefulness of is illustrated by formulas for the partial derivative with respect to of expressions involving sums and products of and other variables. The S-expressions that we shall differentiate are formed as follows.

1. An atomic symbol is an allowed expression.

2. If are allowed expressions, ( PLUS, ) and (TIMES, ) are also, and represent the sum and product, respectively, of .

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 differentiation formula, which gives the derivative of with respect to , is

diff [y; x] = [atom [y] [eq [y; x] ONE; T ZERO]; eq [car [Y]; PLUS] cons [PLUS; maplist [cdr [y]; [[z]; diff [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 diff [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 , another useful function with functional arguments is , which is defined as

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

Next: The LISP Programming System Up: Recursive Functions of Symbolic Previous: Functions and Function Definitions
John McCarthy
2006-08-13