Introduction to LISP Page 1 NOTE LISP in this document will be used to mean those things which I have found in most of the LISPs which I have used. These incluce Stamford LISP, IBM LISP, University of Maryland LISP, Franz LISP, INTERLISP 1.0 THE LISP APPROACH TO DATA REPRESENTATION 1.1 DATA TYPES There are 3 basic data types found in LISP. They are: 1. ATOMS (a) identifiers (b) numbers Numbers often come in a variety of types such as: i. fixed numbers ii. big numbers (usually called bignums. These can be indefinitely large) iii. floating point numbers 2. LISTS Lists are the main object of LISP. They can have any LISP data types in them. 3. DOTTED PAIRS These are a special type of list. Introduction to LISP Page 2 1.2 NOTATION FOR INTERNAL REPRESENTATIONS NOTE The internal representations used here are not the implementation of any particular LISP; rather, they are a handy way of visualizing these objects. The basic notation we need is something to represent two addresses somehow associated. We will use: ______________________________ ! ! ! ! ! ! ------------------------------- If we wish to specify what the addesses point to (are the addresses of) we will use the notation: ______________________________ ! ! ----!----> B ! ! ! ! -------!----------------------- ! v A to denote a pair of pointers one to A and one to B. We will write something in one of the boxes to denote some type of flag which is not interpeted as an address. such as: ______________________________ ! atom ! ! ! header ! ! ------------------------------- Introduction to LISP Page 3 1.3 ATOMS 1.3.1 Indentifiers Identifiers are used in many ways in LISP. Associated with identifiers are properties and LISP has functions to retrieve the properties. In almost all LISP implementations, the collection of properties is in list format and is called the property list. Usually two (or more) properties are singled out to have special usage: 1. VALUE This is the everyday value of a variable, much as it is used in other programming languages. 2. PNAME This is the print name and is used when one outputs the name of the identifier. An atom can be visualized as: ______________________________ ! atom ! ------!---->PROPERTY LIST ! header ! ! ------------------------------- NOTE In most of the older LISPs the function which retrieved the object pointed at by the second address returned the property list for atoms. This is not true in many of the newer LISPs. More on this later. Introduction to LISP Page 4 1.3.2 Numbers A number can be visualized as: ______________________________ ______________________________ ! atom ! ------!----> ! number ! ------!-->value ! header ! ! ! type ! ! ------------------------------- ------------------------------- Although different LISPs use many different representations of numbers. The important things to realize about LISP numbers are 1. One can determine its type 2. One can determine its value 3. It is the number representation not the identifier identifying it that has this information. 1.4 LISTS Since lists are the basic object of LISP, they will be discussed throughout this document. This section will just illustrate some basic properties of lists. Some examples of lists are: 1. (A B C D) 2. (A (B C) D) 3. (1 (A) B) 4. (A) 5. ((A)) 6. ((A B C) D) 7. () This last list is a very important object in LISP. It is the empty list and has the special name NIL. Introduction to LISP Page 5 Lists can contain any LISP objects. In LISP, a list is thought of as having two main parts, a head and a tail. These are usually refered to as the CAR and the CDR, as these are the LISP functions used to obtain these from a list. The CAR (or head) is the first element of the list and the CDR (or tail) is the list of the rest of the elements. for the above lists the CAR and CDR are: 1. CAR: A CDR: (B C D) 2. CAR: A CDR: ((B C) D) 3. CAR: 1 CDR: ((A) B) 4. CAR: A CDR: () called NIL 5. CAR: (A) CDR: NIL 6. CAR: (A B C) CDR: (D) 7. for the last list (NIL) the CAR and CDR are either undefined or some special value. These lists can be visualized as follows: NOTE Because of the size of the paper these representations will be on several lines and in parts abbreviated. A pointer to the right hand side of the page is a pointer to the next line. Also we will use the notation *n* to continue a pointer. Introduction to LISP Page 6 1. (A B C D) ______________________________ ______________________________ ! ! ------!----> ! ! ------!--> ! ! ! ! ! ! ! ! -------!----------------------- -------!----------------------- ! ! v v A B ______________________________ ______________________________ ! ! ------!----> ! ! list ! ! ! ! ! ! ! ! terminator ! -------!----------------------- -------!----------------------- ! ! v v C D 2. (A (B C) D) ______________________________ ______________________________ ! ! ------!----> ! ! ------!--> ! ! ! ! ! ! ! ! -------!----------------------- -------!----------------------- ! ! v v A *1* ______________________________ ! ! list ! ! ! ! terminator ! -------!----------------------- ! v D *1*----> ______________________________ ______________________________ ! ! ------!----> ! ! list ! ! ! ! ! ! ! ! terminator ! -------!----------------------- -------!----------------------- ! ! v v B C Introduction to LISP Page 7 3. (1 (A) B) ______________________________ ______________________________ ! ! ------!----> ! ! ------!--> ! ! ! ! ! ! ! ! -------!----------------------- -------!----------------------- ! ! v v 1 *1* ______________________________ ! ! list ! ! ! ! terminator ! -------!----------------------- ! v B *1*----> ______________________________ ! ! list ! ! ! ! terminator ! -------!----------------------- ! v A 4. (A) ______________________________ ! ! list ! ! ! ! terminator ! -------!----------------------- ! v A Introduction to LISP Page 8 5. ((A)) ______________________________ ! ! list ! ! ! ! terminator ! -------!----------------------- ! ! v ______________________________ ! ! list ! ! ! ! terminator ! -------!----------------------- ! v A 6. ((A B C) D) ______________________________ ______________________________ ! ! ------!----> ! ! list ! ! ! ! ! ! ! ! terminator ! -------!----------------------- -------!----------------------- ! ! v v *1* D *1*----> ______________________________ ______________________________ ! ! ------!----> ! ! ------!--> ! ! ! ! ! ! ! ! -------!----------------------- -------!----------------------- ! ! v v A B ______________________________ ! ! list ! ! ! ! terminator ! -------!----------------------- ! v C Introduction to LISP Page 9 7. () ______________________________ ! list ! not ! ! terminator ! used ! ------------------------------- NOTE The above representation does not accurately reflect the nature of NIL. Also, for many reasons we will assume that the special flag "list terminator" is a pointer to NIL. One good reason for this will become apparent when we discuss the function CDR. 1.5 DOTTED PAIRS Dotted pairs are special objects very similar to lists. They are best understood by their representation, and by the value of the functions CAR and CDR on them. (The functions CAR and CDR will be discussed in the section on LISP functions.) Some examples of dotted pairs are: 1. (A . B) 2. (A . (B C) ) 3. (A . () ) this dotted pair is the same as the list (A) 4. (A B . C) 5. (1 . 2) some LISPs represent rational numbers with dotted pairs as values. In that notation this dotted pair would represent 1/2. One of the main similarities between dotted pairs and lists is that dotted pairs like lists have a head (CAR) and a tail (CDR). The main difference is that for dotted pairs the tail is not in general a list. Introduction to LISP Page 10 Dotted pairs have many uses. One use as mentioned above is in the representation of rational numbers. Another common use is to use a list of dotted pairs to represent some type of relation or function. For the above dotted pairs the CARs and CDRs are: 1. CAR: A CDR: B 2. CAR: A CDR: (B C) NOTE This type of dotted pair is why the usual definition (namely that the tail is not a list) is slightly inaccurate. however this dotted pair is the same as the list (A B C). 3. CAR: A CDR: NIL 4. CAR: A CDR: (B . C) 5. CAR: 1 CDR: 2 One can visualize these dotted pairs as follows: 1. (A . B) ______________________________ ! ! ----!----> B ! ! ! ! -------!----------------------- ! v A Introduction to LISP Page 11 2. (A . (B C) ) ______________________________ ______________________________ ! ! ------!----> ! ! ------!--> ! ! ! ! ! ! ! ! -------!----------------------- -------!----------------------- ! ! v v A B ______________________________ ! ! list ! ! ! ! terminator ! -------!----------------------- ! v C 3. (A . () ) ______________________________ ! ! list ! ! ! ! terminator ! -------!----------------------- ! v A 4. (A B . C) _____________________________ ____________________________ ! ! -----!----> ! ! ------!--> C ! ! ! ! ! ! ! ! -------!---------------------- ------!---------------------- ! ! v v A B 5. (1 . 2) ______________________________ ! ! ----!----> 2 ! ! ! ! -------!----------------------- ! v 1 Introduction to LISP Page 12 1.6 DATA BINDINGS LISP (unlike most compiled languages but like many interpeted languages) does not have data types associated with identifiers. Each data type may have some internal marking specifying its data type. Also, LISP does not have strong typing (although some LISP implementations have slightly stronger typing then others). 1.7 PROPERTY LISTS Every identifier has associated with it a property list. One use of the property list is to store the value and pname of the Identifier. The property list is also used by programmers to associate properties with identifiers. Such as, one might note that the dog is red by giving the atom representing the dog the property color with the property value red. This would give one a property list for dog of the form: (value nil color red pname dog) NOTE In our representations we will assume that the property list is the CDR of an identifier. In most LISPs nowadays that is not true; however, it is still a good way of visualizing the property list and almost all LISPs allow one some method of obtaining the property list. Some LISPs, in fact, have a special function called OLDCDR for those who want these features. Introduction to LISP Page 13 1.7.1 Representation Of The Above Example ______________________________ ______________________________ ! atom ! ------!----> ! ! ------!--> ! header ! ! ! ! ! ! ------------------------------- --------!---------------------- ! v VALUE ______________________________ ______________________________ ! ! ------!----> ! ! ------!--> ! ! ! ! ! ! ! ! -------!----------------------- -------!----------------------- ! ! v v NIL COLOR ______________________________ ______________________________ ! ! ------!----> ! ! -------!--> ! ! ! ! ! ! ! ! -------!----------------------- -------!----------------------- ! ! v v RED PNAME ______________________________ ! ! list ! ! ! ! terminator ! -------!----------------------- ! v ASCII /DOG/ Introduction to LISP Page 14 2.0 THE BASIC LISP FUNCTIONS AND WHAT THEY DO 2.1 FUNCTIONAL NOTATION In LISP the function f applied to x is denoted (f x). NOTE In LISP most functions "EVAL" their arguments. The meaning of this will be made clear later; for the time being in order for the examples to be correct while still avoiding this issue most of the arguments to functions will have the symbol "'" before them. This symbol acts as a sort of a right-hand inverse to EVAL. (It is however in no way a left-hand inverse.) 2.2 CAR, CDR AND CONS The three functions CAR, CDR and CONS are available in all LISP implementations; in fact, LISP can be defined as a language with these three functions. The term "pure LISP" is sometime used to refer to a LISP implementation with no functions other than these three (other definitions of "pure LISP" will be mentioned later). 2.2.1 CAR The function CAR returns the head of a list or the first element of a dotted pair. Applied to other things the definition of CAR is implemenation dependent. Introduction to LISP Page 15 In terms of our internal representation ______________________________ ! ! ----!----> B ! ! ! ! -------!----------------------- ! v A CAR returns the left hand pointer (the pointer to A). examples: 1. (CAR '(A B C D) ) = A 2. (CAR '(A (B C) D) ) = A 3. (CAR '(1 (A) B) ) = 1 4. (CAR '(A) ) = A 5. (CAR '((A)) ) = (A) 6. (CAR '((A B C) D) ) = (A B C) 7. (CAR '() ) is implementation dependent 8. (CAR '(A . B) ) = A 9. (CAR '(A . (B C)) ) = A 10. (CAR '(A . () ) ) = A 11. (CAR '(A B . C) ) = A 12. (CAR '(1 . 2) ) = 1 2.2.2 CDR The function CDR returns the tail of a list or the second element of a dotted pair. Applied to other things the definition of CDR is implemenation dependent. Introduction to LISP Page 16 In terms of our internal representation ______________________________ ! ! ----!----> B ! ! ! ! -------!----------------------- ! v A CDR returns the right hand pointer (the pointer to B). examples: 1. (CDR '(A B C D) ) = (B C D) 2. (CDR '(A (B C) D) ) = ( (B C) D) 3. (CDR '(1 (A) B) ) = ( (A) B) 4. (CDR '(A) ) = () that is NIL NOTE This is why, as mentioned earlier, it is convenient to think of "list terminator" as a pointer to NIL. 5. (CDR '((A)) ) = () that is NIL 6. (CDR '((A B C) D) ) = (D) 7. (CDR '() ) is implementation dependent 8. (CDR '(A . B) ) = B 9. (CDR '(A . (B C)) ) = (B C) 10. (CDR '(A . () ) ) = () that is NIL 11. (CDR '(A B . C) ) = (B . C) 12. (CDR '(1 . 2) ) = 2 Introduction to LISP Page 17 2.2.3 CONS The function CONS takes two arguments and creates a list whose CAR is the first argument and whose CDR is the second argument. Dotted pairs are the result of applying CONS to a second argument which is not a list. examples: 1. (CONS 'A '(B C D) ) = (A B C D) 2. (CONS 'A '((B C ) D) ) = (A (B C) D) 3. (CONS '1 '((A) B) ) = (1 (A) B) 4. (CONS 'A '() ) = (A) 5. (CONS '(A) NIL ) = ((A)) 6. (CONS '(A B C) '(D) ) = ((A B C) D) 7. There is no corresponding example. The value of CONS is never NIL 8. (CONS 'A 'B ) = (A . B) 9. (CONS 'A '(B C) ) = (A . (B C)) 10. (CONS 'A '() ) = (A . () ) which is the same as (A) 11. (CONS 'A '(B . C) ) = (A B . C) 12. (CONS 1 2 ) = (1 . 2) NOTE The reason that the 1 and the 2 do not have "'" before them is that '1 is the same as 1. This is expressed in LISP terms as numbers EVAL to themselves. Introduction to LISP Page 18 2.2.4 The Relationship Of CAR, CDR And CONS. CAR and CDR are the two partial inverses of CONS. I.e. 1. (CAR (CONS 'A 'B) ) = A 2. (CDR (CONS 'A 'B) ) = B 3. (CONS (CAR A) (CDR A) ) = A if both CAR and CDR of A are defined. 2.3 "EVAL" AND "QUOTE" 2.3.1 "EVAL" When an expression is typed into the LISP interpeter, it responds with its "value". In most LISPs there is a function EVAL which represents this action. The complete workings of this function are both implementation dependent and rather complicated; but, piece by piece, we will try to explain how this works. In this section we will explain what EVAL (and the LISP interpeter) do in the three simplest cases. 1. EVAL on a number EVAL of a number is the number. 2. EVAL of an identifier If the Identifier had a VALUE property on its property list, the value returned is the property-value associated with the "VALUE" property. 3. EVAL on a list (where the first element of the lisp is a "simple" function). Is the functional value of the function which is the CAR of the list applied to the list obtained by "EVAL"ing each of the elements of the CDR of the list. This takes a while to fully understand but is very fundamental to LISP programming. Introduction to LISP Page 19 Some examples (for these examples, I am assuming that there is an explicit function EVAL): 1. (EVAL 1) = 1 2. if A has the "value" 7 then (EVAL A) = 7 3. (EVAL (CDR '(A B C) ) ) = (B C) NOTE In this case this is not what LISP would respond if one gave it the expression "(EVAL (CDR '(A B C) ) )" since there would be an implicit second EVAL; rather, it is what LISP would respond to "(CDR '(A B C) )". 2.3.2 QUOTE QUOTE is a "special" or unusual function in that it does not "EVAL" its arguments. It is used to avoid the "EVAL"ing of things. (QUOTE A) is commonly abbreviated 'A. some examples of its use are: NOTE We will not anymore make explicit (as we did in our last example the "top-level EVAL". I.e. when we say something equals something else, we will mean that it EVALs to that. 1. (QUOTE A) = A 2. (CAR (QUOTE (A) ) ) = A 3. (CAR (QUOTE (QUOTE (A) ) ) = QUOTE that is the identifier quote Introduction to LISP Page 20 This example is clearer if written (CAR '(QUOTE (A)) ) = QUOTE. 4. (QUOTE (EVAL (CAR '(A B) ) ) ) = (EVAL (CAR '(A B) ) ) 5. (EVAL (QUOTE (EVAL (CAR '(A B))))) = A 2.4 PRETTY PRINTING The above example becomes much easier to read if formatted over several lines. E.g. (EVAL (QUOTE (EVAL (CAR '(A B)) ))) is much clearer. 2.5 SPECIAL NAMES FOR COMPOSITIONS OF CAR AND CDR. most LISPs have functions for many of the compostions of up to 4 or 5 CARs and CDRs. such as 1. (CAR (CAR X)) = (CAAR X) 2. (CAR (CDR X)) = (CADR X) 3. (CDR (CAR X)) = (CDAR X) In general a function whose name begins with a C ends with an R and has a series of Ds and As in between is a composition of CARs and CDRs. Introduction to LISP Page 21 2.6 COND The function COND is one of the main control facilities in LISP. It is also one of the functions which is sometimes used in the definition of "pure LISP" (pure LISP has been defined as a LISP with CAR, CDR, CONS, and COND). COND functions as a case statement and it is well to keep this in mind when trying to make sense of the actual definition. COND takes as arguments; a list whose elements are two element lists. These two element lists will represent cases and actions. The value of COND is as follows: If there is a two element list whose CAR is not NIL, then the value of COND is the CADR of the first two element list whose CAR is not NIL; otherwise the value of COND is implementation dependent, but usually NIL. In order to facilitate giving examples of COND, we will introduce some testing type functions and also the special atom T. We will also discuss defining functions. 2.7 T AND SOME TESTING TYPE (PREDICATE) FUNCTIONS. T is a special atom used to indicate truth, although most logical functions consider anything that isnt NIL to be true. Names of the following functions vary widely but most LISPs have functions that act like these: 1. (NULL X) = T if X is NIL; NIL otherwise 2. (ATOM X) = T if X is an atom; NIL otherwise 3. (NUMBERP X) = T if X is a number; NIL otherwise 4. (EQ X Y) = T if X and Y are the same object; NIL otherwise 5. (AND X1 ... XN) = T if all Xi are non NIL; NIL otherwise Introduction to LISP Page 22 6. (OR X1 ... XN) = T if any Xi is non NIL; NIL otherwise 7. (LESS X Y) undefined if X and Y are not numbers; T if XY; NIL otherwise 9. (ZEROP X) undefined if X is not a number; T if X is 0; NIL otherwise 2.8 DEFINING FUNCTIONS Each LISP has its own way of defining functions and we will return to this subject when we discuss the special symbol LAMBDA; however, for the time being, we will introduce the following method of defining functions. (DEFINE_FUNCTION FUNCTION_NAME (ARGS) (FUNCTION_DEFINITION)) Most LISPs have a function similar to this. 2.9 EXAMPLES OF COND 1. (DEFINE_FUNCTION EQUAL (X Y) (COND ((EQ X Y) T) ((ATOM X) NIL) ((ATOM Y) NIL) ((EQUAL (CAR X) (CAR Y)) (EQUAL (CDR X) (CDR Y))) (T NIL))) NOTE This example may not be entirely accurate for all LISPs, since it assumes that EQ will be true for any equal atoms. Also it assumes that any non-atoms are lists (i.e. have a CAR and a CDR defined). To make this example work in other LISPs one simply adds conditions (elements of the list which is the argument of COND) to handle these cases. Introduction to LISP Page 23 The above example says that two things are EQUAL as follows: (a) If they are EQ they are EQUAL. (b) If they are not EQ and one of them is an atom they are not EQUAL. (c) If their CARs are EQUAL, then they are EQUAL, if and only if their CDRs are EQUAL. (d) If none of these apply, they are not EQUAL. NOTE The above example points out quite a few LISP programming techniques; namely, (a) LISP functions tend to be recursive. (b) the main programming technique in LISP is to handle the simple cases; then recurse on the CDRs. 2. (DEFINE_FUNCTION REVERSE (X) (REVERSESUB X NIL) (DEFINE_FUNCTION REVERSESUB (X Y) (COND ((ATOM X) Y) (T (REVERSESUB (CDR X) (CONS (CAR X) Y))))) Introduction to LISP Page 24 NOTE Most LISPs have a function which reverses a list; however, if you are using one which doesnt you will still be able to define the function in a manner similar to the above. In general any function we introduce in this manner can be added to a LISP not having it. NOTE For the rest of this section we will alternate between explaining a few more functions and giving more examples. 2.10 SOME NUMERICAL FUNCTIONS 1. (ADD1 N) if N is a number returns N+1 2. (SUB1 N) if N is a number returns N-1 3. (ADD X Y) if X and Y are numbers returns X+Y 4. (SUB X Y) if X and Y are numbers returns X-Y 5. (TIMES X Y) if X and Y are numbers returns X*Y 6. (QUOT X Y) if X and Y are numbers returns X/Y 7. (MOD X Y) if X and Y are numbers returns X mod Y Introduction to LISP Page 25 2.11 MORE EXAMPLES 1. For positive integers, one can define the function ADD as follows: (DEFINE_FUNCTION ADD (X Y) (COND ((ZEROP X) Y) (T (ADD (SUB1 X) (ADD1 Y))))) 2. (DEFINE_FUNCTION LENGTH (L) (COND ((ATOM L) 0) (T (ADD1 (LENGTH (CDR L)))))) NOTE By this definition the length of a dotted pair is 1. 3. (DEFINE_FUNCTION FACTORIAL (N) (COND ((EQ N 1) 1) (T (TIMES N (FACTORIAL (SUB1 N)))))) Introduction to LISP Page 26 2.12 PROPERT LIST FUNCTIONS 2.12.1 Getting The Property List In most LISPs there is a function on an atom which returns its property list. In old LISPs the function that did this was CDR. For convenience, we will call this function GET_PROPERTY_LIST (although as far as I know that is not its name in any LISP. 2.12.2 GET GET is the function which given a property allows one to get its associated property value. It can be defined as: (DEFINE_FUNCTION GET (A P) (COND ((NULL (GET_PROPERTY_LIST A)) NIL) (T (LIST_AS_FUNCTION P (GET_PROPERTY_LIST A))))) (DEFINE_FUNCTION LIST_AS_FUNCTION (VALUE LIST) (COND ((NULL LIST) NIL) ((EQ (LENGTH LIST) 1) NIL) ((EQ (CAR LIST) VALUE) (CADR LIST)) (T (LIST_AS_FUNCTION P (CDDR LIST))))) What this means is that GET of A and P is 1. If A does not have a property list or if P is not an odd-numbered member of the property list of A; NIL Introduction to LISP Page 27 2. If A has a property list and P is an odd-numbered member of the property list of A; the member of the property list of A following P. 2.12.3 PUTPROP PUTPROP is a function which enters properties and property-values on a property-list. It takes three arguments an Identifier, a value and a property. Its value is the the value of the second argument. NOTE PUTPROP is one of many LISP functions where the side-effect (in this case putting a property on a property list) is the important thing, and the value returned by the function is incidental. As an example: (PUTPROP 'DOG 'RED 'COLOR) would give DOG the property-value RED for the property COLOR. 2.12.4 Relationship Of PUTPROP And GET. After having done the above PUTPROP, the value of (GET 'DOG 'COLOR) would be RED. Introduction to LISP Page 28 2.12.5 SET PUTPROP can also be used to give a value to an identifier, since value is just one of the properties on the property list. However, it is usually easier to do this with a function such as set which is specific for the value property. (DEFINE_FUNCTION SET (A B) (PUTPROP A B 'VALUE)) 2.12.6 SETQUOTE Most LISPs have a function similar to set which does not evaluate its first argument. This function is used very similarly to the assignment statement in most languages. 2.13 OTHER USEFUL FUNCTIONS The rest of this section is going to be just definitions of functions, taken from my favorite LISP. These will serve partly as examples an partly be useful later on in going over programming techniques. 2.13.1 APPLY The function APPLY or something like it occurs in many LISPs. We will assume it takes two arguments, although in many LISPs instead of the second argument being a list, each element of the list is a seperate argument. The first argument is a function and the second argument is a list with as many elements as the function takes. The result is the function "applied" to the arguments. Introduction to LISP Page 29 2.13.2 Other Functions 2.13.2.1 APPEND (DEFINE_FUNCTION APPEND (X Y) (COND ((NULL X) Y) (T (CONS (CAR X) (APPEND (CDR X) Y))))) 2.13.2.2 LIST (DEFINE_FUNCTION LIST (X) (CONS X NIL)) NOTE Most LISPs have a much more general definition of the function LIST; however, these definitions usually involve defining it as a function of a variable number of arguments. Functions of a variable number of arguments are handled very differently in different LISPs. Some of the techniques for handling this is: 1. Functions of more than one argument which are part of the language are not a problem and no additional mechanisms are involved. 2. One can have alternate function definition methods such as: Introduction to LISP Page 30 (a) A method of defining functions where the list of arguments to the function is handed unevaluated to the function. (b) A method of defining functions which involves a special function of n which for such functions gives one the nth argument. (c) A method of defining functions recursively on the number of arguments. 2.13.2.3 LAST (DEFINE_FUNCTION LAST (X) (COND ((NULL X) NIL) ((ATOM (CDR X) (CAR X)) (T (LAST (CDR X))) 2.13.2.4 SUBST (DEFINE_FUNCTION SUBST (X Y S) (COND ((EQUAL Y S) X) ((ATOM S) S) (T (CONS (SUBST X Y (CAR S)) (SUBST X Y (CDR S)))))) Introduction to LISP Page 31 2.13.2.5 MAPLIST MAPLIST is a function which applies a function to a list and all its CD..DRs. (DEFINE_FUNCTION MAPLIST (F L) (COND ((NULL L) NIL) (T (CONS (F L) (MAPLIST F (CDR L)))))) 2.13.2.6 MEMQ (DEFINE_FUNCTION MEMQ (I L) (COND ((NULL L) NIL) ((EQ I (CAR L)) T) (T (MEMQ I (CDR L))))) 2.13.2.7 MEMBER (DEFINE_FUNCTION MEMBER (I L) (COND ((NULL L) NIL) ((EQUAL I (CAR L)) T) (T (MEMBER I (CDR L)))))) Introduction to LISP Page 32 2.13.2.8 MAPCAR MAPCAR is similar to MAPLIST only it works on succesive CAD...DRs of the list. This makes it in general much more useful. (DEFINE_FUNCTION MAPCAR (F L) (COND ((NULL L) NIL) (T (CONS (F (CAR L)) (MAPCAR F (CDR L)))))) 2.13.3 PROG We have saved the discussion of PROG for the end of this section because it is the function which: 1. Is most definitely not a part of "pure LISP". (In fact, another definition of "pure LISP" is one which does not have PROG.) 2. Leads to programming techniques which if overused inhibits one from being totally comfortable with LISP. PROG takes two arguments; a list of local variables and a list of LISP expressions which are executed sequentially. It has the value NIL. NOTE There are many forms of PROG with many other features but this again is what is most commonly available. One feature, however, is worth mentioning and that is the function RETURN. The function RETURN has as value its argument and is only defined with a PROG. It has the side effect of making the value of the PROG the value of its argument. Introduction to LISP Page 33 3.0 SOME PROGRAMMING EXAMPLES FROM AI. NOTE The handout now differs from the abstract for the following reason: this section and the previous section (and the lecture on them) will give one an appreciation of how one approaches programming in LISP. We shall take up the problem of parsing an english sentence. This is a very good application for LISP and can be done at every increasing levels of sophistication. NOTE In the programming examples we will have no concern with the efficiency of the programs for the following reasons 1. Efficient programming isn't always the most understandle. 2. When designing a program in LISP it is not usually best to worry about efficiency until one has the application designed. (This is true mainly becuase of the types of applications LISP is used for, where getting something to work is often a major research effort. (Often as soon as an application is running under LISP, one starts reprogramming it in some more efficient language.) Introduction to LISP Page 34 3. Which techniques of LISP programming are most efficient in a given LISP program is often implementation dependent 4. Many of the techniques to make a LISP program efficient are also implementation dependent We shall start with a very simple vocabulary and grammar. 3.1 VOCABULARY We shall define the vocabulary by constructing propertly list for the various words in the vocabulary. 3.1.1 The Function PUTPROPQ The function PUTPROPQ is the same as the function PUTPROP, except that it does not evaluate its arguments. The advantage of this is that it saves us several "'"s when we define the vocabulary 3.1.2 Verbs (PUTPROPQ HAS VERB PART_OF_SPEECH) (PUTPROPQ HAS ((SUBJECT VERB OBJECT)) PARADIGM) (PUTPROPQ HAS OWNERSHIP ACTION) (PUTPROPQ IS VERB PART_OF_SPEECH) (PUTPROPQ IS ( (SUBJECT VERB PREDICATE_NOUN) (SUBJECT VERB ADJECTIVE)) PARADIGM) (PUTPROPQ IS DEFINE ACTION) Introduction to LISP Page 35 3.1.3 Nouns (PUTPROPQ CAT NOUN PART_OF_SPEECH) (PUTPROPQ CAT T ANIMATE) (PUTPROPQ DOG NOUN PART_OF_SPEECH) (PUTPROPQ DOG T ANIMATE) (PUTPROPQ BALL NOUN PART_OF_SPEECH) (PUTPROPQ BALL NILL ANIMATE) 3.1.4 Adjectives (PUTPROPQ A ADJECTIVE PART_OF_SPEECH) (PUTPROPQ A NIL TYPE) (PUTPROPQ THE ADJECTIVE PART_OF_SPEECH) (PUTPROPQ THE NIL TYPE) (PUTPROPQ RED ADJECTIVE PART_OF_SPEECH) (PUTPROPQ RED (COLOR) TYPE) 3.2 SOME SIMPLE FUNCTIONS 3.2.1 Part Of Speech Functions These functions are used to determine the part of speech of a word. (DEFINE_FUNCTION PART_OF_SPEECH (WORD) (GET WORD 'PART_OF_SPEECH)) (DEFINE_FUNCTION VERBP (WORD) (EQ 'VERB (PART_OF_SPEECH WORD)) (DEFINE_FUNCTION NOUNP (WORD) (EQ 'NOUN (PART_OF_SPEECH WORD)) (DEFINE_FUNCTION ADJECTIVEP (WORD) (EQ 'ADJECTIVE (PART_OF_SPEECH (WORD)) Introduction to LISP Page 36 3.2.2 Some Other Useful Functions These functions are simply utility functions, (as are the functions above) which make the definitions of the functions for parsing a sentence much more readable. (DEFINE_FUNCTION VPARADIGM (VERB) (GET VERB 'PARADIGM)) (DEFINE_FUNCTION VERB_ACTION (VERB) (GET VERB 'ACTION)) (DEFINE_FUNCTION NOUN_PHRASEP (L) (COND ((NULL L) NIL) ((EQ (LENGTH L) 1) (NOUNP (CAR L))) ((ADJECTIVEP (CAR L)) (NOUN_PHRASEP (CDR L))))) This definition says that a noun phrase is a series of adjectives followed by a noun. In a way this is an important example of one of the basic techniques in natural language programming. A noun phrase is much more complex than the above function makes it out to be; however, this definition will work for simple cases. When one has gotten a parser working with this definition of a noun phrase, one can rewrite this portion of the code independently of the rest of the parser. This might be called structure prototyping. Introduction to LISP Page 37 3.2.3 TEST_FUNCTION (DEFINE_FUNCTION TEST_FUNCTION (WORD) (GET WORD 'TEST_FUNCTION)) With this we need to define a few more properties (PUTPROPQ VERB VERBP TEST_FUNCTION) (PUTPROPQ ADJECTIVE ADJECTIVEP TEST_FUNCTION) (PUTPROPQ NOUN NOUN_PHRASEP TEST_FUNCTION) NOTE If we wished to make our parser allow for adjective phrases and verb phrases, we would only need to change the test functions for verbs and adjectives and then add appropriate functions. 3.3 PARSING THE SENTENCE These first few sections will define some of the simpler functions dealinq with sentences. After that we will take a top down approach to parsing a sentence. 3.3.1 Finding The Senctence Structure Introduction to LISP Page 38 3.3.1.1 Function VERBS (DEFINE_FUNCTION VERBS (SENTENCE) (COND ((NULL SENTENCE) NIL) ((VERBP (CAR SENTENCE)) (CONS (CAR SENTENCE) (VERBS (CDR SENTENCE))) (T (VERBS (CDR SENTENCE))))) 3.3.1.2 Function PARADIGM (DEFINE_FUNCTION PARADIGM (SENTENCE) (MAPCAR VPARADIGM (VERBS SENTENCE))) 3.4 PARSE This is the function that we will hand the sentence to. It will determine whether the sentence belongs to that class of English sentences which we recognize, returning NIL if it doesn't. The function will do very little except call subfunctions. In LISP it is wise to do modular programming in the extreme, doing very little in each function and having many functions. NOTE Many of the following functions could be written (often slightly simpler) using the PROG function; however, in learning LISP it is wise to avoid PROG as long as possible. Introduction to LISP Page 39 (DEFINE_FUNCTION PARSE (SENTENCE) (PARSE0 SENTENCE (VERBS SENTENCE)) 3.4.1 Subfunctions Of PARSE 3.4.1.1 PARSE0 (DEFINE_FUNCTION PARSE0 (SENTENCE VERBS) (COND ((NULL VERBS) NIL) ((PARSE1 SENTENCE (CAR VERBS) (VPARADIGM (CAR VERBS))) (PARSE2 SENTENCE (CAR VERBS) (VPARADIGM (CAR VERBS)))) (T (PARSE0 SENTENCE (CDR VERBS)))))) What this function does is for each verb it tests whether the sentence parses with that as the main verb (in the sentences we will be dealing with there will be only one verb, but I have tried to make some of the functions more general in order to give one an idea of how to proceed to a fully general natural language program). If the sentence parses with the chosen verb, a function, PARSE2 is called to take some appropriate action, otherwise the next verb is tried, if none works the sentence is considered unparsable. Introduction to LISP Page 40 3.4.1.2 PARSE1 (DEFINE_FUNCTION PARSE1 (SENTENCE VERB PARALIST) (COND ((NULL PARALIST) NIL) ((PARSE11 SENTENCE VERB (CAR PARALIST)) T) (T (PARSE1 SENTENCE VERB (CDR PARALIST))))) This function simply tries each of the paradigms associated with the verb, in the same manner as PARSE0 tried each verb 3.4.1.3 PARSE11 (DEFINE_FUNCTION PARSE11 (SENTENCE VERB PARADIGM) (AND ( (TEST_FUNCTION (CAR PARADIGM)) (CAR (BREAK_UP SENTENCE NIL VERB))) ( (TEST_FUNCTION (CDDAR PARADIGM)) (CDAR (BREAK_UP SENTENCE NIL VERB))))) 3.4.1.3.1 BREAK_UP The function BREAK_UP simply returns a list consisting of two lists. The first list is all the words which occur before the verb and the second list is all the words which occur after the verb. Introduction to LISP Page 41 NOTE The trick of having it recursively build the list BEFORE_VERB and having it called with NIL to start this process off is a common one in LISP. (DEFINE_FUNCTION BREAK_UP (SENTENCE BEFORE_VERB VERB) (COND ((EQ (CAR SENTENCE) VERB) (CONS BEFORE_VERB (LIST (CDR SENTENCE)))) (T (BREAK_UP (CDR SENTENCE) (APPEND BEFORE_VERB (LIST (CAR SENTENCE))) VERB)))) 3.4.2 PARSE2 If we wanted in this example to add the capability of responding to sentences, PARSE2 is where that would be handled. It is the function which obtains the sentence when we know its structure. It is written here as a function of two variables a sentence and a verb. In more sophisticated applications one would add a third variable: the paradigm being used. If one wished to create a still more sophisticated function one might give it a fourth variable containing some form of parse tree for the sentence. (DEFINE_FUNCTION PARSE2 (SENTENCE VERB) ( (VERB_ACTION VERB) (BREAK_UP SENTENCE NIL VERB))) What this function does is apply the function associate with the verb to the sentence. Introduction to LISP Page 42 3.4.3 The Verb Action Functions. 3.4.3.1 Ownership (DEFINE_FUNCTION OWNERSHIP (STRUCTURED_SENTENCE) (PUTPROP (LAST (CAR STRUCTURED_SENTENCE)) (LAST (CDAR STRUCTURE_SENTENCE)) 'OWNS)) NOTE The function LAST is used here to obtain a noun from a noun phrase. If one made this example more general in its handling of noun phrases then this function would have to be redefined. This situtation can be handled in the following manner. 3.4.3.1.1 Noun_of_noun_phrase (DEFINE_FUNCTION NOUN_OF_NOUN_PHRASE (NOUN_PHRASE) (LAST NOUN_PHRASE) Introduction to LISP Page 43 3.4.3.1.2 OWNERSHIP Redefined (DEFINE_FUNCTION OWNERSHIP (STRUCTURED_SENTENCE) (PUTPROP (NOUN_OF_NOUN_PHRASE (CAR STRUCTURED_SENTENCE)) (NOUN_OF_NOUN_PHRASE (CADR STRUCTURED_SENTENCE)) 'OWNS)) And then one simply redefines NOUN_OF_NOUN_PHRASE when one expands the definition of a noun phrase. 3.4.3.2 DEFINE (DEFINE_FUNCTION DEFINE (STRUCTURED_SENTENCE) (COND ((ADJECTIVEP (CAADR STRUCTURED_SENTENCE)) (DEFINE_ADJECTIVE (NOUN_OF_NOUN_PHRASE (CAR STRUCTURED_SENTENCE)) (CAADR STRUCTURED_SENTENCE))) (T (DEFINE_NOUN (NOUN_OF_NOUN_PHRASE (CAR STRUCTURED_SENTENCE)) (NOUN_OF_NOUN_PHRASE (CADR STRUCTURED_SENTENCE)))))) NOTE In this definition there are plenty of places for refinement. some of them are: 1. The (CAADR STRUCTURED_SENTENCE) could be replaced by (ADJECTIVE_OF_ADJECTIVE_PHRASE (CADR STRUCTURED_SENTENCE)). In fact even that can be improved on because what one really wants is not so much CADR but a function Introduction to LISP Page 44 PREDICATE_NOMINATIVE. 2. similary the CAR could be replaced by a function SUBJECT. 3.4.3.2.1 DEFINE_NOUN (DEFINE_FUNCTION DEFINE_NOUN (SUBJECT_NOUN PREDICATE_NOUN) (PUTPROP SUBJECT_NOUN PREDICATE_NOUN 'IS)) In a much more sophisticated example this function one also check the knowledge base for any consequences of this new information. 3.4.3.2.2 DEFINE_ADJECTIVE (DEFINE_FUNCTION DEFINE_ADJECTIVE (SUBJECT_NOUN PREDICATE_ADJECTIVE) (COND ((GET PREDICATE_ADJECTIVE 'TYPE) NIL) (T (PUTPROP SUBJECT_NOUN PREDICATE_ADJECTIVE (CAR (GET PREDICATE_ADJECTIVE 'TYPE)))))) NOTE Again this function can be easily made more general; however, it is one of the most difficult. The major improvement to make in this function is one that replaces the CAR with a function that determines the type of the adjective from among the types listed. Such a function would need information as to the context of the sentence, since a sentence such as "The dog is Introduction to LISP Page 45 red." means something different if one is discussing colors of dogs or political persuasions. 4.0 SUGGESTIONS FOR FURTHER STUDY It would probably be very educational and possibly amusing to do the following: 1. Implement the above example in a LISP available to you. 2. DEBUG it. In doing this it might be well to learn if they are available to you: (a) A LISP DEBUGGER (b) A LISP EDITOR 3. Extend the above example. 4. Read the literature in Artificial Intelligence and try implementing some of the concepts discussed.