1.6 A Universal LISP Function

An interpreter or universal function is one that can compute the value of any given function applied to its arguments when given a description of that function. (Of course, if the function that is being interpreted has infinite recursion, the interpreter will recur infinitely also. )

We are now in a position to define the universal LISP function evalqyote[fn;args]. When evalquote is given a function and a list of arguments for that function, it computes the value of the function applied to the arguments.

LISP functions have S-expressions as arguments. In particular, the argument "fn" of the function evalquote must be an S-expression. Since we have been writing functions as M-expressions, it is necessary to translate them into S-expressions.

The following rules define a method of translating functions written in the metalanguage into S-expressions.

1. If the function is represented by its name, it is translated by changing all of the letters to upper case, making it an atomic symbol. Thus car is translated to CAR.

2. If the function uses the lambda notation, then the expression $\lambda {[}{[}x_{1}; \ldots ;x_{n}{]};\epsilon {]}$ is translated into (LAMBDA (X1 ... XN) $\epsilon ^{*}$), where $\epsilon ^{*}$ is the translation of $\epsilon$.

3. If the function begins with label, then the translation of $label{[}a; \epsilon {]}$ is (LABEL $a^{*} \epsilon ^{*}$).

Forms are translated as follows:

1. A variable, like a function name, is translated by using uppercase letters. Thus the translation of var1 is VAR1.

2. The obvious translation of letting a constant translate into itself will not work. Since the translation of x is X, the translation of X must be something else to avoid ambiguity. The solution is to quote it. Thus X is translated into (QUOTE X).

3. The form $fn{[}arg_{1}; \ldots ; arg_{n}{]}$ is translated into $(fn^{*}   arg_{1}^{*} \ldots  arg_{n}^{*})$.

4. The conditional expression ${[}p_{1}\rightarrow e_{1}; \ldots ;p_{n}\rightarrow e_{n}{]}$ is translated into (COND ( $p_{1}^{*}  e_{1}^{*}) \ldots   (p_{n}^{*} e_{n}^{*}))$.

Examples

M-expressions	S-expressions
x	X
car	CAR
car[x]	(CAR X)
T	(QUOTE T)
ff[car[x]]	(FF (CAR X))
[atom[x] $\rightarrow$ x; T $\rightarrow$ ff[car[x]]]	(COND ((ATOM X) X)
((QUOTE T) (FF (CAR X))))
label[ff; $\lambda$[[x]; [atom[x] $\rightarrow$x;
$T\rightarrow$ff[car[x]]]]]	(LABEL FF (LAMBDA (X) (COND
((ATOM X) X)
((QUOTE T) (FF (CAR X))))))

Some useful functions for handling S-expressions are given below. Some of them are needed as auxiliary functions for evalquote.

equal[x;y]

This is a predicate that is true if its two arguments are identical S-expressions, and is false if they are different. (The elementary predicate eq is defined only for atomic arguments.) The definition of equal is an example of a conditional expression inside a conditional expression.

equal[x;y]=[atom[x] $\rightarrow$[atom[y] $\rightarrow$eq[x;y]; T $\rightarrow$F]; 
        equal[car[x];car[y]] $\rightarrow$equal[cdr[x]; cdr[y]]; 
        T $\rightarrow$F]

This can be translated into the following S-expression:

(LABEL EQUAL (LAMBDA (X Y) (COND 
        ((ATOM X) (COND ((ATOM Y) (EQ X Y)) ((QUOTE T) (QUOTE F)))) 
        ((EQUAL (CAR X) (CAR Y)) (EQUAL (CDR X) (CDR Y))) 
        ((QUOTE T) (QUOTE F))    )))

subst[x;y;z]

This function gives the result of substituting the S-expression x for all occurrences of the atomic symbol y in the S-expression z. It is defined by

subst[x;y;z] = [equal[y;z] $\rightarrow$x; atom[z] $\rightarrow$z; T $\rightarrow$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)

null[x]

This predicate is useful for deciding when a list is exhausted. It is true if and only if its argument is NIL.

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

1. append[x;y]

append[x;y] = [null[x] $\rightarrow$y;T $\rightarrow$cons[car[x];append[cdr[x];y]]]

An example is

append[(A B);(C D E)] = (A B C D E)

2. member[x;y]

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

member[x;y] = [null[y] $\rightarrow$F; 
        equal[x;car[y]] $\rightarrow$T; 
        T $\rightarrow$member[x;cdr[y]]]

3. pairlis[x;y;a]

This function gives the list of pairs of corresponding elements of the lists x and y, and appends this to the list a. The resultant list of pairs, which is like a table with two columns, is called an association list. We have

pairlis[x;y;a] = [null[x] $\rightarrow$a;T $\rightarrow$cons[cons[car[x];car[y]]; 
        pairlis[cdr[x];cdr[y];a]]]

An example is

pairlis[(A B C);(U V W);((D . X) (E . Y))] = 
        ((A . U)(B . V)(C . W)(D . X)(E . Y))

4. assoc[x;a]

If a is an association list such as the one formed by pairlis in the above example, then assoc will produce the first pair whose first term is x. Thus it is a table searching function. We have

assoc[x;a] = [equal[caar[a];x] $\rightarrow$car[a];T $\rightarrow$assoc[x;cdr[a]]]

An example is

assoc[B;((A . (M N)), (B . (CAR X)), (C . (QUOTE M)), (C . (CDR X)))] 
        = (B . (CAR X))

5. sublis[a;y]

