3 LISP and Other Al Programming Languages LISP is one of the oldest computer programming languages. It was invented byJohn McCarthy during the late 1950s, shortly after the development of FORTRAN. LISP (for List Processing) is particularly suited for Al programs because of its ability to process symbolic information effectively. It is a language with a simple syntax, with little or mo data typing and dynamic memory management. There ore ‘Several dialects of LISP inchiding FRANZLISP, INTERLISP, MACLISP, QLISP. SCHEME, and COMMON LISP. The COMMON LISP version is a recent attempt |__ 10 standardize the language to make it more portable and easier to maintain LISP has become the language of choice for most Al practitioners. It was Practically unheard of outside the research community until Al began to gain some ‘Popularity ten to fifteen years ago. Since then, special LISP processing machines _ have been built and its popularity has spread to many new sectors of business. and ~ Bovernment, In this chapter we give a summary of the important features of LISP -and briefly introduce PROLOG and other AI languages. INTRODUCTION TO LISP: SYNTAX AND NUMERIC FUNCTIONS ‘The basic building blocks of LISP are the atom, list, and the string. An atom is a ‘number or string of contiguous characters, including numbers and special characters A list is a sequence of atoms and/or other lists enclosed within parentheses A 19 Scanned with CamScanner20 Lisp and Other Al Programming Languages string is @ group of characters enclosed in double quotation marks. atoms, lists and strings are VALID ATOMS INVALID ATOMS! s-a-symbolic-atom (abe Poin (123abe , ‘TOQHOI SS? abe fe , mountaintop (ab) *var* ab cde Dlock #6 al23s , a S51 VAUIO LISTS Wee Se \ { ti wegen a i eat) eet} ; TCS wor (father sam (joe bill sue) Jabek efg( (mon tue wed thur fri sat sun) (abc (de) (ab) Scanned with CamScannerScanned with CamScannerLisp and Other Al Programming Languages Chap, Iso the same as the empty list (). It is the OMY obje slit, Since these elements return their ogt 2 ) Nil is al ih an atom and lid expressions. 7 nil (for logical false Be in LISP that is bot value, the following are val NIL : 32 BASIC LIST MANIPULATION FUNCTIONS IN LISP M Sessa we wish to take atoms or lists literally and not have them evaluated or eored as function calls as, for example, when the list represents data. To accomplish the, we precede the atom or the list with a single quotation mark, as in ‘man wea ta bed). The quotation mark informs the interpreter that the atom or lig Should not be evaluated, but should be taken literally as an atom or list. Variables in LISP are symbolic (nonnumeric) atoms. They may be assigned values, that is, bound to Values with the function setq. Setq takes two arguments, the firgt of which must be a variable. It is never evaluated and should not be in quotation marks, The second argument is evaluated (unless in quotation matks and the result is bound to the first argument. The variable retains this value until a ew assignment is made, When variables are evaluated, they return the last value bound to them. Trying to evaluate an undefined variable (one not previously bound to 2 value) results in an error. Some examples of the use of setq are as follows (note that comments in LISP code may be placed anywhere after a semicolon). sthe number 10 evaluates to itself <> (seta x 10) # 10 sis bound to x and 10 is returned x jthe variable x is e 10 jreturn the valu ->{setq x (+ 35) ‘x is reset to the value (+ 3 5) 8 jand that value returned ->isetq x (+ 35)) {x is reset to the literal value | (+35) AU+ 3.6), quote inhibits a the variable y was not previously Unbound variable:¥ _—_;bound to a value, causing an error Some basic symbol processing functions are car, cdr, cons, and list. Examples i of these functions are given in Table 3.2, Car takes one argument, which must be cist, It returns the first top element of the list. Cdr also takes a list as is argument, and it retums a list consisting of all elements except the first. Cons takes (wo Scanned with CamScanner3.2 Basic List Manipulation Functions in LISH 3.2 BASIC LIST MANIPULATION FUNCTIONS: ‘Car takes one argument alist, and returns the first clement Cd takes one argument. a list, afd ‘returns a list with the first element, Cons takes (wo arguments, an ele ‘ment, and a list and returns 2 list ‘with the element inserted at the beginning, favor List take any number of arguments ‘and returns a list with the argu ments as elements. by making the element ments, and makes them ‘an element and a list. It constructs a new ist ‘member of the list. List takes any number of argu ‘with each argument a top member. e the quotation marks preceding the arguments in the function calls of 12, As pointed out above, an error will result if they are not there, Because will try to evaluate each argument before evaluating the function. Jrence in results with and without the quotation marks ~ jthe literal list (* 2 3) is ‘consed” to the list (1) the evaluated list (* 2 3) is seonsed to the list (1) yx is bound to the literal list be) the quote ‘ inhibits evaluation . rot x but unquoted x evaluates to its ipreviously bound value name arg) arg?) Whena function scaled, the arguments = Js within quotation marks) and then the * nent values, Complete the list manipula- Scanned with CamScannersear toa i960 8 cated ear (ab) ed) @) ‘one ‘ttwo three!) Jone Two THREE) wea neers A a “fede (a bel) (asc ; ‘wy ea “ee =D ie Scanned with CamScannerScanned with CamScannerScanned with CamScannerScanned with CamScannerScanned with CamScannerScanned with CamScanner( “Tere Pre (The primitive function terpri takes no argumen 30 <0.° LISP and Other Al Programming Languages Chap. 3 San ie We can avoid the double quotation marks in the output by using the printing function princ. It is the same as print except it does not print the unwanted quotation marks. For example, we use princ to print the following without the marks, line i i ins. )Again, that is because [Link] the quotes, but the echo still remains. Again, th: aaa its argument (in a form that LISP could red), and, since that was the last thing returned, it was printed by the read-evaluate-print loop. In a typical program, the returned value would not be printed on the screen as it would be by another function. Prise orntive ts, It introduces a new-line \d line feed) wherever it appears and then returns nil. Below is a tur. an ‘She. i age rea of a circle which uses several /O functidhs, including program to compute the a user prompts. ->(defun circle-area () (terpri) (prince “Please enter the radius (seta radius (read)) » i (prine “The area of the circle is: ") i {prine (* 3.1416 radius radius)) t (terpri) CIRCLE-AREA i ->(circle-area) ' Please enter the radius: 4 ‘The area of the circle is: 50.2656 > Notice that princ permits us to print multiple itemson the same line and to introduce a new-line sequence we use terpri. The format function permits us to create Cleaner output than is possible with just the eae praaing faa \s. It has the form (format arg arg2 . . .). Destination specifies where the ‘Output is to be directed, like to the ‘or some other external file. For our purposes, destination will always be 1 ify the default output, the monitor. String is the desired output string, but intermixed with format directives which specify how each argument is to be repre- sented. Directives appear in the string in the same order the arguments are to be printed. Each directive is preceded with a tilde character (*) to identify it as a directive. We list only the most comman directives below. : “A The argument is printed as though princ were used. “S The argument is printed as though prin! were used. \ Scanned with CamScannerScanned with CamScannerScanned with CamScannerScanned with CamScanner“ LISP and Other Al Programming Languages Chap. OF course, Jet and other functions can be embedded within the loop construct jp local variables are needed, Recursion For many problems, recursion is the natural method of solution. Such pr occur frequently in mathematical logic, and the use of recursion will often result in programs which are both elegant and simple. A recursive function is one which calls itself successively to reduce a problem to a sequence of simpler steps. Recursion s ping condition and a recursive ste ' re lusate witha recursive version of factorial. The recursive step in factoriay > is the product of n and factorial(n-1). The stopping condition is reached when n = 0. ->(defun factorial (n) (cond ((zerop a} 1) (U(* n (factorial (- 9 1))))) FACTORIAL ->(factorial 6) 720 Note the stopping condition on the second line of the function definition, and the recursive step on the last line. We present another example of recursion which defines the member function called newmember. ->(defun newmember (et 1st) {cond ((null 1st) nit) Mlequal el (car 1st)) 1st) A(t (newmember el (cdr 1st) NEWMEMBER > If the atom ¢ and list (a be d) are given as the arguments in the call to newmember, © gets bound to el and (a b ¢ d) is bound to Ist. With these bindings, the first cond test fails. since Ist is not null. Consequently, the second test is executed. This also fails since cl, bound to c, does not equal the car of /st which is a. The last test of the cond construct is forced to succeed because of the t test. This initiates a recursive call (0 newmember with the new arguments ¢/ (still bound to c) and the cdr of which is (bcd). Again, a match fails during the cond tests; so another recursi call is made, this time with arguments e/ (still bound to c) and Ist now bound (c d), When this call is executed. a match is found in the second cond test so value of /s¢ (¢ d) ix returned, Scanned with CamScannerSec%8 Property tet afd Arrevi 4.6 PROPERTY LISTS AND ARRAYS Property Lists: re, the unique and mos sei features of LISP as an Al language is the ibility to assign properties to atoms, For example, any object, say an atom which represents a person, can be given a number of properties which in some way character- ie the person, such as height, weight, sex, color of eyes and hair, address, profession, family members, and so on. Property list functions permit one to assign such properties to an atom, and to retrieve, replace, or remove them as required, ‘The function putprop assigns properties to an atom, It takes three arguments: an object name (an atom), a property or attribute name, and property or attribute value. For éxample, to assign properties to a car, we can assign properties such as make, year, color, and style with the following statements: <> {putprop ‘car ‘ford ‘make) FORD ->{putprop ‘car 1988 ‘year) 1968 =>{putprop ‘ear ‘red “color) ‘RED => (putprop ‘er ‘four-door style) FOUR-DOOR > As you can see, the form of putprop is ° putprop object velve atvibute) where value is retumed))The object, car, will retain these properties until they are replaced with new ones’or until removed with the remprop function which takes two ‘he object and its attribute. In other words, properties are global assignments(To retrieve a property value, such as the ealor of car, we use the function get also takes the two arguments object and attribute. => (get ‘car ‘color) RED => (get ‘car ‘make) FORD ->(putprop ‘car ‘blue ‘color) BLUE ->(get ‘car ‘color)1 ISP and Other Al Programming Languages 6 USP an hog list. For example, if Danny ‘The property value may be an atom oF a US. - named Scale, Penny, and Etoile, they can be assigned as Pets ->(putprop ‘danny ‘(schultz penny etoile) ‘pets) (SCHULTZ PENNY ETOILED “>iget ‘danny ‘pets) ee (SCHULTZ PENNY ETOILE) V > To add a new pet named Heid without Knowing the existing ets one candy the following: “Stputprop ‘danny (cons “neil (get ‘danny ‘pets “pets) 7 (HEIDI SCHULTZ PENNY ETOILE) Items can be removed from a list of values in a similar manner Sate some versions of Common LISP do not provide the putprop function, it may be necessary to define your own. [Link] be-done with the following code. >(defun putprop (object value property) (setf (get object property) value) PUTPROP oo j The new function setf used in the above definition is like setq except it is more general. It is an assignment function. which also takes two arguments. the, first of which may be either an atom or an access function (like car, cdr, and get), and the second, the value to be assigned. When the first argument is an atom. setf behaves the same as setq. It simply binds the evaluated second argument to the places the second argument, first. When the first argument is an access function, setf the value, at the location accessed by the access function. For example, if (a b ¢) hhas been bound tox, the expression (setf (car x) “d) will replace the a in (a bc) with d. Likewise (setf can be used directly to assign or replace a property value. e ->(setf (get ‘car ‘color! ‘pink! PINK ->(get ‘car ‘color) PINK = ‘As we shall see in later chapters, property lists provide us with a convenient mechanism with which to represent knowledge. One such representation is the conceP tual network where objects, their attributes, and relations to other objects are easily Scanned with CamScannerScanned with CamScannerLISP and Other Al Programming Languages Chap, 3 (nett (aret rmyarray 0) 26) 2s inant (aret myarray 1) ‘red RED Sieett (aret myarray 2) ‘sam sue linda) su UNDA) 3.7 MISCELLANEOUS TOPICS We complete our presentation of LISP in this section with a few additional topics, including the functions mapcar, eval, lambda, trace and untrace, and a brief description /of the internal! representation of atoms and lists. / Ed, Mapping Functions Ger 4s one of several mapping functions provided in LISP to apply some function successively to one or more lists of elements. The first argument of mapcar is function. and the remaining argument(s) are lists of elements to which the named fonction is applied. The results of applying the function to successive members of the lists are placed: in a new list which is retumed. For example, suppose we wish to add 1 to each element of the list (5 10 15 20 25). We can do this quite simply ‘with mapcar and the function 1+. ->{mapear ‘1+ “(5 10 15 20 25) (6 11 16 21 26) > If we wish to add the corresponding elements of two lists (even of unequal length), say (1 23 45.6) and (1 23 4), we use the + function with the lists to ‘obtain the sum of the first four elements. ->imapcar + (123456) '(123.4N) a4 e ‘ It should be clear that mapcar can be used in a variety of ways in lieu of iterative flnctions. And, the function being applied to the lists may be either user defined or built-in. Lambda Functions When 2 function is defined with defun, its name and address must be stored in ‘symbol table for retrieval whenever it is called in a program. Sometimes, however. it is desirable to use a function only once in a program. This will be the caseEE SW’ Sece&? — Misgaitaneous Toplea «10 bas 21) 8 ‘when it is used in a mapping operation such as with mapcar, which must take Procedure as argument. LISP provides a method of writing unnamed or ‘anonymous functions that are evaluated only when they are encountered in a program. Such functions are called lambda functions. They have the following form (lambda (arguments) ) We illustrate the use of a lambda function to compute the cubed value of a list of numbers. This will be accomplished by using mapcar to apply a lambda cute funtion wo ait of numbers; When 2 fusion called by another function it should be preceded by the characters #" to indicate that the following item is a function. This is equivalent to preceding the function with a single quotation mark (or the function named function in some LISP dialects. The lambda function we need to find the cube of a single number is just (lambda (x) (* x x x)). We use this with mapcar now to find the cubes of the numbers (1 2 3 4) ->I(detun cubertst (Ist) (mapear # (lambda (x) (* x x x))tst)) CUBE-LIST ->(cubelist (12.3 4)) (182764) - Internal Storage ‘As we have seen, lists are flexible data structures that can shrink or grow almost without limit. This is made Possible through the use of linked cell structures in memory to represent lists. These can be visualized as storage boxes having two components which correspond’ to the car and cdr of a list. The cells are called ‘cons-cells, because they are constructed with the cons function, where the left compo- ‘ent points to the first element of a list (the car of the list) and the right component ‘oints to the remainder of the list (the cdr of the list). An example of the representation ‘or the list (a (b c (4)) ¢ f) is given in Figure 3.2. Figure 3.2 Representation for the list (a (b c (d)) ef). Scanned with CamScannerOGRAMMING LANGUAGES 20cie) was invented by Alain ; pROLOG (for PROgramming in LOT sng the early Pe his associates at the University G uses the syntax of has a number of built-in feat pects of Programming in PROLOG i: and rules about objects, their properties. : t jes can then be po: veers and valid conclusions will be ‘and returned by the program. Responses to user queries are i form of inferencing control known as Tesolution. This process next chapter. Facts in PROLOG are declared with predicates and c letters. The arguments of predicates are enclosed 10 eemas. For example, some facts about family relationships could be written ai 3.8 PROLOG AND OTHER Al PR -onstants written in. and sister([Link]) parent([Link]) parent([Link]) maletjoe) female(ann} ‘The first fact is the predicate sister with arguments sue that Sue is the sister of Bill. Likewise, the conditions in the if part are satisfied begin with |. Rules may contain vari . we write mi as Ese o represent he gcaeral ra * (X21 :- parentiX.Y), parentiY,2), male(X) This rule has the following meaning: Scanned with CamScanner