| Mirror on informatimago.com
| Mirror on free.fr
|
Here is a transcription into machine readable form of the original AI Memo 8, AIM-008.pdf
Also available as compressed text file (utf-8).
March 23, 1959 Artificial intelligence Project---RLE and MIT Computation Center Memo 8 RECURSIVE FUNCTIONS OF SYMBOLIC EXPRESSIONS AND THEIR COMPUTATION BY MACHINE by J. McCarthy An Error in Memo 8 The definition of eval given on page 15 has two errors, one of which is typographical and the other conceptual. The typographical error is in the definition of evcon where "1⟶" and "T⟶" should be interchanged. The second error is in evlam. The program as it stands will not work if a quoted expressoin contains a symbol which also acts as a variable bound by the lambda. This can be corrected by using insteaad of subst in evlam a function subsq defined by subsq=λ[[x;y;z];[null[z]⟶⋀;atom[z]⟶ [y=z⟶x;l⟶z];first[z]=QUOTE⟶z;l⟶ combine[subsq[x;y;first[z]];subsq[x;y;rest[x]]]]]
March 4, 1959 Artificial intelligence Project---RLE and MIT Computation Center Memo 8 RECURSIVE FUNCTIONS OF SYMBOLIC EXPRESSIONS AND THEIR COMPUTATION BY MACHINE by J. McCarthy The attached paper is a description of the LISP system starting with the machine-independent system of recursive functions of symbolic expressions. This seems to be a better point of view for looking at the system than the original programming approach. After revision, the paper will be sub- mitted for publication in a logic or computing journal. This memorandum contains only the machine independent parts of the system. The representation of S-expressions in the computer and the system for representing S-functions by computer subroutines will be added.
-1- RECURSIVE FUNCTIONS OF SYMBOLIC EXPRESSIONS AND THEIR COMPUTATION BY MACHINE by J. McCarthy, MIT Computation Center 1. Introduction A programming system called LISP (for LISt Processor) has been developed for the IBM 704 computer by the Artificial Intelligence Group at MIT. The system was designed to facili- tate experiments with a proposed system called the Advice Taker whereby a machine could be instructed in declarative as well as imperative sentences and could exhibit "common sense" in carrying out its instructions. The original proposal for the Advice Taker is contained in reference 1. The main require- ment was a programming system for manipulating expressions representing formalized declarative and imperative sentences so that the ADvice Taker system could make deductions. The development of the LISP system went through several stages of simplification in the course of its development and was eventually seen 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 or any other electronic computer and it now seems expedient to expound the system starting with the class of expressions called S-expressions and the functions called S-functions. In this paper, we first describe the class of S-expressions and S-functions. Then we describe the representation of S-functions by S-expressions which enables us to prove that all computable partial functions have been obtained, to obtain a universal S-function, and to exhibit a set of questions about S-expressions which cannot be decided by an S-function. We describe the representation of the system in the IBM 704, including the representation of S-expressions by list structures similar to those used by Newell, Simon, and Shaw (see refer- ence 2), and the representation of S-functions by subroutines. Finally, we give some applications to symbolic calculations including analytic differentiation, proof checking, and compiling including a description of the present status of the LISP compiler itself which is being written in the system. Although we have not carried out the development of
-2- recursive function theory in terms of S-functions and their representation by S-expressions beyond the simplest theorems, it seems that formulation of this theory in terms of S-func- tions has important advantages. Devices such as Gödel number- ing are unnecessary and so is the construction of particular Turing machines. (These constructions are all artificial in terms of what is intended to be accomplished by them). The advantage stems from the fact that functions of symbolic expressoins are easily and briefly described as S-expressions and the representation of S-functions by S-expressions is trivial. Moreover, in a large class of cases the S-expression representations of S-functions translate directly into effi- cient machine programs for the computation of the functions. Although, the functions described in the manner of this paper include all computable functions of S-expressions, describe many important processes in a very convenient way, and compile into fast running programs for carrying out the processes; there are other kinds of processes whose description by S-func- tions is inconvenient and for which the S-functions once found do not naturally compile into efficient programs. For this reason, the LISP system includes the possibility of combining S-functions into Fortran or IAL-like programs. Even this will not provide the flexibility of description of processes hoped for from the Advice Taker system which is beyond the scope of this paper. 2. Recursive Functions of Symbolic Expressions In this section we define the S-expressions and the S-functions. (Actually they are partial functions. The distinction between a partial function and a function that the former need not be defined for all arguments because, for example, the computation process defining it may not terminate.) 2.1. S-expressions The expression with which we shall deal are formed using the special characters "," and "(" and ")" and an infinite set of distinguishable atomic symbols p₁,p₂,p₃,....
-3- The S-expressions are formed according to the following recursive rules. 1. The atomic symbols p₁ p₂ etc are S-expressions. 2. A null expression ⋀ is also admitted. 3. If e is an S-expression so is (e). 4. If e₁ and (e₂) are S-expressions so is (e₁,e₂). In what follows we shall use sequences of capital Latin letters as atomic symbols. Since we never juxatpose them with- out intervening commas they cannot cause confusion by running together. Some examples of S-expressions are; AB (AB,A) (AB,A,,C,) ((AB,C),A,(BC,(B,B))) 2.2 Elementary functions and predicates The functions we shall need are built up from certain elementary ones according to certain recursive rules. There are three elementary predicates: 1. null[e] null[e] is true if and only if S-expression e is the null expression ⋀. (We shall use square brackets and semi-colons for writing functions of S-expressions since parentheses and commas have been pre-empted. When writing about functions in general we may continue to use parentheses and commas.) 2. atom[e] atom[e] is true if and only if the S-expression is an atomic symbol. 3. p₁=p₂ p₁=p₂ is defined only when p₁ and p₂ are both atomic symbols in which case it is true if and only if they are the same symbol. This predicate expresses the distinguishability of the symbols. There are three basic functions of S-expressions whose values are S-expressions. 4. first[e] first[e] is defined for S-expressions which are neither null nor atomic. If e has the form (e₁,e₂) where e₁ is an expression, then first[e]=e₁. If e has the form (e₁) wehre e₁ is an S-expression again we have first[e]=e₁.
-4- Some examples are: first[(A,B)]=A first[A] is undefined first[(A)]=A first[((A,B),C,D)]=(A,B) 5. rest[e] rest[e] is also defined for S-expressions which are neither null nor atomic. If e has the form (e₁,e₂) where e₁ is an S-expression, then rest[e]=(e₂). If e has the form (e₁) wehre e₁ is an S-expression we have rest[e]=⋀. Some examples are: rest[(A,B)]=(B) rest[(A)]=⋀ rest[(A,B,C)]=(B,C) 6. combine[e₁;e₂] combine[e₁;e₂] is defined when e₂ is not atomic. When e₂ has the form (e₃), then combine[e₁;e₂]=(e₁,e₃) When e₂ is ⋀ we have combine[e₁;e₂]=(e₁). Some examples are: combine[A;⋀]=(A) combine[(A,B);(B,C)]=((A,B),B,C) The functions first, rest and combine are related by the relations first[combine[e₁;e₂]]=e₁ rest[combine[e₁;e₂]]=e₂ combine[first[e];rest[e]]=e whenever all the quantities involved are defined. 2.3 Functional Expressions and Functions formed from the elementary functions by composition. Additional functions may be obtained by composing the elementary functions of the preceding section. These functions are decribed by expressions in the meta-language which should not be confused with the S-expressions being manipulated. For example, the expression first[rest[e]] debute the second sub- expression of the S-expression e, e.g. first[rest[(A,B,C)]]=B. In general compositions of first and rest give sub-expressions of an S-expression in a given position within the expression and
-5- compositions of combine form S-expressions from their sub- expressions. For example, combine[x;combine[y;combine[z,⋀]]] forms as sequence of three ters from the terms, e.g. combine [A;combine[(B,C);combine[A,⋀]]]=(A,(B,C),A). In order to be able to name compositions of functions and not merely functional expressions (forms) we use the Church λ-notation. If ℰ is a functional expression and x₁,...,xn are variables which may occur in ℰ, then λ[[x₁,...,xn],] denotes the function of n variables that maps x₁,...,xn into ℰ. For example, λ[[x],first[rest[x]]] is the function which selects the second element of a list and we have λ[[x],first[rest[x]]][(A, [B,C],A)]=[B,C]. λ[[x];[A,B]] is the constant function that maps every S-expression into [A,B]. The variables occuring in the list of a λ-expression are bound and replacing such a variable throughout a λ-expression by a new variable does not change the function represented. Thus λ[[x,y], combine[x,combine[y,⋀]]] is the same function as λ[[u,v], combine[u,combine[v,⋀]]] but different from λ[[y,x], combine[x,combine[y,⋀]]]. If some of the variables in a functional expressoin or form are bound by λ's and others are not, we get a function dependent on parameters or from another point of view a form whose value is a function when values have been assigned to the variables. 2.4 Conditional Expressions Let p₁,p₂,...,pk be expressions representing propositions and let e₁,...,ek be arbitrary expressions. The expression [p₁⟶e₁,...pk⟶ek] is called a conditional expression and its value is determined from the values assigned to the variables occuring in it as follows: If the value of p₁ is not defined neither is that of the conditional expression. If p₁ is defined and true the value of the conditional expression is that of e₁ if the latter is defined and otherwise is undefined. If p₁ is defined and false, then the value of [p₁⟶e₁,...,pk⟶ek] is that of [p₂⟶e₂,...pk⟶ek]. Finally if pk is false the value of [pk⟶ek] is undefined. An example of a conditional expression is [null[x]⟶⋀; atom[x]⟶⋀;1⟶first[x]]. The "1" occuring in the above expression is the propositional constant "truth". We also use
-6- "0" for the propositional constant "falsehood". When used as then last proposition in a conditional expression "1" may be read "in all remaining cases". The expression given is a sort of extension of the expressoin first[x] which is defined for all S-expressions. We could define a corresponding function by first_a=λ[[x]; [null[x]⟶⋀;atom[x]⟶⋀;1⟶first[x]]]. It is very important to note that for a conditional expressoin to be defined it is not necessary for all of its sub-expressions to be defined. If p₁ is defined and true and e₁ is defined, the conditional expression [p₁⟶e₁,...,pk⟶ek] is defined even if none of the other p's or e's is defined. If p₁ is defined and false, p₂ is defined and true and e₂ is defined, the expression is defined even if e₁ and all the other p's and e's are undefined. The propositional connectives ∧ and ∨ and ∼ may be defined in terms of conditional expressions. We have p₁∧p₂=[p₁⟶[p₂ ⟶1,1⟶0],1⟶0] and p₁∨p₂=[p₁⟶1,p₂⟶1,1⟶0] and ∼p=[p⟶0,1⟶1] There is a slight difference between the connecetives defined this way and the ordinary connectives. Suppose that p₁ is defined and true but p₂ is undefined. Then p₁∨p₂ is defined and true but p₂∨p₁ is undefined. 2.5 Recursive Function Definitions The functions which can be obtained from the elementary functions and predicates by composition and conditional expres- sions form a limited class. As we have decribed them they are not defined for all S-expressions but if we modified the definitions of the elementary functions so that the undefined cases are defined in some trivial way, as in the example of the pervious section, the would be always defined. Additional functions may be defined by writing definitions of the form, f=λ[[x₁,...,xn],ℰ] where the expression ℰ may contain the symbol f itself. A function f defined in this way is to be computed for a given argument is to be computed by substitution of the argument into the expression and attempting to evaluate the resulting expression. When a conditional expression is encountered we evaluate p's until we find a true p and then evaluate the corresponding e. No attempt is made
-7- to evaluate later p's or any e except the one corresponding to the first e. It may happen that in evaluating for given values of the variables it is unnecessary to evaluate any expression involving the defined function f. In this case, the evaluation may be completed and the function defined for this argument. If expressions involving f do have to be evaluated we substitute the arguments of f and again proceed to evaluate. The process may or may not terminate. For those arguments for which the process does terminate the function is defined. We shall illustrate this concept by several examples: 1. Our first example is a function which gives the first symbol of an expression: We defined ff=λ[[x];[null[x]∨atom[x]⟶x;1⟶ff[first[x]]]] Let us trace the computation of ff[(((A),B),C)]. We have ff[(((A),B),C)]=[null[(((A),B),C)]∨atom[(((A),B),C)]⟶x; 1⟶ff[first[(((A),B),C)]]]] =ff[((A),B)] =[null[((A),B)]∨atom[((A),B)]⟶((A),B);1⟶ff[first[((A),B)]]] =ff[(A)] =[null[(A)]∨atom[(A)]⟶(A);1⟶ff[first[(A)]]] =ff[A] =[null[A]∨atom[A]⟶A;1⟶ff[first[A]]] =A * Note that it does not matter that first A occuring in the next to last step is undefined. 2. The second example is a function which gives the result of substituting the expression x for the symbol y in the expres- sion s. We define subst=λ[[x;y;s];[null[s]⟶⋀;atom[s]⟶[y=s⟶x;1⟶s];1⟶ combine[subst[x;y;first[s]];subst[x;y;rest[s]]]]] We shall illustrate teh application of this definition by computing subst[(A,B);X;((X,A),C)]. In order to make the tracing shorter we shall give the situation at each recursion and leave it to the reader to substitute the definition of each subst expression and to check the determination of which case of the
-8- conditional is applicable. We have subst[(A,B);X;((X,A),C)]= =combine[subst[(A,B);X;(X,A)];subst[(A,B);X;(C)]] =combine[combine[subst[(A,B);X;X];subst[(A,B);X;(A)]];combine[ subst[(A,B);X;C];subst[(A,B);X;⋀]]] =combine[combine[(A,B);combine[subst[(A,B);X;A];subst[(A,B) ;X;⋀]]];combine[C;⋀]] =combine[combine[(A,B);combine[A;⋀]];(C)] =(((A,B),A),C) 2.6 Functions with Functions as arguments If we allow variables representing functions to occur in expressions and create functions by incorporating these variables as arguments of λ's we can define certain functions more concisely than without this facility. However, as we shall show later no additional S-function become definable. As an example of this facility we define a function maplist [x,f] where x is an S-expression and f is a function from S-expres- sions to S-expressions. We have maplist=λ[[x,f];[null[x]⟶⋀;1⟶combine[f[x];maplist[rest[x];f]]]] The usefulness of maplist is illustrated byb formulas for the partial derivative with respect to x of expressions involving sums and products of x and other variables. The S-expressions we shall differentiate are formed as follow: 1. An atomic symbol is an allowed expression. 2. If e₁;e₂;...;en are allowed expressions so are (PLUS,e₁, ...,en) and (TIMES,e₁,...,en) and represent the sum and product respectively of e₁;...;en 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 is diff=λ[[y;x];[atom[y]⟶[y=x]⟶ONE;1⟶ZERO]; first[y]=PLUS⟶combine[PLUS;maplist[rest[y];λ[[z];diff[ first[z];x]]]];first[y]=TIMES⟶combine[PLUS;maplist[ rest[y];λ[[z];combine[TIMES;maplist[rest[y];λ[[w];[z≠w ⟶first[w];1⟶diff[first[w];x]]]]]]]]]
-9- The derivative of the above expression computed by this formula is (PLUS,(TIMES,ONE,(PLUS,ONE,ZERO),Y),(TIMES,X,(PLUS,ONE,ZERO),Y), (TIMES,X,(PLUS,X,ZERO),ZERO)) 2.7 Labelled Expressions The λ-notation used for naming functions is inadequate for naming recursive functions. For example, if the function named as the second argument of a maplist is to be allowed to be recursive an additional notation is required. We define label[s;e] where s is a symbol and e is an expression to be the same as the exression e except that if s occurs as a sub-expression of e it is understood to refer to the exression e. The symbol s is bound in label [s;e] and has no significance outside this expression. Label acts as a quantifier with respect to its first argument but a quantifier of a different sort from λ. As an example label[subst;λ[[x;y;s];[null[s]⟶⋀;atom[s]⟶ [y=s⟶x;1⟶s];1⟶combine[subst[x;y;first[s]]; subst[x;y;rest[s]]]]]] is a name suitable for inclusion in a maplist of the substitu- tion function mentioned earlier. 2.8 Computable Functions In this section we shall show that all functions compu- table by Turing machine are expressable as S-functions. If, as we contend, S-functions are a more suitable device for developing a theory of computability than Turing machines, the proof in this section is out of place and should be re- placed by a plausibility argument similar to what is called "Turing's thesis" to the effect that S-functions satisfy our intuitive notion of effectively computable functions. The reader unfamiliar with Turing machines should skip this section. Nevertheless, Turing machines are well entrenched at present so we shall content ourselves with showing that any function computable by turing machine is an S-function. This is done as follows: 1. We give a way of describing the instantaneous con- figurations of a Turing machine calculation by an S-expression. This S-expression must describe the turing machine, its
-10- internal state, the tape, and the square on the tape being read. 2. We give an S-function succ whose arguments is an instantaneous configuration and whose value is the immediately succeeding configuration if there is one and otherwise is 0. 3. We construct from succ another S-function, turing, whose arguments are a Turing machine, with a canonical initial state and an initial tape in a standard position and whose value is defined exactly when the corresponding Turing machine calculation terminates and in that case is the final tape. We shall consider Turing machines as given by sets of quintuples. Each quintuple consists of a state, a symbol read, a symbol to be printed, a direction of motion and a new state. The states are represented by a finite set of symbols, the symbols which may occur by another finite set of symbols (it doesn't matter whether these sets overlap) and the two directions by the symbols "L" and "R". A quintuple is then represented by an S-expression (st,sy,nsy,dir,nst). The Turing machine is represented by an S-expression. (ist, blank,quin1,...quink) were ist represents the canonical initial state, blank is the symbol used for a blank square (squares beyond the region explicitly represented in the S-expression for a tape are assumed to be blank and are read that way when reached). As an example, we give the representa- tion of a Turing machine which moves to the right on a tape and computes the parity of the number of 1's on the tape ignoring 0's and stopping when it comes to a blank square: (0,B,(0,0,B,R,0),(0,1,B,R,1),(0,B,0,R,2),(1,0,B,R,1),(1,1,B,R,0), (1,B,1,R,2)) The machine is assumed to stop if there is no quintuple with a given symbol state pair so that the above machine stops as soon as it enters state 2. A Turing machine tape is represented by an S-expression as follows: The symbols on the squares to the right of the scanned square are given in a list v, the symbols to the left of the scanned square in a list u and the scanned symbol as a quantity w. These care combined in a list (w,u,v). This the tape ...bb1101⓪10b... is represented by the expression (0,(1,0,1,b,b),(1,1,0,b))
-11- We adjoin the state to this triplet to make a quadruplet (s,w,u,v) which describes the instantaneous configuration of a machine. The function succ[m;c] whose arguments are a Turing machine m and a configuration c has as value the immediately suc- ceeding configuration of c provided the state-symbol pair is listed among the quintuplets of m and otherwise has value zero. succ is defined with the aid of auxiliary functions. The first of these find[st;sy;qs] given the triplet (nsy;dir;nst) which consists of the last 3 terms of the quintuplet of m which contains (st,sy) as its first two elements. The recursive definition is simplified by defining find [st;sy;qs] where qs=rest[rest[m]] since qs then represents the list of quintuplets of m. We have find[st;sy;qs]=[null[qs]⟶0;first[first[qs]] =st∧first[rest[first[qs]]]=sy⟶rest[rest[first[qs]]];1⟶find [st;sy;rest[qs]]] The new auxiliary function is move[m;nsy;tape;dir] which gives a new tape triplet obtained by writing nsy on the scanned square of tape, and moving in the direction dir. move[m;nsy;tape;dir]=[dir=L⟶combine[[ null[first[rest[tape]]]⟶first[rest[m]];1⟶first[first[rest[tape]]] ];combine[[null[first[rest[tape]]]⟶⋀;1⟶ rest[first[rest[tape]]]];combine[combine[nsy; first[rest[rest[tape]]]];⋀]]];dir=R⟶ combine[[null[first[rest[rest[tape]]]]⟶ first[rest[m]];1⟶first[first[rest[rest[tape]]]]]; combine[combine[nsy;first[rest[tape]]]; combine[[null[first[rest[rest[tape]]]]⟶⋀;1⟶ rest[first[rest[rest[tape]]]]];⋀]]]] The reader should not be alarmed at the monstrous size of the last formula. It rises mainly from the compositions of first and rest required to select the proper elements of the structure representing the tape. Later we shall descrirbe ways of writing such expressions more concisely. We now have succ[m;c]=[find[first[c];first[rest[c]];rest[rest[m]]] =0⟶0;1⟶combine[first[rest[rest[find[ first[c];first[rest[c]];rest[rest[m]]]]]]; move[m;first[find[first[c];first[rest[c]]; rest[rest[m]]]];rest[c];first[rest[find[ first[c];first[rest[c]];rest[rest[m]]]]]]]]
-12- Finally we define turing[m;tape]=tu[m;combine[first[m];tape]] where tu[m;c]=[succ[m;c]=0⟶rest[c];1⟶tu[m;succ[m;c]]] We reiterate that these definitions can be greatly shortened by some devices that will be discussed in the sections on the machines computation of S-functions.
-13- 3. Lisp Self-applied The S-functions have been described by a class of expres- sions which has been informally introduced. Let us call these expressions F-expressions. If we provide a way of translating F-expressions into S-expressions, we can use S-functions to represent certain functions and predicates of S-expressions. First we shall describe this translation. 3.1 Representation of S-functions as S-expressions. The representation is determined by the following rules. 1. Constant S-expressions can occur as parts of the F-expressions representing S-functions. An S-expression ℰ is represented by the S-expression. (QUOTE,ℰ) 2. Variables and function names which were represented by strings of lower case letters are represented by the cor- responding strings of the corresponding upper case letters. Thus we have FIRST, REST and COMBINE, and we shall use X,Y etc. for variables. 3. A form is represented by an S-expression whose first term is the name of the main function and whose remaining terms are the argumetns of the function. Thus combin[first[x]; rest[x]] is represented by (COMBINE,(FIRST,X),(REST,X)) 4. The null S-expression ⋀ is named NIL. 5. The truth values 1 and 0 are denoted by T and F. The conditional expressoin write[p₁⟶e₁,p₂⟶e₂,...pk⟶ek] is repersented by (COND,(p₁,e₁),(p₂,e₂),...(pk,ek)) 6. λ[[x;..;s];ℰ] is represented by (LAMBDA,(X,...,S),ℰ) 7. label[α;ℰ] is represented by (LABEL,α,ℰ) 8. x=y is represented by (EQ,X,Y) With these conventions the substitution function mentioned earlier whose F-expression is label[subst;λ[[x;y;s];[null[s]⟶⋀;atom[s]⟶ [y=s⟶x;1⟶s];1⟶combine[subst[x;y;first[s]]; subst[x;y;rest[s]]]]]] is represented by the S-expression. (LABEL,SUBST,(LAMBDA,(X,Y,Z),(COND,((NULL, Z),NIL),((ATOM,Z),(COND)((EQ,Y,Z),X),(1,Z))), (1,(COMBINE,(SUBST,X,Y,(FIRST,Z)), (SUBST,X,Y,(REST,Z))))))
-14- This notation is rather formidable for a human to read, and when we come to the computer form of the system we will see how it can be made easier by adding some features to the read and print routines without changing the internal compu- tation processes. 3.2. A Function of S-expressions which is not an S-function. It was mentioned in section 2.5 that an S-function is not defined for values of its arguments for which the process of evaluation does not terminate. It is easy to give examples of S-functions which are defined for all arguments, or examples which are defined for no arguments, or examples which are defined for some arguments. It would be nicie to be able to determine whether a given S-function is defined for given arguments. Consider, then, the function def[f;s] whose value is 1 if the S-function whose corresponding S-expression is f is defined for the list of arguments s and is zero otherwise. We assert that def[f,s] is not an S-function. (If we assume Turing machine theory this is an obvious consequence of the results of section 2.8, but in support of the contentions that S-functions are a good vehicule for expounding the theory of recursive functions we give a separate proof). Theorem: def[f;s] is not an S-function. Proof: Suppose the contrary. Consider the function g=λ[[f];[∼def[f;f]⟶1;1⟶first[⋀]]] If def were an S-function g would also be an S-function. For any S-function u with S-expression u' g[u'] is 1 if u[u'] undefined and is undefined otherwise. Consider now g[g'] where g' is an S-expression for g. Assume first that g[g'] were defined. This is precisely the condi- tion that g' be the kind of S-expression for which g is undefined. Contrawise, were g[g'] undefined g' would be the kind of S-expression for which g is defined. Thus our assumption that def[f;s] is an S-function leads to a contradiction. The proof is the same as the corresponding proof in Turing machine theory. The simplicity of the rules by which S-functions are represented as S-expressions makes the develop- ment from scratch simplier, however.
-15- 3.3 The Universal S-Function, Apply There is an S-function apply such that if f is an S-expression for an S-function φ and args is a list of the form (arg1,...,arg n) where arg1,---,arg n are arbitrary S-expressions then apply[f,args] and φ[arg1;...;argn] are defined for the same values of arg1,...arg n and are equal when defined. apply is defined by apply[f;args]=eval[combine[f;args]] eval is defined by eval[e]=[ first[e]=NULL⟶[null[eval[first[rest[e]]]]⟶T;1⟶F] first[e]=ATOM⟶[atom[eval[first[rest[e]]]]⟶T;1⟶F] first[e]=EQ⟶eval[first[rest[e]]]=eval[first[rest[rest[e]]]]⟶T; 1⟶F] first[e]=QUOTE⟶first[rest[e]]; first[e]=FIRST⟶first[eval[first[rest[e]]]]; first[e]=REST⟶rest[eval[first[rest[e]]]]; first[e]=COMBINE⟶combine[eval[first[rest[e]]];eval[first[rest[rest [e]]]]]; first[e]=COND⟶evcon[rest[e]]; first[first[e]]=LAMBDA⟶evlam[first[rest[first[e]]];first[rest[rest [first[e]]]];rest[e]]; first[first[e]]=LABEL⟶eval[combine[subst[first[e];first[rest [first[e]]];first[rest[rest[first[e]]]]];rest[e]]]] where: evcon[c]=[eval[first[first[c]]]=1⟶eval[first[rest[first[c]]]]; T⟶evcon[rest[c]]] and evlam[vars;exp;args]=[null[vars]⟶eval[exp];1⟶evlam[ rest[vars];subst[first[args];first[vars];exp];rest[args]]] The proof of the above assertion is by induction on the subexpressions of e. The process described by the above functions is exactly the process used in the hand-worked examples of section 2.5.
-16- 4. Variants of Lisp There are a number of ways of defining 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 definitions, but the class of expressions corresponding to S-expressions differs and sod o the precise definitions of the functions. We shall describe two fo these variants. 4.1 Linear Lisp The L-expressions are defined as follows: 1. A finite list of characters is admited. 2. Any string of admited characters in an L-expres- sion. This includes the null string denoted by ⋀ There are three functions of strings 1. first[x] is the first character of the string x. first[⋀] is undefined. For example, first [ABC]=A. 2. rest[x] is the string of characters remaining when the first character of the string is deleted. rest[⋀] is undefined. For example, rest[ABC]=BC 3. combine[x;y] is the string formed by prefixing the character x to the string y. For example, combine[A;BC]=ABC There are three predicates on strings 1. char[x], x is a single character 2. null[x], x is the null string 3. x=y, defined for x and y characters. The advantage of linear Lisp is that no cahracters are given special roles as are parentheses and comma in Lisp. This permits computations with any notation which can be written linearly. The disadvantage of linear Lisp is that the extraction of sub-expressions is a fairly involed rather than an elementary operation. It is not hard to write in linear lisp functions corresponding to the basic functions of Lisp so that mathematically linear Lisp includes Lisp. This turns otu to be the most convenient way of programming more complicated manipulations. However, it tunrs out that if the functions are to be represented by computer routines Lisp is essentially faster.
-17- 4.2 Binary Lisp The unsymmetrical status of first and rest may be a source of uneasiness. If we admit only two element lists then we can define first[(e₁,e₂)]=e₁ rest[(e₁,e₂)]=e₂ combine[e₁;e₂]=(e₁,e₂) We need only two predicates, equality for symbols and atom. The null list can be dispensed with. This system is easier until we try to represent functions by expressions which is, after all, the principal application; moreover, in order to apply the system to itself we need to be abel to write functions.