Here a is assumed to be an association list of the form $((u_{1} . v_{1}) \ldots (u_{n} . v_{n}))$, where the u's are atomic, and y is any S-expression. What sublis does. is to treat the u's as variables when they occur in y. and to substitute the corresponding v's from the pair list. In order to define sublis, we first define an auxiliary function. We have

sub2[a;z] = [null[a] $\rightarrow$z;eq[caar[a];z] $\rightarrow$cdar[a];T $\rightarrow$ sub2[cdr[a];z]]

and

sublis[a;y] = [atom[y] $\rightarrow$sub2[a;y];T $\rightarrow$cons[sublis[a;car[y]]; 
        sublis[a;cdr[y]]]]

An example is

sublis[((X . SHAKESPEARE) (Y . (THE TEMPEST)));(X WROTE Y)] 
        = (SHAKESPEARE WROTE (THE TEMPEST))

The universal function evalquote that is about to be defined obeys the following identity. Let f be a function written as an M-expression, and let fn be its translation. (fn is an S-expression.) Let f be a function of n arguments and let $args=(arg_{1} \ldots arg_{n})$, a list of the n S-expressions being used as arguments. Then

evalquote[fn;args]=f[ $arg_{1}; \ldots ;arg_{n}$]

if either side of the equation is defined at all.

Example

f:         $\lambda$[[x;y];cons[car[x];y]] 
fn:     (LAMBDA (X Y) (CONS (CAR X) Y)) $arg_{1}$:     (A B) $arg_{2}$:     (C D) 
args:     ((A B) (C D)) 
 
evalquote[(LAMBDA (X Y) (CONS (CAR X) Y)); ((A B) (C D))] = 
         $\lambda$[[x;y];cons[car[x];y]][(A B);(C D)] 
        = (A C D)

evalquote is defined by using two main functions, called eval and apply. apply handles a function and its arguments, while eval handles forms. Each of these functions also has another argument that is used as an association list for storing the values of bound variables and function names.

evalquote[fn;x] = apply[fn;x;NIL]

where

apply[fn;x;a] = 
        [atom[fn] $\rightarrow$ [eq[fn;CAR] $\rightarrow$caar[x]; 
                eq[fn;CDR] $\rightarrow$ cdar[x]; 
                eq[fn;CONS] $\rightarrow$ cons[car[x];cadr[x]]; 
                eq[fn;ATOM] $\rightarrow$ atom[car[x]]; 
                eq[fn;EQ] $\rightarrow$ eq[car[x];cadr[x]]; 
                T $\rightarrow$ apply[eval[fn;a];x;a]]; 
        eq[car[fn];LAMBDA] $\rightarrow$ eval[caddr[fn];pairlis[cadr[fn];x;a]]; 
        eq[car[fn];LABEL] $\rightarrow$ apply[caddr[fn];x;cons[cons[cadr[fn], 
                                        caddr[fn]];a]]] 
 
eval[e;a] = [atom[e] $\rightarrow$ cdr[assoc[e;a]]; 
        atom[car[e]] $\rightarrow$                [eq[car[e];QUOTE] $\rightarrow$ cadr[e]; 
                eq[car[e];COND] $\rightarrow$ evcon[cdr[e];a]; 
                T $\rightarrow$ apply[car[e];evlis[cdr[e];a];a]]; 
        T $\rightarrow$ apply[car[e];evlis[cdr[e];a];a]]

pairlis and assoc have been previously defined.

evcon[c;a] = [eval[caar[c];a] $\rightarrow$ eval[cadar[c];a]; 
        T $\rightarrow$ evcon[cdr[c];a]]

and

evlis[m;a] = [null[m] $\rightarrow$ NIL; 
        T $\rightarrow$ cons[eval[car[m];a];evlis[cdr[m];a]]]

We shall explain a number of points about these definitions.

The first argument for apply is a function. If it is an atomic symbol, then there are two possibilities. One is that it is an elementary function: car, cdr, cons, eq, or atom. In each case, the appropriate function is applied to the argument(s). If it is not one of these, then its meaning has to be looked up in the association list.

If it begins with LAMBDA, then the arguments are paired with the bound variables, and the form is given to eval to evaluate.

If it begins with LABEL, then the function name and definition are added to the association list, and the inside function is evaluated by apply.

The first argument of eval is a form. If it is atomic, then it must be a variable, and its value is looked up on the association list.

If car of the form is QUOTE, then it is a constant, and the value is cadr of the form itself.

If car of the form is COND. then it is a conditional expression, and evcon evaluates the prepositional terms in order, and choses the form following the first true predicate.

In all other cases, the form must be a function followed by its arguments. The arguments are then evaluated, and the function is given to apply.

The LISP Programming System has many added features that have not been described thus far. These will be treated hereafter. At this point, it is worth noting the following points.

1. In the pure theory of LISP, all functions other than the five basic ones need to be defined each time they are to be used. This is unworkable in a practical sense. The LISP programming system has a larger stock of built-in functions known to the interpreter, and provision for adding as many more as the programmer cares to define.

2. The basic functions car, and cdr were said to be undefined for atomic arguments. In the system, they always have a value, although it may not always be meaningful. Similarly, the basic predicate eq always has a value. The effects of these functions in unusual cases will be understood after reading the chapter on list structures in the computer.

3. Except for very unusual cases, one never writes (QUOTE T) or (QUOTE F), but T, and F respectively.

4. There is provision in LISP for computing with fixed and floating point numbers. These are introduced as psuedo-atomic symbols.

The reader is warned that the definitions of apply and eval given above are pedagogical devices and are not the same functions as those built into the LISP programming system. Appendix B contains the computer implemented version of these functions and should be used to decide questions about how things really work.