perm filename CH4[206,LSP] blob sn#237890 filedate 1976-09-17 generic text, type C, neo UTF8

COMMENT ⊗ VALID 00003 PAGES C REC PAGE DESCRIPTION C00001 00001 C00002 00002 .device xgp C00004 00003 .sec COMPUTABILITY C00034 ENDMK C⊗; .device xgp .EVENLEFTBORDER←ODDLEFTBORDER←1000 .require "pubmac[206, NXL]" source_file .standard front(I, 1) .font 1 "basl30" <<text>> .font 2 "bdr30" <<sym>> .font 3 "basi30" <<var>> .font 4 "basb30" <<bold>> .font 5 "bdr30" <<const>> .font 6 "sub" .font 7 "sup" .font A "fix40" .font B "fix30" .PAGE FRAME 52 HIGH 90 WIDE; .AREA TEXT LINES 4 TO 50 CHARS 1 TO 83; .TITLE AREA HEADING LINES 1 TO 3 CHARS 1 TO 83; .TITLE AREA FOOTING LINE 51 CHARS 1 TO 83; .PLACE TEXT; .turn on "%#π" ; .every heading(, {SECNAME}, {page}) ; .<<EVERY FOOTING(, {SECTION!}.{SUBSECTION!}, )>> .AT 8 ⊂"%1 %*"⊃ ; .AT 16 ⊂"%1 %*"⊃ ; .COUNT ITEM .COUNT SUBITEM IN ITEM .AT "#" ⊂NEXT ITEM;(ITEM!);⊃; .AT "&" ⊂NEXT SUBITEM;ONCE INDENT 10;(ITEM!&"."&SUBITEM!);⊃; .NEXT SECTION .NEXT SECTION .NEXT SECTION .sec COMPUTABILITY .ss The function %3eval%1. 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 %3eval%1 is a universal LISP function in the sense that any computation done by any LISP function can be done by %3eval%1 when %3eval%1 is given suitable arguments. %3eval%1 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 %3eval%1, and we can start our computations with the second argument NIL. To illustrate this, suppose we want to apply the function %3alt%1 to the list (A B C D E), i.e. we wish to evaluate %3alt%2[%5(A B C D E)%2]%1. This can be obtained by computing .NOFILL %3eval%2[%5((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%2]%1, .FILL and gives the expected result (A C E). The second argument of %3eval%1, 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 %3eval%2[%5(CAR X), ((X.(B.C)) (Y.A) (X.B))%2] = %5B%1, i.e. we have evaluated %4a %3x%1 with %3 x%2 = %5(B.C)%1. The value associated with a variable in such a list of pairs is computed by the auxiliary function %3assoc%1 which has the recursive definition %3assoc%2[%3v, a%2] ← %4if n %3a %4then %5NIL %4else if aa %3a %4 eq %3v %4then a %3a %4else %3alt%2[%3v, %4d %3a%2]%1. .BEGIN PREFACE 0 NOFILL Thus we have %3assoc%2[%5X, ((X.(B.C)) (Y.A) (X.B))%2] = %5(X.(B.C))%1. A simplified version of the usual LISP %3eval%1 is the following: %3eval%2[%3e, a%2] ← .FILL %4if at %3e %4then %2[%4if %3numberp %3e %2∨ %3e %4eq %5NIL %2∨ %3e %4eq %5T %4then %3e %4else%3 assoc%2[%3e, a%2]] .NOFILL %4else if at a%3 e %4then %2[%4if a %3e%4 eq %5CAR %4then a %3eval%2[%4ad %3e, a%2] %4else if a %3e%4 eq %5CDR %4then d %3eval%2[%4ad %3e, a%2] .FILL %4else if a %3e%4 eq %5CONS %4then %3eval%2[%4ad %3e, a%2] . %3eval%2[%4add %3e, a%2] .NOFILL %4else if a %3e%4 eq %5ATOM %4then at %3eval%2[%4ad %3e, a%2] .FILL %4else if a %3e%4 eq %5EQ %4then at %3eval%2[%4ad %3e, a%2] %4eq %3eval%2[%4add %3e, a%2] .NOFILL %4else if a %3e%4 eq %5QUOTE %4then ad %3e %4else if a %3e%4 eq %5COND %4then %3evcon%2[%4d %3e, a%2] .FILL %4else if a %3e%4 eq %5LIST %4then %3mapcar%2[%4d %3e, λ%3x%2: %3eval%2[%3x, a%2]] .NOFILL %4else %3eval%2[%4d %3assoc%2[%4a %3e, a%2] . %4d %3e, a%2]] .FILL %4else if aa %3e %4eq %5LAMBDA %4then %3eval%2[%4adda %3e, prup%2[%4ada %3e, mapcar%2[%4d %3e, %2λ%3x%2: %3eval%2[%3x, a%2]]] * %3a%2] .BREAK %4else if aa %3e %4eq %5LABEL %4then %3eval%2[%4adda %3e . %4d %3e, %2[%4ada %3e . %4a %3e%2] . %3a%2]%1, .NOFILL where the auxiliary function %3evcon%1 is defined by .FILL %3evcon%2[%3u, a%2] ← %4if %3eval%2[%4aa %3u, a%2] %4then %3eval%2[%4ada %3u, a%2] %4else %3evcon%2[%4d %3u, a%2]%1, .END and the auxiliary function %3prup%1 used for pairing up the elements of two lists of equal length is defined by .BEGIN PREFACE 0 NOFILL .FILL %3prup%2[%3u, v%2] ← %4if n %3u %4then %5NIL %4else %2[%4a %3u . %4a %3v%2] . %3prup%2[%4d %3u, %4d %3u%2].%1 .NOFILL .END The way %3eval%1 works should be clear; atoms are either immediately evaluable or have to be looked up on the list %3a%1; expressions whose first term is one of the elementary functions are evaluated by performing the indicated operation on the result of evaluating the arguments; %3list%1 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 %3a%1 and substituted for their names; when a function is specified by a λ, the inner expression is evaluated with a new %3a%1 which is obtained by evaluating the arguments and pairing them up with the variables and putting them on the front of the old %3a%1; and finally, %4label%1 is handled by pairing the name of the function with the expression on %3a%1 and replacing the whole function by the λ-part. %3eval%1 plays both a theoretical and a practical role in LISP. Historically, the list notation for LISP functions and %3eval%1 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 %3eval%1 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 %3eval%1 has remained a feature of most LISP systems. The way %3eval%1 handles arguments corresponds to the call-by-value method of parameter passing in ALGOL and similar languages. There is also a form of %3eval%1 that corresponds to call-by-name. Here it is: .BEGIN PREFACE 0 NOFILL %3neval%2[%3e, a%2] ← %4if at %3e%4 then %2[%4if %3e %4eq %5T %4 then %5T %4else if %3e %4eq %5NIL %4then %5NIL %4else if %3numberp e %4then %3e %4else %3neval%2[%4ad %3assoc%2[%3e, a%2], %4dd %3 assoc%2[%3e, a%2]]] %4else if at a %3e %4 then %2[%4if a %3e %4eq %5CAR %4then a %3neval%2[%4ad %3e, a%2] %4else if a %3e %4eq %5CDR %4then d %3neval%2[%4ad %3e, a%2] .FILL %4else if a %3e %4eq %5CONS %4then %3neval%2[%4ad %3e, a%2] . neval%2[%4add %3e, a%2] .NOFILL %4else if a %3e %4eq %5ATOM %4then at %3neval%2[%4ad %3e, a%2] .FILL %4else if a %3e %4eq %5EQ %4then %3neval%2[%4ad %3e, a%2] %4eq %3neval%2[%4add %3e, a%2] .NOFILL %4else if a %3e %4eq %5QUOTE %4then ad %3e %4else if a %3e %4eq %5COND %4then %3nevcon%2[%4d %3e, a%2] .FILL %4else if a %3e %4eq %5LIST %4then %3mapcar%2[%4d %3e %2, λ%3x%2: %3neval%2[%3x, a%2]] .NOFILL %4else %3neval%2[%4d %3assoc%2[%4a %3e, a%2] . %4d %3e, a%2]] .FILL %4else if aa %3e %4eq %5LAMBDA %4then %3neval%2[%4adda %3e, nprup%2[%4ada %3e, %4d %3e%2, %3a%2]] .NOFILL .FILL %4else if aa %3e %4eq %5LABEL %4then %3neval%2[%4adda %3e . %4d %3e, %2[%4ada %3e . %4a %3e%2] . %3a%2], %1 .NOFILL where the auxiliary function %3nevcon%1 is given by .FILL %3nevcon%2[%3u, a%2] ← %4if %3neval%2[%4aa %3u, %3a%2] %4then %3neval%2[%4ada %3u, %3a%2] %4else %3nevcon%2[%4d %3u, %3a%2].%1 and nprup is .FILL %3nprup%2[%3u, v%2] ← %4if n %3u %4then %3a %4else %2[%4a %3u . %2[%4a %3v . a%2]] . %3prup%2[%4d %3u, %4d %3u%2].%1 .END The difference between %3eval%1 and %3neval%1 is only in two terms. %3eval%1 evaluates a variable by looking it up on the association list whereas %3neval%1 looks it up on the association list and evaluates the result in the context in which it was put on the association list. Correspondingly, when a λ-expression is encountered, %3eval%1 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 %3neval%1 pairs the arguments themselves with the variables and puts them on the front of the association list. The function neval also saves the current association list with each variable on the association list, so that the variables can be evaluated in the correct context. In most cases both give the same result with the same work, but %3neval%1 gives a result in some cases in which %3eval%1 loops. An example is obtained by evaluating %3F%2[2, 1]%1 where %3F%1 is defined by .NOFILL %3F%2[%3x, y%2] ← %4if%3 x%2=0 %4then %20 %4else %3F%2[%3x%2-1, %3F%2[%3y%2-2, %3x%2]].%1 Exercises .FILL 1. Write %3neval%1 and the necessary auxiliary functions in list form, and try them out on some examples. .ss Computability.%1 Some LISP calculations run on indefinitely. The most trivial case occurs if we make the recursive definition %3loop x %2← %3loop x%1 and attempt to compute %3loop%2[%3x%2]%1 for any %3x%1 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 %3f%1 is a LISP function and %3a%1 is an S-expression, and we would like to know whether the computation of %3f%2[%3a%2]%1 terminates. Suppose %3f%1 is represented by the S-expression %3f*%1 in the usual S-expression notation for LISP functions. Then the S-expression %5(f* (QUOTE a))%1 represents %3f%2[%3a%2]%1. Define the function %3term%1 by giving %3term%2[%3e%2]%1 the value %4true%3 if %3e%1 is an S-expression of the form %5(f* (QUOTE a))%1 for which %3f%2[%3a%2]%1 terminates and %4false%1 otherwise. We now ask whether %3term%1 is a LISP function, i.e. can it be constructed from %3car, cdr, cons, atom, %1 and %3eq%1 using λ, %4label%1, and conditional expressions? Well, it can't, as we shall shortly prove, and this means that it is not %3computable%1 whether a LISP calculation terminates, since if %3term%1 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 %3terma%1 defined from %3term%1 by %3terma u %2← %4if%3 term list%2[%3u, list%2[%5QUOTE%3, u%2]] %4then%3 loop u %4else true%1, and suppose that %3f%1 is a LISP function and that %3f*%1 is its S-expression representation. What is %3terma f*%1? Well %3terma f*%1 tells us whether the computation of %3f%2[%3f*%2]%1 terminates, and it tells us this by going into a loop if %3f%2[%3f*%2]%1 terminates and giving %4true%1 otherwise. Now if %3term%1 were a LISP function, then %3terma%1 would also be a LISP function. Indeed if %3term%1 were represented by the S-expression %3term*%1, then %3terma%1 would be represented by the S-expression %3terma* %5= (LAMBDA (U) (COND ((%3term*%5 (LIST U (LIST (QUOTE QUOTE) U))) (LOOP U)) (T T))). Now consider %3terma%2[%3terma*%2]%1. According to the definition of %3terma%1, this will tell us whether %3terma%2[%3terma*%2]%1 is defined, i.e. it tells about itself. However, it gives this answer in a contradictory way; namely %3terma%2[%3terma*%2]%1 looping tells us that %3terma%2[%3terma*%2]%1 terminates, and %3terma%2[%3terma*%2]%1 being %4true%1 tells us that %3terma%2[%3terma*%2]%1 doesn't terminate. This contradiction tells us that %3term%1 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 %3t%1 that sometimes says calculations terminate, sometimes says they don't terminate, and sometimes runs on indefinitely. We shall further assume that when %3t%1 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 %3t%2[%3e%2]%1 with a computation of %3eval%2[%3e, %5NIL%2]%1 doing the computations alternately. If the %3eval%2[%3e, %5NIL%2]%1 computation ever terminates, then the new function asserts termination. Given such a %3t%1, we can always find a calculation that does not terminate but %3t%1 doesn't say so. The construction is just like that used in the previous proof. Given %3t%1, we construct %3ta u %2← %4if%3 t list%2[%3u, list%2[%5QUOTE%3, u%2]] %4then%3 loop u %4else true%1, and then we consider %3ta%2[%3ta*%2]%1. If this had the value %4true%1, then it wouldn't terminate so therefore it doesn't terminate but is not one of those expressions which %3t%1 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 %3t%61%2[%3e%2] ← %4if%3 e %2= %3ta* %4then %5DOESN'T-TERMINATE %4else%3 t%2[%3e%2]%1. Of course, %3t%61%1 isn't much better than %3t%1, since it can decide only one more computation, but we can form %3t%62%1 by applying the same process, and so forth. In fact, we can even form %3t%6∞%1 which decides all the cases decided by any %3t%6n%1. 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. .ITEM←0; #. Write a function that gives %3t%6n+1%1 in terms of %3t%6n%1. #. Write a function that gives %3t%6∞%1 in terms of %3t%1. #. If you know about Turing machines, write a LISP function to simulate an arbitrary Turing machine given a description of the machine in some convenient notation. #. Write a LISP function that will translate a Turing machine description into a LISP function that will do the same computation. #. If you really like Turing machines, write a description of a Turing machine that will interpret LISP internal notation.