perm filename TEXC.PUB[206,LMM] blob sn#096395 filedate 1974-04-05 generic text, type C, neo UTF8

COMMENT ⊗ VALID 00019 PAGES C REC PAGE DESCRIPTION C00001 00001 C00003 00002 .device xgp C00005 00003 .sec INTRODUCTION TO LISP C00009 00004 .ss Atoms. C00011 00005 .ss List structures. C00015 00006 .ss S-expressions. C00021 00007 .ss The basic functions and predicates of LISP. C00029 00008 .ss Conditional expressions. C00032 00009 .ss Boolean expressions. C00035 00010 .ss Recursive function definitions. C00051 00011 .ss Lambda expressions and functions with functions as arguments. C00060 00012 .ss Label. C00062 00013 .sec HOW TO WRITE RECURSIVE FUNCTION DEFINITIONS C00067 00014 .ss Simple list recursion. C00075 00015 .ss Simple S-expression recursion. C00078 00016 .ss Other structural recursions. C00081 00017 .AT "\J" ⊂FILL⊃ C00096 00018 .ss Game trees. C00108 00019 .STANDARD BACK C00109 ENDMK C⊗; .device xgp .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 53 HIGH 81 WIDE; .AREA TEXT LINES 4 TO 51 CHARS 1 TO 81; .TITLE AREA HEADING LINES 1 TO 3 CHARS 1 TO 81; .TITLE AREA FOOTING LINE 52 CHARS 1 TO 81; .PLACE TEXT; .turn on "%#π" ; .<<TURN ON "@" FOR "∂" ;>> .every heading(, {SECNAME}, {page}) ; .<<EVERY FOOTING(, {SECTION!}.{SUBSECTION!}, )>> .AT 8 ⊂"%1 %*"⊃ ; .AT 16 ⊂"%1 %*"⊃ ; .<<AT "\→" KK "." ; ⊂KK ← CHAR⊃ ;>> .sec INTRODUCTION TO LISP .ss Lists. Symbolic information in LISP is expressed by S-expressions and these are represented in the memory of the computer by list structures. Before giving formal definitions, we shall give some examples. The most common form of S-expression is the list, and here are some lists: .NOFILL The list %5(A B C E) %1has four elements. The list %5(A B (C D) E) %1has four elements one of which is itself a list. The list %5(A) %1has one element. The list %5((A B C D)) %1also has one element which itself is a list. The list %5() %1has no elements; it is also written %5NIL. %1The list %5(PLUS X Y) %1has three elements and may be used to represent the expression %3x%2 + %3y. %1The list %5(PLUS (TIMES X Y) X 3) %1has four elements and may be used to represent the expression %3xy%2 + %3x%2 + %53. %1The list %5(EXIST X (ALL Y (IMPLIES (P X) (P Y)))) %1may be used to represent the logical expression %2(∃%3x%2)(∀%3y%2).%3P%2(%3x%2)⊃%3P%2(%3y%2). %1The list %5(INTEGRAL 0 ∞ (TIMES (EXP (TIMES I X Y)) (F X)) X) %1may be used to represent the expression %Aπ~%3e%7ixy%3f%2(%3x%2)%3dx. %1The list %5((A B) (B A C D) (C B D E) (D B C E) (E C D F) (F E)) %1 .FILL is used to represent the network of Figure 1 according to a scheme whereby there is a sublist for each vertex consisting of the vertex itself followed by the vertices to which it is connected. .GROUP .GROUP SKIP 10 Figure 1 .APART The elements of a list are surrounded by parentheses and separated by spaces. A list may have any number of terms and any of these terms may themselves be lists. In this case, the spaces surrounding a sublist may be omitted, and extra spaces between elements of a list are allowed. Thus the lists %5(A B(C D) E) %1and %5(A B (C D) E) %1are regarded as the same. .ss Atoms. The expressions %5A, B, X, Y, 3, PLUS, %1and %5ALL%1 occurring in the above lists are called atoms. In general, an atom is expressed by a sequence of capital letters, digits, and special characters with certain exclusions. The exclusions are <space>, <carriage return>, and the other non-printing characters, and also the parentheses, brackets, semi-colon, and comma. Numbers are expressed as signed decimal or octal numbers, the exact convention depending on the implementation. Floating point numbers are written with decimal points and, when appropriate, an exponent notation depending on the implementation. The reader should consult the programmer's manual for the LISP implementation he intends to use. Some examples of atoms are .NOFILL %5THE-LAST-TRUMP A307B 345 3.14159, .FILL %1and from these we can form lists like ((345 3.14159 -47) A307B THE-LAST-TRUMP -45.21). %1 .ss List structures. Lists are represented in the memory of the computer by list structures. A list structure is a collection of memory words each of which is divided into two parts, and each part is capable of containing an address in memory. The two parts are called are called the a-part and the d-part. There is one computer word for each element of the list, and the a-part of the word contains the address of the list or atom representing the element, and the d-part contains the address of the word representing the next element of the list. If the list element is itself a list, then, of course, the address of the first word of its list structure is given in the a-part of the word representing that element. A diagram shows this more clearly than words, and the list structure corresponding to the list %5(PLUS (TIMES X Y) X 3)%1 which may represent the expression %3xy%2 + %3x%2 + %53 is shown in figure 2. .GROUP .GROUP SKIP 11 Figure 2. .APART Atoms are represented by the addresses of their property lists which are list structures of a special kind depending on the implementation. (In some implementations, the first word of a property list is in a special are of memory, in others the first word is distinguished by sign, in still others it has a special a-part. For basic LISP programming, it is enough to know that atoms are distinguishable from other list structures by a predicate called %4at%1.) The last word of a list cannot have the address of a next word in its d-part since there isn't any next word, so it has the address of a special atom called %5NIL%1. A list is referred to by giving the address of its first element. According to this convention, we see that the a-part of a list word is the list element and the d-part is a pointer to a sublist formed by deleting the first element. Thus the first word of the list structure of figure 2 contains a pointer to the list structure representing the atom %5PLUS%1, while its d-part points to the list %5((TIMES X Y) X 3)%1. The second word contains the list structure representing %5(TIMES X Y)%1 in its a-part and the list structure representing %5(X 3)%1 in its d-part. The last word points to the atom %53%1 in its a-part and has a pointer to the atom %5NIL%1 in its d-part. This is consistent with the convention that %5NIL%1 represents the null list. .ss S-expressions. When we examine the way list structures represent lists we see a curious asymmetry. Namely, the a-part of a list word can contain an atom or a list, but the d-part can contain only a list or the special atom %5NIL%1. This restriction is quite unnatural from the computing point of view, and we shall allow arbitrary atoms to inhabit the d-parts of words, but then we must generalize the way list structures are expressed as character strings. To do this, we introduce the notion of S-expression. An S-expression is either an atom or a pair of S-expressions separated by "#.#" and surrounded by parentheses. In BNF, we can write <S-expression> ::= <atom> | (<S-expression> . <S-expression>). Examples of S-expressions are .NOFILL %5A (A . B) (A . (B . A)) (PLUS (X . (Y . NIL))) (3 . 3.4) .FILL In the memory of a computer, an S-expression is represented by the address of a word whose a-part contains the first element of the pair and whose d-part contains the second element of the pair. Thus, the S-expressions %5(A.B), (A.(B.A))%1, and %5(PLUS.(X.(Y.NIL))) %1 are represented by the list structures of figure 3. .GROUP .GROUP SKIP 15 Figure 3. .APART Note that the list %5(PLUS X Y)%1 and the S-expression %5 (PLUS . (X . (Y . NIL)))%1 are represented in memory by the same list structure. The simplest way to treat this is to regard S-expressions as primary and lists as abbreviations for certain S-expressions, namely those that never have any atom but NIL as the second part of a pair. In giving input to LISP, either the list form or the S-expression form may be used for lists. On output, LISP will print a list structure as a list as far as it can, otherwise as an S-expression. Thus, some list structures will be printed in a mixed notation, e.g. %5((A . B) (C . D) (3))%1. In general, the list %2(%3a b . . . z%2)%1 may be regarded as an abbreviation of the S-expression %2(%3a%2 . (%3b%2 . (%3c%2 . (... (%3z . %5NIL%2) ...)))%1. .SKIP 2 Exercises 1. If we represent sums and products as indicated above and use %5(MINUS X), (QUOTIENT X Y)%1, and %5(POWER X Y)%1 as representations of %2-%3x%1, %3x%2/%3y%1, and %3x%2↑%3y%1 respectively, then a. What do the lists %5(QUOTIENT 2 (POWER (PLUS X (MINUS Y)) 3)) %1and %5(PLUS -2 (MINUS 2) (TIMES X (POWER Y 3.3))) %1represent? b. How are the expressions %3xyz%2+%53%2(%3u%2+%3v%2)↑(-%53%2)%1 and %2(%3xy%2-%3yx%2)/(%3xy%2+%3yx%2)%1 to be represented? 2. In the above mentioned graph notation, what graph is represented by the list %5((A D E F)(B D E F)(C D E F)(D A B C)(E A B C)(F A B C))? %13. Write the list %5((PLUS (TIMES X Y) X 3)%1 as an S-expression. This is sometimes referred to as "dot-notation". 4. Write the following S-expressions in list notation to whatever extent is possible: .NOFILL a. (A . NIL) b. (A . B) c. ((A . NIL) . B) d. ((A . B) . ((C . D) . NIL). .FILL .ss The basic functions and predicates of LISP. Just as numerical computer programs are based on the four arithmetic operations of addition subtraction, multiplication, and division, and the arthmetic predicates of equality and comparison, so symbolic computation has its basic predicates and functions. LISP has three basic functions and two predicates. First, we have two functions %4a%1 and %4d%1. %4a %3x%1 is the a-part of the S-expression %5x%1. Thus, %4a%5(A . B) %2= %5A%1, and %4a%5((A . B) . A) %2= %5(A . B)%1. %4d %3x%1 is the d-part of the S-expression %3x%1. Thus %4d%5(A . B) %2= %5B%1, and %4d%5((A . B) . A) %2= %5A%1. %4a %3x%1 and %4d %3x%1 are undefined in basic LISP when %3x%1 is an atom, but they may have a meaning in some implementations. Since lists are a particular kind of S-expression, the meanings of %4a%1 and %4d%1 for lists are also determined by the above definitions. Thus, we have %4a%5(A B C D) %2=%4 A %1and %4d%5(A B C D) %2= %5(B C D), %1and we see that, in general, %4a %3x%1 is the first element of the list %3x%1, and %4d %3x%1 is the rest of the list, deleting that first element. Notice that for S-expressions, the definitions of %4a %3x%1 and %4d %3x%1 are symmetrical, while for lists the symmetry is lost. This is because of the unsymmetrical nature of the convention that defines lists in terms of S-expressions. Notice, further, our convention of writing %4a%1 and %4d%1## without brackets surrounding the argument. Also, we use lower case letters for our function names and for variables, reserving the upper case letters for the S-expressions themselves. The third function %3cons%2[%3x%2, %3y%2]%1 forms the S-expression whose a-part and d-part are %3x%1 and %3y%1 respectively. Thus %3cons%2[%5(A.B), A%2] = %5((A.B).A). %1We see that for lists, %3cons%1 is a prefixing operation. Namely, %3cons%2[%3x%2, %3y%2]%1 is the list obtained by putting the element %3x%1## onto the front of the list %3y%1. Thus %3cons%2[%5A, (B C D E)%2] = %5(A B C D E). %1If we want %3cons%2[%3x%2, %3y%2]%1 to be a list, then %3y%1 must be a list (possibly the null list %5NIL%1), and %3x%1 must be a list or an atom. In the case of S-expressions in general, there is no restriction on the arguments of %3cons%1. Usually, we shall write %3x . y%1 instead of %3cons%2[%3x%2, %3y%2]%1 since this is briefer. The first predicate is %4at %3x%1. %4at %3x%1 is true if the S-expression %3x%1 is atomic and false otherwise. The second predicate is equality of atomic symbols written %3x %4eq %3y%1. Equality of S-expressions is tested by a program based on %4eq%1. Actually %4eq%1 does a bit more than testing equality of atoms. Namely, %3x %4eq %3y%1 is true if and only if the addresses of the first words of the S-expressions %3x%1 and %3y%1 are equal. Therefore, if %3x %4eq %3y%1, then %3x%1 and %3y%1 are certainly the same S-expression since they are represented by the same structure in memory. The converse is false because there is no guarantee in general that the same S-expression is not represented by two different list structures. In the particular case where at least one of the S-expressions is known to be an atom, this guarantee can be given, because LISP represents atoms uniquely in memory. The above are all the basic functions of LISP; all other LISP functions can be built from them using recursive conditional expressions as will shortly be explained. However, the use of certain abbreviations makes LISP programs easier to write and understand. %4n %3x%1 is an abbreviation for %3x %4eq %5NIL%1. It rates a special notation because %5NIL%1 plays the same role among lists that zero plays among numbers, and list variables often have to be tested to see if their value is %5NIL%1. The notation %3list%2[%3x1, x2, . . . , xn%2]%1 is used to denote the composition of %3cons%1's that forms a list from its elements. Thus %3list%2[%3x, y, z%2] = %3cons%2[%3x, cons%2[%3y, cons%2[%3z, %5NIL%2]]] %1and forms a list of three elements out of the quantities %3x, y, %1 and %3z%1. We often write %2<%3x y . . . z%2>%1 instead of %3list%2[%3x, y, . . . , z%2]%1 when this will not cause confusion. Compositions of %4a%1 and %4d%1 are written by concatenating the letters %4a%1 and %4d%1. Thus, it is easily seen that %4ad %3x%1 denotes the second element of the list %3x%1, and %4add %3x%1 denotes the third element of that list. .ss Conditional expressions. When the form that represents a function depends on whether a certain predicate is true of the arguments, conditional expressions. are used. The conditional expression %4if %3p %4then %3a %4else %3b %1is evaluated as follows: First %3p%1 is evaluated and determined to be true or false. If %3p%1 is true, then %3a%1 is evaluated and its value is the value of the expression. If %3p%1 is false, then %3b%1 is evaluated and its value is the value of the expression. Note that if %3p%1 is true, %3b%1 is never evaluated, and if %3p%1 is false, then %3a%1 is never evaluated. The importance of this will be explained later. A familiar function that can be written conveniently using conditional expressions is the absolute value of a real number. We have %2|%3x%2| = %4if %3x%2<%50 %4then %2-%3x %4else %3x. %1A more general form of conditional expression is %4if %3p %4then %3a %4else if %3q %4then %3b . . . %4else if %3s %4then %3d %4else %3e. %1There can be any number of terms; the value is determined by evaluating the propositional terms %3p, q%1, etc. until a true term is found; the value is then that of the term following the next %4then%1. If none of the propositional terms is true, then the value is that of the term following the %4else%1. The function graphed in figure 4 is described by the equation %3tri%2[%3x%2] = %4if %3x%2<-%51 %4then %50 %4else if %3x%2<%50 %4then %51%2+%3x %4else if %3x%2<%51 %4then %51%2-%3x %4else %50. .GROUP .GROUP SKIP 10 %1 Figure 4. .APART .ss Boolean expressions. In making up the propositional parts of conditional expressions, it is often necessary to combine elementary propositional expressions using the Boolean operators and, or, and not. We use the symbols %2∧%1, %2∨%1, and %2¬%1 respectively, for these operators. In LISP, the atoms %5T%1 and %5NIL%1 are used for the truth values. The Boolean operators may be described simply by listing the values of the elementary Boolean expressions for each case of the arguments. Thus we have: .NOFILL %5T%2∧%5T %2= %5T T%2∧%5F %2= %5F F%2∧%5T %2= %5F F%2∧%5F %2= %5F T%2∨%5T %2= %5T T%2∨%5F %2= %5T F%2∨%5T %2= %5T F%2∨%5F %2= %5F %2¬%5T %2= %5F %2¬%5F %2= %5T. .FILL %1The Boolean operators can be described by conditional expressions in the following way: .NOFILL %3p%2∧%3q %2= %4if %3p %4then %3q %4else %5F %3p%2∨%3q %2= %4if %3p %4then %5T %4else %3q %2¬%3p %2= %4if %3p %4then %5F %4else %5T. .FILL %1Note that if %3p%1 is false %3p%2∧%3q%1 is false independent of the value of %3q%1, and likewise if %3p%1 is true, then %3p%2∨%3q%1 is true independent of %3q%1. If %3p%1 has been evaluated and found to be false, then %3q%1 does not have to be evaluated at all to find the value of %3p%2∧%3q%1, and, in fact, LISP does not evaluate %3q%1 in this case. Similarly, %3q%1 is not evaluated in evaluating %3p%2∨%3q%1 if %3p%1 is true. This procedure is in accordance with the above conditional expression descriptions of the Boolean operators. The importance of this convention which contrasts with that of ALGOL 60, will be apparent later when we discuss recursive definitions of functions and predicates. .ss Recursive function definitions. In such languages as FORTRAN and Algol, computer progrrams are expressed in the main as sequences of assignment statements and conditional go to's. In LISP, programs are mainly expressed in the form of recursively defined functions. We begin with an example. The function %3alt%2[%3x%2]%1 gives a list whose elements are alternate elements of the list %3x%1 beginning with the first. Thus .NOFILL %3alt%2[%5(A B C D E)%2] = %5(A C E), %3alt%2[%5(((A B) (C D))%2] = %5((A B)), %3alt%2[%5(A)%2] = %5(A), %1and %3alt%2[%5NIL%2] = %5NIL. The function %3alt%1 is defined by the equation alt%2[%3x%2] ← %4if n %3x %2∨ %4n d %3x %4then %3x %4else a %3x . alt%2[%4dd %3x%2]. .FILL %1The above definition is best explained by using it to evaluate some expressions. We start with %3alt%2[%5NIL%2]%1. To evaluate this expression we evaluate the expression to the right of the %2←%1 sign remembering that the variable %3x%1 has the value %5NIL%1. A conditional expression is evaluated by first evaluating the first propositional term ¬ in this case %4n %3x %2∨ %4n d %3x%1. This expression is a disjunction and in its evaluation we first evaluate the first disjunct, namely %4n#%3x%1. Since %3x %2= %5NIL, %4n %3x%1 is true, the disjunction is true, and the value of the conditional expression is the value of the term after the first true propositiional term. The term is %3x%1, and its value is %5NIL%1, so the value of %3alt%2[%5NIL%2]%1 is %5NIL%1 as stated above. Obeying the rules about the order of evaluation of terms in conditional and Boolean expressions is important in this case since if we didn't obey these rules, we might find ourselves trying to evaluate %4n d %3x%1 or %3alt%2[%4dd %3x%2]%1, and since %3x%1 is %5NIL%1, neither of these has a value. An attempt to evaluate them in LISP would give rise to an error return. As a second example, consider %3alt%2[%5(A B)%2]%1. Since neither %4n %3x%1 nor %4n d %3x%1 is true in this case, the disjunction %4n %3x %2∨ %4n d %3x %1is false and the value of the expression is the value of %4a %3x . alt%2[%4dd %3x%2]. %4a %3x%1 has the value %5A%1, and %4dd %3x%1 has the value %5NIL%1, so we must now evaluate %3alt%2[%5NIL%2]%1, and we already know that the value of this expression is %5NIL%1. Therefore, the value of %3alt%2[%5(A B)%2]%1 is that of %5A.NIL%1 which is %5(A)%1. We can describe this evaluation in a less wordy way by writing .NOFILL %3alt%2[%5(A B)%2] = %4if n%5(A B) %2∨ %4n d%5(A B) %4then %5(A B) %4else %4a%5(A B).%3alt%2[%4dd%5(A B)%2] = %4if %5NIL %2∨ %4n d%5(A B) %4then %5(A B) %4else %4a%5(A B).%3alt%2[%4dd%5(A B)%2] = %4if %5NIL %4then %5(A B) %4else %4a%5(A B).%3alt%2[%4dd%5(A B)%2] = %4a%5(A B).%3alt%2[%4dd%5(A B)%2] = %5A.%3alt%2[%5NIL%2] = %5A%2.[%4if n%5NIL %2∨ %4nd%5NIL %4then %5NIL %4else a%5NIL.%3alt%2[%4dd%5NIL%2]] = %5A%2.[%4if %5T %2∨ %4nd%5NIL %4then %5NIL %4else a%5NIL.%3alt%2[%4dd%5NIL%2]] = %5A%2.[%4if %5T %4then %5NIL %4else a%5NIL.%3alt%2[%4dd%5NIL%2]] = %5A%2.[%5NIL%2] = %5(A). .FILL %1This is still very long-winded, and now that the reader understands the order of evaluation of conditional and Boolean expressions, we can proceed more briefly to evaluate %3alt%2[%5(A B C D E)%2] = %5A.%3alt%2[%5(C D E)%2] = %5A%2.[%5C.%3alt%2[%5(E)%2]] = %5A.%2[%5C.(E)%2] = %5(A C E). %1Here are three more examples of recursive functions and their application: We define %3last%1 by %3last%2[%3x%2] ← %4if n d %3x %4then a %3x %4else %3last%2[%4d %3x%2], %1and we compute %3last%2[%5(A B C)%2] = %4if nd%5(A B C) %4then a%5(A B C) %4else %3last%2[%4d%5(A B C)%2] = %3last%2[%5(B C)%2] = %3last%2[%5(C)%2] = %5C. %1Clearly %3last%1 computes the last element of a list. %3last%2[%5NIL%2]%1 is undefined in the LISP language; the result of trying to compute it may be an error message or may be some random result depending on the implementation. The function %3subst%1 is defined by .NOFILL %3subst%2[%3x, y, z%2] ← %4if at %3z %4then %2[%4if %3z %4eq %3y %4then %3x %4else %3z%2] %4else %3subst%2[%3x, y, %4a %3z%2].%3subst%2[%3x, y, %4d %3z%2]. %1We have %3subst%2[%5(A.B), X, ((X.A).X)%2] = = %3subst%2[%5(A.B), X, (X.A)%2]%3subst%2[%5(A.B), X, X%2] = [%3subst%2[%5(A.B), X, X%2].%3subst%2[%5(A.B), X, A%2]].%5(A.B) %2= [[%5(A.B)%2].%5A%2].%5(A.B)%2] = %5(((A.B).A).(A.B)). .FILL %3subst%1 computes the result of substituting the S-expression %3x%1 for the atom %3y%1 in the S-expression %3z%1. This is an important operation in all kinds of symbolic computation. Another important operation is the concatenation of lists, and it is generally denoted by the infixed expression %3x%2*%3y%1 since it is associative. We have the examples %5(A B C)%2*%5(D E F) %2= %5(A B C D E F), %1and %5NIL%2*%5(A B) %2= %5(A B) %2= %5(A B)%2*%5NIL, %1and the formal definition %3x%2*%3y %2← %4if n %3x %4then %3y %4else %2[%4a %3x%2].[[%4d %3x%2]*%3y%2]. %1The Boolean operations can also be used in making recursive definitions provided we observe the order of evaluation of constituents. First, we define a predicate %3equal%1 by .NOFILL %3equal%2[%3x, y%2] ← %3x %4eq %3y %2∨ [¬%4at %3x %2∧ ¬%4at %3y %2∧ %3equal%2[%4a %3x, %4a %3y%2] ∧ %3equal%2[%4d %3x, %4d %3y%2]]. .FILL %3equal%2[%3x, y%2]%1 is true if and only if %3x%1 and %3y%1 are the same S-expression, and the use of this predicate makes up for the fact that the basic predicate %4eq%1 is guaranteed to test equality only when one of the operands is known to be an atom. We shall also use the infixes %2=%1 and %2≠%1. Membership of an S-expression %3x%1 in a list %3y%1 is tested by %3member%2[%3x, y%2] ← ¬%4n %3y %2∧ [[%3x %2= %4a %3y%2] ∨ %3member%2[%3x, %4d %3y%2]]. %1This relation is also denoted by %3x%2ε%3y. Here are some computations: .NOFILL %3member%2[%5B, (A B)%2] = ¬%4n %5(A B) %2∧ [[%5B %2= %4a %5(A B)%2] ∨ %3member%2[%5B, %4d %5(A B)%2]], = %3member%2[%5B, (B)%2] = %5T. .FILL %1Sometimes a function is defined with the help of auxiliary functions. Thus, the reverse of a list %3x%1 , (e.g. %3reverse%2[%5(A B C D)%2] = %5(D C B A)%1), is given by .NOFILL %3reverse%2[%3x%2] ← %3rev%2[%3x, %5NIL%2] %1where %3rev%2[%3x, y%2] ← %4if n %3x %4then %3y %4else %3rev%2[%4d %3x%2, [%4a %3x%2].%3y%2]. %1A computation is %3reverse%2[%5(A B C)%2] = %3rev%2[%5(A B C), NIL%2] = %3rev%2[%5(B C), (A)%2] = %3rev%2[%5(C), (B A)%2] = %3rev%2[%5NIL, (C B A)%2] = %5(C B A). %1A more elaborate example of recursive definition is given by %3flatten%2[%3x%2] ← %3flat%2[%3x, %5NIL%2] %3flat%2[%3x, y%2] ← %4if at %3x %4then %3x.y %4else %3flat%2[%4a %3x, flat%2[%4d %3x, y%2]]. %1We have %3flatten%2[%5((A.B).C)%2] = %3flat%2[%5((A.B).C), NIL%2] = %3flat%2[%5(A.B), %3flat%2[%5C, NIL%2]] = %3flat%2[%5(A.B), (C)%2] = %3flat%2[%5A, %3flat%2[%5B, (C)%2]] = %3flat%2[%5A, (B C)%2] = %5(A B C). .FILL %1The reader will see that the value of %3flatten%2[%3x%2]%1 is a list of the atoms of the S-expression %3x%1 from left to write. Thus %3flatten%2[%5((A B) A)%2] = %5(A B NIL A NIL)%1. Many functions can be conveniently written in more than one way. For example, the function %3reverse%1 mentioned above can be written without an auxiliary function as follows: %3reverse%2[%3x%2] ← %4if n %3x %4then %5NIL %4else %3reverse%2[%4d %3x%2]*%5<a x> %1but it will be explained later that the earlier definition involves less computation. The use of conditional expressions for recursive function definition is not limited to functions of S-expressions. For example, the factorial function and the Euclidean algorithm for the greatest common divisor are expressed as follows: .NOFILL %3n%2! ← %4if %3n%2=%50 %4then %51 %4else %3n%2(%3n%2-%51%2)! %1and %3gcd%2(%3m, n%2) ← %4if %3m%2>%3n %4then %3gcd%2(%3n, m%2) %4else if %3m%2=%50 %4then %3n %4else %3gcd%2(%3n mod m, m%2) .FILL %1where %3n mod m%1 denotes the remainder when %3n%1 is divided by %3m%1 and may itself be expressed recursively by %3n mod m %2← %4if %3n%2<%3m %4then %3n %4else %2(%3n%2-%3m%2) %3mod m. %1 Exercises 1. Consider the function %3drop%1 defined by %3drop%2[%3x%2] ← %4if n %3x %4then %5NIL %4else %2<%4a %3x%2>.%3drop%2[%4d %3x%2]. %1Compute (by hand) %3drop%2[%5(A B C)%2]%1. What does %3drop%1 do to lists in general? 2. What does the function %3r2%2[%3x%2] ← %4if n %3x %4then %5NIL %4else %3reverse%2[%4a %3x%2].%3r2%2[%4d %3x%2] %1do to lists of lists? How about %3r3%2[%3x%2] ← %4if at %3x %4then %3x %4else %3reverse%2[%3r4%2[%3x%2]] %3r4%2[%3x%2] ← %4if n %3x %4then %5NIL %4else %3r3%2[%4a %3x%2].%3r4%2[%4d %3x%2]? %13. Compare %3r3'%2[%3x%2] ← %4if at %3x %4then %3x %4else %3r3'%2[%4d %3x%2]*<%3r3'%2[%4a %3x%2]> %1with the function %3r3%1 of the preceding example. 4. Consider %3r5%1 defined by .NOFILL %3r5%2[%3x%2] ← %4if n %3x %2∨ %4n d %3x %4then %3x %4else %2[%4a %3r5%2[%4d %3x%2]] . %3r5%2[%4a %3x . r5%2[%4d %3r5%2[%4d %3x%2]]]. .FILL %1Compute %3r5%2[%5(A B C D)%2]%1. What does %5r5%1 do in general? Needless to say, this is not a good way of computing this function even though it involves no auxiliary functions. .ss Lambda expressions and functions with functions as arguments. It is common to use phrases like "the function 2%3x%2+%3y%1". This is not a precise notation because we cannot say 2%3x%2+%3y%2(%53, 4%2)%1 and know whether the desired result is 2%Bπ.%13+4 or 2%Bπ.%14+3 regarding the expression as a function of two variables. Worse yet, we might have meant a one-variable function of %3x%1 wherein %3y%1 is regarded as a parameter. The problem of giving names to functions is solved by Church's λ-notation. In the above example, we would write %2λ%3x y%2: %52%3x%2+%3y%1 to denote the function of two variables with first argument %3x%1 and second argument %3y%1 whose value is given by the expression 2%3x%2+%3y%1. Thus, %2[λ%3x y%2: %52%3x%2+%3y%2][%53, 4%2] = %510%1. %1Likewise, %2[λ%3y x%2: %52%3x%2+%3y%2][%53, 4%2] = %511%1. Like variables of integration and the bound variables of quantifiers in logic, variables following λ are bound or dummy and the expression as a whole may be replaced by any others provided the replacement is done consistently and does not make any variable bound by λ the same as a free variable in the expression. Thus %2λ%3x y%2: %52%3x%2+%3y%1 represents the same function as %2λ%3y x%2: %52%3y%2+%3x%1 or %2λ%3u v%2: %52%3u%2+%3v%1 , but in the function of one argument %2λ%3x%2: %52%3x%2+%3y%1 , we cannot replace the variable %3x%1 by %3y%1 , though we could replace it by %3u%1. λ-notation plays two important roles in LISP. First, it allows us to rewrite an expression containing two or more occurrences of the same sub-expression in such a way that the expression occurs only once. Thus %2(%52%3x%2+%51%2)↑%54%2+%53%2(%52%3x%2+%51%2)↑%53%1 can be written %2[λ%3w%2: %3w%2↑%54%2+%53%3w%2↑%53%2][%52%3x%2+%51%2]%1. This can save considerable computation, and corresponds to the practice in ordinary programming of assigning to a variable the value of a sub-expression that occurs more than once in an expression and then writing the expression in terms of the variable. The second use of λ-expressions is in using functions that take functions as arguments. Suppose we want to form a new list from an old one by applying a function %3f%1 to each element of the list. This can be done using the function %3mapcar%1 defined by %3mapcar%2[%3x, f%2] ← %4if n %3x %4then %5NIL %4else %3f%2[%4a %3x%2] . %3mapcar%2[%4d %3x, f%2]. %1Suppose the operation we want to perform is squaring, and we want to apply it to the list %5(1 2 3 4 5 6 7)%1. We have %3mapcar%2[%5(1 2 3 4 5 6 7), %2λ%3x%2: %3x%2↑%52%2] = %5(1 4 9 16 25 36 49). %1A more generally useful operation than %3mapcar%1 is %3maplist%1 in which the function is applied to the successive sublists of the list rather than to the elements. %3maplist%1 is defined by %3maplist%2[%3x, f%2] ← %4if n %3x %4then %5NIL %4else %3f%2[%3x%2] . %3maplist%2[%4d %3x, f%2]. %1As an application of %3maplist%1 and functional arguments, we shall define a function for differentiating algebraic expressions involving sums and products. The expressions are built up from atoms denoting variables and integer constants according to the syntax .NOFILL <expression> ::= <variable> | <integer> | (PLUS <explist>) | (TIMES <explist>) <explist> ::= <expression> | <expression><explist> .FILL Here, %5PLUS%1 followed by a list of arguments denotes the sum of these arguments and %5TIMES%1 followed by a list of arguments denotes their product. The function %3diff%2[%3e, v%2]%1 gives the partial derivative of the expression %3e%1 with respect to the variable %3v%1. We have .NOFILL %3diff%2[%3e, v%2] ← %4if at %3e %4then %2[%4if %3e %4eq %3v %4then %51 %4else %50%2] %4else if a %3e %4eq %5PLUS %4then %5PLUS . %3mapcar%2[%4d %3e%2, λ%3x%2: %3diff%2[%3x, v%2]_] %4else if a %3e %4eq %5TIMES %3then %5PLUS.%3maplist%2[%4d %3e%2, λ%3x%2: %5TIMES . %3maplist%2[%4d %3e%2, λ%3y%2: %4if %3x %4eq %3y %4then %3diff%2[%4a %3y, v%2] %4else a %3y%2]]. .FILL %1The term that describes the rule for differentiating products corresponds to the rule .NOFILL %2∂/∂%3v %3e%6i%2 = [%4if %3i%2=%3j %4then %2∂%3e%6j%2/∂%3v %4else %3e%6j%2]. .FILL and %3maplist%1 has to be used rather than %3mapcar%1 since whether to differentiate in forming the product is determined by equality of the indices %3i%1 and %3j%1 rather than equality of the terms %3e%6i%1 and %3e%6j%1. Two more useful functions with functions as arguments are the predicates %3andlis%1 and %3orlis%1 defined by the equations %3andlis%2[%3u, p%2] ← %4n %3u %2∨ [%3p%2[%4a %3u%2] ∧ %3andlis%2[%4d %3u, p%2]] %1and %3orlis%2[%3u, p%2] ← ¬%4n %3u %2∧ [%3p%2[%4a %3u%2] ∨ %3orlis%2[%4d %3u, p%2]]. %1 Exercises 1. Compute %3diff%2[%5(TIMES X (PLUS Y 1) 3), X%2]%1 using the above definition of %3diff%1. Now do you see why algebraic simplification is important? 2. Compute %3orlis%2[%5((A B) (C D) E), %4at%2]%1. .ss Label. The λ mechanism is not adequate for providing names for recursive functions, because in this case there has to be a way of referring to the function name within the function. Therefore, we use the notation %4label%2[%3f, e%2]%1 to denote the expression %3e%1 but where occurrences of %3f%1 within %3e%1 refer to the whole expression. For example, suppose we wished to define a function that takes alternate elements of each element of a list and makes a list of these. Thus, we want %3glub%2[%5((A B C) (A B C D) (X Y Z))%2] = %5((A C) (A C) (X Z)). %1We can make the definition .NOFILL %3glub%2[%3x%2] ← %3mapcar%2[%3x, %4label%2[%3alt%2, λ%3x%2: %4if n %3x %2∨ %4n d %3x %4then %3x %4else a %3x . alt%2[%4dd %3x%2]]]. .FILL %1The identifier %3alt%1 in the above example is bound by the label and is local to that expression, and this is the general rule. The label construction is not often used in LISP since it is more usual to give functions global definitions. D. M. R. Park pointed out that if we allow variables to represent functions and use a suitable λ construction, the use of label could be avoided. .sec HOW TO WRITE RECURSIVE FUNCTION DEFINITIONS .ss Static and dynamic ways of programming. In order to write recursive function definitions, one must think about programming differently than is customary when writing programs in languages like Fortran or Algol or in machine language. In these languages, one has in mind the state of the computation as represented by the values of certain variables or locations in the memory of the machine, and then one writes statements or machine instructions in order to make the state change in an appropriate way. When writing LISP recursive functions one thinks differently. Namely, one thinks about the value of the function, asks for what values of the arguments the value of the function is immediate, and, given an arbitrary values of the arguments, for what simpler arguments must the function be known in order to give the value of the function for the given arguments. Let us take a numerical example; namely, suppose we want to compute the function %3n%2!%1. For what argument is the value of the function immediate. Clearly, for %3n %2= %50 or %3n %2= %51%1, the value is immediately seen to be 1. Moreover, we can get the value for an arbitrary %3n%* if we know the value for %3n%2-%51. Also, we see that knowing the value for %3n %2= %51 is redundant, since it can be obtained from the %3n %2= %50 case by the same rule as gets it for a general %3n%* from the value for %3n%2-%51%1. All this talk leads to the simple recursive formula: %3n%2! ← %4if %3n %2= %50 %4then %51 %4else %3n%2(%3n%2-%51%2)!. %1We may regard this as a static way of looking at programming. We ask what simpler cases the general case of our function depends on rather than how we build up the desired state of the computation. One often is led to believe that static = bad and dynamic = good, but in this case, the static way is often better than the dynamic way. LISP offers both, but since it is less usual, we shall concentrate on the static way for now. Compare the above recursive definition with the following obvious Algol program for computing %3n%2!: .NOFILL %4integer procedure %3factorial%2(%3n%2); %4integer %3s%2; %4begin %3s %2:= %51%2; %3loop%2: %4if %3n %2= %50 %4then go to %3done%2; %3s %2:= %3n%2*%3s%2; %3n %2:= %3n%2-%51%2; %4go to %3loop%2; %3done%2: %3factorial %2:= %3s%2; %4end%2; .FILL %1The LISP program is shorter and clearer in this particularly favorable case. Actually, when we discuss the mechanism of recursion, it will turn out that the LISP program will be inefficient in using the pushdown mechanism unnecessarily and should be replaced by the following somewhat longer program that corresponds to the above Algol program rather precisely: %3n%2! ← %3fact%2(%3n%2, %3s%2), %1where %3fact%2(%3n%2, %3s%2) ← %4if %3n %2= %50 %4then %3s %4else %3fact%2(%3n%2-%51%2, %3n%2*%3s%2). %1In fact, compilers should produce the same object code from the two programs. .ss Simple list recursion. About the simplest form of recursion in LISP occurs when one of the arguments is a list, the result is immediate when the argument is null, and otherwise we need only know the result for the %4d%*-part of that argument. Consider, for example, %3u%2*%3v%1, the concatenation of the lists %3u%* and %3v%*. The result is immediate for the case %4n %3u%1 and otherwise depends on the result for %4d %3u%1. Thus, we have %3u%2*%3v %2← %4if n %3u %4then %3v %4else a %3u %2. [%4d %3u %2* %3v%2]. %1On the other hand, if we had tried to recur on %3v%1 rather than on %3u%1 we would not have been successful. The result would be immediate for %4n %3v%1, but %3u%2*%3v%1 cannot be constructed in any direct way from %3u%2*%4d %3v%1 without a function that puts an element onto the end of a list. (From a strictly list point of view, such a function would be as elementary as %3cons%1 which puts an element onto the front of a list, but, when we consider the implementation of lists by list structures, we see that the function is not so elementary. This has led some people to construct systems in which lists are bi-directional, but, in the main, this has turned out to be a bad idea). Anyway, it is usually easier to recur on one argument of a function than to recur on the other. It is often necessary to represent a correspondence between the elements of a small set of atoms and certain S-expressions by a list structure. This is conveniently done by means of an association list which is a list of pairs, each pair consisting of an atom and the corresponding S-expression. Thus the association list %5((X . (PLUS A B)) (Y . C) (Z . (TIMES U V)), %1which would print as %5((X PLUS A B)) (Y . C) (Z TIMES U V)), %1pairs %5X%1 with %5(PLUS A B), Y%1 with %5C%1, etc. We need a function to tell whether anything is associated with the atom %3x%1 in the association list %3a%1, and, if so, to tell us what. We have .NOFILL %3assoc%2[%3x, a%2] ← %4if n %3a %4then %5NIL %4else if %3x %4eq aa %3a %4then a %3a %4else %3assoc%2[%3x, %4d %3a%2]. .FILL %1Its value is %5NIL%1 if nothing is associated with %3x%1 and the association pair otherwise. E.g. %3assoc%2[%5X, ((X.W) (Y.V))%2] = %5(X.W)%1. It commonly happens that a function has no simple recursion, but there is a simple recursion for a function with one more variable that reduces to the desired function when the extra variable is set to %5NIL%1. Thus %3reverse%2[%3u%2] ← %3rev1%2[%3x, %5NIL%2], %1where %3rev1%2[%3u, v%2] ← %4if n %3u %4then %3v %4else %3rev1%2[%4d %3u, %4a %3u . v%2]. %3reverse%1 has a direct recursive definition as discovered by S. Ness, but no-one would want to use the following in actual computation nor does it generate much understanding, only appreciation of Mr. Ness's ingenuity: .NOFILL %3reverse%2[%3u%2] ← %4if n %3u %2∨ %4n d %3u %4then %3u %4else a %3reverse%2[%4d %3u%2] . %3reverse%2[%4a %3u. %3reverse%2[%4d %3reverse%2[%4d %3u%2]]]. %1 .FILL Exercises 1. Using the function %3member%2[%3x, u%2]%1 defined in Chapter I which may also be written %3x %2ε %3u%1, write function definitions for the union %3u %2∪ %3v%1 of lists %3u%1 and %3v%1, the intersection %3u %2∩ %3v%1, and the set difference %3u%2-%3v%1. What is wanted should be clear from the examples: %5(A B C) %2∪%5 (B C D) %2=%5 (A B C D), (A B C) %2∩%5 (B C D) %2=%5 (B C), %1and %5(A B C) %2-%5 (B C D) %2=%5 (A). %1Pay attention to getting correct the trivial cases in which some of the arguments are %5NIL%1. In general, it is important to understand clearly the trivial cases of functions. 2. Suppose %3x%1 takes numbers as values and %3u%1 takes as values lists of numbers in ascending order, e.g. %5(2 4 7)%1. Write a function %3merge%2[%3x, u%2]%1 whose value is obtained from that of %3u%1 by putting %3x%1 in %3u%1 in its proper place. Thus %3merge%2[%53, (2 4)%2] = %5(2 3 4)%1, and %3merge%2[%53, (2 3)%2] = %5(2 3 3)%1. 3. Write functions giving the union, intersection, and set difference of ordered lists; the result is wanted as an ordered list. Note that computing these functions of unordered lists takes a number of comparisons proportional to the square of the number of elements of a typical list, while for ordered lists, the number of comparisons is proportional to the number of elements. 4. Using %3merge%1, write a function %3sort%1 that transforms an unordered list into an ordered list. 5. Write a function %3goodsort%1 that sorts a list using a number of comparisons proportional to %3n log n%1, where %3n%1 is the length of the list to be sorted. .ss Simple S-expression recursion. In another class of problems, the value of the function is immediate for atomic symbols, and for non atoms depends only on the values for the a-part and the d-part of the argument. Thus %3subst%1 was defined by .NOFILL %3subst%2[%3x, y, z%2] ← %4if at %3z %4then %2[%4if %3z %4eq %3y %4then %3x %4else %3z%2] %4else %3subst%2[%3x, y, %4a %3z%2] . %3subst%2[%3x , y , %4d %3z%2]. .FILL %1Two other examples are %3equal%1 which gives the equality of S-expressions and %3flat%1 which spreads an S-expression into a list of atoms: They are defined by %3x%2=%3y %2← %3x %4eq %3y %2∨ [¬%4at %3x %2∧ ¬%4at %3y %2∧ %4a %3x %2= %4a %3y %2∧ %4d %3x %2= %4d %3y%2], %1and %3flat%2[%3x%2] ← %3flata%2[%3x, %5NIL%2] %1where %3flata%2[%3x, u%2] ← %4if at %3x %4then %3x.y %4else %3flata%2[%4a %3x, flata%2[%4d %3x, y%2]]. %1 EXERCISES 1. Write a predicate to tell whether a given atom occurs in a given S-expression, e.g. %3occur%2[%5B, ((A.B).C)%2] = %5T%1. 2. Write a predicate to tell how many times a given atom occurs in an S-expression. 3. Write a function to make a list without duplications of the atoms occurring in an S-expression. 4. Write a function to make a list of all atoms that occur more than once in a given S-expression paired with their multiplicities. 5. Write a predicate to tell whether an S-expression has more than one occurrence of a given S-expression as a sub-expression. .ss Other structural recursions. When lists are used to represent algebraic expressions, functions of these algebraic expressions often have a recursive form closely related to the inductive definition of the expressions. Suppose, for example, that sums and products are represented respectively by the forms %5(PLUS X Y)%1 and %5(TIMES X Y)%1 and that the values of variables are given on an a-list. We can write a recursive formula for the value of an expression as follows: .NOFILL %3value%2[%3e, a%2] ← %4if at %3e %4then d %3assoc%2[%3e, a%2] %4else if a %3e %4eq %5PLUS %4then %3value%2[%4ad %3e, a%2] + %3value%2[%4add %3e, a%2] %4else if a %3e %4eq %5TIMES %4then %3value%2[%4ad %3e, a%2] * %3value%2[%4add %3e, a%2]. .FILL %1On the other hand, suppose that sums and products are not restricted to have just two arguments; then we must use auxiliary functions to define the value of an expression, as follows: .NOFILL %3value%2[%3e, a%2] ← %4if at %3e %4then d %3assoc%2[%3e, a%2] %4else if a %3e %4eq %5PLUS %4then %3vplus%2[%4d %3e, a%2] %4else if a %3e %4eq %5TIMES %4then %3vtimes%2[%4d %3e, a%2]. %1where %3vplus%2[%3u, a%2] ← %4if n %3u %4then %50 %4else %3value%2[%4a %3u, a%2] + %3vplus%2[%4d %3u, a%2], %1and %3vtimes%2[%3u, a%2] ← %4if n %3u %4then %51 %4else %3value%2[%4a %3u, a%2] * %3vtimes%2[%4d %3u, a%2]. .FILL %1In both cases, the recursion form is related to the structure of the algebraic expressions more closely than to the structure of S-expressions or lists. .AT "\J" ⊂FILL⊃ ; .AT "\." ⊂NOFILL⊃ ; .turn on "↔" for "←" ; .<<\\M0NGR25;\M1BDJ25;\M2BDR25X;\M3SUB;\M4NGR30;\M5NGR40;\M6SUP;%1 >> .ss Tree search. \J We begin with a general depth first tree search function. It can be used to search specific trees of possibilities by defining three auxiliary functions in a way that depends on the application. We have\. %3search p %2← %4if %3lose p %4then %1LOSE %4else if %3ter p %4then %3p %4else %3searchlis%2[%*successors p%2]%1 where \J %3searchlis u %2← %4 if n %3u %4then %1LOSE %4else %3%2{%*search %4a %3u%2}[%*λx%2:%* %4if %3x %2= %1LOSE %4then %3searchlis %4d %3u %4else %3x%2]%*.%1\. \JIn the applications, we start with a position %3p%60%1, and we are looking for a win in the successor tree of %3p%60%1. Certain positions lose and there is no point looking at their successors. This is decided by the predicate %3lose%1. A position is a win if it doesn't lose and it satisfies the predicate %3ter%1. The successors of a position is given by the function %3successors%1, and the value of %3search p%1 is the winning position. No non-losing position should have the name LOSE or the function won't work properly. Our first example is finding a path from an initial node to a final node in a graph represented by a list structure as described in chapter I. A position is a path starting from the initial node and continuing to some intermediate node and is represented by a list of its nodes in reverse order. The three functions for this application are\. %3lose p %2← %4a %3p %2ε %4d %3p, ter p %2← [%4a %3p %2=%* final%2]%*, %1 and %3successors p %2←%* mapcar%2[%4d %3assoc%2[%4a %3p, graph%2]%*, λx%2:%* x.p%2]%*.%1 \J Another example is the so-called %3Instant Insanity%1 puzzle. There are four cubical blocks, and each face of each block is colored with one of four colors. The object of the puzzle is to build a tower of all four blocks such that each vertical face of the tower involves all four colors. In order to use the above defined function %3search%1 for this purpose, we must define the representation of positions and give the functions %3lose, ter, %1and %3successors%1. A position is represented by a list of lists ¬ one for each face of the tower. Each sublist is the list of colors of the faces of the blocks showing in that face. We shall assume that the blocks are described in the following longwinded but convenient way. (We'll take up precomputing this description later.) For each block there is a list of the 24 orientations of the block where each orientation is described as a list of the colors around the vertical faces of the block when it is in that orientation. Thus the puzzle is described by a list of lists of lists which we shall call %3puzz%1.\. We now have %3p%60%1 %2=%* (NIL NIL NIL NIL), %3lose p %2←%* orlis%2[%*p, λu%2:%* %4a %3u %2ε %4d %3u%2]%*, ter p %2← [%*length %4a %3p %2=%* 4%2]%1, and \J %3successors p %2←%* mapcar%2[%4a %3nth%2[%*puzz, 1 + length %4a %3p%2]%* , λx%2:%* mapcar2%2[%*p, x, λyz%2:%* z.y%2]]%*, %1\. where \J %3mapcar2%2[%*u, v, f%2] ← %3if n %3u %4then %1NIL %4else f%2[%4a %3u, %4a %3v%2]%* . mapcar2%2[%4d %3u, %4d %3v, f%2]%*.%1\. \J Getting the initial position in the desired form is as complicated a computation as the actual tree search. It can be conveniently done by a sequence of assignment statements starting with a description of the blocks: \. %3puzz1 %2← %1((G B B W R G) (G G B G W R) (G W W R B R) (G G R B W W)). \JHere each block is represented by a list of the colors of the faces starting with the top face, going around the sides in a clockwise direction and finishing with the bottom face. We need to go from this description of the blocks to a list of the possible cycles of colors on the vertical faces for the 24 orientations of the block. This not easy, because the order in which we have given the colors is not invariant under rotations of the block. An easy way out is to start with a block whose faces are assigned the numbers 1 thru 6 starting with the top, going clockwise around the sides and finishing with the bottom. We write down one cycle of side colors for each choice of the face put on top and get the list of all 24 cycles by appending the results of generating the cyclic permutations of the cycles. All this is accomplished by the assignment\. \J %3puzz2 %2←%* cycles%2[%1(2 3 4 5)%2]%*%2*%*%3cycles%2[%*(%1(2 5 4 3)%2]%*%2*%* %3cycles%2[%*(1 2 6 4)%2]%*\. %2*%*cycles%2[%*(1 4 6 2)%2]%*%2*%*cycles%2[%*(1 3 6 5)%2]%*%2*%*cycles%2[%*(1 5 6 3)%2]%*, %1 where the function %3cycles%1 is defined by %3cycles u %2←%* maplist%2[%*u, λx%2:%* x%2*%*upto%2[%*u, x%2]]%1 with the auxiliary function \J %3upto%2[%*u, x%2] ← %4if %3x %4eq %3u %4then %1NIL %4else a %3u . upto%2[%4d %3u, x%2]%*.%1\. \JNext we create for each block a list of substitutions expressing the colors of the six numbered faces. We have\. %3puzz3 %2←%* mapcar%2[%*puzz1, λx%2:%* prup%2[%1(1 2 3 4 5 6), %3x%2]]%*, %1 \Jand we use these substitutions to get for each block the list of 24 orientations of the block. Thus\. %3puzz4 %2←%* mapcar%2[%*puzz3, λs%2:%* sublis%2[%*s, puzz3%2]]%*. \Jpuzz4%1 has all 24 orientations of the first block while for symmetry reasons we need only consider three as distinct, say the first, ninth, and seventeen. So we finally get\. \J %3puzz %2←%* (%4a %3nth%2[%4a %3puzz4, 1%2] %4a %3nth%2[%4a %3puzz4, 9%2]%* %4a %3nth%2[%4a %3puzz4, 17%2]%*) . %4d %3puzz4.%1\. \JThe program when compiled runs about 11 seconds on the PDP-10. A more sophisticated representation of face cycles and partial towers makes a factor of ten speedup without changing the basic search algorithm. A face cycle is represented by 16 bits in a word four for each face a particular one of which being turned on tells us the color of the face. If we %4or%1 these words together for the blocks in a partial tower we get a word which tells us for each face of the tower what colors have been used. A particular face cycle from the next block can be added to the tower if the %4and%1 of its word with the word representing the tower is zero. We represent a position by a list of words representing its partial towers with 0 as the last element and the highest partial tower as the first element. The virtue of this representation is that it makes the description of the algorithm short. The initial position is (0). The new %3puzz%1 can be formed from the old one by the assignment\. %3puzza %2←%* mapcar%2[%*puzz, λx%2:%* mapcar%2[%*x, zap%2]]%*, %1 where \J %3zap v %2← %4if n %3v %4then %30 %4else %3poo %4a %3v + 16zap %4d %3v, %1\. and \J %3poo x %2← %4if %3x%2=%1R %4then %31 %4else if %3x%2=%1W %4then %12 %4else if %3x%2=%1G %4then %14 %4else %18.\. \JNow we need the new functions %3lose, ter, %1and %3successors%1. These are\. %3lose p %2← %4false%3, %3ter p %2← [%*length p %2=%* 5%2]%*, %1 and \J %3successors p %2←%* mapchoose%2[%4a %3nth%2[%*puzza, length p%2]%*, λx%2:%* %4a %3p %4and %3x %2=%* 0, λx%2:%* %2[%4a %3p %4or %3x%2]%* . p%2]%*.%1\. where %3mapchoose%2[%*u, pred, fn%2] ← %4if n %3u %4then %1NIL \J %4else if %3pred %4a %3u %4then %3fn%2[%4a %3u%2]%* . mapchoose%2[%4d %3u , pred, fn%2] %4\. else %3mapchoose%2[%4d %3u, pred, fn%2]%*.%1 \J%3lose%1 is trivial, because the %3mapchoose%1 is used to make sure that only non-losing new positions are generated by %3successors%1. This version runs in a little less than one second on the PDP-10. A greater speedup can be made by the application of some mathematics. In fact, with enough mathematics, extensive tree search is unnecessary in this problem. %3search%1 is used when we want to search a tree of possibilities for a solution to a problem. What if we want to find all solutions to a problem? This can be done with a function %3allsol%1 that uses the same %3lose, ter, %1and %3successors%1 functions as does %3search%1. The simplest way to write %3allsol%1 is\. \J %3allsol p %2← %4if %3lose p %4then %1NIL %4else if %3ter p %4then %3(p) %4else %3mapapp%2[%*successors p, allsol%2]%*, %1\. where \J %3mapapp%2[%*u, fn%2] ← %4if n %3u %4then %1NIL %4else %3fn%2[%4a %3u%2]%* . mappap%2[%4d %3u, fn%2]%*.%1\. \JThis form of the function is somewhat inefficient because of all the %3append%1ing. A more efficient form uses an auxiliary function as follows: \. %3allsol p %2←%* allsola%2[%*p, %1NIL%2]%* %3allsola%2[%*p, found%2] ← %4if %3lose p %4then %3found %4else if %3ter p %4then %3p . found %4else %3allsolb%2[%*successors p, found%2]%*, \J %3allsolb%2[%*u, found%2] ← %4if n %3u %4then %3found %4else %3allsolb%2[%4d %3u, allsola%2[%4a %3u, found%2]]%*.%1\. \JThe recursive program structure that arises here is common when a list is to be formed by recurring through a list structure.\. .ss Game trees. \J The positions that can be reached from an initial position in a game form a tree, and deciding what move to make often involves searching this tree. However, game trees are searched in a different way than the trees we have looked at, because the opposing interests of the players makes it not a search for a joint line of play that will lead to the first player winning, but rather a search for a strategy that will lead to a win regardless of what the other player does. The simplest situation is characterized by a function %3successors%1 that gives the positions that can be reached in one move, a predicate %3ter%1 that tells when a position is to be regarded as terminal for the given analysis, and a function %3imval%1 that gives a number approximating the value of the position to one of the players. We shall call this player the maximizing player and his opponent the minimizing player. Usually, the numerical values arise, because the search cannot be carried out to the end of the game, and the analysis stops with reasonably static positions that can be evaluated by some rule. Naturally, the function %3imval%1 is chosen to be easy to calculate and to correlate well with the probability that the maximizing player can win the position. The simplest rule for finding the correct move in a position uses auxiliary functions %3valmax%1 and %3valmin%1 that give a value to a position by using %3imval%1 if the position is terminal and taking the max or min of the successor positions otherwise. For this we want functions for getting the maximum or the minimum of a function on a list, and they are defined as follows: \. \J %3maxlis%2[%*u, f%2] ← %4if n %3u %4then %3-%2∞%* %4else %3 max%2[%*f%2[%4a %3u%2]%*, maxlis%2[%4d %3u, f%2]]%*, %1\. and \J %3minlis%2[%*u, f%2] ← %4if n %3u %4then %3%2∞%* %4else %3 min%2[%*f%2[%4a %3u%2]%*, minlis%2[%4d %3u, f%2]]%*.%1\. \JIn these functions, -%2∞%* and %2∞%* represent numbers that are smaller and larger than any actual values that will occur in evaluating %3f%1. If these numbers are not available, then it is necessary to prime the function with the values of %3f%1 applied to the first element of the list, and the functions are meaningless for null lists. Iterative versions of the functions are generally better; we give only the iterative version of %3maxlis%1, namely\. %3maxlis%2[%*u, f%2] ←%* maxlisa%2[%*u, -%2∞%*, f%2]%*, %1 where \J %3maxlisa%2[%*u, x, f%2] ← %3if n %3u %4then %3x %4else %3maxlisa%2[%4d %3u, max%2[%*x, f%2[%4a %3u%2]]%*, f%2]%*.%1\. We now have \J %3valmax p %2← %4if %3ter p %4then %3imval p %4else %3maxlis%2[%*successors p, valmin%2]%1, \. and \J %3valmin p %2← %4if %3ter p %4then %3imval p %4else %3minlis%2[%*successors p, valmax%2]%1.\. The best move is now chosen by %3movemax p %2←%* bestmax%2[%*succesors p, valmin%2]%*, %1 or %3movemin p %2←%* bestmin%2[%*succesors p, valmax%2]%*, %1 where %3bestmax%2[%*u, f%2] ←%* bestmaxa%2[%4d %3u, %4a %3u, f%2[%4a %3u%2]%*, f%2]%*, %3bestmaxa%2[%*u, sofar, valsofar, f%2] ← %4if n %3u %4then %3sofar \J %4else if %3f%2[%4a %3u%2] ≤ %3bestsofar %4then %3bestmaxa%2[%4d %3u, sofar, bestsofar, f%2]%*\. %4else %3bestmaxa%2[%4d %3u, %4a %3u, f%2[%4a %3u%2]%*, f%2]%*, %3bestmin%2[%*u, f%2] ←%* bestmina%2[%4d %3u, %4a %3u, f%2[%4a %3u%2]%*, f%2]%*, %1 and %3bestmina%2[%*u, sofar, valsofar, f%2] ← %4if n %3u %4then %3sofar \J %4else if %3f%2[%4a %3u%2] ≥ %3bestsofar %4then %3bestmina%2[%4d %3u, sofar, bestsofar, f%2]%*\. %4else %3bestmina%2[%4d %3u, %4a %3u, f%2[%4a %3u%2]%*, f%2]%*.%1 \J However, this straight minimax computation of the best move does much more computation in general than is usually necessary. The simplest way to see this is from the move tree of Figure 2.6.\. .GROUP; .GROUP SKIP 11; ↔Figure 2.6 .APART; \JWe see from this figure that it is unnecessary to examine the moves marked x, because their values have no effect on the value of the game or on the correct move since the presence of the 9 is sufficient information at this point to show that the move leading to the vertex preceding it should not be chosen by the minimizing player. The general situation is that it is unnecessary to examine further moves in a position once a move is found that refutes moving to the position in the first place. This idea is called the αβ-heuristic and expressed in the following recursive definitions: \. %3maxval p %2←%* maxval1%2[%*p, -%2∞%*, %2∞%*%2]%*, \J maxval1%2[%*p, α, β%2] ← %4if %3ter p %4then %3max%2[%*α, min%2[%*β, imval p%2]]%* %4else %3maxval2%2[%*successors p, α, β%2]%*, \. \J maxval2%2[%*u, α, β%2] ← {%*minval1%2[%4a %3u, α, β%2]}[%*λw%2:%* %4if %3w %2=%* β %4then %3β %4else %3maxval2%2[%4d %3u, w, β%2]]%*, \. %3minval p %2←%* minval1%2[%*p, -%2∞%*, %2∞%*%2]%*, \J minval1%2[%*p, α, β%2] ← %4if %3ter p %4then %3max%2[%*α, min%2[%*β, imval p%2]]%* %4else %3minval2%2[%*successors p, α, β%2]%*, \. \J minval2%2[%*u, α, β%2] ← {%*maxval1%2[%4a %3u, α, β%2]}[%*λw%2:%* %4if %3w %2=%* α %4then %3α %4else %3minval2%2[%4d %3u, α, w%2]%*.%1\. \J The reduction in number of positions examined given by the αβ algorithm over the simple minimax algorithm depends on the order in which the moves are examined. In the worst case, the moves happen to be examined in inverse order of merit in every position on the tree, i.e. the worst move first. In that case, there is no improvement over minimax. The best case is the one in which the best move in every position is examined first. If we look %3n%1 moves deep on a tree that has %3k%1 successors to each position, then minimax looks at %3k%7n%1 positions while αβ looks at about only %3k%7n/2%1. Thus a program that looks at 10%74%1 moves with αβ might have to look at 10%78%1 with minimax. For this reason, game playing programs using αβ make a big effort to include as good as possible an ordering of moves into the %3successors%1 function. When there is a deep tree search to be done, the way to make the ordering is with a short look-ahead to a much smaller depth than the main search. Still shorter look-aheads are used deeper in the tree, and beyond a certain depth, non-look-ahead ordering methods are of decreasing complexity. A version of αβ incorporating optimistic and pessimistic evaluations of positions was first proposed by McCarthy about 1958. Edwards and Hart at M.I.T. about 1959 proved that the present version of αβ works and calculated the improvement it gives over minimax. The first publication, however, was Brudno (1963). It is worth noting that αβ was not used in the early chess playing programs in spite of the fact that it is clearly used in any human play. Its non-use, therefore, represents a failure of self-observation. Very likely, there are a number of other algorithms used in human thought that we have not noticed an incorporated in our programs. To the extent that this is so, artificial intelligence will be %3a posteriori%1 obvious even though it is %3a priori%1 very difficult.\. .STANDARD BACK;