perm filename CH4[206,LMM] blob sn#094127 filedate 1974-04-05 generic text, type C, neo UTF8

COMMENT ⊗ VALID 00002 PAGES C REC PAGE DESCRIPTION C00001 00001 C00002 00002 \\M0BDR25\M1BDJ25\M2BDR25X\M3SUB\M4NGR30\M5NGR40\F0 C00031 ENDMK C⊗; \\M0BDR25;\M1BDJ25;\M2BDR25X;\M3SUB;\M4NGR30;\M5NGR40;\F0 (This version of this chapter is very incomplete and preliminary.) \F5\CCHAPTER IV \CLISP SELF-APPLIED \F41. The list representation of LISP functions.\F0 \J When one computes with symbolic expressions, it is necessary to face the fact that the most convenient notation for reading and writing is not the most convenient notation for symbolic data from the point of view of the programmer who must write programs for manipulating the data. So far, we have resolved this dilemma by using S-expressions for data and writing LISP functions and programs in a language that is hopefully convenient for reading and writing. Now LISP programs are also symbolic information, and we want to be able to manipulate LISP programs with LISP functions and programs. In order to do this we use a representation of LISP functions by LISP lists. In Chapter 6, we shall discuss procedures for translating between S-expression notation and other notations for symbolic information. We use the following conventions: 1. Variables are represented by atomic symbols composed of upper case letters. Thus the variable \F1x\F0 will normally be represented by the corresponding upper case letter X. 2. An S-expression \F1e\F0 will be represented as (QUOTE \F1e\F0). Thus the atom X is represented by (QUOTE X). 3. The basic LISP functions \F1car, cdr, cons, atom\F0 and \F1eq\F0, the functions \F1list\F0 and \F1null\F0 derived from them are represented by writing the words in upper case. Thus we have CAR, CDR, CONS, ATOM, EQ, LIST, and NULL. Defined functions are also represented by atoms, e.g. ALT, DIFF, etc. 4. Numbers are represented by the S-expression notation for numbers without QUOTE, and the special atoms T and NIL are represented by themselves without QUOTE. Avoiding QUOTE here is for convenience and can be regarded as using variables T and NIL whose permanent values are the S-expressions T and NIL. 5. The application of a function to arguments is represented by a list the first element of which is the function name and the remaining elements are the arguments in the same order. Thus \F1f[x, y]\F0 is represented by (F X Y).\. 6. The conditional expression \F2if\F1 p\F31\F2 then \F1e\F31\F1 ... \F2\; else if \F1p\F3n\F2 then \F1e\F3n\F0 is represented by (COND (\F1p\F31\F1 e\F31\F1) ... (\F1p\F3n\F1 e\F3n\F0)). There is no way of representing a final \F2else\F0, so \F2if\F1 p \F2then\F1 a \F2else \F1b\F0 is represented by (COND (\F1p a)(\F0T \F1b\F0)). Thus \F2if n \F1u ∨ \F2n d \F1u \F2then\F1 u \F2else a\; \F1u . \F1alt \F2dd \F1u\F0 is represented by (COND ((OR (NULL U) (NULL (CDR U))) U) (T (CONS (CAR U) (ALT (CDDR U))))). \J 7. The λ-expression λ\F1x...z: \F0 is represented by (LAMBDA (X ... Z) \F1e\F0). Thus\. λ\F1x y: \F2if n \F1x \F2 then \F1y \; \F2else a \F1x . append[\F2d \F1x, y]\F0 is represented by (LAMBDA (X Y) (COND ((NULL X) Y) (T (CONS (CAR X) (APPEND (CDR X) Y)))))). \J 8. Finally, \F2label\F1[fname, e]\F0 is represented by (LABEL \F1fname e), so that\. \F2label\F1[alt, \F0λ\F1x: \F2if n \F1x ∨ \F2n d \F1x \F2then \F1x\; \F2else a \F1x . alt[\F2dd\F1 x]]\F0 is represented by (LABEL ALT (LAMBDA (X) (COND ((OR (NULL X) (NULL (CDR X))) X) (T (CONS (CAR X) (ALT (CDDR X))))))). \J Actually, \F2label\F0 is rarely used in LISP programming, because it names a function for immediate use only, and usually one wants to attach a function definition to its name for later use in several places in the program. The notation for making definitions varies with the implementation of LISP. \F42. The function \F1eval\F0. Except for speed and memory size all present day stored program computers are equivalent in what computations they can do. A program written for one computer can be translated to run on another. Indeed, one can write a simulator for one computer to run on another. To put it in commercial terms, no computer manufacturer can advertise that his machine can do calculations impossible on the machine made by his competitors. This is well known intuitively, and the first mathematical theorem of this kind was proved by A.M. Turing (1936), who defined a primitive kind of computer now called a Turing machine, and showed how to make a universal machine that could do any computation done by any Turing machine when given a description of the machine to be simulated and the initial tape of the computation to be imitated. In LISP the function \F1eval\F0 is a universal LISP function in the sense that any computation done by any LISP function can be done by \F1eval\F0 when \F1eval\F0 is given suitable arguments. \F1eval\F0 has two arguments the first of which is a LISP expression in the notation given in the previous section, while the second is a list of pairs that give the values of any free variables that may occur in the expression. Since any computation can be described as evaluating an expression without free variables, the second argument plays a role mainly in the recursive definition of \F1eval\F0, and we can start our computations with the second argument NIL. To illustrate this, suppose we want to apply the function \F1alt\F0 to the list (A B C D E), i.e. we wish to evaluate \F1alt\F0[(A B C D E)]. This can be obtained by computing \F1eval\F0[((LABEL ALT (LAMBDA (X) (COND ((OR (NULL X) (NULL (CDR X))) X) (T (CONS (CAR X) (ALT (CDDR X))))))) (QUOTE (A B C D E)), NIL], and gives the expected result (A C E). The second argument of \F1eval\F0, taken as NIL in the above example is a list of dotted pairs where the first element of each pair is an atom representing a variable and the second element is the value assigned to that variable. A variable may occur more than once in the list and the value chosen is that paired with the first occurrence of the variable. We illustrate this by the equation \F1eval\F0[(CAR X), ((X.(B.C)) (Y.A) (X.B))] = B, i.e. we have evaluated \F2a \F1x\F0 with \F1 x\F0 = (B.C). The value associated with a variable in such a list of pairs is computed by the auxiliary function \F1assoc\F0 which has the recursive definition\. \F1assoc[v, a] ← \F2if n \F1a \F2then \F0NIL \F2else if aa \F1a\; \F2 eq \F1v \F2then a \F1a \F2else \F1alt[v, \F2d \F1a]\F0. Thus we have \F1assoc\F0[X, ((X.(B.C)) (Y.A) (X.B))] = (X.(B.C)). A simplified version of the usual LISP \F1eval\F0 is the following: \F1eval[e, a] ← \F2if at \F1e \F2then \F0[\F2if numberp \F1e ∨ e\; \F2eq \F0NIL ∨ \F1e \F2eq \F0T \F2then \F1e \F2else\F1 assoc[e, a]] \F2else if at a\F1 e \F2then \F1[\F2if a \F1e\F2 eq \F0CAR \F2then a \F1eval[\F2ad \F1e, a] \F2else if a \F1e\F2 eq \F0CDR \F2then d \F1eval[\F2ad \F1e, a] \F2else if a \F1e\F2 eq \F0CONS \F2then \F1eval[\F2ad \F1e, a]\; . eval[\F2add \F1e, a] \F2else if a \F1e\F2 eq \F0ATOM \F2then at \F1eval[\F2ad \F1e, a] \F2else if a \F1e\F2 eq \F0EQ \F2then at \F1eval[\F2ad \F1e, a]\; \F2eq \F1eval[\F2add \F1e, a] \F2else if a \F1e\F2 eq \F0QUOTE \F2then ad \F1e \F2else if a \F1e\F2 eq \F0COND \F2then \F1evcon[\F2d \F1e, a] \F2else if a \F1e\F2 eq \F0LIST \F2then \F1mapcar[\F2d \F1e, \; λx: eval[x, a]] \F2else \F1eval[\F2d \F1assoc[\F2a \F1e, a] . \F2d \F1e, a]] \F2else if aa \F1e \F2eq \F0LAMBDA \F2then\; \F1eval[\F2adda \F1e, prup[\F2ada \F1e, mapcar[\F2d \F1e, λx: eval[x, a]]] . a] \F2else if aa \F1e \F2eq \F0LABEL \F2then\; \F1eval[\F2adda \F1e . \F2d \F1e, [\F2ada \F1e . \F2a \F1e] . a]\F0, where the auxiliary function \F1evcon\F0 is defined by \F1evcon[u, a] ← \F2if \F1eval[\F2aa \F1u, a] \F2then \F1eval[\F2ada \F1u, a]\; \F2else \F1evcon[\F2d \F1u, a]\F0, \Jand the auxiliary function \F1prup\F0 used for pairing up the elements of two lists of equal length is defined by\. \F1prup[u, v] ← \F2if n \F1u \F2then \F0NIL \F2else \F1[\F2a \F1u\; . \F2a \F1v] . prup[\F2d \F1u, \F2d \F1u].\F0 \J The way \F1eval\F0 works should be clear; atoms are either immediately evaluable or have to be looked up on the list \F1a\F0; expressions whose first term is one of the elementary functions are evaluated by performing the indicated operation on the result of evaluating the arguments; \F1list\F0 has to be handled specially, because it has an indefinite number of arguments; conditionals are handled by an auxiliary function that evaluates the terms in the right order; quoted S-expressions are trivial; non-elementary functions have their definitions looked up on \F1a\F0 and substituted for their names; when a function is specified by a λ, the inner expression is evaluated with a new \F1a\F0 which is obtained by evaluating the arguments and pairing them up with the variables and putting them on the front of the old \F1a\F0; and finally, \F2label\F0 is handled by pairing the name of the function with the expression on \F1a\F0 and replacing the whole function by the λ-part. \F1eval\F0 plays both a theoretical and a practical role in LISP. Historically, the list notation for LISP functions and \F1eval\F0 were first devised in order to show how easy it is to define a universal function in LISP - the idea was to advocate LISP as an alternative to Turing machines for doing the elementary theory of computability. The notation used was chosen without much regard for human convenience, because the original idea was purely theoretical; the notation for conditional expressions, for example, has an unnecessary extra level of parentheses. However, S. R. Russell noted that \F1eval\F0 could serve as an interpreter for LISP and promptly programmed it in machine language with minor modifications for practical purposes. Since a compiler was long delayed, the interpreter was more easily modified and handled some difficult cases with functional arguments better, an interpreter based on \F1eval\F0 has remained a feature of most LISP systems. The way \F1eval\F0 handles arguments corresponds to the call-by-value method of parameter passing in ALGOL and similar languages. There is also a form of \F1eval\F0 that corresponds to call-by-name. Here it is:\. \F1neval[e, a] ← \F2if at \F1e\F2 then \F1[\F2if \F1e \F2eq \F0T \F2 then \F0T \F2else if \F1e \F2eq \F0NIL \F2then \F0NIL \F2else if \F1numberp e \F2then \F1e \F2else \F1neval[\F2d \F1assoc[e, a], a]] \F2else if at a \F1e \F2 then \F1[\F2if a \F1e \F2eq \F0CAR \F2then a \F1neval[\F2ad \F1e, a] \F2else if a \F1e \F2eq \F0CDR \F2then d \F1neval[\F2ad \F1e, a] \F2else if a \F1e \F2eq \F0CONS \F2then \F1neval[\F2ad \F1e, a]\; . neval[\F2add \F1e, a] \F2else if a \F1e \F2eq \F0ATOM \F2then at \F1neval[\F2ad \F1e, a] \F2else if a \F1e \F2eq \F0EQ \F2then \F1neval[\F2ad \F1e, a]\; \F2eq \F1neval[\F2add \F1e, a] \F2else if a \F1e \F2eq \F0QUOTE \F2then ad \F1e \F2else if a \F1e \F2eq \F0COND \F2then \F1nevcon[\F2d \F1e, a] \F2else if a \F1e \F2eq \F0LIST \F2then \F1mapcar[\F2d \F1e\; , λx: neval[x, a]] \F2else \F1neval[\F2d \F1assoc[\F2a \F1e, a] . \F2d \F1e, a]] \F2else if aa \F1e \F2eq \F0LAMBDA \F2then \F1neval[\F2adda \F1e, \; prup[\F2ada \F1e, \F2d \F1e] . a] \F2else if aa \F1e \F2eq \F0LABEL \F2then \F1neval[\F2adda \F1e\; . \F2d \F1e, [\F2ada \F1e . \F2a \F1e] . a], \F0 where the auxiliary function \F1nevcon\F0 is given by \F1nevcon[u, a] ← \F2if \F1neval[\F2aa \F1u, a] \F2then\; \F1neval[\F2ada \F1u, a] \F2else \F1nevcon[\F2d \F1u, a].\F0 \J The difference between \F1eval\F0 and \F1neval\F0 is only in two terms. \F1eval\F0 evaluates a variable by looking it up on the association list whereas \F1neval\F0 looks it up on the association list and evaluates the result. Correspondingly, when a λ-expression is encountered, \F1eval\F0 forms a new association list by pairing the values of the arguments with the variables bound by the λ and putting the new pairs in front of the old association list, whereas \F1neval\F0 pairs the arguments themselves with the variables and puts them on the front of the association list. In most cases both give the same result with the same work, but \F1neval\F0 gives a result in some cases in which \F1eval\F0 loops. An example is obtained by evaluating \F1F[2, 1]\F0 where \F1F\F0 is defined by\. \F1F[x, y] ← \F2if\F1 x=0 \F2then \F10 \F2else \F1F[x-1, F[y-2, x]].\F0 Exercises \J 1. Write \F1neval\F0 and the necessary auxiliary functions in list form, and try them out on some examples. \F43. Computability.\F0 Some LISP calculations run on indefinitely. The most trivial case occurs if we make the recursive definition\. \F1loop x ← loop x\F0 \Jand attempt to compute \F1loop[x]\F0 for any \F1x\F0 whatsoever. Don't dismiss this example just because no-one would write such an obviously useless function definition. There is a sense in which it is the "zero" of a large class of non¬terminating function definitions, and, as the Romans experienced but never learned, leaving zero out of the number system is a mistake. Nevertheless, in most programming, non-terminating calculations are the results of errors in defining functions. Therefore, it would be useful to be able to tell whether a function definition gives a result for all arguments. In fact, it would be useful to be able to tell whether a function will terminate for a single argument. Let us make this goal more precise. Suppose that \F1f\F0 is a LISP function and \F1a\F0 is an S-expression, and we would like to know whether the computation of \F1f[a]\F0 terminates. Suppose \F1f\F0 is represented by the S-expression \F1f*\F0 in the usual S-expression notation for LISP functions. Then the S-expression \F1(f* (QUOTE a))\F0 represents \F1f[a]\F0. Define the function \F1term\F0 by giving \F1term[e]\F0 the value \F2true\F1 if \F1e\F0 is an S-expression of the form \F1(f* (QUOTE a))\F0 for which \F1f[a]\F0 terminates and \F2false\F0 otherwise. We now ask whether \F1term\F0 is a LISP function, i.e. can it be constructed from \F1car, cdr, cons, atom, \F0 and \F1eq\F0 using λ, \F2label\F0, and conditional expressions? Well, it can't, as we shall shortly prove, and this means that it is not \F1computable\F0 whether a LISP calculation terminates, since if \F1term\F0 were computable by any computer or in any recognized sense, it could be represented as a LISP function. Here is the proof:\. Consider the function \F1terma\F0 defined from \F1term\F0 by \F1terma u ← \F2if\F1 term list[u, list[\F0QUOTE\F1, u]] \F2then\F1 loop u\; \F2else true\F0, \Jand suppose that \F1f\F0 is a LISP function and that \F1f*\F0 is its S-expression representation. What is \F1terma f*\F0? Well \F1terma f*\F0 tells us whether the computation of \F1f[f*]\F0 terminates, and it tells us this by going into a loop if \F1f[f*]\F0 terminates and giving \F2true\F0 otherwise. Now if \F1term\F0 were a LISP function, then \F1terma\F0 would also be a LISP function. Indeed if \F1term\F0 were represented by the S-expression \F1term*\F0, then \F1terma\F0 would be represented by the S-expression\. \F1terma\F0* = (LAMBDA (U) (COND ((\F1term*\F0 (LIST U \; (LIST (QUOTE QUOTE) U))) (LOOP U)) (T T))). \JNow consider \F1terma[terma*]\F0. According to the definition of \F1terma\F0, this will tell us whether \F1terma[terma*]\F0 is defined, i.e. it tells about itself. However, it gives this answer in a contradictory way; namely \F1terma[terma*]\F0 looping tells us that \F1terma[terma*]\F0 terminates, and \F1terma[terma*]\F0 being \F2true\F1 tells us that \F1terma[terma*]\F0 doesn't terminate. This contradiction tells us that \F1term\F0 is not a LISP function, and there is no general procedure for telling whether a LISP calculation terminates. The above result does not exclude LISP functions that tell whether LISP calculations terminate. It just excludes perfect ones. Suppose we have a function \F1t\F0 that sometimes says calculations terminate, sometimes says they don't terminate, and sometimes runs on indefinitely. We shall further assume that when \F1t\F0 gives an answer it is always right. Given such a function we can improve it a bit so that it will always give the right answer when the calculation it is asked about terminates. This is done by mixing the computation of \F1t[e]\F0 with a computation of \F1eval[e, \F0NIL] doing the computations alternately. If the \F1eval[e, \F0NIL] computation ever terminates, then the new function asserts termination. Given such a \F1t\F0, we can always find a calculation that does not terminate but \F1t\F0 doesn't say so. The construction is just like that used in the previous proof. Given \F1t\F0, we construct\. \F1ta u ← \F2if\F1 t list[u, list[\F0QUOTE\F1, u]] \F2then\F1 loop u\; \F2else true\F0, \Jand then we consider \F1ta[ta*]\F0. If this had the value \F2true\F0, then it wouldn't terminate so therefore it doesn't terminate but is not one of those expressions which \F1t\F0 decides. Thus for any partial decider we can find a LISP calculation which doesn't terminate but which the decider doesn't decide. This can in turn be used to get a slightly better decider, namely\. \F1t\F31\F1[e] ← \F2if\F1 e = ta* \F2then \F0DOESN'T-TERMINATE\; \F2else\F1 t[e]\F0. \JOf course, \F1t\F31\F0 isn't much better than \F1t\F0, since it can decide only one more computation, but we can form \F1t\F32\F0 by applying the same process, and so forth. In fact, we can even form \F1t\F3∞\F0 which decides all the cases decided by any \F1t\F3n\F0. This can be further improved by the same process, etc. How far can we go? The answer is technical; namely, the improvement process can be carried out any recursive ordinal number of times. Unfortunately, this kind of improvement seems to be superficial, since none of the new computations proved not to terminate are likely to be of practical interest. \. Exercises. 1. Write a function that gives \F1t\F3n+1\F0 in terms of \F1t\F3n\F0. 2. Write a function that gives \F1t\F3∞\F0 in terms of \F1t\F0.